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