Chicago Journal of Theoretical Computer Science

Author of this document: Michael J. O'Donnell
Host: The University of Chicago , Department of Computer Science

The Chicago Journal of Theoretical Computer Science is a peer-reviewed scholarly journal in theoretical computer science. Articles are submitted and published in LaTeX source form, and distributed internationally over the InterNet. Articles are augmented by refereed forward references to improvements and subsequent related work. Readers may obtain articles through FTP , and HTTP ( World Wide Web ). Other widely used network tools will be supported as they arise in the future. The Journal is committed to minimizing publication delays, and to promoting maximum flexibility in the ways that readers use the journal for teaching, research, and scholarship. Access to articles is open, but we depend on subscriptions to support journal operations.

---

Journal Articles

(recent articles in reverse chronology)

• 2002 Articles
  • 1. Self-Stabilizing Local Mutual Exclusion and Definition Refinement by Jeffrey Beauquier, Ajoy K. Datta, Maria Gradinariu, and Frederic Magniette. July 24, 2002
  • 2. The Query Complexity of Program Checking by Constant-Depth Circuits by V. Arvind, K. V. Subrahmanyam and N. V. Vinodchandran. December 5, 2002
• 2000 Articles
  • 4. Supporting Increment and Decrement Operations in Balancing Networks by William Aiello, Costas Busch, Maurice Herlihy, Marios Mavronicolas, Nir Shavit, and Dan Touitou. December 14, 2000
  • 3. Orthogonal Accuracy Clock Synchronization by Ulrich Schmid 17 August, 2000
  • 2. Characterizing Small Depth and Small Space Classes by Operators of Higher Type by Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, and Klaus W. Wagner 6 August, 2000
  • 1. Heuristics Versus Completeness for Graph Coloring by Jorg Rothe 29 February, 2000
• 1999 Articles
  • 11. Satisfiability Coding Lemma by Ramamohan Paturi, Pavel Pudlak, and Francis Zane, 31 December, 1999
  • 10. Self-Stabilizing Distributed Constraint Satisfaction by Zeev Collin, Rina Dechter, and Shmuel Katz, 31 December, 1999
  • 9. Time Bounds for Strong and Hybrid Consistency for Arbitrary Abstract Data Types by Martha J. Kosa, 6 August 1999
  • 8. Bounds for Linear Satisfiability Problems by Jeff Erickson, 6 August 1999
  • 7. The Permanent Requires Large Uniform Threshold Circuits by Eric Allender, 6 August 1999
  • 6. Hopfield Neural Networks and Self-Stabilization by Arun Jagota, 6 August 1999
  • 5. The Complexity of Problems on Graphs Represented as OBDDs byJoan Feigenbaum, Sampath Kannan, Moshe Y. Vardi, and Mahesh Viswanathan, 6 August 1999
  • 4. The Complexity of Generating Test Instances by Christoph Karg, Johannes Köbler, and Rainer Schuler ( Special Issue on Computational Complexity , results from Dagstuhl-Seminar 1996, Eric Allender editor), 22 April 1999
  • 3. Complements of Multivalued Functions by Stephen Fenner, Frederic Green, Steven Homer, Alan L. Selman, Thomas Thierauf, and Heribert Vollmer, 19 March 1999
  • 2. Randomized Reductions and Isomorphisms by Jie Wang ( Special Issue on Computational Complexity , results from Dagstuhl-Seminar 1996, Eric Allender editor), 24 February 1999
  • 1. On Finding the Number of Graph Automorphisms by Robert Beals, Richard Chang, William Gasarch, and Jacobo Torán, 10 February 1999.
• 1998 Articles
  • 4. Multitolerance in Distributed Reset by Sandeep S. Kulkarni and Anish Arora ( Special Issue on Self-Stabilization , Shlomi Dolev and Jennifer Welch editors), 7 December 1998
  • 3. Self-Stabilizing Unidirectional Network Algorithms by Power Supply by Yehuda Afek and Anat Bremler( Special Issue on Self-Stabilization , Shlomi Dolev and Jennifer Welch editors), 7 December 1998
  • 2. Verification of Fair Transition Systems by Orna Kupferman and Moshe Y. Vardi , 16 March 1998.
  • 1. The Isomorphism Problem for Read-Once Branching Programs and Arithmetic Circuits by Thomas Thierauf ( Special Issue on Computational Complexity from the 1996 Dagstuhl-Seminar, Eric Allender editor), 10 March 1998.
• 1997 Articles
  • 5. Determinant: Combinatorics, Algorithms, and Complexity by Meena Mahajan and V. Vinay , 31 December 1997.
  • 4. Superstabilizing Protocols for Dynamic Distributed Systems by Shlomi Dolev and Ted Herman ( Special Issue on Self-Stabilization , Shlomi Dolev and Jennifer Welch editors), 19 December 1997.
  • 3. Self-Stabilization by Tree Correction by George Varghese, Anish Arora, and Mohamed Gouda ( Special Issue on Self-Stabilization , Shlomi Dolev and Jennifer Welch editors), 4 November 1997.
  • 2. On the Hardness of Approximating Max k-Cut and its Dual by Viggo Kann , Sanjeev Khanna , Jens Lagergren, and Alessandro Panconesi , 3 June 1997.
  • 1. On Limited versus Polynomial Nondeterminism by Uriel Feige and Joe Kilian, 12 March 1997.
• 1996 Articles
  • 6. Manhattan Channel Routing is NP-complete Under Truly Restricted Settings by Martin Middendorf, 30 December 1996.
  • 5. Uniform Self-Stabilizing Orientation of Unicyclic Networks under Read/Write Atomicity by H. James Hoover and Piotr Rudnicki ( Special Issue on Self-Stabilization , Shlomi Dolev and Jennifer Welch editors), 5 December 1996.
  • 4. Weakly Growing Context-Sensitive Grammars by Gerhard Buntrock and Gundula Niemann , 13 November 1996.
  • 3. Optimal Virtual Path Layout in ATM Networks With Shared Routing Table Switches by Ornan Gerstel, Israel Cidon, and Shmuel Zaks ( Selected Papers from PODC 1994 , David Peleg editor), 31 October 1996.
  • 2. Sparse Hard Sets for P Yield Space-Efficient Algorithms by Mitsunori Ogihara , 27 March 1996.
  • 1. Rank Predicates vs. Progress Measures in Concurrent-Program Verification by Moshe Y. Vardi , 9 February 1996.