| 2020 | 35th Computational Complexity Conference, CCC 2020, Saarbrücken, Germany (Virtual Conference), July 28-31, 2020 Shubhangi Saraf |
| 2020 | A Generalized Sylvester-Gallai Type Theorem for Quadratic Polynomials. Shir Peleg, Amir Shpilka |
| 2020 | A Quadratic Lower Bound for Algebraic Branching Programs. Prerona Chatterjee, Mrinal Kumar, Adrian She, Ben Lee Volk |
| 2020 | A Super-Quadratic Lower Bound for Depth Four Arithmetic Circuits. Nikhil Gupta, Chandan Saha, Bhargav Thankey |
| 2020 | Algebraic Branching Programs, Border Complexity, and Tangent Spaces. Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, Nitin Saurabh |
| 2020 | Algebraic Hardness Versus Randomness in Low Characteristic. Robert Andrews |
| 2020 | Algorithms and Lower Bounds for De Morgan Formulas of Low-Communication Leaf Gates. Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor C. Oliveira |
| 2020 | Approximability of the Eight-Vertex Model. Jin-Yi Cai, Tianyu Liu, Pinyan Lu, Jing Yu |
| 2020 | Circuit Lower Bounds from NP-Hardness of MCSP Under Turing Reductions. Michael E. Saks, Rahul Santhanam |
| 2020 | Connecting Perebor Conjectures: Towards a Search to Decision Reduction for Minimizing Formulas. Rahul Ilango |
| 2020 | Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs. Susanna F. de Rezende, Jakob Nordström, Kilian Risse, Dmitry Sokolov |
| 2020 | Factorization of Polynomials Given By Arithmetic Branching Programs. Amit Sinhababu, Thomas Thierauf |
| 2020 | Finding Small Satisfying Assignments Faster Than Brute Force: A Fine-Grained Perspective into Boolean Constraint Satisfaction. Marvin Künnemann, Dániel Marx |
| 2020 | Front Matter, Table of Contents, Preface, Conference Organization. |
| 2020 | Geometric Rank of Tensors and Subrank of Matrix Multiplication. Swastik Kopparty, Guy Moshkovitz, Jeroen Zuiddam |
| 2020 | Groups with ALOGTIME-Hard Word Problems and PSPACE-Complete Circuit Value Problems. Laurent Bartholdi, Michael Figelius, Markus Lohrey, Armin Weiß |
| 2020 | Hardness of Bounded Distance Decoding on Lattices in ℓ Huck Bennett, Chris Peikert |
| 2020 | Hitting Sets Give Two-Sided Derandomization of Small Space. Kuan Cheng, William M. Hoza |
| 2020 | Limits of Preprocessing. Yuval Filmus, Yuval Ishai, Avi Kaplan, Guy Kindler |
| 2020 | Log-Seed Pseudorandom Generators via Iterated Restrictions. Dean Doron, Pooya Hatami, William M. Hoza |
| 2020 | Lower Bounds for Matrix Factorization. Mrinal Kumar, Ben Lee Volk |
| 2020 | Multiparty Karchmer - Wigderson Games and Threshold Circuits. Alexander Kozachinskiy, Vladimir V. Podolskii |
| 2020 | NP-Hardness of Circuit Minimization for Multi-Output Functions. Rahul Ilango, Bruno Loff, Igor C. Oliveira |
| 2020 | Near-Optimal Erasure List-Decodable Codes. Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma |
| 2020 | Non-Disjoint Promise Problems from Meta-Computational View of Pseudorandom Generator Constructions. Shuichi Hirahara |
| 2020 | On the Complexity of Branching Proofs. Daniel Dadush, Samarth Tiwari |
| 2020 | On the Complexity of Modulo-q Arguments and the Chevalley - Warning Theorem. Mika Göös, Pritish Kamath, Katerina Sotiraki, Manolis Zampetakis |
| 2020 | On the Quantum Complexity of Closest Pair and Related Problems. Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin, Chunhao Wang, Ruizhe Zhang |
| 2020 | Optimal Error Pseudodistributions for Read-Once Branching Programs. Eshan Chattopadhyay, Jyun-Jie Liao |
| 2020 | Optimal Lower Bounds for Matching and Vertex Cover in Dynamic Graph Streams. Jacques Dark, Christian Konrad |
| 2020 | Palette-Alternating Tree Codes. Gil Cohen, Shahar Samocha |
| 2020 | Quantum Lower Bounds for Approximate Counting via Laurent Polynomials. Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler |
| 2020 | Quantum Query-To-Communication Simulation Needs a Logarithmic Overhead. Sourav Chakraborty, Arkadev Chattopadhyay, Nikhil S. Mande, Manaswi Paraashar |
| 2020 | Schur Polynomials Do Not Have Small Formulas If the Determinant Doesn't. Prasad Chaugule, Mrinal Kumar, Nutan Limaye, Chandra Kanta Mohapatra, Adrian She, Srikanth Srinivasan |
| 2020 | Search Problems in Algebraic Complexity, GCT, and Hardness of Generators for Invariant Rings. Ankit Garg, Christian Ikenmeyer, Visu Makam, Rafael Mendes de Oliveira, Michael Walter, Avi Wigderson |
| 2020 | Sign Rank vs Discrepancy. Hamed Hatami, Kaave Hosseini, Shachar Lovett |
| 2020 | Simultaneous Max-Cut Is Harder to Approximate Than Max-Cut. Amey Bhangale, Subhash Khot |
| 2020 | Statistical Physics Approaches to Unique Games. Matthew Coulson, Ewan Davies, Alexandra Kolla, Viresh Patel, Guus Regts |
| 2020 | Sum of Squares Bounds for the Ordering Principle. Aaron Potechin |
| 2020 | Super Strong ETH Is True for PPSZ with Small Resolution Width. Dominik Scheder, Navid Talebanfard |