Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
1 | Neeraj Kayal, Chandan Saha 0001 |
On the Sum of Square Roots of Polynomials and Related Problems. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, USA, June 8-10, 2011, pp. 292-299, 2011, IEEE Computer Society, 978-0-7695-4411-3. The full citation details ...](Pics/full.jpeg) |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Shachar Lovett, Emanuele Viola |
Bounded-Depth Circuits Cannot Sample Good Codes. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, USA, June 8-10, 2011, pp. 243-251, 2011, IEEE Computer Society, 978-0-7695-4411-3. The full citation details ...](Pics/full.jpeg) |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Thomas Watson 0001 |
Pseudorandom Generators for Combinatorial Checkerboards. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, USA, June 8-10, 2011, pp. 232-242, 2011, IEEE Computer Society, 978-0-7695-4411-3. The full citation details ...](Pics/full.jpeg) |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Xin Li 0006 |
A New Approach to Affine Extractors and Dispersers. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, USA, June 8-10, 2011, pp. 137-147, 2011, IEEE Computer Society, 978-0-7695-4411-3. The full citation details ...](Pics/full.jpeg) |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Venkatesan Guruswami |
Linear-Algebraic List Decoding of Folded Reed-Solomon Codes. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, USA, June 8-10, 2011, pp. 77-85, 2011, IEEE Computer Society, 978-0-7695-4411-3. The full citation details ...](Pics/full.jpeg) |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Yuichi Yoshida |
Lower Bounds on Query Complexity for Testing Bounded-Degree CSPs. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, USA, June 8-10, 2011, pp. 34-44, 2011, IEEE Computer Society, 978-0-7695-4411-3. The full citation details ...](Pics/full.jpeg) |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Eli Ben-Sasson, Ghid Maatouk, Amir Shpilka, Madhu Sudan 0001 |
Symmetric LDPC Codes are not Necessarily Locally Testable. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, USA, June 8-10, 2011, pp. 55-65, 2011, IEEE Computer Society, 978-0-7695-4411-3. The full citation details ...](Pics/full.jpeg) |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Arkadev Chattopadhyay, Shachar Lovett |
Linear Systems over Finite Abelian Groups. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, USA, June 8-10, 2011, pp. 300-308, 2011, IEEE Computer Society, 978-0-7695-4411-3. The full citation details ...](Pics/full.jpeg) |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Paul Beame, Widad Machmouchi |
Making Branching Programs Oblivious Requires Superlogarithmic Overhead. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, USA, June 8-10, 2011, pp. 12-22, 2011, IEEE Computer Society, 978-0-7695-4411-3. The full citation details ...](Pics/full.jpeg) |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Andrew Drucker |
Improved Direct Product Theorems for Randomized Query Complexity. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, USA, June 8-10, 2011, pp. 1-11, 2011, IEEE Computer Society, 978-0-7695-4411-3. The full citation details ...](Pics/full.jpeg) |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Zohar Shay Karnin, Yuval Rabani, Amir Shpilka |
Explicit Dimension Reduction and Its Applications. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, USA, June 8-10, 2011, pp. 262-272, 2011, IEEE Computer Society, 978-0-7695-4411-3. The full citation details ...](Pics/full.jpeg) |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Andris Ambainis, Loïck Magnin, Martin Roetteler, Jérémie Roland |
Symmetry-Assisted Adversaries for Quantum State Generation. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, USA, June 8-10, 2011, pp. 167-177, 2011, IEEE Computer Society, 978-0-7695-4411-3. The full citation details ...](Pics/full.jpeg) |
2011 |
DBLP DOI BibTeX RDF |
|
1 | Kristoffer Arnsfelt Hansen, Vladimir V. Podolskii |
Exact Threshold Circuits. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010, pp. 270-279, 2010, IEEE Computer Society, 978-0-7695-4060-3. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP DOI BibTeX RDF |
Exact Threshold Functions, Boolean Circuits, Threshold Functions |
1 | Thanh Minh Hoang |
On the Matching Problem for Special Graph Classes. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010, pp. 139-150, 2010, IEEE Computer Society, 978-0-7695-4060-3. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP DOI BibTeX RDF |
NC-computations, Perfect matchings, maximum matchings |
1 | Oded Regev 0001 |
The Learning with Errors Problem (Invited Survey). ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010, pp. 191-204, 2010, IEEE Computer Society, 978-0-7695-4060-3. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP DOI BibTeX RDF |
learning with errors, lattice-based cryptography |
1 | Ronen Shaltiel |
Derandomized Parallel Repetition Theorems for Free Games. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010, pp. 28-37, 2010, IEEE Computer Society, 978-0-7695-4060-3. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP DOI BibTeX RDF |
Derandomization, Randomness extractors, Parallel repetition |
1 | Zeev Dvir |
On Matrix Rigidity and Locally Self-Correctable Codes. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010, pp. 291-298, 2010, IEEE Computer Society, 978-0-7695-4060-3. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP DOI BibTeX RDF |
complexity, arithmetic circuits, matrices |
1 | Mohammad Mahmoody, David Xiao |
On the Power of Randomized Reductions and the Checkability of SAT. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010, pp. 64-75, 2010, IEEE Computer Society, 978-0-7695-4060-3. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP DOI BibTeX RDF |
Colusure, Instance Checkers, Complexity, Randomization |
1 | Ilias Diakonikolas, Rocco A. Servedio, Li-Yang Tan, Andrew Wan |
A Regularity Lemma, and Low-Weight Approximators, for Low-Degree Polynomial Threshold Functions. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010, pp. 211-222, 2010, IEEE Computer Society, 978-0-7695-4060-3. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP DOI BibTeX RDF |
Boolean function, regularity lemma, polynomial threshold function |
1 | Parikshit Gopalan, Ryan O'Donnell, Yi Wu 0002, David Zuckerman |
Fooling Functions of Halfspaces under Product Distributions. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010, pp. 223-234, 2010, IEEE Computer Society, 978-0-7695-4060-3. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP DOI BibTeX RDF |
Pseudorandness, complexity theory, halfspace |
1 | Alexandra Kolla |
Spectral Algorithms for Unique Games. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010, pp. 122-130, 2010, IEEE Computer Society, 978-0-7695-4060-3. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP DOI BibTeX RDF |
|
1 | Matei David, Periklis A. Papakonstantinou |
Trade-Off Lower Bounds for Stack Machines. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010, pp. 163-171, 2010, IEEE Computer Society, 978-0-7695-4060-3. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP DOI BibTeX RDF |
AuxPDA, lower bound, streaming, communication complexity, stack, reversals, space bound |
1 | Dan Gutfreund, Akinori Kawachi |
Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010, pp. 38-49, 2010, IEEE Computer Society, 978-0-7695-4060-3. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP DOI BibTeX RDF |
Arthur-Merlin protocols, derandomization, circuit complexity, approximate counting |
1 | Luca Trevisan |
The Program-Enumeration Bottleneck in Average-Case Complexity Theory. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010, pp. 88-95, 2010, IEEE Computer Society, 978-0-7695-4060-3. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP DOI BibTeX RDF |
Universal Search, Average-case Complexity |
1 | Matt DeVos, Ariel Gabizon |
Simple Affine Extractors Using Dimension Expansion. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010, pp. 50-57, 2010, IEEE Computer Society, 978-0-7695-4060-3. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP DOI BibTeX RDF |
affine extractors, dimension expansion, derandomization, Extractors, pseudorandomness |
1 | Dániel Marx |
Completely Inapproximable Monotone and Antimonotone Parameterized Problems. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010, pp. 181-187, 2010, IEEE Computer Society, 978-0-7695-4060-3. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP DOI BibTeX RDF |
parameterized comlexity, approximation, fixed-parameter tractability, inapproximability |
1 | Eric Allender, Klaus-Jörn Lange |
Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010, pp. 172-180, 2010, IEEE Computer Society, 978-0-7695-4060-3. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP DOI BibTeX RDF |
Symmetric Computation, Auxiliary Pushdown Automata, LogCFL, Reversible Computation |
1 | Eric Blais, Ryan O'Donnell |
Lower Bounds for Testing Function Isomorphism. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010, pp. 235-246, 2010, IEEE Computer Society, 978-0-7695-4060-3. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP DOI BibTeX RDF |
lower bounds, Boolean functions, property testing |
1 | Ran Raz |
Parallel Repetition of Two Prover Games (Invited Survey). ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010, pp. 3-6, 2010, IEEE Computer Society, 978-0-7695-4060-3. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP DOI BibTeX RDF |
|
1 | Derrick Stolee, Chris Bourke, N. V. Vinodchandran |
A Log-Space Algorithm for Reachability in Planar Acyclic Digraphs with Few Sources. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010, pp. 131-138, 2010, IEEE Computer Society, 978-0-7695-4060-3. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP DOI BibTeX RDF |
acyclic digraph, logspace algorithm, planar graph, reachability |
1 | Irit Dinur, Or Meir |
Derandomized Parallel Repetition of Structured PCPs. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010, pp. 16-27, 2010, IEEE Computer Society, 978-0-7695-4060-3. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP DOI BibTeX RDF |
Low error, Direct Product Test, Derandomized Parallel Repetition, PCP, Direct Product, de-Bruijn |
1 | Subhash Khot |
On the Unique Games Conjecture (Invited Survey). ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010, pp. 99-121, 2010, IEEE Computer Society, 978-0-7695-4060-3. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP DOI BibTeX RDF |
|
1 | Jakob Nordström |
On the Relative Strength of Pebbling and Resolution. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010, pp. 151-162, 2010, IEEE Computer Society, 978-0-7695-4060-3. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP DOI BibTeX RDF |
pebbling formula, resolution, space, trade-off, proof complexity, pebble games |
1 | Iftach Haitner, Mohammad Mahmoody, David Xiao |
A New Sampling Protocol and Applications to Basing Cryptographic Primitives on the Hardness of NP. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010, pp. 76-87, 2010, IEEE Computer Society, 978-0-7695-4060-3. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP DOI BibTeX RDF |
sampling protocols, constant-round statistically hiding commitments, black-box lower bounds, collision-resistant hash functions |
1 | Julia Kempe, Oded Regev 0001 |
No Strong Parallel Repetition with Entangled and Non-signaling Provers. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010, pp. 7-15, 2010, IEEE Computer Society, 978-0-7695-4060-3. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP DOI BibTeX RDF |
entangled two-prover games, unique games, parallel repetition |
1 | Pavel Hrubes, Avi Wigderson, Amir Yehudayoff |
Relationless Completeness and Separations. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010, pp. 280-290, 2010, IEEE Computer Society, 978-0-7695-4060-3. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP DOI BibTeX RDF |
Completeness, Separations, Algebraic complexity |
1 | Daniel M. Kane |
The Gaussian Surface Area and Noise Sensitivity of Degree-d Polynomial Threshold Functions. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010, pp. 205-210, 2010, IEEE Computer Society, 978-0-7695-4060-3. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP DOI BibTeX RDF |
|
1 | Harry Buhrman, Lance Fortnow, Michal Koucký 0001, Bruno Loff |
Derandomizing from Random Strings. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010, pp. 58-63, 2010, IEEE Computer Society, 978-0-7695-4060-3. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP DOI BibTeX RDF |
Truth-table Reducibility, Kolmogorov Complexity, Derandomization |
1 | Russell Impagliazzo, Ryan Williams 0001 |
Communication Complexity with Synchronized Clocks. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010, pp. 259-269, 2010, IEEE Computer Society, 978-0-7695-4060-3. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP DOI BibTeX RDF |
time-communication tradeoffs, lower bounds, communication complexity |
1 | Rahul Jain 0001, Hartmut Klauck |
The Partition Bound for Classical Communication Complexity and Query Complexity. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010, pp. 247-258, 2010, IEEE Computer Society, 978-0-7695-4060-3. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP DOI BibTeX RDF |
Partition Bound, Lower Bounds, Linear Programming, Communication Complexity, Query Complexity |
1 | |
Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010 ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![IEEE Computer Society, 978-0-7695-4060-3 The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP BibTeX RDF |
|
1 | Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan 0001, Michael Viderman |
Locally Testable Codes Require Redundant Testers. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pp. 52-61, 2009, IEEE Computer Society, 978-0-7695-3717-7. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Kristoffer Arnsfelt Hansen, Michal Koucký 0001 |
A New Characterization of ACC0 and Probabilistic CC0. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pp. 27-34, 2009, IEEE Computer Society, 978-0-7695-3717-7. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Nitin Saxena 0001, C. Seshadhri 0001 |
An Almost Optimal Rank Bound for Depth-3 Identities. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pp. 137-148, 2009, IEEE Computer Society, 978-0-7695-3717-7. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Pavel Hrubes, Iddo Tzameret |
The Proof Complexity of Polynomial Identities. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pp. 41-51, 2009, IEEE Computer Society, 978-0-7695-3717-7. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Neeraj Kayal |
The Complexity of the Annihilating Polynomial. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pp. 184-193, 2009, IEEE Computer Society, 978-0-7695-3717-7. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Guy N. Rothblum, Salil P. Vadhan |
Are PCPs Inherent in Efficient Arguments? ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pp. 81-92, 2009, IEEE Computer Society, 978-0-7695-3717-7. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Troy Lee, Adi Shraibman |
An Approximation Algorithm for Approximation Rank. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pp. 351-357, 2009, IEEE Computer Society, 978-0-7695-3717-7. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Zeev Dvir |
Extractors for Varieties. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pp. 102-113, 2009, IEEE Computer Society, 978-0-7695-3717-7. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Per Austrin, Subhash Khot, Muli Safra |
Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pp. 74-80, 2009, IEEE Computer Society, 978-0-7695-3717-7. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Troy Lee, Gideon Schechtman, Adi Shraibman |
Lower Bounds on Quantum Multiparty Communication Complexity. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pp. 254-262, 2009, IEEE Computer Society, 978-0-7695-3717-7. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Mark Braverman |
Poly-logarithmic Independence Fools AC0 Circuits. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pp. 3-8, 2009, IEEE Computer Society, 978-0-7695-3717-7. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan |
Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pp. 126-136, 2009, IEEE Computer Society, 978-0-7695-3717-7. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Andrew Drucker |
Multitask Efficiencies in the Decision Tree Model. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pp. 286-297, 2009, IEEE Computer Society, 978-0-7695-3717-7. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Ronen Shaltiel |
Weak Derandomization of Weak Algorithms: Explicit Versions of Yao's Lemma. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pp. 114-125, 2009, IEEE Computer Society, 978-0-7695-3717-7. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Zohar Shay Karnin, Amir Shpilka |
Reconstruction of Generalized Depth-3 Arithmetic Circuits with Bounded Top Fan-in. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pp. 274-285, 2009, IEEE Computer Society, 978-0-7695-3717-7. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Parikshit Gopalan, Shachar Lovett, Amir Shpilka |
On the Complexity of Boolean Functions in Different Characteristics. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pp. 173-183, 2009, IEEE Computer Society, 978-0-7695-3717-7. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Kazuyuki Amano |
k-Subgraph Isomorphism on AC0 Circuits. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pp. 9-18, 2009, IEEE Computer Society, 978-0-7695-3717-7. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Pascal Koiran, Sylvain Perifel |
A Superpolynomial Lower Bound on the Size of Uniform Non-constant-depth Threshold Circuits for the Permanent. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pp. 35-40, 2009, IEEE Computer Society, 978-0-7695-3717-7. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Luis Filipe Coelho Antunes, Lance Fortnow |
Worst-Case Running Times for Average-Case Algorithms. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pp. 298-303, 2009, IEEE Computer Society, 978-0-7695-3717-7. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Ilias Diakonikolas, Rocco A. Servedio |
Improved Approximation of Linear Threshold Functions. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pp. 161-172, 2009, IEEE Computer Society, 978-0-7695-3717-7. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Nikos Leonardos, Michael E. Saks |
Lower Bounds on the Randomized Communication Complexity of Read-Once Functions. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pp. 341-350, 2009, IEEE Computer Society, 978-0-7695-3717-7. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Anup Rao 0001 |
Extractors for Low-Weight Affine Sources. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pp. 95-101, 2009, IEEE Computer Society, 978-0-7695-3717-7. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Adam R. Day |
Increasing the Gap between Descriptional Complexity and Algorithmic Probability. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pp. 263-273, 2009, IEEE Computer Society, 978-0-7695-3717-7. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Tsuyoshi Ito, Hirotada Kobayashi, Keiji Matsumoto |
Oracularization and Two-Prover One-Round Interactive Proofs against Nonlocal Strategies. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pp. 217-228, 2009, IEEE Computer Society, 978-0-7695-3717-7. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
1 | |
Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009 ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![IEEE Computer Society, 978-0-7695-3717-7 The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP BibTeX RDF |
|
1 | Manindra Agrawal, Osamu Watanabe 0001 |
One-Way Functions and the Berman-Hartmanis Conjecture. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pp. 194-202, 2009, IEEE Computer Society, 978-0-7695-3717-7. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Scott Aaronson |
Quantum Copy-Protection and Quantum Money. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pp. 229-242, 2009, IEEE Computer Society, 978-0-7695-3717-7. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Lance Fortnow, Rahul Santhanam, Ryan Williams 0001 |
Fixed-Polynomial Size Circuit Bounds. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pp. 19-26, 2009, IEEE Computer Society, 978-0-7695-3717-7. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
1 | T. S. Jayram, Swastik Kopparty, Prasad Raghavendra |
On the Communication Complexity of Read-Once AC^0 Formulae. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pp. 329-340, 2009, IEEE Computer Society, 978-0-7695-3717-7. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Richard Královic |
Infinite vs. Finite Space-Bounded Randomized Computations. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pp. 316-325, 2009, IEEE Computer Society, 978-0-7695-3717-7. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Moses Charikar, Venkatesan Guruswami, Rajsekar Manokaran |
Every Permutation CSP of arity 3 is Approximation Resistant. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pp. 62-73, 2009, IEEE Computer Society, 978-0-7695-3717-7. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Akitoshi Kawamura |
Lipschitz Continuous Ordinary Differential Equations are Polynomial-Space Complete. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pp. 149-160, 2009, IEEE Computer Society, 978-0-7695-3717-7. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Rahul Jain 0001, Hartmut Klauck |
New Results in the Simultaneous Message Passing Model via Information Theoretic Techniques. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pp. 369-378, 2009, IEEE Computer Society, 978-0-7695-3717-7. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Rahul Jain 0001, John Watrous |
Parallel Approximation of Non-interactive Zero-sum Quantum Games. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pp. 243-253, 2009, IEEE Computer Society, 978-0-7695-3717-7. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Joshua Brody |
The Maximum Communication Complexity of Multi-Party Pointer Jumping. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pp. 379-386, 2009, IEEE Computer Society, 978-0-7695-3717-7. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Joshua Brody, Amit Chakrabarti |
A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pp. 358-368, 2009, IEEE Computer Society, 978-0-7695-3717-7. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
1 | David Xiao |
On Basing ZK ≠ BPP on the Hardness of PAC Learning. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pp. 304-315, 2009, IEEE Computer Society, 978-0-7695-3717-7. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner |
Planar Graph Isomorphism is in Log-Space. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pp. 203-214, 2009, IEEE Computer Society, 978-0-7695-3717-7. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
1 | Nati Linial, Adi Shraibman |
Learning Complexity vs. Communication Complexity. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, 23-26 June 2008, College Park, Maryland, USA, pp. 53-63, 2008, IEEE Computer Society, 978-0-7695-3169-4. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
large margin classifiers, communication complexity, discrepancy, rigidity |
1 | Erik D. Demaine, Robert A. Hearn |
Constraint Logic: A Uniform Framework for Modeling Computation as Games. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, 23-26 June 2008, College Park, Maryland, USA, pp. 149-162, 2008, IEEE Computer Society, 978-0-7695-3169-4. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
games, undecidability, hardness |
1 | Elena Grigorescu, Tali Kaufman, Madhu Sudan 0001 |
2-Transitivity Is Insufficient for Local Testability. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, 23-26 June 2008, College Park, Maryland, USA, pp. 259-267, 2008, IEEE Computer Society, 978-0-7695-3169-4. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
error correcting codes, property testing, sublinear time algorithms |
1 | Zeev Dvir, Amir Shpilka |
Towards Dimension Expanders over Finite Fields. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, 23-26 June 2008, College Park, Maryland, USA, pp. 304-310, 2008, IEEE Computer Society, 978-0-7695-3169-4. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
Cayley graphs, expanders, explicit constructions |
1 | Troy Lee, Adi Shraibman |
Disjointness Is Hard in the Multi-party Number-on-the-Forehead Model. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, 23-26 June 2008, College Park, Maryland, USA, pp. 81-91, 2008, IEEE Computer Society, 978-0-7695-3169-4. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
multiparty communication complexity, disjointness, lower bounds |
1 | Emanuele Viola |
The Sum of d Small-Bias Generators Fools Polynomials of Degree d. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, 23-26 June 2008, College Park, Maryland, USA, pp. 124-127, 2008, IEEE Computer Society, 978-0-7695-3169-4. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
|
1 | Tsuyoshi Ito, Hirotada Kobayashi, Daniel Preda, Xiaoming Sun 0001, Andrew Chi-Chih Yao |
Generalized Tsirelson Inequalities, Commuting-Operator Provers, and Multi-prover Interactive Proof Systems. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, 23-26 June 2008, College Park, Maryland, USA, pp. 187-198, 2008, IEEE Computer Society, 978-0-7695-3169-4. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
multi-prover interactive proof systems, quantum nonlocality, Tsirelson inequality, entanglement |
1 | Parikshit Gopalan, Venkatesan Guruswami |
Hardness Amplification within NP against Deterministic Algorithms. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, 23-26 June 2008, College Park, Maryland, USA, pp. 19-30, 2008, IEEE Computer Society, 978-0-7695-3169-4. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
Hardness Amplication, Error-Correcting Codes, Derandomization, NP |
1 | Andrew C. Doherty, Yeong-Cherng Liang, Ben Toner, Stephanie Wehner |
The Quantum Moment Problem and Bounds on Entangled Multi-prover Games. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, 23-26 June 2008, College Park, Maryland, USA, pp. 199-210, 2008, IEEE Computer Society, 978-0-7695-3169-4. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
quantum entanglement, nonlocal games, multi-prover interactive proof systems |
1 | Harry Buhrman, Michal Koucký 0001, Nikolai K. Vereshchagin |
Randomised Individual Communication Complexity. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, 23-26 June 2008, College Park, Maryland, USA, pp. 321-331, 2008, IEEE Computer Society, 978-0-7695-3169-4. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
individual communication complexity, Kolmogorov complexity, rounds, randomized protocols |
1 | Alexander A. Sherstov |
Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, 23-26 June 2008, College Park, Maryland, USA, pp. 112-123, 2008, IEEE Computer Society, 978-0-7695-3169-4. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
Approximate inclusion/exclusion, approximate degree of Boolean functions, linear-programming duality, Chebyshev polynomials |
1 | Kord Eickmeyer, Martin Grohe, Magdalena Grüber |
Approximation of Natural W[P]-Complete Minimisation Problems Is Hard. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, 23-26 June 2008, College Park, Maryland, USA, pp. 8-18, 2008, IEEE Computer Society, 978-0-7695-3169-4. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
derandomisation, parameterized complexity, inapproximability |
1 | Richard Chang 0001, Suresh Purini |
Amplifying ZPP^SAT[1] and the Two Queries Problem. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, 23-26 June 2008, College Park, Maryland, USA, pp. 41-52, 2008, IEEE Computer Society, 978-0-7695-3169-4. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
ZPP, amplification, bounded queries |
1 | Swastik Kopparty, Sergey Yekhanin |
Detecting Rational Points on Hypersurfaces over Finite Fields. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, 23-26 June 2008, College Park, Maryland, USA, pp. 311-320, 2008, IEEE Computer Society, 978-0-7695-3169-4. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
Chevalley-Warning Theorem, Lang-Weil Theorem, Nonsingular Spaces of Matrices, Polynomial Identity Testing |
1 | Kiran S. Kedlaya, Sergey Yekhanin |
Locally Decodable Codes From Nice Subsets of Finite Fields and Prime Factors of Mersenne Numbers. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, 23-26 June 2008, College Park, Maryland, USA, pp. 175-186, 2008, IEEE Computer Society, 978-0-7695-3169-4. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
Locally decodable codes, Mersenne primes |
1 | Dmitry Gavinsky, Pavel Pudlák |
Exponential Separation of Quantum and Classical Non-interactive Multi-party Communication Complexity. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, 23-26 June 2008, College Park, Maryland, USA, pp. 332-339, 2008, IEEE Computer Society, 978-0-7695-3169-4. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
separation of communication classes, communication complexity, quantum communication |
1 | Harry Buhrman, John M. Hitchcock |
NP-Hard Sets Are Exponentially Dense Unless coNP C NP/poly. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, 23-26 June 2008, College Park, Maryland, USA, pp. 1-7, 2008, IEEE Computer Society, 978-0-7695-3169-4. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
hard sets, polynomial advice, instance complexity |
1 | |
Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, 23-26 June 2008, College Park, Maryland, USA ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![IEEE Computer Society, 978-0-7695-3169-4 The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP BibTeX RDF |
|
1 | Ran Raz, Amir Yehudayoff |
Lower Bounds and Separations for Constant Depth Multilinear Circuits. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, 23-26 June 2008, College Park, Maryland, USA, pp. 128-139, 2008, IEEE Computer Society, 978-0-7695-3169-4. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
Constant Depth, Lower Bounds, Separations, Arithmetic Circuits |
1 | Per Austrin, Elchanan Mossel |
Approximation Resistant Predicates from Pairwise Independence. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, 23-26 June 2008, College Park, Maryland, USA, pp. 249-258, 2008, IEEE Computer Society, 978-0-7695-3169-4. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
Max k-CSP, Approximation Resistance, Pairwise Independence, Unique Games Conjecture |
1 | Alexander A. Sherstov |
Communication Complexity under Product and Nonproduct Distributions. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, 23-26 June 2008, College Park, Maryland, USA, pp. 64-70, 2008, IEEE Computer Society, 978-0-7695-3169-4. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
Randomized/distributional communication complexity, product/nonproduct distributions, Yao's Minimax Principle |