Electronic Colloquium on Computational Complexity, Volume 15, 2008

Volume 15, 2008

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