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.
Access to
articles is open, Under the journal copyright policy
authors retain copyright to their work: papers are published
under a Creative Commons Attribution License.

To submit papers, send email to chicago-journal at cs.uchicago.edu

- 2016 Articles
- 9.
**Computing the Degenerate Ground Space of Gapped Spin Chains in Polynomial Time**by Christopher T. Chubb and Steven T. Flammia - 8.
**On Fractional Block Sensitivity**by Raghav Kulkarni and Avishay Tal - 7.
**A Note on Discrete Gaussian Combinations of Lattice Vectors**by Divesh Aggarwal, and Oded Regev - 6.
**Some Lower Bound Results for Set-Multilinear Arithmetic Computations**by V. Arvind, and S. Raja - 5.
**On deciding the existence of perfect entangled strategies for nonlocal games**by Laura Mančinska, David E. Roberson, and Antonios Varvitsiotis - 4.
**QMA with subset state witnesses**by Alex B. Grilo, Iordanis Kerenidis, and Jamie Sikora - 3.
**Homomorphism Polynomials complete for VP**by Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, and Nitin Saurabh - 2.
**Nonnegative Rank vs. Binary Rank**by Thomas Watson - 1.
**Layouts of Expander Graphs**by Vida Dujmovič, Anastasios Sidiropoulos and David R. Wood

- 9.
- 2015 Articles
- 4.
**Noise Stable Halfspaces are Close to Very Small Juntas**by Ilias Diakonikolas, Ragesh Jaiswal, Rocco A. Servedio, Li-Yang Tan, and Andrew Wan - 3.
**Reducing uniformity in Khot-Saket hypergraph coloring hardness reductions**by Girish Varma - 2.
**Entropy of weight distributions of small-bias spaces and pseudobinomiality**by Louay Bazzi - 1.
**Unique Games on the Hypercube**by Naman Agarwal, Guy Kindler, Alexandra Kolla, and Luca Trevisan

- 4.
- 2014 Articles
- 10.
**Simpler Exact Leader Election via Quantum Reduction**by Hirotada Kobayashi, Keiji Matsumoto, and Seiichiro Tani - 9.
**A Note on Subspace Evasive Sets**by Avraham Ben-Aroya, and Igor Shinkar - 8.
**Computing in Matrix Groups Without Memory**by Peter J. Cameron, Ben Fairbairn and Maximilien Gadouleau - 7.
**Computing in Permutation Groups Without Memory**by Peter J. Cameron, Ben Fairbairn and Maximilien Gadouleau - 6.
**A composition theorem for decision tree complexity**by Ashley Montanaro

- 5.
**Complexity of Testing Reachability in Matroids**by B. V. Raghavendra Rao and Jayalal Sarma

- 4.
**Quantum Adversary Lower Bound for Element Distinctness with Small Range**by Ansis Rosmanis

- 3.
**Near-linear time simulation of linear extensions of a height-2 poset with bounded interaction**by Mark Huber - 2.
**Reachability in K_{3,3}-free and K_5-free Graphs is in Unambiguous Logspace**by Thomas Thierauf and Fabian Wagner - 1.
**Lift-and-Project Integrality Gaps for the Traveling Salesperson Problem**by Thomas Watson

- 10.
- 2013 Articles
- 14.
**Testing Booleanity and the Uncertainty Principle**by Tom Gur and Omer Tamuz - 13.
**Graph Pricing Problem on Bounded Treewidth, Bounded Genus and k-Partite Graphs**by Parinya Chalermsook, Shiva Kintali, Richard J. Lipton, and Danupon Nanongkai - 12.
**A Lower Bound for Fourier Transform Computation in a Linear Model Over 2x2 Unitary Gates Using Matrix Entropy**by Nir Ailon - 11.
**Coherent state exchange in multi-prover quantum interactive proof systems**by Debbie Leung, Ben Toner, and John Watrous - 10.
**On the complexity of solving linear congruences and computing nullspaces modulo a constant**by Niel de Beaudrap - 9.
**Complexity of the homomorphism extension problem in the random case**by Alexandr Kazda - 8.
**Simpler semidefinite programs for completely bounded norms**by John Watrous - 7.
**Interactive proofs with competing teams of no-signaling provers**by Gus Gutoski - 6.
**The non-adaptive query complexity of testing k-parities**by Harry Buhrman, David García-Soriano, Arie Matsliah, and Ronald de Wolf - 5.
**Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic**by Eric Allender, George Davie, Luke Friedman, Samuel B. Hopkins, and Iddo Tzameret - 4.
**Quantum Adversary (Upper) Bound**by Shelby Kimmel - 3.
**A Turing Machine Resisting Isolated Bursts Of Faults**by Ilir Çapuni, and Peter Gács - 2.
**Few Product Gates but Many Zeroes**by Bernd Borchert, Pierre McKenzie and Klaus Reinhardt - 1.
**Improved Soundness for**by Alessandro Chiesa and Michael A. Forbes*QMA*with Multiple Provers

