default search action
32nd CCC 2017: Riga, Latvia
- Ryan O'Donnell:
32nd Computational Complexity Conference, CCC 2017, July 6-9, 2017, Riga, Latvia. LIPIcs 79, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2017, ISBN 978-3-95977-040-8 - Front Matter, Table of Contents, Preface, Awards, Conference Organization, External Reviewers. 0:i-0:xiv
- Pavel Pudlák, Neil Thapen:
Random Resolution Refutations. 1:1-1:10 - Massimo Lauria, Jakob Nordström
:
Graph Colouring is Hard for Algorithms Based on Hilbert's Nullstellensatz and Gröbner Bases. 2:1-2:20 - Mateus de Oliveira Oliveira, Pavel Pudlák:
Representations of Monotone Boolean Functions by Linear Programs. 3:1-3:14 - Aaron Potechin
A Note on Amortized Branching Program Complexity. 4:1-4:12 - Dieter van Melkebeek, Gautam Prakriya:
Derandomizing Isolation in Space-Bounded Settings. 5:1-5:32 - Danny Nguyen, Igor Pak:
The Computational Complexity of Integer Programming with Alternations. 6:1-6:18 - Shuichi Hirahara, Rahul Santhanam
On the Average-Case Complexity of MCSP and Its Variants. 7:1-7:20 - Cody D. Murray, R. Ryan Williams
Easiness Amplification and Uniform Circuit Lower Bounds. 8:1-8:21 - Dominik Scheder
PPSZ for General k-SAT - Making Hertli's Analysis Simpler and 3-SAT Faster. 9:1-9:15 - Anindya De, Elchanan Mossel, Joe Neeman:
Noise Stability Is Computable and Approximately Low-Dimensional. 10:1-10:11 - Mrinalkanti Ghosh, Madhur Tulsiani:
From Weak to Strong LP Gaps for All CSPs. 11:1-11:27 - Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson:
Query-to-Communication Lifting for P^NP. 12:1-12:16 - Roei Tell:
Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials. 13:1-13:48 - Elad Haramaty, Chin Ho Lee, Emanuele Viola:
Bounded Independence Plus Noise Fools Products. 14:1-14:30 - Avishay Tal:
Tight Bounds on the Fourier Spectrum of AC0. 15:1-15:31 - Yuval Dagan, Yuval Filmus, Hamed Hatami, Yaqiao Li
Trading Information Complexity for Error. 16:1-16:59 - Alexey Milovanov, Nikolay K. Vereshchagin:
Stochasticity in Algorithmic Statistics for Polynomial Time. 17:1-17:18 - Igor C. Oliveira, Rahul Santhanam
Conspiracies Between Learning Algorithms, Circuit Lower Bounds, and Pseudorandomness. 18:1-18:49 - Mrinal Kumar:
A Quadratic Lower Bound for Homogeneous Algebraic Branching Programs. 19:1-19:16 - Karl Bringmann, Christian Ikenmeyer, Jeroen Zuiddam:
On Algebraic Branching Programs of Small Width. 20:1-20:31 - Neeraj Kayal, Vineet Nair, Chandan Saha, Sébastien Tavenas:
Reconstruction of Full Rank Algebraic Branching Programs. 21:1-21:61 - Scott Aaronson, Lijie Chen:
Complexity-Theoretic Foundations of Quantum Supremacy Experiments. 22:1-22:67 - Ashwin Nayak, Dave Touchette:
Augmented Index and Quantum Streaming Algorithms for DYCK(2). 23:1-23:21 - Anurag Anshu, Shalev Ben-David, Ankit Garg, Rahul Jain
Separating Quantum Communication and Approximate Rank. 24:1-24:33 - Srinivasan Arunachalam, Ronald de Wolf:
Optimal Quantum Sample Complexity of Learning Algorithms. 25:1-25:31 - Xi Chen, Rocco A. Servedio
Settling the Query Complexity of Non-Adaptive Junta Testing. 26:1-26:19 - Clément L. Canonne, Tom Gur:
An Adaptivity Hierarchy Theorem for Property Testing. 27:1-27:25 - Eric Blais, Clément L. Canonne, Tom Gur:
Distribution Testing Lower Bounds via Reductions from Communication Complexity. 28:1-28:40 - Irit Dinur
Exponentially Small Soundness for the Direct Product Z-Test. 29:1-29:50 - Aleksandrs Belovs, Gábor Ivanyos
On the Polynomial Parity Argument Complexity of the Combinatorial Nullstellensatz. 30:1-30:24 - Mrinal Kumar, Ramprasad Saptharishi
An Exponential Lower Bound for Homogeneous Depth-5 Circuits over Finite Fields. 31:1-31:30 - Daniel Minahan, Ilya Volkovich:
Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas. 32:1-32:13 - Markus Bläser, Gorav Jindal
Greedy Strikes Again: A Deterministic PTAS for Commutative Rank of Matrix Spaces. 33:1-33:16
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-12-13 19:00 CET 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: