Skip Navigation
York U: Redefine the PossibleHOME | Current Students | Faculty & Staff | Research | International
Search »FacultiesLibrariesCampus MapsYork U OrganizationDirectorySite Index
Future Students, Alumni & Visitors
Research

Recent Publications

Many of the papers listed below may be downloaded from the authors' web pages.

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.

2020

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

2019

  • Giorgio Bacci, Giovanni Bacci, Kim G. Larsen, Radu Mardare, Qiyi Tang, Franck van Breugel. Computing Probabilistic Bisimilarity Distances for Probabilistic Automata. In Proc. 30th International Conference on Concurrency Theory, 2019.
  • Panagiota Fatourou, Elias Papavasileiou, Eric Ruppert. Persistent Non-Blocking Binary Search Trees Supporting Wait-Free Range Queries. In Proc. 31st ACM Symposium on Parallelism in Algorithms and Architectures, 2019.
  • Christina Göpfert, Shai Ben-David, Olivier Bousquet, Sylvain Gelly, Ilya O. Tolstikhin, Ruth Urner. When can unlabeled data improve the learning rate? In Proc. 32nd Conference on Learning Theory, 2019.
  • Niloufar Shafiei. Non-blocking Patricia tries with replace operations. Distributed Computing, 32(5): 423-442, 2019.

2018

  • Jeff Edmonds, Venkatesh Medabalimi, Toniann Pitassi. Hardness of Function Composition for Semantic Read once Branching Programs. In Proc. Computational Complexity Conference, 2018.
  • Qiyi Tang, Franck van Breugel. Deciding Probabilistic Bisimilarity Distance One for Labelled Markov Chains. In Proc. 30th International Conference on Computer Aided Verification Part 1, 2018.
  • Qiyi Tang, Franck van Breugel. Deciding Probabilistic Bisimilarity Distance One for Probabilistic Automata. In Proc. 29th International Conference on Concurrency Theory, 2018.

2017

  • Franck van Breugel. Probabilistic bisimilarity distances. In ACM SIGLOG News 4(4): 33-51, 2017.
  • Stefan Dobrev, Jeff Edmonds, Dennis Komm, Rastislav Královic, Richard Královic, Sacha Krug, Tobias Mömke. Improved analysis of the online set cover problem with advice. Theoretical Computer Science, 689: 96-107, 2017.
  • Aryeh Kontorovich, Sivan Sabato, Ruth Urner. Active Nearest-Neighbor Learning in Metric Spaces. Journal of Machine Learning Research, 18: 195:1-195:38, 2017.
  • Eric Ruppert. Brief Announcement: Readers of Wait-Free Unbounded Registers Must Write. In Proc. ACM Symposium on Principles of Distributed Computing, 2017.
  • Ben Spencer, Michael Benedikt, Anders Møller, Franck van Breugel. ArtForm: a tool for exploring the codebase of form-based websites. In Proceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis , 2017.
  • Qiyi Tang, Franck van Breugel. Algorithms to Compute Probabilistic Bisimilarity Distances for Labelled Markov Chains. In Proc. 28th International Conference on Concurrency Theory, 2017.

2016

  • James Aspnes, Eric Ruppert. Depth of a random binary search tree with concurrent insertions. In Proc. International Conference on Distributed Computing, 2016.
  • Arkadev Chattopadhyay, Jeff Edmonds, Faith Ellen, Toniann Pitassi. Upper and Lower Bounds on the Power of Advice. SIAM Journal on Computing, 45(4): 1412-1432, 2016.
  • Stephen A. Cook, Jeff Edmonds, Venkatesh Medabalimi, Toniann Pitassi. Lower bounds for nondeterministic semantic read-once branching programs. In Proc. International Colloquium on Automata, Languages, and Programming, 2016.
  • Qiyi Tang, Franck van Breugel. Computing probabilistic bisimilarity distances via policy iteration. In Proc. International Conference on Concurrency Theory, 2016.
  • George Tourlakis. A new arithmetically incomplete first-order extension of GL all theorems of which have cut free proofs. In Bulletin of the Section of Logic, 45(1):17-31, 2016.

2015

  • Carole Delporte-Gallet, Hugues Fauconnier, Petr Kuznetsov, Eric Ruppert. On the space complexity of set agreement. In Proc. ACM Symposium on Principles of Distributed Computing, 2015.
  • Feng Gao, George Tourlakis. A short and readable proof of cut elimination for two first-order modal logics. In Bulletin of Section of Logic, 44(3-4):131-148, 2015.
  • Md. Kowsar Hossain, Suprakash Datta, Jeff Edmonds. Ad-ATMA: An efficient MAC protocol for wireless sensor and ad hoc networks. In Proc. International Conference on Ambient Systems, Networks and Technologies, 2015.
  • Niloufar Shafiei. Doubly-linked lists with good amortized complexity. In Proc. 19th International Conference on Principles of Distributed Systems, 2015. This paper won the conference's best paper award.

Publications in Previous Years

Graduate Theses

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

Undergraduate Research Projects

  • Koko NanahJi and Jordan Malek, Lock-free Bag Data Structures, 2020-21.
  • Trevor Brown, Non-blocking Search Trees, 2010.
  • 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.
Last modified:
2021/11/22 16:33