- 14.
- 2012 Articles
- 10.
**Learning graph based quantum query algorithms for finding constant-size subgraphs**by Troy Lee, Frédéric Magniez and Miklos Santha - 9.
**On Quantum Interactive Proofs with Short Messages**by Attila Pereszlényi - 8.
**Almost all decision trees do not allow significant quantum speed-up**by Ashley Montanaro - 7.
**Computational Models with No Linear Speedup**by Amir M. Ben-Amram, Niels H. Christensen and Jakob Grue Simonsen - 6.
**Interactive proofs with efficient quantum prover for recursive Fourier sampling**by Matthew McKague - 5.
**Best Effort and Priority Queuing Policies for Buffered Crossbar Switches**by Alex Kesselman, Kirill Kogan and Michael Segal - 4.
**Hardness of the Covering Radius Problem on Lattices**by Ishay Haviv and Oded Regev. - 3.
**Linear cover time for trees is exponentially unlikely**by Amir Yehudayoff. - 2.
**Minimum and maximum against $k$ lies**by Michael Hoffman, Jiří Matoušek, Yoshio Okamoto and Philipp Zumstein. - 1.
**A concentration inequality for the overlap of a vector on a large set, with application to the communication complexity of the Gap-Hamming-Distance problem**by Thomas Vidick.

- 10.
- 2011 Articles
- 6.
**The One-Way Communication Complexity of Subgroup Membership**by Scott Aaronson, François LeGall, Alexander Russell and Seiichiro Tani. - 5.
**Mediated Equilibria in Load-Balanced Games**by Joshua R. Davis, David Liben-Nowell, Alexa Sharp and Tom Wexler. - 4.
**Notes on Large Angle Crossing Graphs**by Vida Dujmović, Joachim Gudmundsson, Pat Morin, and Thomas Wolle.

(Special Issue: Selected Papers from CATS 2010.) - 3.
**On Directional vs. General Randomized Decision Tree Complexity for Read-Once Formulas**by Kazuyuki Amano.

(Special Issue: Selected Papers from CATS 2010.) - 2.
**$k$-Cographs are Kruskalian**by Ling-Ju Hung and Ton Kloks.

(Special Issue: Selected Papers from CATS 2010.) - 1.
**Non-clairvoyant Scheduling for Weighted Flow Time and Energy on Speed Bounded Processors**by Sze-Hang Chan, Tak-Wah Lam, Lap-Kei Lee, Hing-Fung Ting, and Pan Zhang.

(Special Issue: Selected Papers from CATS 2010.)

- 6.
- 2010 Articles
- 13.
**Single-Query Learning from Abelian and Non-Abelian Hamming Distance Oracles**by David A. Meyer and James Pommersheim. - 12.
**Distributing Frequency-Dependent Data Stream Computations**by Sumit Ganguly.

(Special Issue: Selected Papers from CATS 2009.) - 11.
**An Algorithm for Affine Approximation of Binary Decision Diagrams**by Kevin Henshall, Peter Schachte, Harald Søndergaard and Leigh Whiting.

(Special Issue: Selected Papers from CATS 2009.) - 10.
**Type Checking and Inference for Polymorphic and Existential Types in Multiple-Quantifier and Type-Free Systems**by Koji Nakazawa and Makoto Tatsutay.

(Special Issue: Selected Papers from CATS 2009.) - 9.
**Transformation Rules for Z**by Mark Utting, Petra Malik and Ian Toyn.

(Special Issue: Selected Papers from CATS 2009.) - 8.
**Longest Paths in Planar DAGs in Unambiguous Log-Space**by Nutan Limaye, Meena Mahajan and Prajakta Nimbhorkar.

(Special Issue: Selected Papers from CATS 2009.) - 7.
**An Efficient Algorithm to Test Square-Freeness of Strings Compressed by Balanced Straight Line Programs**by Wataru Matsubara, Shunsuke Inenaga and Ayumi Shinohara.

(Special Issue: Selected Papers from CATS 2009.) - 6.
**Edge-Selection Heuristics for Computing Tutte Polynomials**by David J. Pearce, Gary Haggard and Gordon Royle.

(Special Issue: Selected Papers from CATS 2009.) - 5.
**On the Structure of Classes of Random Graphs**by András Faragó.

