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.
=== 2014 ===

  * Tareq Adnan, [[http://www.cse.yorku.ca/~datta|Suprakash Datta]], Stuart MacLean.  Efficient and accurate sensor network localization. //Personal and Ubiquitous Computing//, 18(4): 821-833, 2014

  * [[http://www.cse.yorku.ca/~franck|Franck van Breugel]], James Worrell.  The Complexity of Computing a Bisimilarity Pseudometric on Probabilistic Automata.  In //Horizons of the Mind//, 2014.

  * [[http://www.cse.yorku.ca/~franck|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, [[http://www.cse.yorku.ca/~ruppert|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, [[http://www.cse.yorku.ca/~ruppert|Eric Ruppert]]. The amortized complexity of non-blocking binary search trees. In //Proc. ACM Symposium on Principles of Distributed Computing//, 2014.

  * Rachid Guerraoui, [[http://www.cse.yorku.ca/~ruppert|Eric Ruppert]]. A paradox of eventual linearizability in shared memory. In //Proc. ACM Symposium on Principles of Distributed Computing//, 2014.

  * Rachid Guerraoui, [[http://www.cse.yorku.ca/~ruppert|Eric Ruppert]]. Linearizability Is Not Always a Safety Property. In //Proc. 2nd International Conference on Networked Systems//, 2014.

  * Stuart MacLean, [[http://www.cse.yorku.ca/~datta|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, [[http://www.cse.yorku.ca/~gt|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, [[http://www.cse.yorku.ca/~franck|Franck van Breugel]]. Automatic handling of native methods in Java PathFinder. In //Proc. International Symposium on Model Checking of Software//, 2014.

=== 2013 ===

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

  * [[http://www.cse.yorku.ca/~franck|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, [[http://www.cse.yorku.ca/~ruppert|Eric Ruppert]], Hung Tran-The. Byzantine agreement with homonyms. //Distributed Computing//, 26(5-6): 321-340, 2013.

  * Stuart MacLean, [[http://www.cse.yorku.ca/~datta|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, [[http://www.cse.yorku.ca/~gt|George Tourlakis]].  A proof theoretic tool for first-order modal logic.  In //Bulletin of the Section of Logic//, 42(3-4):93-110, 2013.

  * [[http://www.cse.yorku.ca/~niloo"|Niloufar Shafiei]]. Non-blocking patricia tries with replace operations.  In //Proc. 33rd International Conference on Distributed Computing Systems//, 2013

  * Hui Wang, Michael Jenkin, [[http://www.cse.yorku.ca/~patrick|Patrick W. Dymond]]. Enhancing Exploration in Topological Worlds with a Directional Immovable Marker. In //Proc. 10th Conference on Computer and Robot Vision//, 2013.

=== 2012 ===

  * [[http://www.cse.yorku.ca/~franck|Franck van Breugel]]. On behavioural pseudometrics and closure ordinals. //Information Processing Letters//, 112(19): 715-718, 2012.

  * Arkadev Chattopadhyay, [[http://www.cse.yorku.ca/~jeff|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, [[http://www.cse.yorku.ca/~franck|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, [[http://www.cse.yorku.ca/~franck|Franck van Breugel]].  Measuring Progress of Probabilistic LTL Model Checking. In //Proc. 10th Workshop on Quantitative Aspects of Programming Languages and Systems//, 2012.

  * [[http://www.cse.yorku.ca/~jeff|Jeff Edmonds]]. On the Competitiveness of AIMD-TCP within a General Network. //Theoretical Computer Science// 462: 12-22, 2012.

  * [[http://www.cse.yorku.ca/~jeff|Jeff Edmonds]], Kirk Pruhs. Scalably scheduling processes with arbitrary speedup curves. //ACM Transactions on Algorithms//, 8(3): 28, 2012.

  * [[http://www.cse.yorku.ca/~gt|George Tourlakis]], //Theory of Computation//, John Wiley and Sons, 2012.

  * Hui Wang, Michael Jenkin, [[http://www.cse.yorku.ca/~patrick|Patrick W. Dymond]]. Enhancing Exploration in Topological Worlds with Multiple Immovable Markers. In //Proc. 9th Conference on Computer and Robot Vision//, 2012.

=== 2011 ===

  * Tareq Adnan, [[http://www.cse.yorku.ca/~datta|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, [[http://www.cse.yorku.ca/~zbigniew|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, [[http://www.cse.yorku.ca/~ruppert|Eric Ruppert]].  Pragmatic primitives for non-blocking data structures. In //Proc. PODC//, 2013.

  * Ho-Leung Chan, [[http://www.cse.yorku.ca/~jeff|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, [[http://www.cse.yorku.ca/~jeff|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, [[http://www.cse.yorku.ca/~ruppert|Eric Ruppert]] and Hung Tran-The.  Byzantine Agreement with Homonyms.  In //Proc. 30th ACM Symposium on Principles of Distribued Computing//, pages 21-30, 2011.

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

  * [[http://www.cse.yorku.ca/~jeff|Jeff Edmonds]], Kirk Pruhs. Cake cutting really is not a piece of cake. //ACM Transactions on Algorithms//, 7(4): 51, 2011.

  * Stuart MacLean, [[http://www.cse.yorku.ca/~datta|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, [[http://www.cse.yorku.ca/~datta|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, [[http://www.cse.yorku.ca/~gt|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, [[http://www.cse.yorku.ca/~patrick|Patrick W. Dymond]]. The relative power of immovable markers in topological mapping. In //Proc. IEEE International Conference on Robotics and Automation//, 2011.

  * Xin Zhang, [[http://www.cse.yorku.ca/~franck|Franck van Breugel]].  A Progress Measure for Explicit-State Probabilistic Model-Checkers. In //Proc. 38th International Colloquium on Automata, Languages and Programming//, 2011.

=== 2010 ===

  * S. Chakraborty and [[http://www.cse.yorku.ca/~jeff|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.

  * [[http://www.cs.yorku.ca/~datta|Suprakash Datta]], [[http://www.cs.yorku.ca/~dymond|Patrick Dymond]] and [[http://www.cs.yorku.ca/~jeff|Jeff Edmonds]].  TCP is competitive with Resource Augmentation (against a limited adversary).  In //Theory of Computing
 Systems//, Vol 47 pp.~174-183, 2010.

  * [[http://www.cse.yorku.ca/~jeff|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, [[http://www.cse.yorku.ca/~ruppert|Eric Ruppert]] and [[http://www.cse.yorku.ca/~franck|Franck van Breugel]].  Non-blocking binary search trees.  In //Proc. 29th ACM Symposium on Principles of Distributed Computing//, 2010.
 
  * Yehuda Schwartz, [[http://www.cse.yorku.ca/~gt|George Tourlakis]].  On the proof-theory of two formalisations of modal first-order logic.  In //Studia Logica// 96:349-373, 2010.