Computational Complexity Conference

CCC'20 - Accepted Papers

  • Near-Optimal Erasure List-Decodable Codes
    Avraham Ben-Aroya, Dean Doron, and Amnon Ta-Shma
  • A Quadratic Lower Bound for Algebraic Branching Programs
    Prerona Chatterjee, Mrinal Kumar, Adrian She, and Ben Lee Volk
  • Super Strong ETH is true for strong PPSZ with Small Resolution Width
    Dominik Scheder, and Navid Talebanfard
  • Approximability of the eight-vertex model
    Jin-Yi Cai, Tianyu Liu, Pinyan Lu, and Jing Yu
  • Lower Bounds for Matrix Factorization
    Mrinal Kumar and Ben Lee Volk
  • Log-Seed Pseudorandom Generators via Iterated Restrictions
    Dean Doron, Pooya Hatami, and William Hoza
  • Quantum Lower Bounds for Approximate Counting via Laurent Polynomials
    Scott Aaronson, Robin Kothari, William Kretschmer, and Justin Thaler
  • A generalized Sylvester-Gallai type theorem for quadratic polynomials
    Shir Peleg and Amir Shpilka
  • Simultaneous Max-Cut is harder to approximate than Max-Cut
    Amey Bhangale and Subhash Khot
  • Hitting Sets Give Two-Sided Derandomization of Small Space
    Kuan Cheng and William Hoza
  • Palette-Alternating Tree Codes
    Gil Cohen and Shahar Samocha
  • Search Problems in Algebraic Complexity, GCT, and Hardness of Generators for Invariant Rings
    Ankit Garg, Christian Ikenmeyer, Visu Makam, Rafael Oliveira, Michael Walter, and Avi Wigderson
  • Statistical physics approaches to Unique Games
    Matthew Coulson, Ewan Davies, Alexandra Kolla, Viresh Patel, and Guus Regts
  • Schur Polynomials do not have small formulas if the Determinant doesn't!
    Chandra Kanta Mohapatra, Mrinal Kumar, Nutan Limaye, Srikanth Srinivasan, Prasad Chaugule, and Adrian She
  • Algorithms and lower bounds for de Morgan formulas of low-communication leaf gates
    Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, and Igor C. Oliveira
  • On the Quantum Complexity of Closest Pair, and Related Problems
    Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin, Chunhao Wang, and Ruizhe Zhang
  • Limits of Preprocessing
    Yuval Filmus, Yuval Ishai, Avi Kaplan, and Guy Kindler
  • Sign rank vs Discrepancy
    Kaave Hosseini, Hamed Hatami, and Shachar Lovett
  • On the Complexity of Modulo-q Arguments and the Chevalley-Warning Theorem
    Mika Göös, Pritish Kamath, Katerina Sotiraki, and Manolis Zampetakis
  • Non-Disjoint Promise Problems from Meta-Computational View of Pseudorandom Generator Constructions
    Shuichi Hirahara
  • Algebraic Branching Programs, Border Complexity, and Tangent Spaces
    Markus Blaeser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, and Nitin Saurabh
  • NP-Hardness of Circuit Minimization for Multi-Output Functions
    Rahul Ilango, Bruno Loff, and Igor Oliveira
  • A Super-Quadratic Lower Bound for Depth Four Arithmetic Circuits
    Nikhil Gupta, Chandan Saha, and Bhargav Thankey
  • Multiparty Karchmer-Wigderson Games and Threshold Circuits
    Alexander Kozachinskiy and Vladimir Podolskii
  • Optimal Error Pseudodistributions for Read-Once Branching Programs
    Eshan Chattopadhyay and Jyun-Jie Liao
  • Circuit Lower Bounds from NP-Hardness of MCSP under Turing Reductions
    Michael Saks and Rahul Santhanam
  • Finding Small Satisfying Assignments Faster Than Bruteforce: A Fine-grained Perspective into Boolean Constraint Satisfaction
    Marvin Künnemann and Dániel Marx
  • Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs
    Susanna F. de Rezende, Jakob Nordstrom, Kilian Risse, and Dmitry Sokolov
  • Groups with ALOGTIME-hard word problems and PSPACE-complete circuit value problems
    Laurent Bartholdi, Michael Figelius, Markus Lohrey, and Armin Weiß
  • Optimal Lower Bounds for Matching and Vertex Cover in Dynamic Graph Streams
    Jacques Dark and Christian Konrad
  • Connecting Perebor Conjectures: Towards a Search to Decision Reduction for Minimizing Formulas
    Rahul Ilango
  • Quantum Query-to-Communication Simulation Needs a Logarithmic Overhead
    Sourav Chakraborty, Arkadev Chattopadhyay, Nikhil Mande and Manaswi Paraashar
  • Factorization of Polynomials Given by Arithmetic Branching Programs
    Amit Sinhababu and Thomas Thierauf
  • On the Complexity of Branching Proofs
    Daniel Dadush and Samarth Tiwari
  • Geometric Rank of Tensors and Subrank of Matrix Multiplication
    Swastik Kopparty, Guy Moshkovitz, and Jeroen Zuiddam
  • Hardness of Bounded Distance Decoding on Lattices in $\ell_p$ Norms
    Huck Bennett and Chris Peikert
  • Algebraic Hardness versus Randomness in Low Characteristic
    Robert Andrews
  • Sum of squares bounds for the ordering principle
    Aaron Potechin

Organized by:

In Cooperation with: