Theory Group

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.

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.

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.

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.

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.