default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID27th CCC 2012: Porto, Portugal
- Proceedings of the 27th Conference on Computational Complexity, CCC 2012, Porto, Portugal, June 26-29, 2012. IEEE Computer Society 2012, ISBN 978-1-4673-1663-7
- Richard J. Lipton, Ryan Williams
:
Amplifying Circuit Lower Bounds against Polynomial Time with Applications. 1-9 - Holger Dell, Valentine Kabanets, Dieter van Melkebeek, Osamu Watanabe:
Is Valiant-Vazirani's Isolation Probability Improvable? 10-20 - Gus Gutoski, Xiaodi Wu:
Parallel Approximation of Min-max Problems with Applications to Classical and Quantum Zero-Sum Games. 21-31 - André Chailloux, Or Sattath:
The Complexity of the Separable Hamiltonian Problem. 32-41 - Dmitry Gavinsky:
Quantum Money with Classical Verification. 42-52 - Per Austrin, Johan Håstad:
On the Usefulness of Predicates. 53-63 - Prasad Raghavendra, David Steurer, Madhur Tulsiani:
Reductions between Expansion Problems. 64-73 - Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, Magnus Wahlström:
On Problems as Hard as CNF-SAT. 74-84 - Yuichi Yoshida:
Testing List H-homomorphisms. 85-95 - Sangxia Huang, Pinyan Lu:
A Dichotomy for Real Weighted Holant Problems. 96-106 - Kazuhisa Seto, Suguru Tamaki:
A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis. 107-116 - Paul Beame, Russell Impagliazzo, Srikanth Srinivasan:
Approximating AC^0 by Small Height Decision Trees and a Deterministic Algorithm for #AC^0SAT. 117-125 - Parikshit Gopalan, Raghu Meka, Omer Reingold:
DNF Sparsification and a Faster Deterministic Counting Algorithm. 126-135 - Toniann Pitassi:
Communication Complexity and Information Complexity: Foundations and New Directions. 136 - Guy Kindler, Ryan O'Donnell:
Gaussian Noise Sensitivity and Fourier Tails. 137-147 - Sourav Chakraborty, Eldar Fischer, David García-Soriano, Arie Matsliah:
Junto-Symmetric Functions, Hypergraph Isomorphism and Crunching. 148-158 - Guy Moshkovitz:
Complexity Lower Bounds through Balanced Graph Properties. 159-169 - Andrew Drucker:
Limitations of Lower-Bound Methods for the Wire Complexity of Boolean Operators. 170-180 - Samuel R. Buss, Ryan Williams:
Limits on Alternation-Trading Proofs for Time-Space Lower Bounds. 181-191 - Anil Ada, Arkadev Chattopadhyay, Stephen A. Cook, Lila Fontes, Michal Koucký, Toniann Pitassi:
The Hardness of Being Private. 192-202 - Joshua A. Grochow:
Matrix Isomorphism of Matrix Lie Algebras. 203-213 - Noga Alon, Amir Shpilka, Christopher Umans:
On Sunflowers and Matrix Multiplication. 214-223 - Markus Bläser, Bekhan Chokaev:
Algebras of Minimal Multiplicative Complexity. 224-234 - Peter Bürgisser:
Prospects for Geometric Complexity Theory. 235 - Troy Lee, Jérémie Roland:
A Strong Direct Product Theorem for Quantum Query Complexity. 236-246 - Ran Raz, Ricky Rosen:
A Strong Parallel Repetition Theorem for Projection Games on Expanders. 247-257 - Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Ilan Orlov:
Share Conversion and Private Information Retrieval. 258-268 - Baris Aydinlioglu, Dieter van Melkebeek:
Nondeterministic Circuit Lower Bounds from Mildly De-randomizing Arthur-Merlin Games. 269-279 - Chi-Jen Lu:
Hitting Set Generators for Sparse Polynomials over Any Finite Fields. 280-286 - Dmitry Gavinsky, Shachar Lovett, Srikanth Srinivasan:
Pseudorandom Generators for Read-Once ACC^0. 287-297 - Gil Cohen, Ran Raz, Gil Segev:
Non-malleable Extractors with Short Seeds and Applications to Privacy Amplification. 298-308 - Amnon Ta-Shma, Christopher Umans:
Better Condensers and New Extractors from Parvaresh-Vardy Codes. 309-315 - Elena Grigorescu, Chris Peikert:
List Decoding Barnes-Wall Lattices. 316-325 - Derrick Stolee, N. V. Vinodchandran:
Space-Efficient Algorithms for Reachability in Surface-Embedded Graphs. 326-333 - Yuval Filmus, Massimo Lauria, Jakob Nordström, Neil Thapen, Noga Ron-Zewi:
Space Complexity in Polynomial Calculus. 334-344 - Or Meir:
Combinatorial PCPs with Short Proofs. 345-355
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-12-04 01:26 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:
