CCC'21 - Accepted Papers
-
Rate Amplification and Query-Efficient Distance Amplification for linear LCC and LDC
Gil Cohen and Tal Yankovitz
-
An Improved Protocol for the Exactly-N Problem
Adi Shraibman and Nati Linial
-
Proof complexity of natural formulas via communication arguments
Artur Riazanov and Dmitry Itsykson
-
A Lower Bound on Determinantal Complexity
Mrinal Kumar and Ben Lee Volk
-
Optimal tiling of the Euclidean space using permutation-symmetric bodies
Mark Braverman and Dor Minzer
-
On the Power and Limitations of Branch and Cut
Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, and Avi Wigderson
-
Separating ABPs and Some Structured Formulas in the Non-Commutative Setting
Prerona Chatterjee
-
The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications
Alexander Golovnev and Ishay Haviv
-
Shadows of Newton polytopes
Amir Yehudayoff and Pavel Hrubes
-
Fractional Pseudorandom Generators from Any Fourier Level
Eshan Chattopadhyay, Jason Gaitonde, Chin Ho Lee, Shachar Lovett, and Abhishek Shetty
-
Deterministic identity testing paradigms for bounded top-fanin depth-4 circuits
Pranjal Dutta, Prateek Dwivedi, and Nitin Saxena
-
Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing
Oded Goldreich and Avi Wigderson
-
Barriers for recent methods in geodesic optimization
Cole Franks and Philipp Reichenbach
-
Communication Complexity with Defective Randomness
Marshall Ball, Tal Malkin, and Oded Goldreich
-
On the cut dimension of a graph
Troy Lee, Tongyang Li, Miklos Santha, and Shengyu Zhang
-
On p-Group Isomorphism: search-to-decision, counting-to-decision, and nilpotency class reductions via tensors
Joshua Grochow and Youming Qiao
-
Branching Programs with Bounded Repetitions and Flow Formulas
Anastasia Sofronova and Dmitry Sokolov
-
A Majority Lemma for Randomised Query Complexity
Mika Göös and Gilbert Maystre
-
Hitting Sets and Reconstruction for Dense Orbits in VP and ΣΠΣ circuits
Dori Medini and Amir Shpilka
-
Variety Evasive Subspace Families
Zeyu Guo
-
A Lower Bound for Polynomial Calculus with Extension Rule
Yarolsav Alekseev
-
Error Reduction For Weighted PRGs Against Read Once Branching Programs
Gil Cohen, Dean Doron, Oren Renard, Ori Sberlo, and Amnon Ta-Shma
-
A Stress-Free Sum-of-Squares Lower Bound for Coloring
Peter Manohar and Pravesh Kothari
-
Junta Distance Approximation with Sub-Exponential Queries
Vishnu Iyer, Avishay Tal, and Michael Whitmeyer
-
Arithmetic Circuit Complexity of Division and Truncation
Pranjal Dutta, Gorav Jindal, Anurag Pandey, and Amit Sinhababu
-
SOS lower bound for exact planted clique
Shuo Pang
-
A Direct Product Theorem for One-Way Quantum Communication
Rahul Jain and Srijita Kundu
-
Quantum complexity of minimum cut
Simon Apers and Troy Lee
-
On the complexity of evaluating highest weight vectors
Markus Bläser, Julian Dörfler, and Christian Ikenmeyer
-
On Query-to-Communication Lifting for Adversary Bounds
Anurag Anshu, Shalev Ben-David, and Srijita Kundu
-
Hardness of Constant-round Communication Complexity
Rahul Ilango, Shuichi Hirahara, and Bruno Loff
-
Polynomial time algorithms in invariant theory for torus actions
Peter Bürgisser, M. Levent Doğan, Visu Makam, Michael Walter, and Avi Wigderson
-
Pseudodistributions That Beat All Pseudorandom Generators
Edward Pyne and Salil Vadhan
-
GSF-locality is not sufficient for proximity-oblivious testing
Isolde Adler, Noleen Köhler, and Pan Peng
-
Hardness of KT Characterizes Parallel Cryptography
Hanlin Ren and Rahul Santhanam
-
On the Pseudo-deterministic Query Complexity of NP Search Problems
Shafi Goldwasser, Russell Impagliazzo, Toniann Pitassi, and Rahul Santhanam
-
A Simple Proof of a New Set Disjointness with Applications to Data Streams
Akshay Kamath, Eric Price, and David P. Woodruff
-
Toward better depth lower bounds: the XOR-KRW conjecture
Ivan Mikhailin and Alexander Smal
-
Fourier Growth of Parity Decision Trees
Uma Girish, Avishay Tal, and Kewen Wu
-
The Power of Negative Reasoning
Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, and Dmitry Sokolov
-
Matrix rigidity depends on the target field
Laszlo Babai and Bohdan Kivva