Research

Younghun Roh, Panagiota Fatourou, Siddhartha Jayanti, Eric Ruppert, Julian Shun, Yuanhao Wei. Aggregating Funnels for Faster Fetch&Add and Queues. To appear in Proc. ACM Symposium on Principles and Practice of Parallel Programming, 2025.

Spyros Angelopoulos, Christoph Dürr, Shendan Jin, Shahin Kamali, Marc P. Renault. Online computation with untrusted advice. Journal of Computer and System Sciences, 144, 2024.

Magnus Berg, Shahin Kamali. Online Bin Covering with Frequency Predictions. In Proc. Scandinavian Symposium and Workshops on Algorithm Theory, 10:1-10:17, 2024.

Magnus Berg, Shahin Kamali, Katherine Ling, Cooper Sigrist. Space-Efficient Data Structures for Polyominoes and Bar Graphs. In Proc. Data Compression Conference, 253-262, 2024.

Joan Boyar, Shahin Kamali, Kim S. Larsen, Ali Mohammad Lavasani, Yaqiao Li, Denis Pankratov. On the Online Weighted Non-Crossing Matching Problem. In Proc. Scandinavian Symposium and Workshops on Algorithm Theory, 16:1-16:19, 2024.

Elisabet Burjons, Fabian Frei, Edith Hemaspaandra, Dennis Komm, David Wehner. Finding Optimal Solutions with Neighborly Help. Algorithmica, 86(6): 1921-1947, 2024.

Charlie Carlson, Ewan Davies, Alexandra Kolla, Aditya Potukuchi. A Spectral Approach to Approximately Counting Independent Sets in Dense Bipartite Graphs. In Proc. 51st International Colloquium on Automata, Languages, and Programming, 35:1-35:18, 2024.

Panagiota Fatourou, Eric Ruppert. Lock-Free Augmented Trees, In Proc. International Symposium on Distributed Computing, 2024.

Pascale Gourdeau, Tosca Lechner, Ruth Urner. On the Computability of Robust PAC Learning. In Proc. 37th Conference on Learning Theory, 2092-2121, 2024.

Matthew Jenssen, Will Perkins, Aditya Potukuchi, Michael Simkin. Sampling, counting, and large deviations for triangle-free graphs near the critical density. To appear in Proc. 65th IEEE Symposium on Foundations of Computer Science, 2024.

Jeffrey Kam, Shahin Kamali, Avery Miller, Naomi Nishimura. Reconfiguration of Multisets with Applications to Bin Packing. In Proc. 18th International Conference and Workshops on Algorithms and Computation, 212-226, 2024.

Adam Lechowicz, Rik Sengupta, Bo Sun, Shahin Kamali, Mohammad Hajiesmaili. Time Fairness in Online Knapsack Problems. In Proc. 12th International Conference on Learning Representations, 2024.

Hossein Naderibeni, Eric Ruppert. A Wait-free Queue with Polylogarithmic Step Complexity. Distributed Computing 37(4):309-334, 2024.

Alireza Torabian, Ruth Urner. Investigating Calibrated Classification Scores Through the Lens of Interpretability. In Proc. Second World Conference on eXplainable Artificial Intelligence, 2024.

Chester Wyke, Ruth Urner. An Axiomatic Perspective on Anomaly Detection. To appear in Proc. European Conference on Artificial Intelligence, 2024.

Spyros Angelopoulos, Shahin Kamali. Contract Scheduling with Predictions. Journal of Artificial Intelligence Research, 77, 2023.

Spyros Angelopoulos, Shahin Kamali. Rényi-Ulam Games and Online Computation with Imperfect Advice. In Proc. 48th International Symposium on Mathematical Foundations of Computer Science, 2023.

Spyros Angelopoulos, Shahin Kamali, Kimia Shadkami. Online Bin Packing with Predictions. Journal of Artificial Intelligence Research, 78: 1111-1141, 2023.

Shalom Asbell, Eric Ruppert. A Wait-Free Deque with Polylogarithmic Step Complexity. In Proc. International Conference on Principles of Distributed Systems, 2023.

Hassan Ashtiani, Vinayak Pathak, Ruth Urner. Adversarially Robust Learning with Tolerance. In Proc. International Conference on Algorithmic Learning Theory, 2023.

Paul Bastide, Marthe Bonamy, Anthony Bonato, Pierre Charbit, 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, Shahin Kamali, Kim S. Larsen. Online Interval Scheduling with Predictions. In Proc. 18th International Symposium on Algorithms and Data Structures, 2023.

Elisabet Burjons, Fabian Frei, Matthias Gehnen, Henri Lotze, Daniel Mock, Peter Rossmanith. Delaying Decisions and Reservation Costs. In Proc. 29th International Conference on Computing and Combinatorics, Part 1, 371-383, 2023.

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, Ruth Urner. Precision Recall Cover: A Method For Assessing Generative Models. In Proc. International Conference on Artificial Intelligence and Statistics, 2023.

