Electronic Colloquium on Computational Complexity, Volume 14, 2007

Volume 14, 2007

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