default search action
Electronic Colloquium on Computational Complexity, 2007
Volume TR07, 2007
- Stefan S. Dantchev, Barnaby Martin
, Stefan Szeider:
Parameterized Proof Complexity: a Complexity Gap for Parameterized Tree-like Resolution. - Moti Yung, Yunlei Zhao:
Concurrent Knowledge-Extraction in the Public-Key Model. - Jin-yi Cai, Pinyan Lu:
Bases Collapse in Holographic Algorithms. - Lance Fortnow, Rahul Santhanam:
Time Hierarchies: A Survey. - Rahul Santhanam:
Circuit Lower Bounds for Merlin-Arthur Classes. - David P. Woodruff:
New Lower Bounds for General Locally Decodable Codes. - Jan Krajícek:
An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams. - Philipp Weis, Neil Immerman:
Structure Theorem and Strict Alternation Hierarchy for FO^2 on Words. - Nathan Segerlind:
Nearly-Exponential Size Lower Bounds for Symbolic Quantifier Elimination Algorithms and OBDD-Based Proofs of Unsatisfiability. - Arist Kojevnikov:
Improved Lower Bounds for Resolution over Linear Inequalities. - Bodo Manthey:
On Approximating Restricted Cycle Covers. - Shachar Lovett, Sasha Sodin:
Almost Euclidean sections of the N-dimensional cross-polytope using O(N) random bits. - Andris Ambainis, Joseph Emerson:
Quantum t-designs: t-wise independence in the quantum world. - Amit Chakrabarti:
Lower Bounds for Multi-Player Pointer Jumping. - Oded Goldreich, Or Sheffet:
On the randomness complexity of property testing. - Prasad Raghavendra:
A Note on Yekhanin's Locally Decodable Codes. - Ashish Rastogi, Richard Cole:
Indivisible Markets with Good Approximate EquilibriumPrices. - Christian Glaßer, Alan L. Selman, Liyu Zhang:
The Informational Content of Canonical Disjoint NP-Pairs. - Jin-yi Cai, Pinyan Lu:
On Block-wise Symmetric Signatures for Matchgates. - Jin-yi Cai, Pinyan Lu:
Holographic Algorithms: The Power of Dimensionality Resolved. - Brett Hemenway, Rafail Ostrovsky:
Public Key Encryption Which is Simultaneously a Locally-Decodable Error-Correcting Code. - Rafail Ostrovsky, William E. Skeith III:
Algebraic Lower Bounds for Computing on Encrypted Data. - Heribert Vollmer, Michael Bauland, Elmar Böhler, Nadia Creignou, Steffen Reith, Henning Schnoor:
The Complexity of Problems for Quantified Constraints. - László Egri, Benoît Larose, Pascal Tesson:
Symmetric Datalog and Constraint Satisfaction Problems in Logspace. - Benoît Larose, Pascal Tesson:
Universal Algebra and Hardness Results for Constraint Satisfaction Problems. - Dana Moshkovitz, Ran Raz:
Sub-Constant Error Probabilistically Checkable Proof of Almost Linear Size. - Tobias Friedrich, Jun He, Nils Hebbinghaus, Frank Neumann, Carsten Witt:
Approximating Covering Problems by Randomized Search Heuristics Using Multi-Objective Models. - Daniel Sawitzki:
Implicit Simulation of FNC Algorithms. - Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto:
A Dichotomy Theorem within Schaefer for the Boolean Connectivity Problem. - Kai-Min Chung, Omer Reingold, Salil P. Vadhan:
S-T Connectivity on Digraphs with a Known Stationary Distribution. - Yael Tauman Kalai, Ran Raz:
Interactive PCP. - Pavel Pudlák:
Quantum deduction rules. - Michael Navon, Alex Samorodnitsky:
Linear programming bounds for codes via a covering argument. - Anup Rao:
An Exposition of Bourgain's 2-Source Extractor. - Mark Braverman, Raghav Kulkarni, Sambuddha Roy:
Parity Problems in Planar Graphs. - Ryan Williams:
Time-Space Tradeoffs for Counting NP Solutions Modulo Integers. - Leonid Gurvits:
Polynomial time algorithms to approximate mixed volumes within a simply exponential factor. - Iftach Haitner, Jonathan J. Hoch, Omer Reingold, Gil Segev:
Finding Collisions in Interactive Protocols -- A Tight Lower Bound on the Round Complexity of Statistically-Hiding Commitments. - Bodo Manthey, Till Tantau:
Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise. - Kiran S. Kedlaya, Sergey Yekhanin:
Locally Decodable Codes From Nice Subsets of Finite Fields and Prime Factors of Mersenne Numbers. - Nicola Galesi, Massimo Lauria:
Extending Polynomial Calculus to $k$-DNF Resolution. - Zohar Shay Karnin, Amir Shpilka:
Black Box Polynomial Identity Testing of Depth-3 Arithmetic Circuits with Bounded Top Fan-in. - Uriel Feige, Guy Kindler, Ryan O'Donnell:
Understanding Parallel Repetition Requires Understanding Foams. - Philipp Hertel, Toniann Pitassi:
Black-White Pebbling is PSPACE-Complete. - Heribert Vollmer:
The complexity of deciding if a Boolean function can be computed by circuits over a restricted basis. - Philipp Hertel, Toniann Pitassi:
An Exponential Time/Space Speedup For Resolution. - Shafi Goldwasser, Dan Gutfreund, Alexander Healy, Tali Kaufman, Guy N. Rothblum:
A (De)constructive Approach to Program Checking. - Alexandr Andoni, Piotr Indyk, Robert Krauthgamer:
Earth Mover Distance over High-Dimensional Spaces. - Beate Bollig, Niko Range, Ingo Wegener:
Exact OBDD Bounds for some Fundamental Functions. - Arkadev Chattopadhyay:
Discrepancy and the power of bottom fan-in in depth-three circuits. - Pilar Albert, Elvira Mayordomo, Philippe Moser:
Bounded Pushdown dimension vs Lempel Ziv information density. - Li Chen, Bin Fu:
Linear and Sublinear Time Algorithms for the Basis of Abelian Groups. - Jens Groth, Amit Sahai:
Efficient Non-interactive Proof Systems for Bilinear Groups. - Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur:
Testing Properties of Constraint-Graphs. - Oliver Kullmann:
Constraint satisfaction problems in clausal form: Autarkies and minimal unsatisfiability. - Zeev Dvir, Ariel Gabizon, Avi Wigderson:
Extractors and Rank Extractors for Polynomial Sources. - Oded Goldreich:
On the Average-Case Complexity of Property Testing. - Dmitry Gavinsky:
Classical Interaction Cannot Replace a Quantum Message. - Shankar Kalyanaraman, Christopher Umans:
Algorithms for Playing Games with Limited Randomness. - Tali Kaufman, Madhu Sudan:
Sparse Random Linear Codes are Locally Decodable and Testable. - Or Meir:
On the Rectangle Method in proofs of Robustness of Tensor Products. - Oded Goldreich, Or Meir:
The Tensor Product of Two Good Codes Is Not Necessarily Robustly Testable. - Tomás Feder, Carlos S. Subi:
Nearly Tight Bounds on the Number of Hamiltonian Circuits of the Hypercube and Generalizations. - Rahul Jain, Hartmut Klauck, Ashwin Nayak:
Direct Product Theorems for Communication Complexity via Subdistribution Bounds. - Jonathan Katz:
Which Languages Have 4-Round Zero-Knowledge Proofs?. - Christian Hundt, Maciej Liskiewicz:
A Combinatorial Geometric Approach to Linear Image Matching. - Paul G. Spirakis, Haralampos Tsaknakis:
Computing 1/3-approximate Nash equilibria of bimatrix games in polynomial time.. - Thomas Thierauf, Fabian Wagner:
The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace. - Ronen Shaltiel, Christopher Umans:
Low-end uniform hardness vs. randomness tradeoffs for AM. - Nir Ailon, Edo Liberty:
Fast Dimension Reduction Using Rademacher Series on Dual BCH Codes. - Jacobo Torán:
Reductions to Graph Isomorphism. - Alexander A. Sherstov:
Communication Complexity under Product and Nonproduct Distributions. - Parikshit Gopalan, Subhash Khot, Rishi Saket:
Hardness of Reconstructing Multivariate Polynomials over Finite Fields. - Dmitry Gavinsky, Pavel Pudlák:
Exponential Separation of Quantum and Classical Non-Interactive Multi-Party Communication Complexity. - Shachar Lovett:
Unconditional pseudorandom generators for low degree polynomials. - Satyen Kale, C. Seshadhri:
Testing Expansion in Bounded Degree Graphs. - Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. Servedio, Andrew Wan:
Testing for Concise Representations. - Ran Raz, Iddo Tzameret:
Resolution over Linear Equations and Multilinear Proofs. - Emanuele Viola, Avi Wigderson:
One-way multi-party communication lower bound for pointer jumping with applications. - Chris Peikert, Brent Waters:
Lossy Trapdoor Functions and Their Applications. - Andrej Bogdanov, Emanuele Viola:
Pseudorandom bits for polynomials. - Christian Borgs, Jennifer T. Chayes, Nicole Immorlica, Adam Kalai, Vahab S. Mirrokni, Christos H. Papadimitriou:
The Myth of the Folk Theorem. - Artur Czumaj, Asaf Shapira, Christian Sohler
Testing Hereditary Properties of Non-Expanding Bounded-Degree Graphs. - Brendan Juba, Madhu Sudan:
Universal Semantic Communication I. - Ran Raz, Amir Yehudayoff:
Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors. - Venkatesan Guruswami, James R. Lee, Alexander A. Razborov:
Almost Euclidean subspaces of ℓ1N via expander codes. - Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao:
Arithmetizing classes around NC^1 and L. - Elad Hazan, C. Seshadhri:
Adaptive Algorithms for Online Decision Problems. - Parikshit Gopalan, Venkatesan Guruswami:
Deterministic Hardness Amplification via Local GMD Decoding. - Shachar Lovett:
Tight lower bounds for adaptive linearity tests. - Martin Grohe:
Logic, Graphs, and Algorithms. - Piotr Berman, Bhaskar DasGupta:
Approximating the Online Set Multicover Problems Via Randomized Winnowing. - Andrei A. Bulatov:
The complexity of the counting constraint satisfaction problem. - Christian Glaßer, Heinz Schmitz, Victor L. Selivanov:
Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages. - Vikraman Arvind, Partha Mukhopadhyay:
The Ideal Membership Problem and Polynomial Identity Testing. - Lance Fortnow, Rahul Santhanam:
Infeasibility of Instance Compression and Succinct PCPs for NP. - Miklós Ajtai, Cynthia Dwork:
The First and Fourth Public-Key Cryptosystems with Worst-Case/Average-Case Equivalence.. - Tali Kaufman, Simon Litsyn, Ning Xie:
Breaking the ε-Soundness Bound of the Linearity Test over GF(2). - Dieter van Melkebeek:
A Survey of Lower Bounds for Satisfiability and Related Problems. - Alexander A. Sherstov:
The Pattern Matrix Method for Lower Bounds on Quantum Communication. - Patrick Briest, Martin Hoefer, Piotr Krysta:
Stackelberg Network Pricing Games. - Andrej Bogdanov, Muli Safra
Hardness amplification for errorless heuristics. - Emanuele Viola:
Selected Results in Additive Combinatorics: An Exposition. - Moses Charikar, Konstantin Makarychev, Yury Makarychev:
On the Advantage over Random for Maximum Acyclic Subgraph. - Jelani Nelson:
A Note on Set Cover Inapproximability Independent of Universe Size. - Yijia Chen, Martin Grohe, Magdalena Grüber:
On Parameterized Approximability. - Nathan Segerlind, Toniann Pitassi:
Exponential lower bounds and integrality gaps for tree-like Lovasz-Schrijver procedures. - Moses Charikar, Konstantin Makarychev, Yury Makarychev:
Local Global Tradeoffs in Metric Embeddings. - Venkatesan Guruswami, Atri Rudra:
Better Binary List-Decodable Codes via Multilevel Concatenation. - Beate Bollig:
The Optimal Read-Once Branching Program Complexity for the Direct Storage Access Function. - Tali Kaufman, Madhu Sudan:
Algebraic Property Testing: The Role of Invariance. - Alexander A. Sherstov:
Unbounded-Error Communication Complexity of Symmetric Functions. - Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar, Lisa Zhang:
Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs. - Jakob Nordström:
A Simplified Way of Proving Trade-off Results for Resolution. - Or Meir:
Combinatorial Construction of Locally Testable Codes. - Alexander A. Sherstov:
Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions. - Edward A. Hirsch, Dmitry Itsykson:
An infinitely-often one-way function based on an average-case assumption. - Asaf Nachmias, Asaf Shapira:
Testing the Expansion of a Graph. - Piotr Berman, Bhaskar DasGupta, Marek Karpinski:
Approximating Transitive Reductions for Directed Networks. - Moran Feldman, Guy Kortsarz, Zeev Nutov:
Improved approximation algorithms for directed Steiner forest. - Zeev Dvir, Amir Shpilka, Amir Yehudayoff:
Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits. - Zeev Dvir, Amir Shpilka:
Towards Dimension Expanders Over Finite Fields. - Shachar Lovett, Roy Meshulam, Alex Samorodnitsky:
Inverse Conjecture for the Gowers norm is false. - Nitin Saxena:
Diagonal Circuit Identity Testing and Lower Bounds. - Ali Juma, Valentine Kabanets, Charles Rackoff, Amir Shpilka:
The black-box query complexity of polynomial summation. - Nathan Segerlind:
On the relative efficiency of resolution-like proofs and ordered binary decision diagram proofs. - Arie Matsliah, Eli Ben-Sasson, Prahladh Harsha, Oded Lachish:
Sound 3-query PCPPs are Long. - Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio:
Testing Halfspaces. - Jeffrey C. Jackson, Homin K. Lee, Rocco A. Servedio, Andrew Wan:
Learning Random Monotone DNF. - Ronen Shaltiel, Emanuele Viola:
Hardness amplification proofs require majority. - Satyen Kale:
Boosting and hard-core set constructions: a simplified approach. - Emanuele Viola:
The sum of d small-bias generators fools polynomials of degree d. - Craig Gentry, Chris Peikert, Vinod Vaikuntanathan:
Trapdoors for Hard Lattices and New Cryptographic Constructions. - Jeff Kinne, Dieter van Melkebeek:
Space Hierarchy Results for Randomized and Other Semantic Models. - Paul Valiant:
Testing Symmetric Properties of Distributions. - Felix Brandt, Felix A. Fischer, Markus Holzer:
Equilibria of Graphical Games with Symmetries. - Yijia Chen, Jörg Flum, Moritz Müller:
Lower Bounds for Kernelizations.
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-11 20:33 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: