default search action
35th CCC 2020: Saarbrücken, Germany (Virtual Conference)
- Shubhangi Saraf:
35th Computational Complexity Conference, CCC 2020, July 28-31, 2020, Saarbrücken, Germany (Virtual Conference). LIPIcs 169, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2020, ISBN 978-3-95977-156-6 - Front Matter, Table of Contents, Preface, Conference Organization. 0:1-0:16
- Avraham Ben-Aroya, Dean Doron
, Amnon Ta-Shma
Near-Optimal Erasure List-Decodable Codes. 1:1-1:27 - Prerona Chatterjee
A Quadratic Lower Bound for Algebraic Branching Programs. 2:1-2:21 - Dominik Scheder
Super Strong ETH Is True for PPSZ with Small Resolution Width. 3:1-3:12 - Jin-Yi Cai, Tianyu Liu, Pinyan Lu
Approximability of the Eight-Vertex Model. 4:1-4:18 - Mrinal Kumar, Ben Lee Volk:
Lower Bounds for Matrix Factorization. 5:1-5:20 - Dean Doron
Log-Seed Pseudorandom Generators via Iterated Restrictions. 6:1-6:36 - Scott Aaronson, Robin Kothari
Quantum Lower Bounds for Approximate Counting via Laurent Polynomials. 7:1-7:47 - Shir Peleg, Amir Shpilka
A Generalized Sylvester-Gallai Type Theorem for Quadratic Polynomials. 8:1-8:33 - Amey Bhangale, Subhash Khot:
Simultaneous Max-Cut Is Harder to Approximate Than Max-Cut. 9:1-9:15 - Kuan Cheng
Hitting Sets Give Two-Sided Derandomization of Small Space. 10:1-10:25 - Gil Cohen
Palette-Alternating Tree Codes. 11:1-11:29 - Ankit Garg, Christian Ikenmeyer, Visu Makam, Rafael Mendes de Oliveira, Michael Walter
Search Problems in Algebraic Complexity, GCT, and Hardness of Generators for Invariant Rings. 12:1-12:17 - Matthew Coulson, Ewan Davies
Statistical Physics Approaches to Unique Games. 13:1-13:27 - Prasad Chaugule, Mrinal Kumar, Nutan Limaye, Chandra Kanta Mohapatra
Schur Polynomials Do Not Have Small Formulas If the Determinant Doesn't. 14:1-14:27 - Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis
Algorithms and Lower Bounds for De Morgan Formulas of Low-Communication Leaf Gates. 15:1-15:41 - Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin, Chunhao Wang, Ruizhe Zhang:
On the Quantum Complexity of Closest Pair and Related Problems. 16:1-16:43 - Yuval Filmus, Yuval Ishai, Avi Kaplan, Guy Kindler:
Limits of Preprocessing. 17:1-17:22 - Hamed Hatami, Kaave Hosseini
Sign Rank vs Discrepancy. 18:1-18:14 - Mika Göös, Pritish Kamath, Katerina Sotiraki
On the Complexity of Modulo-q Arguments and the Chevalley - Warning Theorem. 19:1-19:42 - Shuichi Hirahara:
Non-Disjoint Promise Problems from Meta-Computational View of Pseudorandom Generator Constructions. 20:1-20:47 - Markus Bläser, Christian Ikenmeyer, Meena Mahajan
Algebraic Branching Programs, Border Complexity, and Tangent Spaces. 21:1-21:24 - Rahul Ilango, Bruno Loff
NP-Hardness of Circuit Minimization for Multi-Output Functions. 22:1-22:36 - Nikhil Gupta, Chandan Saha, Bhargav Thankey:
A Super-Quadratic Lower Bound for Depth Four Arithmetic Circuits. 23:1-23:31 - Alexander Kozachinskiy
Multiparty Karchmer - Wigderson Games and Threshold Circuits. 24:1-24:23 - Eshan Chattopadhyay, Jyun-Jie Liao:
Optimal Error Pseudodistributions for Read-Once Branching Programs. 25:1-25:27 - Michael E. Saks, Rahul Santhanam:
Circuit Lower Bounds from NP-Hardness of MCSP Under Turing Reductions. 26:1-26:13 - Marvin Künnemann, Dániel Marx:
Finding Small Satisfying Assignments Faster Than Brute Force: A Fine-Grained Perspective into Boolean Constraint Satisfaction. 27:1-27:28 - Susanna F. de Rezende
Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs. 28:1-28:24 - Laurent Bartholdi
Groups with ALOGTIME-Hard Word Problems and PSPACE-Complete Circuit Value Problems. 29:1-29:29 - Jacques Dark
Optimal Lower Bounds for Matching and Vertex Cover in Dynamic Graph Streams. 30:1-30:14 - Rahul Ilango:
Connecting Perebor Conjectures: Towards a Search to Decision Reduction for Minimizing Formulas. 31:1-31:35 - Sourav Chakraborty, Arkadev Chattopadhyay, Nikhil S. Mande
Quantum Query-To-Communication Simulation Needs a Logarithmic Overhead. 32:1-32:15 - Amit Sinhababu, Thomas Thierauf:
Factorization of Polynomials Given By Arithmetic Branching Programs. 33:1-33:19 - Daniel Dadush, Samarth Tiwari:
On the Complexity of Branching Proofs. 34:1-34:35 - Swastik Kopparty, Guy Moshkovitz, Jeroen Zuiddam:
Geometric Rank of Tensors and Subrank of Matrix Multiplication. 35:1-35:21 - Huck Bennett, Chris Peikert:
Hardness of Bounded Distance Decoding on Lattices in ℓp Norms. 36:1-36:21 - Robert Andrews
Algebraic Hardness Versus Randomness in Low Characteristic. 37:1-37:32 - Aaron Potechin
Sum of Squares Bounds for the Ordering Principle. 38:1-38:37
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-09-26 23:31 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: