Theory Group

Tareq Adnan, Suprakash Datta, Stuart MacLean. Efficient and accurate sensor network localization. Personal and Ubiquitous Computing, 18(4): 821-833, 2014

Franck van Breugel, James Worrell. The Complexity of Computing a Bisimilarity Pseudometric on Probabilistic Automata. In Horizons of the Mind, 2014.

Franck van Breugel, Elham Kashefi, Catuscia Palamidessi, Jan Rutten, editors. Horizons of the Mind. A Tribute to Prakash Panangaden - Essays Dedicated to Prakash Panangaden on the Occasion of His 60th Birthday. LNCS 8464, Springer, 2014.

Trevor Brown, Faith Ellen, Eric Ruppert. A general technique for non-blocking trees. In Proc. ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 2014.

Faith Ellen, Panagiota Fatourou, Joanna Helga, Eric Ruppert. The amortized complexity of non-blocking binary search trees. In Proc. ACM Symposium on Principles of Distributed Computing, 2014.

Rachid Guerraoui, Eric Ruppert. A paradox of eventual linearizability in shared memory. In Proc. ACM Symposium on Principles of Distributed Computing, 2014.

Rachid Guerraoui, Eric Ruppert. Linearizability Is Not Always a Safety Property. In Proc. 2nd International Conference on Networked Systems, 2014.

Stuart MacLean, Suprakash Datta. Reducing the Positional Error of Connectivity-Based Positioning Algorithms Through Cooperation Between Neighbors. IEEE Transactions on Mobile Computing, 13(8): 1868-1882, 2014.

Yehuda Schwartz, George Tourlakis. On the proof-theory of a first-order version of GL. In Logic and Logical Philosophy, 23(3):329-363, 2014.

Nastaran Shafiei, Franck van Breugel. Automatic handling of native methods in Java PathFinder. In Proc. International Symposium on Model Checking of Software, 2014.

Tareq Adnan, Suprakash Datta. AdAMAC: A New MAC Protocol for High Traffic Wireless Networks. In Proc. 4th International Conference on Ambient Systems, Networks and Technologies and 3rd International Conference on Sustainable Energy Information Technology, 2013.

Franck van Breugel, Claudio Hermida, Michael Makkai, James Worrell. Addendum to “Recursively defined metric spaces without contraction” [TCS 380 (1/2) (2007) 143-163]. Theoretical Computer Science, 492: 117-122, 2013.

Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, Anne-Marie Kermarrec, Eric Ruppert, Hung Tran-The. Byzantine agreement with homonyms. Distributed Computing, 26(5-6): 321-340, 2013.

Stuart MacLean, Suprakash Datta. Energy Constrained Positioning in Mobile Wireless Ad hoc and Sensor Networks. In Proc. 4th International Conference on Ambient Systems, Networks and Technologies and 3rd International Conference on Sustainable Energy Information Technology, 2013.

Yehuda Schwartz, George Tourlakis. A proof theoretic tool for first-order modal logic. In Bulletin of the Section of Logic, 42(3-4):93-110, 2013.

Niloufar Shafiei. Non-blocking patricia tries with replace operations. In Proc. 33rd International Conference on Distributed Computing Systems, 2013

Hui Wang, Michael Jenkin, Patrick W. Dymond. Enhancing Exploration in Topological Worlds with a Directional Immovable Marker. In Proc. 10th Conference on Computer and Robot Vision, 2013.

Franck van Breugel. On behavioural pseudometrics and closure ordinals. Information Processing Letters, 112(19): 715-718, 2012.

Arkadev Chattopadhyay, Jeff Edmonds, Faith Ellen, and Toniann Pitassi. A little advice can be very helpful. In Proc. ACM-SIAM Symposium on Discrete Algorithms, 2012.

Di Chen, Franck van Breugel, James Worrell. On the Complexity of Computing Probabilistic Bisimilarity. In Proc. 15th International Conference on Foundations of Software Science and Computational Structures, 2012.

Elise Cormie-Bowins, Franck van Breugel. Measuring Progress of Probabilistic LTL Model Checking. In Proc. 10th Workshop on Quantitative Aspects of Programming Languages and Systems, 2012.

Jeff Edmonds. On the Competitiveness of AIMD-TCP within a General Network. Theoretical Computer Science 462: 12-22, 2012.

