default search action
30th CCC 2015: Portland, OR, USA
- David Zuckerman:
30th Conference on Computational Complexity, CCC 2015, June 17-19, 2015, Portland, Oregon, USA. LIPIcs 33, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2015, ISBN 978-3-939897-81-1 - Front Matter, Table of Contents, Preface, Conference Organization. i-xiv
- Oded Goldreich
, Tom Gur, Ilan Komargodski:
Strong Locally Testable Codes with Relaxed Local Decoders. 1-41 - Venkatesan Guruswami, Ameya Velingker:
An Entropy Sumset Inequality and Polynomially Fast Convergence to Shannon Capacity Over All Alphabets. 42-57 - Ishay Haviv, Oded Regev:
The List-Decoding Size of Fourier-Sparse Boolean Functions. 58-71 - Abhishek Bhowmick, Shachar Lovett
Nonclassical Polynomials as a Barrier to Polynomial Lower Bounds. 72-87 - Anup Rao, Amir Yehudayoff:
Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness. 88-101 - Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao:
How to Compress Asymmetric Communication. 102-123 - Igor Carboni Oliveira, Rahul Santhanam
Majority is Incompressible by AC^0[p] Circuits. 124-157 - Neeraj Kayal, Chandan Saha:
Lower Bounds for Depth Three Arithmetic Circuits with Small Bottom Fanin. 158-208 - Suman K. Bera, Amit Chakrabarti
A Depth-Five Lower Bound for Iterated Matrix Multiplication. 183-197 - Rafael Mendes de Oliveira:
Factors of Low Individual Degree Polynomials. 198-216 - Amit Chakrabarti
Verifiable Stream Computation and Arthur-Merlin Communication. 217-243 - Shuichi Hirahara:
Identifying an Honest EXP^NP Oracle Among Many. 244-263 - Rocco A. Servedio
Adaptivity Helps for Testing Juntas. 264-279 - Amey Bhangale, Prahladh Harsha
A Characterization of Hard-to-cover CSPs. 280-303 - Rafael Oliveira, Amir Shpilka
Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas. 304-322 - Rohit Gurjar, Arpita Korwar, Nitin Saxena
Deterministic Identity Testing for Sum of Read-once Oblivious Arithmetic Branching Programs. 323-346 - Alex Samorodnitsky, Ilya D. Shkredov
Kolmogorov Width of Discrete Linear Spaces: an Approach to Matrix Rigidity. 347-364 - Cody D. Murray, Richard Ryan Williams
On the (Non) NP-Hardness of Computing Circuit Complexity. 365-380 - Pavel Hrubes, Anup Rao:
Circuits with Medium Fan-In. 381-391 - Benjamin Rossman:
Correlation Bounds Against Monotone NC^1. 392-411 - Fu Li, Iddo Tzameret, Zhengyu Wang:
Non-Commutative Formulas and Frege Lower Bounds: a New Characterization of Propositional Proofs. 412-432 - Nicola Galesi, Pavel Pudlák, Neil Thapen:
The Space Complexity of Cutting Planes Refutations. 433-447 - Massimo Lauria
Tight Size-Degree Bounds for Sums-of-Squares Proofs. 448-466 - Mladen Miksa, Jakob Nordström
A Generalized Method for Proving Polynomial Calculus Degree Lower Bounds. 467-487 - Hirotada Kobayashi, François Le Gall, Harumichi Nishimura:
Generalized Quantum Arthur-Merlin Games. 488-511 - Kai-Min Chung
Parallel Repetition for Entangled k-player Games via Fast Quantum Search. 512-536 - Cedric Yen-Yu Lin, Han-Hsuan Lin:
Upper Bounds on Quantum Query Complexity Inspired by the Elitzur-Vaidman Bomb Tester. 537-566 - Daniel M. Kane:
A Polylogarithmic PRG for Degree 2 Threshold Functions in the Gaussian Setting. 567-581 - Benny Applebaum, Sergei Artemenko, Ronen Shaltiel, Guang Yang:
Incompressible Functions, Relative-Error Extractors, and the Power of Nondeterministic Reductions (Extended Abstract). 582-600 - Oded Goldreich
On Randomness Extraction in AC0. 601-668
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-11-25 22:32 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: