default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID31st CCC 2016: Tokyo, Japan
- Ran Raz:
31st Conference on Computational Complexity, CCC 2016, May 29 to June 1, 2016, Tokyo, Japan. LIPIcs 50, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2016, ISBN 978-3-95977-008-8 - Front Matter, Table of Contents, Preface, Awards, Conference Organization, External Reviewers. 0:i-0:xvi
- Ruiwen Chen, Rahul Santhanam
, Srikanth Srinivasan:
Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits. 1:1-1:35 - Richard Ryan Williams:
Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation. 2:1-2:17 - Irit Dinur, Or Meir:
Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity. 3:1-3:51 - Andris Ambainis, Martins Kokainis, Robin Kothari:
Nearly Optimal Separations Between Communication (or Query) Complexity and Partitions. 4:1-4:14 - Mika Göös, T. S. Jayram:
A Composition Theorem for Conical Juntas. 5:1-5:16 - Venkatesan Guruswami, Jaikumar Radhakrishnan:
Tight Bounds for Communication-Assisted Agreement Distillation. 6:1-6:17 - Eshan Chattopadhyay, David Zuckerman:
New Extractors for Interleaved Sources. 7:1-7:28 - Gil Cohen:
Non-Malleable Extractors - New Tools and Improved Constructions. 8:1-8:29 - Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, Ronen Shaltiel:
Pseudorandomness When the Odds are Against You. 9:1-9:35 - Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova:
Learning Algorithms from Natural Proofs. 10:1-10:24 - John Y. Kim, Swastik Kopparty:
Decoding Reed-Muller Codes Over Product Sets. 11:1-11:28 - Arnab Bhattacharyya, Sivakanth Gopi:
Lower Bounds for Constant Query Affine-Invariant LCCs and LTCs. 12:1-12:17 - Parikshit Gopalan, Rocco A. Servedio, Avi Wigderson:
Degree and Sensitivity: Tails of Two Distributions. 13:1-13:23 - Joshua Brakensiek, Venkatesan Guruswami:
New Hardness Results for Graph and Hypergraph Colorings. 14:1-14:27 - Yuval Filmus, Guy Kindler, Elchanan Mossel, Karl Wimmer:
Invariance Principle on the Slice. 15:1-15:10 - Yuval Filmus, Elchanan Mossel:
Harmonicity and Invariance on Slices of the Boolean Cube. 16:1-16:13 - Troy Lee, Anupam Prakash, Ronald de Wolf, Henry Yuen:
On the Sum-of-Squares Degree of Symmetric Quadratic Functions. 17:1-17:31 - Shuichi Hirahara, Osamu Watanabe:
Limits of Minimum Circuit Size Problem as Oracle. 18:1-18:20 - Lance Fortnow, Rahul Santhanam:
New Non-Uniform Lower Bounds for Uniform Classes. 19:1-19:14 - Yuqing Ai, Wei Hu, Yi Li, David P. Woodruff:
New Characterizations in Turnstile Streams with Applications. 20:1-20:22 - Nisheeth K. Vishnoi:
Evolution and Computation (Invited Talk). 21:1-21:1 - Aram W. Harrow, Anand Natarajan, Xiaodi Wu:
Tight SoS-Degree Bounds for Approximate Nash Equilibria. 22:1-22:25 - Xiaotie Deng, Jack R. Edmonds, Zhe Feng, Zhengyang Liu, Qi Qi, Zeying Xu:
Understanding PPA-Completeness. 23:1-23:25 - Ryan O'Donnell, Yu Zhao:
Polynomial Bounds for Decoupling, with Applications. 24:1-24:18 - Scott Aaronson, Andris Ambainis, Janis Iraids, Martins Kokainis, Juris Smotrovs:
Polynomials, Quantum Query Complexity, and Grothendieck's Inequality. 25:1-25:19 - Scott Aaronson, Shalev Ben-David:
Sculpting Quantum Speedups. 26:1-26:28 - J. Niel de Beaudrap, Sevag Gharibian:
A Linear Time Algorithm for Quantum 2-SAT. 27:1-27:21 - Adam Bouland, Laura Mancinska, Xue Zhang:
Complexity Classification of Two-Qubit Commuting Hamiltonians. 28:1-28:33 - Rohit Gurjar, Arpita Korwar, Nitin Saxena:
Identity Testing for Constant-Width, and Commutative, Read-Once Oblivious ABPs. 29:1-29:16 - Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk:
Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs. 30:1-30:25 - Gaurav Sinha:
Reconstruction of Real Depth-3 Circuits with Top Fan-In 2. 31:1-31:53 - Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson:
Proof Complexity Lower Bounds from Algebraic Circuit Complexity. 32:1-32:17 - Michael A. Forbes, Mrinal Kumar, Ramprasad Saptharishi:
Functional Lower Bounds for Arithmetic Circuits and Connections to Boolean Circuit Complexity. 33:1-33:19 - Mrinal Kumar, Shubhangi Saraf:
Arithmetic Circuits with Locally Low Algebraic Rank. 34:1-34:27 - Mrinal Kumar, Shubhangi Saraf:
Sums of Products of Polynomials in Few Variables: Lower Bounds and Polynomial Identity Testing. 35:1-35:29
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 2025-04-18 00:17 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:
