| 2021 | 36th Computational Complexity Conference, CCC 2021, Toronto, Ontario, Canada (Virtual Conference), July 20-23, 2021 Valentine Kabanets |
| 2021 | A Direct Product Theorem for One-Way Quantum Communication. Rahul Jain, Srijita Kundu |
| 2021 | A Lower Bound for Polynomial Calculus with Extension Rule. Yaroslav Alekseev |
| 2021 | A Lower Bound on Determinantal Complexity. Mrinal Kumar, Ben Lee Volk |
| 2021 | A Majority Lemma for Randomised Query Complexity. Mika Göös, Gilbert Maystre |
| 2021 | A Simple Proof of a New Set Disjointness with Applications to Data Streams. Akshay Kamath, Eric Price, David P. Woodruff |
| 2021 | A Stress-Free Sum-Of-Squares Lower Bound for Coloring. Pravesh K. Kothari, Peter Manohar |
| 2021 | An Improved Protocol for the Exactly-N Problem. Nati Linial, Adi Shraibman |
| 2021 | Arithmetic Circuit Complexity of Division and Truncation. Pranjal Dutta, Gorav Jindal, Anurag Pandey, Amit Sinhababu |
| 2021 | Barriers for Recent Methods in Geodesic Optimization. William Cole Franks, Philipp Reichenbach |
| 2021 | Branching Programs with Bounded Repetitions and Flow Formulas. Anastasia Sofronova, Dmitry Sokolov |
| 2021 | Communication Complexity with Defective Randomness. Marshall Ball, Oded Goldreich, Tal Malkin |
| 2021 | Deterministic Identity Testing Paradigms for Bounded Top-Fanin Depth-4 Circuits. Pranjal Dutta, Prateek Dwivedi, Nitin Saxena |
| 2021 | Error Reduction for Weighted PRGs Against Read Once Branching Programs. Gil Cohen, Dean Doron, Oren Renard, Ori Sberlo, Amnon Ta-Shma |
| 2021 | Fourier Growth of Parity Decision Trees. Uma Girish, Avishay Tal, Kewen Wu |
| 2021 | Fractional Pseudorandom Generators from Any Fourier Level. Eshan Chattopadhyay, Jason Gaitonde, Chin Ho Lee, Shachar Lovett, Abhishek Shetty |
| 2021 | Front Matter, Table of Contents, Preface, Conference Organization. |
| 2021 | GSF-Locality Is Not Sufficient For Proximity-Oblivious Testing. Isolde Adler, Noleen Köhler, Pan Peng |
| 2021 | Hardness of Constant-Round Communication Complexity. Shuichi Hirahara, Rahul Ilango, Bruno Loff |
| 2021 | Hardness of KT Characterizes Parallel Cryptography. Hanlin Ren, Rahul Santhanam |
| 2021 | Hitting Sets and Reconstruction for Dense Orbits in VP_{e} and ΣΠΣ Circuits. Dori Medini, Amir Shpilka |
| 2021 | Junta Distance Approximation with Sub-Exponential Queries. Vishnu Iyer, Avishay Tal, Michael Whitmeyer |
| 2021 | Matrix Rigidity Depends on the Target Field. László Babai, Bohdan Kivva |
| 2021 | On Query-To-Communication Lifting for Adversary Bounds. Anurag Anshu, Shalev Ben-David, Srijita Kundu |
| 2021 | On p-Group Isomorphism: Search-To-Decision, Counting-To-Decision, and Nilpotency Class Reductions via Tensors. Joshua A. Grochow, Youming Qiao |
| 2021 | On the Complexity of Evaluating Highest Weight Vectors. Markus Bläser, Julian Dörfler, Christian Ikenmeyer |
| 2021 | On the Cut Dimension of a Graph. Troy Lee, Tongyang Li, Miklos Santha, Shengyu Zhang |
| 2021 | On the Power and Limitations of Branch and Cut. Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson |
| 2021 | On the Pseudo-Deterministic Query Complexity of NP Search Problems. Shafi Goldwasser, Russell Impagliazzo, Toniann Pitassi, Rahul Santhanam |
| 2021 | Optimal Tiling of the Euclidean Space Using Permutation-Symmetric Bodies. Mark Braverman, Dor Minzer |
| 2021 | Polynomial Time Algorithms in Invariant Theory for Torus Actions. Peter Bürgisser, M. Levent Dogan, Visu Makam, Michael Walter, Avi Wigderson |
| 2021 | Proof Complexity of Natural Formulas via Communication Arguments. Dmitry Itsykson, Artur Riazanov |
| 2021 | Pseudodistributions That Beat All Pseudorandom Generators (Extended Abstract). Edward Pyne, Salil P. Vadhan |
| 2021 | Quantum Complexity of Minimum Cut. Simon Apers, Troy Lee |
| 2021 | Rate Amplification and Query-Efficient Distance Amplification for Linear LCC and LDC. Gil Cohen, Tal Yankovitz |
| 2021 | Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing. Oded Goldreich, Avi Wigderson |
| 2021 | SOS Lower Bound for Exact Planted Clique. Shuo Pang |
| 2021 | Separating ABPs and Some Structured Formulas in the Non-Commutative Setting. Prerona Chatterjee |
| 2021 | Shadows of Newton Polytopes. Pavel Hrubes, Amir Yehudayoff |
| 2021 | The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications. Alexander Golovnev, Ishay Haviv |
| 2021 | The Power of Negative Reasoning. Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, Dmitry Sokolov |
| 2021 | Toward Better Depth Lower Bounds: The XOR-KRW Conjecture. Ivan Mihajlin, Alexander Smal |
| 2021 | Variety Evasive Subspace Families. Zeyu Guo |