Chicago Journal of Theoretical 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

Journal Articles

2024 Articles
- 2. Influences of Fourier Completely Bounded Polynomials and Classical Simulation of Quantum Algorithms by Francisco Escudero Gutiérrez
2023 Articles

3. Vanishing-Error Approximate Degree and QMA Complexity by Alexander A. Sherstov and Justin Thaler

2. A Family of Dictatorship Tests with Perfect Completeness for 2–to–2 Label Cover by Joshua Brakensiek and Venkatesan Guruswami

1. Discrete logarithm and Diffie-Hellman problems in identity black-box groups by Gábor Iványos, Antoine Joux, and Miklos Santha

2022 Articles

2. Approximating the orthogonality imension of graphs and hypergraphs by Ishay Haviv

1. Complexity of counting feedback vertex sets by Kévin Perrot

2020 Articles

4. Coin Theorems and the Fourier Expansion by Rohit Agrawal

3. The communication complexity of the inevitable intersection problem by Dmitry Gavinsky

2. On Explicit Branching Programs for the Rectangular Determinant and Permanent Polynomials by V. Arvind, Abhranil Chatterjee, Rajit Datta, and Partha Mukhpadhyay

1. Lower bounds for linear decision lists by Arkadev Chattopadhyay, Meena Mahajan, Nikhil Mande, and Nitin Saurabh

2019 Articles

3. H-wise Independence by Ishay Haviv and Michael Langberg

2. Non-commutative computations: lower bounds and polynomial identity testing by Guillaume Lagarde, Guillaume Malod and Sylvain Perifel

1. Collision-Based Testers are Optimal for Uniformity and Closeness by Ilias Diakonikolas, Themis Gouleakis, John Peebles, and Eric Price

2018 Articles

6. Finding Significant Fourier Coefficients: Clarifications, Simplifications, Applications and Limitations by Steven D. Galbraith, Joel Laity and Barak Shani

5. The border support rank of two-by-two matrix multiplication is seven by Markus Bläser, Matthias Christandl, and Jeroen Zuiddam

4. Extended Nonlocal Games from Quantum-Classical Games by Vincent Russo and John Watrous

3. Universal Locally Testable Codes by Oded Goldreich and Tom Gur

2. Local Maxima and Improved Exact Algorithm for MAX-2-SAT by Matthew B. Hastings

1. On monotone circuits with local oracles and clique lower bounds by Jan Krajíček and Igor C. Oliveira

2017 Articles

2.Unique reconstruction threshold for random jigsaw puzzles by Rajko Nenadov, Pascal Pfister and Angelika Steger

1.Quantum Algorithms for Matrix Products over Semirings by François Le Gall, and Harumichi Nishimura

2016 Articles

14. Friedgut--Kalai--Naor Theorem for Slices of the Boolean Cube by Yuval Filmus

13. Optimal Bounds for Semi-honest Quantum Oblivious Transfer by André Chailloux, Gus Gutoski and Jamie Sikora

12. Parity Decision Tree Complexity and 4-Party Communication Complexity of XOR-functions Are Polynomially Equivalent by Penghui Yao

11. Parallel Repetition and Concentration for (sub-)No-Signalling Games via a Flexible Constrained de Finetti Reduction by Cécilia Lancien and Andreas Winter

10. Circuit Complexity of Powering in Fields of Odd Characteristic by Arkadev Chattopadhyay, Frederic Green, and Howard Straubing

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

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

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

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 QMA with Multiple Provers by Alessandro Chiesa and Michael A. Forbes

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.

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

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.

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.

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.

2007 Articles

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

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.

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.

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

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

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.

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.

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 m Representation of Boolean Functions by Vince Grolmusz, 21 July 1995

1. Symmetric Logspace is Closed Under Complement by Noam Nisan and Amnon Ta-Shma, 30 June 1995

CJTCS has a policy of free access to all articles.

Journal Organization

ISSN: 1073-0486

Publisher: Department of Computer Science, The University of Chicago
Editor-in-Chief: Janos Simon

Associate Editor-in-Chief:

Tom Gur

A distinguished board of editors

Journal Resources

Articles published in the journal

returns you to this front page