CCC 2020 July 28-31, 2020, Saarbrücken, Germany (Virtual Conference)

35th Computational Complexity Conference (CCC 2020)



Shubhangi Saraf (Ed.)
ISBN 978-3-95977-156-6, LIPICS Vol. 169 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 24 MB)
Search Publication Server

Authors
  • Aaronson, Scott
  • Andrews, Robert
  • Bartholdi, Laurent
  • Ben-Aroya, Avraham
  • Bennett, Huck
  • Bhangale, Amey
  • Bläser, Markus
  • Cai, Jin-Yi
  • Chakraborty, Sourav
  • Chatterjee, Prerona
  • Chattopadhyay, Arkadev
  • Chattopadhyay, Eshan
  • Chaugule, Prasad
  • Cheng, Kuan
  • Chia, Nai-Hui
  • Cohen, Gil
  • Coulson, Matthew
  • Dadush, Daniel
  • Dark, Jacques
  • Davies, Ewan
  • de Rezende, Susanna F.
  • Doron, Dean
  • Figelius, Michael
  • Filmus, Yuval
  • Garg, Ankit
  • Gupta, Nikhil
  • Göös, Mika
  • Hatami, Hamed
  • Hatami, Pooya
  • Hirahara, Shuichi
  • Hosseini, Kaave
  • Hoza, William M.
  • Ikenmeyer, Christian
  • Ilango, Rahul
  • Ishai, Yuval
  • Kabanets, Valentine
  • Kamath, Pritish
  • Kaplan, Avi
  • Khot, Subhash
  • Kindler, Guy
  • Kolla, Alexandra
  • Konrad, Christian
  • Kopparty, Swastik
  • Koroth, Sajin
  • Kothari, Robin
  • Kozachinskiy, Alexander
  • Kretschmer, William
  • Kumar, Mrinal
  • Künnemann, Marvin
  • Liao, Jyun-Jie
  • Limaye, Nutan
  • Lin, Han-Hsuan
  • Liu, Tianyu
  • Loff, Bruno
  • Lohrey, Markus
  • Lovett, Shachar
  • Lu, Pinyan
  • Lu, Zhenjian
  • Mahajan, Meena
  • Makam, Visu
  • Mande, Nikhil S.
  • Marx, Dániel
  • Mohapatra, Chandra Kanta
  • Moshkovitz, Guy
  • Myrisiotis, Dimitrios
  • Nordström, Jakob
  • Oliveira, Igor C.
  • Oliveira, Rafael
  • Pandey, Anurag
  • Paraashar, Manaswi
  • Patel, Viresh
  • Peikert, Chris
  • Peleg, Shir
  • Podolskii, Vladimir
  • Potechin, Aaron
  • Regts, Guus
  • Risse, Kilian
  • Saha, Chandan
  • Saks, Michael
  • Samocha, Shahar
  • Santhanam, Rahul
  • Saraf, Shubhangi
  • Saurabh, Nitin
  • Scheder, Dominik
  • She, Adrian
  • Shpilka, Amir
  • Sinhababu, Amit
  • Sokolov, Dmitry
  • Sotiraki, Katerina
  • Srinivasan, Srikanth
  • Ta-Shma, Amnon
  • Talebanfard, Navid
  • Thaler, Justin
  • Thankey, Bhargav
  • Thierauf, Thomas
  • Tiwari, Samarth
  • Volk, Ben Lee
  • Walter, Michael
  • Wang, Chunhao
  • Weiß, Armin
  • Wigderson, Avi
  • Yu, Jing
  • Zampetakis, Manolis
  • Zhang, Ruizhe
  • Zuiddam, Jeroen
    		•

    		  
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Saraf, Shubhangi

    Abstract | Document (378 KB) | BibTeX

    Near-Optimal Erasure List-Decodable Codes
    Authors: Ben-Aroya, Avraham ; Doron, Dean ; Ta-Shma, Amnon

    Abstract | Document (637 KB) | BibTeX

    A Quadratic Lower Bound for Algebraic Branching Programs
    Authors: Chatterjee, Prerona ; Kumar, Mrinal ; She, Adrian ; Volk, Ben Lee

    Abstract | Document (562 KB) | BibTeX

    Super Strong ETH Is True for PPSZ with Small Resolution Width
    Authors: Scheder, Dominik ; Talebanfard, Navid

    Abstract | Document (619 KB) | BibTeX

    Approximability of the Eight-Vertex Model
    Authors: Cai, Jin-Yi ; Liu, Tianyu ; Lu, Pinyan ; Yu, Jing

    Abstract | Document (2,413 KB) | BibTeX

    Lower Bounds for Matrix Factorization
    Authors: Kumar, Mrinal ; Volk, Ben Lee

    Abstract | Document (588 KB) | BibTeX

    Log-Seed Pseudorandom Generators via Iterated Restrictions
    Authors: Doron, Dean ; Hatami, Pooya ; Hoza, William M.

    Abstract | Document (734 KB) | BibTeX

    Quantum Lower Bounds for Approximate Counting via Laurent Polynomials
    Authors: Aaronson, Scott ; Kothari, Robin ; Kretschmer, William ; Thaler, Justin

    Abstract | Document (749 KB) | BibTeX

    A Generalized Sylvester-Gallai Type Theorem for Quadratic Polynomials
    Authors: Peleg, Shir ; Shpilka, Amir

    Abstract | Document (685 KB) | BibTeX

    Simultaneous Max-Cut Is Harder to Approximate Than Max-Cut
    Authors: Bhangale, Amey ; Khot, Subhash

    Abstract | Document (745 KB) | BibTeX

    Hitting Sets Give Two-Sided Derandomization of Small Space
    Authors: Cheng, Kuan ; Hoza, William M.

    Abstract | Document (629 KB) | BibTeX

    Palette-Alternating Tree Codes
    Authors: Cohen, Gil ; Samocha, Shahar

    Abstract | Document (537 KB) | BibTeX

    Search Problems in Algebraic Complexity, GCT, and Hardness of Generators for Invariant Rings
    Authors: Garg, Ankit ; Ikenmeyer, Christian ; Makam, Visu ; Oliveira, Rafael ; Walter, Michael ; Wigderson, Avi

    Abstract | Document (581 KB) | BibTeX

    Statistical Physics Approaches to Unique Games
    Authors: Coulson, Matthew ; Davies, Ewan ; Kolla, Alexandra ; Patel, Viresh ; Regts, Guus

    Abstract | Document (628 KB) | BibTeX

    Schur Polynomials Do Not Have Small Formulas If the Determinant Doesn't
    Authors: Chaugule, Prasad ; Kumar, Mrinal ; Limaye, Nutan ; Mohapatra, Chandra Kanta ; She, Adrian ; Srinivasan, Srikanth

    Abstract | Document (635 KB) | BibTeX

    Algorithms and Lower Bounds for De Morgan Formulas of Low-Communication Leaf Gates
    Authors: Kabanets, Valentine ; Koroth, Sajin ; Lu, Zhenjian ; Myrisiotis, Dimitrios ; Oliveira, Igor C.

    Abstract | Document (765 KB) | BibTeX

    On the Quantum Complexity of Closest Pair and Related Problems
    Authors: Aaronson, Scott ; Chia, Nai-Hui ; Lin, Han-Hsuan ; Wang, Chunhao ; Zhang, Ruizhe

    Abstract | Document (854 KB) | BibTeX

    Limits of Preprocessing
    Authors: Filmus, Yuval ; Ishai, Yuval ; Kaplan, Avi ; Kindler, Guy

    Abstract | Document (590 KB) | BibTeX

    Sign Rank vs Discrepancy
    Authors: Hatami, Hamed ; Hosseini, Kaave ; Lovett, Shachar

    Abstract | Document (531 KB) | BibTeX

    On the Complexity of Modulo-q Arguments and the Chevalley - Warning Theorem
    Authors: Göös, Mika ; Kamath, Pritish ; Sotiraki, Katerina ; Zampetakis, Manolis

    Abstract | Document (895 KB) | BibTeX

    Non-Disjoint Promise Problems from Meta-Computational View of Pseudorandom Generator Constructions
    Authors: Hirahara, Shuichi

    Abstract | Document (962 KB) | BibTeX

    Algebraic Branching Programs, Border Complexity, and Tangent Spaces
    Authors: Bläser, Markus ; Ikenmeyer, Christian ; Mahajan, Meena ; Pandey, Anurag ; Saurabh, Nitin

    Abstract | Document (630 KB) | BibTeX

    NP-Hardness of Circuit Minimization for Multi-Output Functions
    Authors: Ilango, Rahul ; Loff, Bruno ; Oliveira, Igor C.

    Abstract | Document (713 KB) | BibTeX

    A Super-Quadratic Lower Bound for Depth Four Arithmetic Circuits
    Authors: Gupta, Nikhil ; Saha, Chandan ; Thankey, Bhargav

    Abstract | Document (877 KB) | BibTeX

    Multiparty Karchmer - Wigderson Games and Threshold Circuits
    Authors: Kozachinskiy, Alexander ; Podolskii, Vladimir

    Abstract | Document (553 KB) | BibTeX

    Optimal Error Pseudodistributions for Read-Once Branching Programs
    Authors: Chattopadhyay, Eshan ; Liao, Jyun-Jie

    Abstract | Document (613 KB) | BibTeX

    Circuit Lower Bounds from NP-Hardness of MCSP Under Turing Reductions
    Authors: Saks, Michael ; Santhanam, Rahul

    Abstract | Document (438 KB) | BibTeX

    Finding Small Satisfying Assignments Faster Than Brute Force: A Fine-Grained Perspective into Boolean Constraint Satisfaction
    Authors: Künnemann, Marvin ; Marx, Dániel

    Abstract | Document (778 KB) | BibTeX

    Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs
    Authors: de Rezende, Susanna F. ; Nordström, Jakob ; Risse, Kilian ; Sokolov, Dmitry

    Abstract | Document (622 KB) | BibTeX

    Groups with ALOGTIME-Hard Word Problems and PSPACE-Complete Circuit Value Problems
    Authors: Bartholdi, Laurent ; Figelius, Michael ; Lohrey, Markus ; Weiß, Armin

    Abstract | Document (684 KB) | BibTeX

    Optimal Lower Bounds for Matching and Vertex Cover in Dynamic Graph Streams
    Authors: Dark, Jacques ; Konrad, Christian

    Abstract | Document (580 KB) | BibTeX

    Connecting Perebor Conjectures: Towards a Search to Decision Reduction for Minimizing Formulas
    Authors: Ilango, Rahul

    Abstract | Document (672 KB) | BibTeX

    Quantum Query-To-Communication Simulation Needs a Logarithmic Overhead
    Authors: Chakraborty, Sourav ; Chattopadhyay, Arkadev ; Mande, Nikhil S. ; Paraashar, Manaswi

    Abstract | Document (534 KB) | BibTeX

    Factorization of Polynomials Given By Arithmetic Branching Programs
    Authors: Sinhababu, Amit ; Thierauf, Thomas

    Abstract | Document (505 KB) | BibTeX

    On the Complexity of Branching Proofs
    Authors: Dadush, Daniel ; Tiwari, Samarth

    Abstract | Document (725 KB) | BibTeX

    Geometric Rank of Tensors and Subrank of Matrix Multiplication
    Authors: Kopparty, Swastik ; Moshkovitz, Guy ; Zuiddam, Jeroen

    Abstract | Document (575 KB) | BibTeX

    Hardness of Bounded Distance Decoding on Lattices in 𝓁_p Norms
    Authors: Bennett, Huck ; Peikert, Chris

    Abstract | Document (631 KB) | BibTeX

    Algebraic Hardness Versus Randomness in Low Characteristic
    Authors: Andrews, Robert

    Abstract | Document (634 KB) | BibTeX

    Sum of Squares Bounds for the Ordering Principle
    Authors: Potechin, Aaron

    Abstract | Document (632 KB) | BibTeX

    		  



    DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI