Computational Complexity Conference

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

Organized by:

In Cooperation with: