PC Chair: Valentine Kabanets
Local Chair: Benjamin Rossman
Best student paper award winner: A Lower Bound for Polynomial Calculus with Extension Rule by Yaroslav Alekseev
Due to Covid-19 related public health measures, the conference was held in a virtual online format instead of the originally planned physical event at Toronto, ON, Canada. The day of tutorials planned for July 19 was cancelled.
Videos of the conference talks: CCC YouTube channel
Call for Papers | Program | Local Arrangements | Proceedings: LIPIcs
PC Chair: Shubhangi Saraf
Local Chair: Markus Blaeser
Best student paper award winner: Connecting Perebor Conjectures: Towards a Search to Decision Reduction for Minimizing Formulas by Rahul Ilango
Best paper award winner: On the Complexity of Branching Proofs by Daniel Dadush and Samarth Tiwari
Due to Covid-19 related public health measures, the conference was held in a virtual online format instead of the originally planned physical event at Saarbruecken, Germany. The day of tutorials planned for July 27 was cancelled.
Videos of the conference talks: CCC YouTube channel
Call for Papers | Program | Local Arrangements | Proceedings: LIPIcs
PC Chair: Amir Shpilka
Local Chair: Eric Allender
Best student paper award winner: Limits on the Universal Method for Matrix Multiplication by Josh Alman
Pre-conference events:
Call for Papers | Program | Local Arrangements | Proceedings: LIPIcs | Special Issue: ToC 16
PC Chair: Rocco Servedio
Local Chair: Shachar Lovett
Best student paper award winner: The Complexity of the Cayley Semigroup Membership Problem by Lukas Fleischer
Call for Papers | Program | Local Arrangements | Proceedings: LIPIcs | Special Issue: ToC 15
PC Chair: Ryan O'Donnell
Local Chair: Andris Ambainis
Best student paper award winner: A quadratic lower bound for homogeneous algebraic branching programs by Mrinal Kumar
Best paper award winner: Settling the query complexity of non-adaptive junta testing by Xi Chen, Rocco Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie
Tutorial: Operator scaling - theory, applications and connections by Avi Wigderson
Call for Papers | Program | Local Arrangements | Proceedings: LIPIcs | Special Issue: ToC 14-15
PC Chair: Ran Raz
Local Chair: Osamu Watanabe
Best paper award winner: Learning algorithms from natural proofs by Marco Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova
Pre-conference event: 30th Anniversary Celebration (slide show)
Call for Papers | Program | Local Arrangements | Proceedings: LIPIcs | Special Issue: ToC 13
PC Chair: David Zuckerman
FCRC Liaison: Dieter van Melkebeek
Best student paper award winner: Factors of polynomials of low individual degree by Rafael Oliveira
Best paper award winner: Correlation bounds against monotone NC1 by Benjamin Rossman
Call for Papers | Program | Local Arrangements | Proceedings: LIPIcs | Special Issue: CC 25(2)
PC Chair: Michael Saks
Local Chair: Valentine Kabanets
Best student paper award winner: Quantum algorithms for learning symmetric juntas via the adversary bound by Alexander Belovs
Call for Papers | Program | Local Arrangements | Proceedings: CSDL/IEEExplore | Special Issue: CC 24(2)
PC Chair: Chris Umans
Local Chair: Luca Trevisan
Best student paper award winner: On the Power of Non-Adaptive Learning Graphs by Aleksandrs Belovs and Ansis Rosmanis
Best paper award winner: The Correct Exponent for the Gotsman-Linial Conjecture by Daniel Kane
Best paper award winner: Approaching the Chasm at Depth Four by Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi
Collocation: STOC June 1-4
Call for Papers | Program | Local Arrangements | Proceedings: CSDL/IEEExplore | Special Issue: CC 23(2)
PC Chair: Venkatesan Guruswami
Local Chair: Luis Antunes
Best student paper award winner: Limitations of Lower-Bound Methods for the Wire Complexity of Boolean Operators by Andrew Drucker
Call for Papers | Program | Local Arrangements | Proceedings: CSDL/IEEExplore | Special Issue: CC 22(2)
PC Chair: Omer Reingold
FCRC Liaison: Peter Bro Miltersen
Best student paper award winner: Improved Direct Product Theorems for Randomized Query Complexity by Andrew Drucker
Best paper award winner: Non-Uniform ACC Circuit Lower Bounds by Ryan Williams
Call for Papers | Program | Local Arrangements | Proceedings: CSDL/IEEExplore | Special Issue: CC 21(2)
PC Chair: Dieter van Melkebeek
Local Chair: Salil Vadhan
Best student paper award winner: The Gaussian surface area and noise sensitivity of degree-d polynomial threshold functions by Daniel Kane
Collocation: STOC June 5-8
Call for Papers | Program | Local Arrangements | Proceedings: CSDL/IEEExplore | Special Issue: CC 20(2)
PC Chair: Johan Håstad
Local Chair: Sophie Laplante
Best student paper award winner: Lipschitz Continuous Ordinary Differential Equations Are Polynomial-Space Complete by Akitoshi Kawamura
Best paper award winner: Poly-logarithmic Independence Fools AC^0 Circuits by Mark Braverman
Call for Papers | Program | Local Arrangements | Proceedings: CSDL/IEEExplore | Special Issue: CC 19(2)
PC Chair: Paul Beame
Local Chair: William Gasarch
Best student paper award winner: Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions by Alexander Sherstov
Best paper award winner: Lower Bounds and Separations for Constant Depth Multilinear Circuits by Ran Raz and Amir Yehudayoff
Best paper award winner: The Sum of d Small-Bias Generators Fools Polynomials of Degree d by Emanuele Viola
Call for Papers | Program | Local Arrangements | Proceedings: CSDL/IEEExplore | Special Issue: CC 18(2)
PC Chair: Peter Bro Miltersen
FCRC Liaison: Pierre McKenzie
Best student paper award winner: Halfspace Matrices by Alexander Sherstov
Best student paper award winner: Time-Space Tradeoffs for Counting NP Solutions Modulu Integers by Ryan Williams
Best paper award winner: Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes by Venkatesan Guruswami, Christopher Umans, and Salil Vadhan
Call for Papers | Program | Local Arrangements | Proceedings: CSDL/IEEExplore | Special Issue: CC 17(2)
PC Chair: Manindra Agrawal
Local Chair: Pavel Pudlák
Best student paper award winner: Polynomial Identity Testing for Depth 3 Circuits by Neeraj Kayal and Nitin Saxena
Best paper award winner: Polynomial Identity Testing for Depth 3 Circuits by Neeraj Kayal and Nitin Saxena
Call for Papers | Program | Local Arrangements | Proceedings: CSDL/IEEExplore | Special Issue: CC 16(2)
PC Chair: Luca Trevisan
Local Chair: D. Sivakumar and Ravi Kumar
Best student paper award winner: Better Time-Space Lower Bounds for SAT and Related Problems by Ryan Williams
Best paper award winner: Pseudorandomness for Approximate Counting and Sampling by Ronen Shaltiel and Chris Umans
Call for Papers | Proceedings: CSDL/IEEExplore | Special Issue: CC 15(2 and 4)
PC Chair: Russell Impagliazzo
Local Chair: David Mix Barrington and Neil Immerman
Best student paper award winner: Limitations of Quantum Advice and One-Way Communication by Scott Aaronson
Best paper award winner: Deterministic Polynomial Identity Testing in Non-commutative Models by Ran Raz and Amir Shpilka
Call for Papers | Program | Local Arrangements | Proceedings: CSDL/IEEExplore | Special Issue: CC 14(1, 2, and 3)
PC Chair: Harry Buhrman
Local Chair: Peter Bro Miltersen
Best student paper award winner: Quantum Certificate Complexity by Scott Aaronson
Best paper award winner: Extremal Properties of Polynomial Threshold Functions by Ryan O'Donnell and Rocco Servedio
Kolmogorov Day (Sunday, July 6th, 2003)
Call for Papers | Program | Local Arrangements | Proceedings: CSDL/IEEExplore | Special Issue: JCSS 74(3)
PC Chair: Anne Condon
Local Chair: Pierre McKenzie
Best student paper award winner: Hardness Amplification within NP by Ryan O'Donnell
Best paper award winner: Resolution Lower Bounds for Perfect Matching Principles by Ran Raz
Best paper award winner: Resolution Lower Bounds for the Weak Pigeon Hole Princple by Alexander Razborov
Collocation: STOC May 19-21
Call for Papers | Program | Local Arrangements | Proceedings: CSDL/IEEExplore | Special Issue: JCSS 69(1)
PC Chair: Madhu Sudan
Local Chair: John Rogers
Best student paper award winner: A Linear Lower Bound on the Unbounded Error Probabilistic Communication Complexity by Juergen Forster
Best paper award winner: In Search of an Easy Witness: Exponential Time vs. Probabilistic Polynomial Time by Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson
Call for Papers | Program | Proceedings: CSDL/IEEExplore | Special Issue: JCSS 65(4)
PC Chair: Pavel Pudlák
Local Chair: Pierluigi Crescenzi
Best student paper award winner: Easiness Assumptions and Hardness Tests: Trading Time for Zero Error by Valentine Kabanets
Call for Papers | Program | Proceedings: CSDL/IEEExplore | Special Issue: JCSS 63(2)
PC Chair: Lance Fortnow
FCRC Liaison: Eric Allender
Best student paper award winner: Graph Ramsey Theory and the Polynomial Hierarchy by Marcus Schaefer
Call for Papers | Program | Proceedings: CSDL/IEEExplore | Special Issue: JCSS 62(2)
PC Chair: Joan Feigenbaum
Local Chair: Ken Regan
Best student paper award winner: Relationships Between Quantum and Classical Space-Bounded Complexity Classes by John Watrous
Call for Papers | Program | Local Arrangements | Proceedings: CSDL/IEEExplore | Special Issue: JCSS 59(2)
PC Chair: José Balcázar
Local Chair: Uwe Schöning and Jacobo Torán
Best student paper award winner: LR(k) Testing is Average-Case Complete by Cristoph Karg
Call for Papers | Program | Proceedings: CSDL/IEEExplore | Special Issue: JCSS 60(2)
PC Chair: Jin-Yi Cai
FCRC Liaison: Steven Homer
Best student paper award winner: Reducing P to a Sparse Set Using a Constant Number of Queries Collapses P to L by Dieter van Melkebeek
Proceedings: CSDL/IEEExplore | Special Issue: JCSS 57(2)
PC Chair: Eric Allender
Local Chair: Ding-Zhu Du
Proceedings: CSDL/IEEExplore | Special Issue: JCSS 54(3)
PC Chair: Uwe Schöning
Local Chair: Peter van Emde Boas and Paul Vitanyi
Proceedings: IEEExplore | Special Issue: JCSS 53(2)
PC Chair: Steven Homer
FCRC Liaison: Timothy Long
Proceedings: IEEExplore | Special Issue: JCSS 53(2)
PC Chair: Timothy Long
Local Chair: Steven Homer and Luc Longpré
Proceedings: IEEExplore | Special Issue: JCSS 50(3)
PC Chair: Neil Immerman
Local Chair: Stuart Kurtz
Proceedings: IEEExplore | Special Issue: JCSS 50(3)
PC Chair: Alan Selman
Local Chair: Jose Balcázar and Jacobo Toran
Proceedings: IEEExplore | Special Issue: TCS 107(1)
PC Chair: Paul Young
Local Chair: Eugene Luks and Chris Wilson
Proceedings: IEEExplore | Special Issue: JCSS 44(2)
PC Chair: Juris Hartmanis
Local Chair: John Cherniavsky
Proceedings: IEEExplore | Special Issue: JCSS 41(3)
PC Chair: Stephen Mahaney
Local Chair: Dexter Kozen
Bibliography | Special Issue: JCSS 39(1 and 3)
PC Chair: Alan Selman and Stephen Mahaney
Local Chair: Gene Lawler
Collocation: STOC May 28-30
Proceedings: Springer LNCS | Special Issue: JCSS 36(3)
CCCstands for
Annual IEEE Conference on Computational Complexityrather than
Computational Complexity Conference.