default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDComputational Complexity, Volume 18
Volume 18, Number 1, April 2009
- Zeev Dvir, Ariel Gabizon, Avi Wigderson:
Extractors And Rank Extractors For Polynomial Sources. 1-58 - Ali Juma, Valentine Kabanets, Charles Rackoff, Amir Shpilka
:
The Black-Box Query Complexity of Polynomial Summation. 59-79 - Peter Bürgisser:
On Defining Integers And Proving Arithmetic Circuit Lower Bounds. 81-103 - Ezequiel Dratman, Guillermo Matera, Ariel Waissbein:
Robust Algorithms For Generalized Pham Systems. 105-154 - Amir Hashemi:
Nullstellensätze for Zero-Dimensional Gröbner Bases. 155-168
Volume 18, Number 2, June 2009
- Paul Beame, Amit Chakrabarti:
Special Issue "Conference on Computational Complexity 2008" Guest Editors' Foreword. 169-170 - Ran Raz, Amir Yehudayoff:
Lower Bounds and Separations for Constant Depth Multilinear Circuits. 171-207 - Emanuele Viola:
The Sum of D Small-Bias Generators Fools Polynomials of Degree D. 209-217 - Alexander A. Sherstov:
Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions. 219-247 - Per Austrin, Elchanan Mossel:
Approximation Resistant Predicates from Pairwise Independence. 249-271 - Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Thomas Vidick:
Using Entanglement in Quantum Multi-Prover Interactive Proofs. 273-307 - Troy Lee, Adi Shraibman:
Disjointness is Hard in the Multiparty Number-on-the-Forehead Model. 309-336
Volume 18, Number 3, October 2009
- Emanuele Viola:
On Approximate Majority and Probabilistic Time. 337-375 - Nutan Limaye, Meena Mahajan, Jayalal Sarma:
Upper Bounds for Monotone Planar Circuit Value and Variants. 377-412 - Johan Håstad:
On the Approximation Resistance of a Random Predicate. 413-434 - Amos Beimel, Renen Hallak, Kobbi Nissim:
Private Approximation of Clustering and Vertex Cover. 435-494
Volume 18, Number 4, December 2009
- Amir Shpilka:
Constructions of Low-degree and Error-Correcting epsilon-Biased Generators. 495-525 - Felipe Cucker, Paulin Jacobé de Naurois:
Parallel Time and Quantifier Prefixes. 527-550 - Pascal Koiran, Sylvain Perifel:
VPSPACE and a Transfer Theorem over the Reals. 551-575 - Emmanuel Briand, Rosa C. Orellana, Mercedes H. Rosas:
Reduced Kronecker Coefficients and Counter-Examples to Mulmuley's Strong Saturation Conjecture SH. 577-600 - Mark Braverman, Raghav Kulkarni, Sambuddha Roy:
Space-Efficient Counting in Graphs on Surfaces. 601-649
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-09 23:25 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:
