Electronic Colloquium on Computational Complexity, Volume 14, 2007

Volume 14, 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, Benoit Larose, Pascal Tesson:
  Symmetric Datalog and Constraint Satisfaction Problems in Logspace.
  
• Benoit 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 $\ell_1^N$ 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 Glasser, 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 $\epsilon$-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.
  
• Sharon 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.
  

Last update Fri May 24 20:16:59 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page