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

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