default search action
Electronic Colloquium on Computational Complexity, 2008
Volume TR08, 2008
- Ran Raz:
Elusive Functions and Lower Bounds for Arithmetic Circuits. - Arkadev Chattopadhyay, Anil Ada:
Multiparty Communication Complexity of Disjointness. - Troy Lee, Adi Shraibman:
Disjointness is hard in the multi-party number-on-the-forehead model. - Zeev Dvir, Amir Shpilka:
Noisy Interpolating Sets for Low Degree Polynomials. - Scott Aaronson, Avi Wigderson:
Algebrization: A New Barrier in Complexity Theory. - Ran Raz, Amir Yehudayoff:
Lower Bounds and Separations for Constant Depth Multilinear Circuits. - Dan Gutfreund, Salil P. Vadhan:
Limitations of Hardness vs. Randomness under Uniform Reductions. - Venkatesan Guruswami, Prasad Raghavendra:
Constraint Satisfaction over a Non-Boolean Domain: Approximation algorithms and Unique-Games hardness. - Per Austrin, Elchanan Mossel:
Approximation Resistant Predicates From Pairwise Independence. - Itai Benjamini, Oded Schramm, Asaf Shapira:
Every Minor-Closed Property of Sparse Graphs is Testable. - Kazuo Iwama, Suguru Tamaki:
The Complexity of the Hajos Calculus for Planar Graphs. - Arnab Bhattacharyya:
A Note on the Distance to Monotonicity of Boolean Functions. - Anup Rao:
Parallel Repetition in Projection Games and a Concentration Bound. - Matei David, Toniann Pitassi:
Separating NOF communication complexity classes RP and NP. - Anup Rao:
Extractors for Low-Weight Affine Sources. - Alexander A. Razborov, Alexander A. Sherstov:
The Sign-Rank of AC^0. - Dieter van Melkebeek, Thomas Watson:
A Quantum Time-Space Lower Bound for the Counting Hierarchy. - Ran Raz:
A Counterexample to Strong Parallel Repetition. - Stasys Jukna:
Entropy of operators or why matrix multiplication is hard for small depth circuits. - Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan:
Decodability of Group Homomorphisms beyond the Johnson Bound. - Shankar Kalyanaraman, Christopher Umans:
The Complexity of Rationalizing Matchings. - Harry Buhrman, John M. Hitchcock:
NP-Hard Sets are Exponentially Dense Unless NP is contained in coNP/poly. - Anindya De, Piyush P. Kurur, Chandan Saha, Ramprasad Saptharishi:
Fast Integer Multiplication using Modular Arithmetic. - Paul Beame, Dang-Trinh Huynh-Ngoc:
On the Value of Multiple Read/Write Streams for Approximating Frequency Moments. - Vikraman Arvind, Partha Mukhopadhyay, Srikanth Srinivasan:
New results on Noncommutative and Commutative Polynomial Identity Testing. - Jakob Nordström, Johan Håstad:
Towards an Optimal Separation of Space and Length in Resolution. - Till Tantau:
Generalizations of the Hartmanis-Immerman-Sewelson Theorem and Applications to Infinite Subsets of P-Selective Sets. - Michael Bauland, Martin Mundhenk, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer:
The Tractability of Model-Checking for LTL: The Good, the Bad, and the Ugly Fragments. - Christian Glaßer, Christian Reitwießner, Victor L. Selivanov:
The Shrinking Property for NP and coNP. - Bruno Durand, Alexander Shen, Andrei E. Romashchenko:
Fixed Point and Aperiodic Tilings. - James I. Lathrop, Jack H. Lutz, Matthew J. Patitz
, Scott M. Summers:
Computability and Complexity in Self-Assembly. - Dmitriy Yu. Cherukhin:
Lower Bounds for Boolean Circuits with Finite Depth and Arbitrary Gates. - Elena Grigorescu, Tali Kaufman, Madhu Sudan:
2-Transitivity is Insufficient for Local Testability. - Dan Gutfreund, Guy N. Rothblum:
The Complexity of Local List Decoding. - James I. Lathrop, Jack H. Lutz, Scott M. Summers:
Strict Self-Assembly of Discrete Sierpinski Triangles. - Venkatesan Guruswami, Atri Rudra:
Soft decoding, dual BCH codes, and better list-decodable eps-biased codes. - Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo:
Curves That Must Be Retraced. - Eric Allender, Michal Koucký:
Amplifying Lower Bounds by Means of Self-Reducibility. - Oded Goldreich, Dana Ron:
Algorithmic Aspects of Property Testing in the Dense Graphs Model. - Sourav Chakraborty, László Babai:
Property Testing of Equivalence under a Permutation Group Action. - Oded Goldreich, Dana Ron:
On Proximity Oblivious Testing. - Zeev Dvir:
Deterministic Extractors for Algebraic Sources. - Gábor Ivanyos, Marek Karpinski, Nitin Saxena:
Schemes for Deterministic Polynomial Factoring. - Miki Hermann, Reinhard Pichler:
Complexity of Counting the Optimal Solutions. - Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan:
Dense Subsets of Pseudorandom Sets. - Nikhil R. Devanur, Lance Fortnow:
A Computational Theory of Awareness and Decision Making. - Vijay V. Vazirani, Lei Wang:
Continuity Properties of Equilibria in Some Fisher and Arrow-Debreu Market Models. - Meena Mahajan, B. V. Raghavendra Rao:
Arithmetic circuits, syntactic multilinearity, and the limitations of skew formulae. - Vikraman Arvind, Partha Mukhopadhyay:
Derandomizing the Isolation Lemma and Lower Bounds for Noncommutative Circuit Size. - Manoj Prabhakaran, Mike Rosulek:
Cryptographic Complexity of Multi-party Computation Problems: Classifications and Separations. - Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter W. Shor:
The Power of Unentanglement. - Vikraman Arvind, T. C. Vijayaraghavan:
The Orbit problem is in the GapL Hierarchy. - Stephen A. Fenner, William I. Gasarch, Brian Postow:
The complexity of learning SUBSEQ(A). - Venkatesan Guruswami, Atri Rudra:
Concatenated codes can achieve list-decoding capacity. - Ryan O'Donnell:
Some Topics in Analysis of Boolean Functions. - Beate Bollig:
On the OBDD complexity of the most significant bit of integer multiplication. - Alexander A. Sherstov:
Communication Lower Bounds Using Dual Polynomials. - Zeev Dvir, Avi Wigderson:
Kakeya sets, new mergers and old extractors. - Farid M. Ablayev, Alexander Vasiliev:
On the Computation of Boolean Functions by Quantum Branching Programs via Fingerprinting. - James R. Lee, Prasad Raghavendra:
Coarse Differentiation and Multi-flows in Planar Graphs. - Paul Beame, Dang-Trinh Huynh-Ngoc:
Multiparty Communication Complexity of AC^0. - Manindra Agrawal, V. Vinay:
Arithmetic Circuits: A Chasm at Depth Four. - Moritz Müller:
Valiant-Vazirani Lemmata for Various Logics. - Or Meir:
On the Efficiency of Non-Uniform PCPP Verifiers. - Noga Alon, Rina Panigrahy, Sergey Yekhanin:
Deterministic Approximation Algorithms for the Nearest Codeword Problem. - Noga Alon, Shai Gutner:
Kernels for the Dominating Set Problem on Graphs with an Excluded Minor. - Scott Aaronson:
On Perfect Completeness for QMA. - Lior Malka:
Instance-Dependent Commitment Schemes and the Round Complexity of Perfect Zero-Knowledge Proofs. - Klim Efremenko:
3-Query Locally Decodable Codes of Subexponential Length. - Dana Moshkovitz, Ran Raz:
Two Query PCP with Sub-Constant Error. - Shachar Lovett, Tali Kaufman:
Worst case to Average case reductions for polynomials. - Dmitry Itsykson:
Structural complexity of AvgBPP. - Neeraj Kayal, Timur Nezhmetdinov:
Factoring groups efficiently. - Olaf Beyersdorff, Johannes Köbler, Sebastian Müller:
Nondeterministic Instance Complexity and Proof Systems with Advice. - Ryan Williams:
Non-Linear Time Lower Bound for (Succinct) Quantified Boolean Formulas. - Felix Brandt, Felix A. Fischer, Markus Holzer:
On Iterated Dominance, Matrix Elimination, and Matched Paths. - Debajyoti Bera, Stephen A. Fenner, Frederic Green, Steven Homer:
Universal Quantum Circuits. - Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, Avi Wigderson:
Uniform Direct-Product Theorems: Simplified, Optimized, and Derandomized. - Ido Ben-Eliezer, Rani Hod, Shachar Lovett:
Random low degree polynomials are hard to approximate. - Alexander A. Razborov:
A simple proof of Bazzi's theorem. - Paul Beame, Dang-Trinh Huynh-Ngoc:
Multiparty Communication Complexity and Threshold Circuit Size of AC^0. - Yijia Chen, Jörg Flum:
A logic for PTIME and a parameterized halting problem. - Sanjeeb Dash:
On the complexity of cutting plane proofs using split cuts. - Farid M. Ablayev, Airat Khasianov, Alexander Vasiliev:
On Complexity of Quantum Branching Programs Computing Equality-like Boolean Functions. - Vikraman Arvind, Partha Mukhopadhyay:
Quantum Query Complexity of Multilinear Identity Testing. - Tomás Feder, Carlos S. Subi:
Nearly Tight Bounds on the Number of Hamiltonian Circuits of the Hypercube and Generalizations (revised). - Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie:
Testing Linear-Invariant Non-Linear Properties. - Noam Berger, Nevin Kapur, Leonard J. Schulman, Vijay V. Vazirani:
Solvency Games. - Ulrich Schöpp, Martin Hofmann:
Pointer Programs and Undirected Reachability. - Vitaly Feldman:
On The Power of Membership Queries in Agnostic Learning. - Scott Aaronson, John Watrous:
Closed Timelike Curves Make Quantum and Classical Computing Equivalent. - Cristopher Moore, Alexander Russell:
A simple constant-probability RP reduction from NP to Parity P. - Piotr Berman, Marek Karpinski, Alexander Zelikovsky:
1.25 Approximation Algorithm for the Steiner Tree Problem with Distances One and Two. - Brendan Juba, Madhu Sudan:
Universal Semantic Communication II: A Theory of Goal-Oriented Communication. - Andrew Drucker:
Multitask Efficiencies in the Decision Tree Model. - Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg:
Hierarchy Theorems for Property Testing. - Victor Chen:
A Hypergraph Dictatorship Test with Perfect Completeness. - Gábor Ivanyos, Marek Karpinski, Lajos Rónyai, Nitin Saxena:
Trading GRH for algebra: algorithms for factoring polynomials and related structures. - Chris Peikert:
Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem. - Marek Karpinski, Warren Schudy:
Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems. - Adi Akavia:
Finding Significant Fourier Transform Coefficients Deterministically and Locally. - Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan:
Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution. - Madhur Tulsiani:
CSP Gaps and Reductions in the Lasserre Hierarchy. - Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra:
List Decoding Tensor Products and Interleaved Codes. - Jack H. Lutz:
A Divergence Formula for Randomness and Dimension. - Zenon Sadowski:
Optimal Proof Systems and Complete Languages. - Nitin Saxena, C. Seshadhri:
An Almost Optimal Rank Bound for Depth-3 Identities. - Marc Kaplan, Sophie Laplante:
Kolmogorov complexity and combinatorial methods in communication complexity. - Chris Calabro:
A Lower Bound on the Size of Series-Parallel Graphs Dense in Long Paths. - Shachar Lovett, Tali Kaufman:
The List-Decoding Size of Reed-Muller Codes.
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-12-12 20:59 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: