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.

2016

  • James Aspnes, Eric Ruppert. Depth of a random binary search tree with concurrent insertions. To appear in Proc. International Conference on Distributed Computing, 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.

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

2014

  • 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.
  • Nastaran Shafiei, 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.
  • 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.
  • 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.

2012

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

2011

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

Publications in Previous Years

Recent Graduate Theses

  • Niloufar Shafiei, Non-Blocking Data Structures Handling Multiple Changes Atomically, Ph.D. 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.
  • 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.)

Recent Undergraduate (CSE4080) Projects

  • 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:
2016/09/02 14:44