dblp.uni-trier.de www.uni-trier.de

Electronic Colloquium on Computational Complexity, Volume 15, 2008

Volume 15, 2008

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

Copyright © Mon Nov 2 21:34:18 2009 by Michael Ley (ley@uni-trier.de)