default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDComputational Complexity, Volume 19
Volume 19, Number 1, March 2010
- Peter Bürgisser, Peter Scheiblechner:
Counting Irreducible Components of Complex Algebraic Varieties. 1-35 - Jin-yi Cai, Xi Chen
, Dong Li:
Quadratic Lower Bound for Permanent Vs. Determinant in any Characteristic. 37-56 - Vikraman Arvind, T. C. Vijayaraghavan:
Classifying Problems on Linear Congruences and Abelian Permutation Groups Using Logspace Counting Classes. 57-98 - Oded Goldreich, Or Sheffet:
On The Randomness Complexity of Property Testing. 99-133 - Alexander A. Sherstov:
Communication Complexity Under Product and Nonproduct Distributions. 135-150
Volume 19, Number 2, May 2010
- Johan Håstad:
Special Issue "Conference on Computational Complexity 2009" Guest Editor's Foreword. 151-152 - Nikos Leonardos, Michael E. Saks:
Lower Bounds on the Randomized Communication Complexity of Read-Once Functions. 153-181 - Kazuyuki Amano:
k-Subgraph Isomorphism on AC0 Circuits. 183-210 - Kristoffer Arnsfelt Hansen, Michal Koucký:
A New Characterization of ACC0 and Probabilistic CC0. 211-234 - Parikshit Gopalan, Amir Shpilka, Shachar Lovett:
The Complexity of Boolean Functions in Different Characteristics. 235-263 - Guy N. Rothblum, Salil P. Vadhan:
Are PCPs Inherent in Efficient Arguments? 265-304 - Akitoshi Kawamura:
Lipschitz Continuous Ordinary Differential Equations are Polynomial-Space Complete. 305-332
Volume 19, Number 3, September 2010
- Mark Giesbrecht, Daniel S. Roche:
Interpolation of Shifted-Lacunary Polynomials. 333-354 - Erich L. Kaltofen, Mark Lavin:
Efficiently Certifying Non-Integer Powers. 355-366 - Dana Moshkovitz, Ran Raz:
Sub-Constant Error Probabilistically Checkable Proof of Almost-Linear Size. 367-422 - Jeff Kinne, Dieter van Melkebeek:
Space Hierarchy Results for Randomized and other Semantic Models. 423-475
Volume 19, Number 4, December 2010
- Noam Livne:
All Natural NP-Complete Problems Have Average-Case Complete Versions. 477-499 - Eli Ben-Sasson, Russell Impagliazzo:
Random Cnf's are Hard for the Polynomial Calculus. 501-519 - Vikraman Arvind, Partha Mukhopadhyay, Srikanth Srinivasan:
New Results on Noncommutative and Commutative Polynomial Identity Testing. 521-558 - Thanh Minh Hoang, Thomas Thierauf:
The Complexity of the Inertia. 559-580 - Adam R. Klivans, Alexander A. Sherstov:
Lower Bounds for Agnostic Learning via Approximate Rank. 581-604 - Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum:
A Complexity Dichotomy For Hypergraph Partition Functions. 605-633
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-05 21:04 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:
