Computational Complexity Conference

Publications

2021

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

volume 200, 2021

36th Computational Complexity Conference, CCC 2021, July 20-23, 2021, Toronto, Ontario, Canada (Virtual Conference). Computational Complexity Conference 200 (2021)

2020

volume 169, 2020

35th Computational Complexity Conference, CCC 2020, July 28-31, 2020, Saarbrücken, Germany (Virtual Conference). Computational Complexity Conference 169 (2020)