(Special Issue: Selected Papers from CATS 2009.) - 4.
**On Process Complexity**by Adam R. Day.

(Special Issue: Selected Papers from CATS 2009.) - 3.
**$d$-collapsibility is NP-complete for $d \ge 4$**by Martin Tancer - 2.
**Varieties Generated by Certain Models of Reversible Finite Automata**by Marats Golovkins and Jean-Eric Pin. June 21, 2010 - 1.
**Quantum boolean functions**by Ashley Montanaro and Tobias J. Osborne. January 13, 2010.

- 13.
- 2009 Articles
- 3.
**Quantum Merlin-Arthur Proof Systems: Are Multiple Merlins More Helpful to Arthur?**by Hirotada Kobayashi, Keiji Matsumoto, and Tomoyuki Yamakami. July 17, 2009. - 2.
**Fast C-K-R Partitions of Sparse Graphs**by Manor Mendel and Chaya Schwob. July 16, 2009. - 1.
**Legally Enforceable Fairness in Secure Two-Party Communication**by by Yehuda Lindell. June 12, 2009.

- 3.
- 2008 Articles
- 7.
**Simultaneous Communication Protocols with Quantum and Classical Messages**by Dmitry Gavinsky, Oded Regev, and Ronald de Wolf, December 29, 2008 - 6.
**Efficient Fully-Simulatable Oblivious Transfer**by Yehuda Lindell, December 2, 2008 - 5.
**The Phase Transition in Exact Cover**by Vamsi Kalapala and Cris Moore, October 1st, 2008 - 4.
**Some perfect matchings and perfect half-integral matchings in NC**by Raghav Kulkarni, Meena Mahajan, and Kasturi R. Varadarajan. 5 September 2008. - 3.
**Syntactic Characterizations of Polynomial Time Optimization Classes**by Prabhu Manyem. 22 May 2008. - 2.
**Representing Hard Lattices with $O(n\log n)$ Bits**by Miklós Ajtai. 12 May 2008. - 1.
**A Priority-Based Model of Routing**by Babak Farzad, Neil Olver and Adrian Vetta. 5 February 2008.

- 7.
- 2007 Articles
- 1.
**Computation at a Distance**by Samuel Kutin, David Moulton and Lawren Smithline. 25 September 2007.

- 1.
- 2006 Articles
- 2.
**Optimal measurements for the dihedral hidden subgroup problem**by Dave Bacon, Andrew M. Childs, and Wim van Dam. 12 October 2006. - 1.
**Protocols for Bounded-Concurrent Secure Two-Party Computation**by Yehuda Lindell. 26 September 2006.

- 2.
- 2005 Articles
- 1.
**On Ajtai's Lower Bound Technique for $R$-way Branching Programs and the Hamming Distance Problem**by Jakob Pagter. 28 May 2005.

- 1.
- 2002 Articles
- 2.
**The Query Complexity of Program Checking by Constant-Depth Circuits**by V. Arvind, K. V. Subrahmanyam and N. V. Vinodchandran. December 5, 2002 - 1.
**Self-Stabilizing Local Mutual Exclusion and Definition Refinement**by Jeffrey Beauquier, Ajoy K. Datta, Maria Gradinariu, and Frederic Magniette. July 24, 2002

- 2.
- 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 Jörg Rothe 29 February, 2000

- 4.
- 1999 Articles
- 12.
**Equivalences for Fair Kripke Structures**by Adnan Aziz, Felice Balarin, Vigyan Singhal, Robert Brayton, and Alberto Sangiovanni-Vincentelli 31 December 1999 - 11.
**Satisfiability Coding Lemma**by Ramamohan Paturi, Pavel Pudlák, 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.

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

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

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

- 6.
- 1995 Articles
- 4.
**Probabilistically Checkable Debate Systems and Nonapproximability of PSPACE-Hard Functions**by Anne Condon, Joan Feigenbaum, Carsten Lund and Peter W. Shor, 19 October 1995. - 3.
**Rabin Measures**by Nils Klarlund and Dexter Kozen, 20 September 1995 - 2.
**On the Weak mod**by Vince Grolmusz, 21 July 1995*m*Representation of Boolean Functions - 1.
**Symmetric**by Noam Nisan and Amnon Ta-Shma, 30 June 1995*Logspace*is Closed Under Complement

*CJTCS*has a policy of free access to all articles.

- 4.

- ISSN: 1073-0486
- Publisher: Department of Computer Science, The University of Chicago
- Editor-in-Chief: Janos Simon
- Associate Editor-in-Chief:
- A distinguished board of editors

- Articles published in the journal

returns you to this front page