Theory Group

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
=== 2019 ===

  * 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.  In //Proc. 30th International Conference on Concurrency Theory//, 2019.

  * Panagiota Fatourou, Elias Papavasileiou, [[http://www.cse.yorku.ca/~ruppert|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, [[http://www.cse.yorku.ca/~ruth|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 ===

  * [[http://www.cse.yorku.ca/~jeff|Jeff Edmonds]], Venkatesh Medabalimi, Toniann Pitassi.  Hardness of Function Composition for Semantic Read once Branching Programs.  In //Proc. Computational Complexity Conference//, 2018.

  * Qiyi Tang, [[http://www.cse.yorku.ca/~franck|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, [[http://www.cse.yorku.ca/~franck|Franck van Breugel]].  Deciding Probabilistic Bisimilarity Distance One for Probabilistic Automata.  In //Proc. 29th International Conference on Concurrency Theory//, 2018.

=== 2017 ===

  * [[http://www.cse.yorku.ca/~franck|Franck van Breugel]].  Probabilistic bisimilarity distances.  In //ACM SIGLOG News// 4(4): 33-51, 2017.

  * Stefan Dobrev, [[http://www.cse.yorku.ca/~jeff|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, [[http://www.cse.yorku.ca/~ruth|Ruth Urner]].  Active Nearest-Neighbor Learning in Metric Spaces. //Journal of Machine Learning Research//, 18: 195:1-195:38, 2017.

  * [[http://www.cse.yorku.ca/~ruppert|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, [[http://www.cse.yorku.ca/~franck|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, [[http://www.cse.yorku.ca/~franck|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, [[http://www.cse.yorku.ca/~ruppert|Eric Ruppert]].  Depth of a random binary search tree with concurrent insertions.  In //Proc. International Conference on Distributed Computing//, 2016.

  * Arkadev Chattopadhyay, [[http://www.cse.yorku.ca/~jeff|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, [[http://www.cse.yorku.ca/~jeff|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, [[http://www.cse.yorku.ca/~franck|Franck van Breugel]].  Computing probabilistic bisimilarity distances via policy iteration. In //Proc. International Conference on Concurrency Theory//, 2016.

  * [[http://www.cse.yorku.ca/~gt|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, [[http://www.cse.yorku.ca/~ruppert|Eric Ruppert]].  On the space complexity of set agreement.  In //Proc. ACM Symposium on Principles of Distributed Computing//, 2015.

  * Feng Gao, [[http://www.cse.yorku.ca/~gt|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, [[http://www.eecs.yorku.ca/~datta|Suprakash Datta]], [[http://www.eecs.yorku.ca/~jeff|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.

  * [[http://www.eecs.yorku.ca/~niloo|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**.