Jeff Edmonds, Kirk Pruhs. Scalably scheduling processes with arbitrary speedup curves. ACM Transactions on Algorithms, 8(3): 28, 2012.

George Tourlakis, Theory of Computation, John Wiley and Sons, 2012.

Hui Wang, Michael Jenkin, Patrick W. Dymond. Enhancing Exploration in Topological Worlds with Multiple Immovable Markers. In Proc. 9th Conference on Computer and Robot Vision, 2012.

Tareq Adnan, Suprakash Datta, Stuart MacLean. Effcient and Accurate Range-based Sensor Network Localization. In Proc. 3rd International Conference on Ambient Systems, Networks and Technologies and 9th International Conference on Mobile Web Information Systems, 2011.

Anton Belov, Matti Järvisalo, Zbigniew Stachniak. Depth-Driven Circuit-Level Stochastic Local Search for SAT. In Proc. 22nd International Joint Conference on Artificial Intelligence, 2011.

Trevor Brown and Joanna Helga. Non-blocking k-ary search trees. Proc. 15th International Conference On Principles Of Distributed Systems, 2011.

Trevor Brown, Faith Ellen, Eric Ruppert. Pragmatic primitives for non-blocking data structures. In Proc. PODC, 2013.

Ho-Leung Chan, Jeff Edmonds, Tak Wah Lam, Lap-Kei Lee, Alberto Marchetti-Spaccamela, Kirk Pruhs. Nonclairvoyant Speed Scaling for Flow and Energy. Algorithmica, 61(3): 507-517, 2011.

Ho-Leung Chan, Jeff Edmonds, Kirk Pruhs. Speed Scaling of Processes with Arbitrary Speedup Curves on a Multiprocessor, Theory of Computing Systems, 49(4): 817-833, 2011.

Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, Anne-Marie Kermarrec, Eric Ruppert and Hung Tran-The. Byzantine Agreement with Homonyms. In Proc. 30th ACM Symposium on Principles of Distribued Computing, pages 21-30, 2011.

Jeff Edmonds, Sungjin Im, Benjamin Moseley. Online scalable scheduling for the l_k-norms of flow time without conservation of work. In Proc. ACM-SIAM Symposium on Discrete Algorithms, 2011.

Jeff Edmonds, Kirk Pruhs. Cake cutting really is not a piece of cake. ACM Transactions on Algorithms, 7(4): 51, 2011.

Stuart MacLean, Suprakash Datta. The minimum positional error incurred by any connectivity-based positioning algorithm for mobile wireless systems. Theoretical Computer Science, 412(50): 6897-6912, 2011.

Stuart MacLean, Suprakash Datta. Improving the accuracy of connectivity-based positioning for mobile sensor networks. In Proc. 22nd IEEE International Symposium on Personal, Indoor and Mobile Radio Communications, 2011.

Yehuda Schwartz, George Tourlakis. Pure iteration and substitution as the basis of computability. In Bulletin of the Section of Logic, 40(3-4):203-213, 2011.

Hui Wang, Michael Jenkin, Patrick W. Dymond. The relative power of immovable markers in topological mapping. In Proc. IEEE International Conference on Robotics and Automation, 2011.

Xin Zhang, Franck van Breugel. A Progress Measure for Explicit-State Probabilistic Model-Checkers. In Proc. 38th International Colloquium on Automata, Languages and Programming, 2011.

S. Chakraborty and Jeff Edmonds, Bounding Variance and Expectation of Longest Path Lengths in DAGs from Variance and Expectation of Edge Lengths, In SODA, ACM Symp. on Discrete Algorithms, 2010.

Suprakash Datta, Patrick Dymond and Jeff Edmonds. TCP is competitive with Resource Augmentation (against a limited adversary). In Theory of Computing Systems, Vol 47 pp.~174-183, 2010.

Jeff Edmonds, A. Sidiropoulos, and A. Zouzias, Hardness of Embedding into R^2 with Constant Distortion, In SODA, ACM Symp. on Discrete Algorithms, 2010.

Faith Ellen, Panagiota Fatourou, Eric Ruppert and Franck van Breugel. Non-blocking binary search trees. In Proc. 29th ACM Symposium on Principles of Distributed Computing, 2010.

Yehuda Schwartz, George Tourlakis. On the proof-theory of two formalisations of modal first-order logic. In Studia Logica 96:349-373, 2010.