CCC 2021 Accepted Papers

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