====== Research ====== ==== Recent Publications ==== === 2023 === * Spyros Angelopoulos, [[https://www.eecs.yorku.ca/~kamalis|Shahin Kamali]]. Contract Scheduling with Predictions. //Journal of Artificial Intelligence Research//, 77, 2023. * Spyros Angelopoulos, [[https://www.eecs.yorku.ca/~kamalis|Shahin Kamali]]. Rényi-Ulam Games and Online Computation with Imperfect Advice. In //Proc. 48th International Symposium on Mathematical Foundations of Computer Science//, 2023. * Shalom Asbell, [[https://www.eecs.yorku.ca/~ruppert|Eric Ruppert]]. A Wait-Free Deque with Polylogarithmic Step Complexity. In //Proc. International Conference on Principles of Distributed Systems//, 2023. * Hassan Ashtiani, Vinayak Pathak, [[https://www.eecs.yorku.ca/~uruth|Ruth Urner]]. Adversarially Robust Learning with Tolerance. In //Proc. International Conference on Algorithmic Learning Theory//, 2023. * Paul Bastide, Marthe Bonamy, Anthony Bonato, Pierre Charbit, [[https://www.eecs.yorku.ca/~kamalis|Shahin Kamali]], Théo Pierron, Mikaël Rabie. Improved Pyrotechnics: Closer to the Burning Number Conjecture. //Electronic Journal of Combinatorics//, 30(4), 2023. * Joan Boyar, Lene M. Favrholdt, [[https://www.eecs.yorku.ca/~kamalis|Shahin Kamali]], Kim S. Larsen. Online Interval Scheduling with Predictions. In //Proc. 18th International Symposium on Algorithms and Data Structures//, 2023. * [[https://www.eecs.yorku.ca/~burjons|Elisabet Burjons]], Matthias Gehnen, Henri Lotze, Daniel Mock, Peter Rossmanith. The Online Simple Knapsack Problem with Reservation and Removability. In //Proc. 48th International Symposium on Mathematical Foundations of Computer Science//, 2023. * Fasil Cheema, [[https://www.eecs.yorku.ca/~uruth|Ruth Urner]]. Precision Recall Cover: A Method For Assessing Generative Models. In //Proc. International Conference on Artificial Intelligence and Statistics//, 2023. * Tosca Lechner, Vinayak Pathak, [[https://www.eecs.yorku.ca/~uruth|Ruth Urner]]. Adversarially Robust Learning with Uncertain Perturbation Sets, In //Proc. Conference on Neural Information Processing Systems//, 2023. * Tosca Lechner, [[https://www.eecs.yorku.ca/~uruth|Ruth Urner]], Shai Ben-David. Strategic Classification with Unknown User Manipulations. In //Proc. International Conference on Machine Learning//, 2023. * Hossein Naderibeni, [[https://www.eecs.yorku.ca/~ruppert|Eric Ruppert]]. A Wait-free Queue with Polylogarithmic Step Complexity. In //Proc. ACM Symposium on Principles of Distributed Computing//, 2023. * Amgad Rady, [[http://www.eecs.yorku.ca/~franck|Franck van Breugel]]. Explainability of Probabilistic Bisimilarity Distances for Labelled Markov Chains. In //Proc. 26th International Conference on Foundations of Software Science and Computation Structures//, 2023. * Matt Walker, Parssa Khazra, Anto Nanah Ji, Hongru Wang, [[http://www.eecs.yorku.ca/~franck|Franck van Breugel]]. jpf-logic: a Framework for Checking Temporal Logic Properties of Java Code. //ACM SIGSOFT Software Engineering Notes// 48(1), 2023. * Yuanhao Wei, Guy E. Blelloch, Panagiota Fatourou, [[https://www.eecs.yorku.ca/~ruppert|Eric Ruppert]]. Practically and Theoretically Efficient Garbage Collection for Multiversioning. In //Proc. 28th ACM Symposium on Principles and Practice of Parallel Programming//, 2023. === 2022 === * Spyros Angelopoulos, [[http://www.eecs.yorku.ca/~kamalis|Shahin Kamali]], Kimia Shadkami. Online Bin Packing with Predictions. In //Proc. International Joint Conference on Artificial Intelligence//, 2022. * Spyros Angelopoulos, [[http://www.eecs.yorku.ca/~kamalis|Shahin Kamali]], Dehou Zhang. Online Search with Best-Price and Query-Based Predictions. In //Proc. 36th AAAI Conference on Artificial Intelligence//, 2022. * Hans-Joachim Böckenhauer, [[http://www.cse.yorku.ca/~burjons|Elisabet Burjons]]. Martin Raszyk, Peter Rossmanith, Reoptimization of Parameterized Problems. //Acta Informatica// 59, 2022. * [[http://www.cse.yorku.ca/~burjons|Elisabet Burjons]], Janosch Fuchs, Henri Lotze. The Slotted Online One-Sided Crossing Minimization Problem on 2-Regular Graphs. In //Proc. 33rd International Workshop on Combinatorial Algorithms//, 2022. * Charlie Carlson, Ewan Davies, Nicolas Fraiman, Alexandra Kolla, [[https://www.adityapotukuchi.com|Aditya Potukuchi]], Corrine Yap. Algorithms for the ferromagnetic Potts model on expanders. In //Proc. 63rd IEEE Symposium on Foundations of Computer Science//, 2022. * Sadia Chowdhury, [[https://www.eecs.yorku.ca/~uruth|Ruth Urner]]. Robustness Should Not Be at Odds with Accuracy. In //Proc. 3rd Symposium on Foundations of Responsible Computing//, 2022. * Carole Delporte-Gallet, Panagiota Fatourou, Hugues Fauconnier, [[http://www.cse.yorku.ca/~ruppert|Eric Ruppert]]. When Is Recoverable Consensus Harder Than Consensus? In //Proc. ACM Symposium on Principles of Distributed Computing//, 2022. * Saulo dos Santos, Japjeet Singh, Ruppa K. Thulasiram, [[http://www.eecs.yorku.ca/~kamalis|Shahin Kamali]], Louis Sirico, Lisa Loud. A New Era of Blockchain-Powered Decentralized Finance (DeFi) - A Review. In //Proc. 46th IEEE Computers, Software and Applications Conference//, 2022. * James Freitag, Neshat Mohammadi, [[https://www.adityapotukuchi.com|Aditya Potukuchi]], Lev Reyzin. On the Geometry of Stable Steiner Tree Instances. In //Proc. 34th Canadian Conference on Computational Geometry//, 2022. * Matthew Jenssen, Will Perkins, [[https://www.adityapotukuchi.com|Aditya Potukuchi]]. Independent sets of a given size and structure in the hypercube. //Combinatorics, Probability and Computing//, 31(4), 2022. * Matthew Jenssen, [[https://www.adityapotukuchi.com|Aditya Potukuchi]], Will Perkins. Approximately counting independent sets in bipartite graphs via graph containers. In //Proc. 33rd ACM-SIAM Symposium on Discrete Algorithms//, 2022. * [[http://www.eecs.yorku.ca/~kamalis|Shahin Kamali]]. Compact representation of graphs with bounded bandwidth or treedepth. //Information and Computation//, 285, 2022. * [[http://www.eecs.yorku.ca/~kamalis|Shahin Kamali]], Pooya Nikbakht. Online Square Packing with Rotation. In //Proc. 34th Canadian Conference on Computational Geometry//, 2022. * [[http://www.eecs.yorku.ca/~kamalis|Shahin Kamali]], Pooya Nikbakht, Arezoo Sajadpour. A Randomized Algorithm for Non-crossing Matching of Online Points. In //Proc. 34th Canadian Conference on Computational Geometry//, 2022. * Tosca Lechner, [[http://www.cse.yorku.ca/~ruth|Ruth Urner]]. Learning Losses for Strategic Classification. In //Proc. 36th AAAI Conference on Artificial Intelligence//, 2022. * [[http://www.cse.yorku.ca/~gt|George Tourlakis]], //Computability//, Springer, 2021. === 2021 === * Sushant Agarwal, Nivasini Ananthakrishnan, Shai Ben-David, Tosca Lechner, [[http://www.cse.yorku.ca/~ruth|Ruth Urner]]. Open Problem: Are all VC-classes CPAC learnable? In //Proc. 33rd Conference on Learning Theory//, 2021. * Nivasini Ananthakrishnan, Shai Ben-David, Tosca Lechner, [[http://www.cse.yorku.ca/~ruth|Ruth Urner]]. Identifying Regions of Trusted Predictions. In //Proc. 37th Conference on Uncertainty in Artificial Intelligence//, 2021. * Giorgio Bacci, Giovanni Bacci, Kim G. Larsen, Radu Mardare, Qiyi Tang, [[http://www.cse.yorku.ca/~franck|Franck van Breugel]]. Computing Probabilistic Bisimilarity Distances for Probabilistic Automata. //Logical Methods in Computer Science//, 17(1), 2021. * Naama Ben-David, Guy E. Blelloch, Panagiota Fatourou, [[http://www.cse.yorku.ca/~ruppert|Eric Ruppert]], Yihan Sun, Yuanhao Wei. Space and Time Bounded Multiversion Garbage Collection. In Proc. //Proc. 35th International Symposium on Distributed Computing//, 2021. * Syyeda Zainab Fatmi, Xiang Chen, Yash Dhamija, Maeve Wildes, Qiyi Tang, [[http://www.cse.yorku.ca/~franck|Franck van Breugel]]. Probabilistic Model Checking of Randomized Java Code. In //Proc. 27th International Symposium on Model Checking Software - 27th International Symposium (SPIN)//, 2021. * Yunge Hao, [[http://www.cse.yorku.ca/~gt|George Tourlakis]], An arithmetically complete predicate modal logic, Bulletin of the Section of Logic, 2021. To appear. * Yuanhao Wei, Naama Ben-David, Guy E. Blelloch, Panagiota Fatourou, [[http://www.cse.yorku.ca/~ruppert|Eric Ruppert]], Yihan Sun. Constant-time snapshots with applications to concurrent data structures. In //Proc. 26th ACM Symposium on Principles and Practice of Parallel Programming//, 2021. === 2020 === * Sushant Agarwal, Nivasini Ananthakrishnan, Shai Ben-David, Tosca Lechner, [[http://www.cse.yorku.ca/~ruth|Ruth Urner]]. On Learnability wih Computable Learners. In //Proc. 31st International Conference on Algorithmic Learning Theory//, 2020. * Hassan Ashtiani, Vinayak Pathak, [[http://www.cse.yorku.ca/~ruth|Ruth Urner]]. Black-box Certification and Learning under Adversarial Perturbations. In //Proc. 37th International Conference on Machine Learning//, 2020. * Qiyi Tang, [[http://www.cse.yorku.ca/~franck|Franck van Breugel]]. Deciding probabilistic bisimilarity distance one for probabilistic automata. //Journal of Computer and System Sciences// 111: 57-84, 2020. === Publications in Previous Years === * [[2015-2019|2015-2019]] * [[2010-2014|2010-2014]] * [[2006-2009|2006-2009]] * [[http://www.cse.yorku.ca/tg/2005-pub.html|2005]] * [[http://www.cse.yorku.ca/tg/2004-pub.html|2004]] * [[http://www.cse.yorku.ca/tg/2003-pub.html|2003]] ==== Graduate Theses ==== * Hossein Naderibeni, Lock-free Queues with Polylogarithmic Step Complexity, M.Sc. thesis, 2022. * Sadia Chowdhury, Novel Examinations of Interpretable Surrogates and Adversarial Robustness in Machine Learning, M.Sc. thesis, 2021. * Yunge Hao, On Solovay's Theorem and a Proof of Arithmetical Completeness of a New Predicate Modal Logic, M.Sc. thesis, 2021. * Karan Singh, Ensuring Fairness Despite Differences in Environment, M.Sc. thesis, 2019. * Kowsar Hossain, An Efficient MAC Protocol for Wireless Sensor and Ad Hoc Networks, M.Sc. thesis, 2017. * Amgad Rady, Characterizing Implementations that Preserve Properties of Concurrent Randomized Algorithms, M.Sc. thesis, 2017. * Feng Gao, A short and readable proof of cut elimination for two 1st-order modal logics, M.Sc. thesis, 2016. * Niloufar Shafiei, Non-Blocking Data Structures Handling Multiple Changes Atomically, Ph.D. thesis, 2015. * Stephen Voland, Random Polyhedral Scenes, M.Sc. thesis, 2015. * Nastaran Shafiei, Model-Checking of Distributed Multithreaded Java Applications, Ph.D. thesis, 2014. * Stuart Maclean, Advances in Connectivity-Based Positioning for Mobile Wireless Sensor Networks, Ph.D. thesis, 2013. * Xiwen Chen, Formal Verification of a Concurrent Binary Search Tree, M.Sc. thesis, 2013. * Elise Cormie-Bowins, Measuring Progress of Probabilistic LTL Model Checking, M.Sc. thesis, 2012. * Rahul Chaturvedi, Electing and Maintaining Leaders in Populations of Autonomous Agents, M.Sc. thesis, 2012. * Yehuda Schwartz, Some Results in Computability and the Proof Theory of Predicate Modal Logic, Ph.D. thesis, 2012. * Joanna Helga, Complexity Analysis of Non-blocking Binary Search Trees, M.Sc. project, 2011. * Xin Zhang, Measuring Progress of Model Checking Randomized Algorithms, M.Sc. thesis, 2010. * [[http://www.cse.yorku.ca/~jeff/research/students/homePages/James.htm|(James) Hyukjoon Kwon]], [[http://www.cse.yorku.ca/~jeff/research/students/James/thesis.pdf|Improved Results on Models of Greedy and Primal-Dual Algorithms]], M.Sc. thesis, 2008. * Nassim Nasser, [[http://www.cse.yorku.ca/~jeff/research/students/Nassim/project.pdf|PBT Framework and BT Reductions]], M.Sc. project, 2008. * [[http://www.cse.yorku.ca/~jeff/research/students/homePages/Jai.htm|Jaisingh Solanki]], [[http://www.cse.yorku.ca/~jeff/research/students/Jai/finalthesis.pdf|A Randomized Algorithm for Cake Cutting]], M.Sc. thesis, 2007. * [[http://www.cse.yorku.ca/~niloo|Niloufar Shafiei]], Array-based Lock-free Implementations of Stacks and Queues, M.Sc. thesis, 2007. * Babita Sharma, An Algorithm to Quantify Behavioural Similarity between Probabilistic Systems, 2006. (Winner of York University's Thesis Prize.) * [[http://www.cs.yorku.ca/~antonb|Anton Belov]], Syntactic Characterization of Propositional Satisfiability, M.Sc. thesis, 2005. (Winner of the department's Joseph Liu Thesis Award.) * Kien Huynh, Analysis Through Reflection: Walking the EMF Model of BPEL4WS, M.Sc. thesis, 2005. * Francisco Kibedi, Adding a Binary Modal Operator to Predicate Logic, M.A. thesis, 2005. * Mariya Koshkina, Verification of Business Processes for Web Services, M.Sc. thesis, 2003. * Mikhail Fomitchev, Lock-Free Linked Lists and Skip Lists, M.Sc. thesis, 2003. (Winner of York University's Thesis Prize.) ==== Undergraduate Research Projects ==== * Shahen Alexanian, Bounds on the Competitive Ratio of the Online n-Knapsack Problem with Reservation Costs (n>2), 2023. * Shalom Asbell, Lock-free Deques, 2023. * Ethan Fifle, Design and Analysis of 3D Algorithms and Data Structures with Industry Applications, 2023. * Katherine Ling, Compact Data Structures for Geometric Graphs, 2023. * Koko NanahJi and Jordan Malek, Lock-free Bag Data Structures, 2020-21. * Trevor Brown, Non-blocking Search Trees, 2010. * Kian Shokouhi, [[http://www.cse.yorku.ca/~jeff/notes/3101/recPic/htm_recim.html|Recursive Pictures]], 2008. * Soheil Pourhashemi, [[http://www.cs.yorku.ca/~aaw/Pourhashemi/index.html|Leftist and Skew Heaps]] (Algorithmics Animation Workshop), 2007. * Daniel Natapov, [[http://www.cse.yorku.ca/~jeff/research/students/4080/Daniel.ppt|The Max Cut Problem]] (Attended CS6111), 2007. * Zhenyu Pan, [[http://www.cs.yorku.ca/~aaw/ZhenyuPan/devor/DeVor.html|Delaunay and Voronoi Diagram]] (Algorithmics Animation Workshop), 2007. * Gregory Fine, [[http://www.cs.yorku.ca/~aaw/GregoryFine/applet.html|Voronoi Diagram]] (Algorithmics Animation Workshop), 2007. *Geri Grolinger, [[http://www.cse.yorku.ca/~jeff/research/students/4080/The Pebble Game.ppt|The Pebble Game]] (Attended CS6111), 2006. * Leonardo Zambito, [[http://www.cs.yorku.ca/~aaw/Zambito/TSP_L/Web/TSPStart.html|Travelling Salesman Problem]] (Algorithmics Animation Workshop), 2006. * Roman Gubarenko, [[http://www.cs.yorku.ca/~aaw/Gubarenko/BSTAnimation.html|Optimal Static Binary Search Tree]] (Algorithmics Animation Workshop), 2005 * Dena Ghiassi, [[http://www.cs.yorku.ca/~aaw/Ghiassi/MST/MSTAlg.htm|Minimum Spanning Tree]] (Algorithmics Animation Workshop), 2005. * Nazanin Mirmohammadi, Techniques in Complexity Theory, 2004. * Stan Li, Implementing DPE in BPEL4WS, 2003. * Hongming Wu, A New Algorithm for Quantitative Verification of Probabilistic Transition Systems, 2002.