Stephane Durocher, Shahin Kamali, Myroslav Kryven, Fengyi Liu, Amirhossein Mashghdoust, Avery Miller, Pouria Zamani Nezhad, Ikaro Penha Costa, Timothy Zapp. Cops and Robbers on 1-Planar Graphs. In Proc. 31st International Symposium on Graph Drawing and Network Visualization, Part 2, 3-17, 2023.

Stephane Durocher, Shahin Kamali, Pouria Zamani Nezhad. Online Square Packing with Predictions. In Proc. 35th Canadian Conference on Computational Geometry, 9-18, 2023.

Matthew Jenssen, Will Perkins, Aditya Potukuchi. Approximately counting independent sets in bipartite graphs via graph containers. Random Structures and Algorithms, 63(1): 215-241, 2023.

Shahin Kamali, Mohammadmasoud Shabanijou. Improved Algorithms for Burning Planar Point Sets. In Proc. 35th Canadian Conference on Computational Geometry, 161-167, 2023.

Tosca Lechner, Vinayak Pathak, Ruth Urner. Adversarially Robust Learning with Uncertain Perturbation Sets, In Proc. Conference on Neural Information Processing Systems, 2023.

Tosca Lechner, Ruth Urner, Shai Ben-David. Strategic Classification with Unknown User Manipulations. In Proc. International Conference on Machine Learning, 2023.

Hossein Naderibeni, Eric Ruppert. A Wait-free Queue with Polylogarithmic Step Complexity. In Proc. ACM Symposium on Principles of Distributed Computing, 2023.

Amgad Rady, 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, 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, Eric Ruppert. Practically and Theoretically Efficient Garbage Collection for Multiversioning. In Proc. 28th ACM Symposium on Principles and Practice of Parallel Programming, 2023.

Spyros Angelopoulos, Shahin Kamali, Kimia Shadkami. Online Bin Packing with Predictions. In Proc. International Joint Conference on Artificial Intelligence, 2022.

Spyros Angelopoulos, 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, Elisabet Burjons. Martin Raszyk, Peter Rossmanith, Reoptimization of Parameterized Problems. Acta Informatica 59, 2022.

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, 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, 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, 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, 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, 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, Aditya Potukuchi. Independent sets of a given size and structure in the hypercube. Combinatorics, Probability and Computing, 31(4), 2022.

Matthew Jenssen, Aditya Potukuchi, Will Perkins. Approximately counting independent sets in bipartite graphs via graph containers. In Proc. 33rd ACM-SIAM Symposium on Discrete Algorithms, 2022.

Shahin Kamali. Compact representation of graphs with bounded bandwidth or treedepth. Information and Computation, 285, 2022.

Shahin Kamali, Pooya Nikbakht. Online Square Packing with Rotation. In Proc. 34th Canadian Conference on Computational Geometry, 2022.

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, Ruth Urner. Learning Losses for Strategic Classification. In Proc. 36th AAAI Conference on Artificial Intelligence, 2022.

George Tourlakis, Computability, Springer, 2021.

Sushant Agarwal, Nivasini Ananthakrishnan, Shai Ben-David, Tosca Lechner, 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, 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, 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, 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, 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, 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, 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.

Sushant Agarwal, Nivasini Ananthakrishnan, Shai Ben-David, Tosca Lechner, Ruth Urner. On Learnability wih Computable Learners. In Proc. 31st International Conference on Algorithmic Learning Theory, 2020.

Hassan Ashtiani, Vinayak Pathak, Ruth Urner. Black-box Certification and Learning under Adversarial Perturbations. In Proc. 37th International Conference on Machine Learning, 2020.

Qiyi Tang, Franck van Breugel. Deciding probabilistic bisimilarity distance one for probabilistic automata. Journal of Computer and System Sciences 111: 57-84, 2020.

2015-2019

2010-2014

2006-2009

2005

2004

2003

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.

(James) Hyukjoon Kwon, Improved Results on Models of Greedy and Primal-Dual Algorithms, M.Sc. thesis, 2008.

Nassim Nasser, PBT Framework and BT Reductions, M.Sc. project, 2008.

Jaisingh Solanki, A Randomized Algorithm for Cake Cutting, M.Sc. thesis, 2007.

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.)

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.)

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, Recursive Pictures, 2008.

Soheil Pourhashemi, Leftist and Skew Heaps (Algorithmics Animation Workshop), 2007.

Daniel Natapov, The Max Cut Problem (Attended CS6111), 2007.

Zhenyu Pan, Delaunay and Voronoi Diagram (Algorithmics Animation Workshop), 2007.

Gregory Fine, Voronoi Diagram (Algorithmics Animation Workshop), 2007.

Geri Grolinger, The Pebble Game (Attended CS6111), 2006.

Leonardo Zambito, Travelling Salesman Problem (Algorithmics Animation Workshop), 2006.

Roman Gubarenko, Optimal Static Binary Search Tree (Algorithmics Animation Workshop), 2005

Dena Ghiassi, 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.