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