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

Electronic Colloquium on Computational Complexity, Volume 12, 2005

Volume 12, 2005

  1. Mario Szegedy:
    Near optimality of the priority sampling procedure.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  2. Magnus Bordewich, Martin E. Dyer, Marek Karpinski:
    Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  3. Scott Aaronson:
    Quantum Computing, Postselection, and Probabilistic Polynomial-Time.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  4. Leslie G. Valiant:
    Memorization and Association on a Realistic Neural Model.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  5. Tomás Feder:
    Constraint Satisfaction on Finite Groups with Near Subgroups.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  6. Edward A. Hirsch, Sergey I. Nikolenko:
    Simulating Cutting Plane proofs with restricted degree of falsity by Resolution.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  7. Vadim Lyubashevsky:
    On Random High Density Subset Sums.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  8. Neeraj Kayal:
    Recognizing permutation functions in polynomial time.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  9. David P. Woodruff, Sergey Yekhanin:
    A Geometric Approach to Information-Theoretic Private Information Retrieval.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  10. Olivier Powell:
    Almost Completeness in Small Complexity Classes.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  11. Christian Glaßer, Mitsunori Ogihara, Aduri Pavan, Alan L. Selman, Liyu Zhang:
    Autoreducibility, Mitoticity, and Immunity.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  12. Luca Trevisan, Salil P. Vadhan, David Zuckerman:
    Compression of Samplable Sources.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  13. Bin Fu:
    Theory and Application of Width Bounded Geometric Separator.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  14. Oded Goldreich:
    Short Locally Testable Codes and Proofs (Survey).
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  15. Andrej Bogdanov, Luca Trevisan:
    On Worst-Case to Average-Case Reductions for NP Problems.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  16. Tomás Feder, Daniel K. Ford:
    Classification of Bipartite Boolean Constraint Satisfaction through Delta-Matroid Intersection.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  17. Phuong Nguyen:
    Two-Sorted Theories for L, SL, NL and P.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  18. Oded Goldreich:
    On Promise Problems (a survey in memory of Shimon Even [1935-2004]).
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  19. Venkatesan Guruswami, Atri Rudra:
    Tolerant Locally Testable Codes.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  20. Sourav Chakraborty:
    On the Sensitivity of Cyclically-Invariant Boolean Functions.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  21. Stasys Jukna:
    Disproving the single level conjecture.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  22. Omer Reingold, Luca Trevisan, Salil P. Vadhan:
    Pseudorandom Walks in Biregular Graphs and the RL vs. L Problem.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  23. Robert H. Sloan, Balázs Szörényi, György Turán:
    On k-term DNF with largest number of prime implicants.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  24. Michael Bauland, Elmar Böhler, Nadia Creignou, Steffen Reith, Henning Schnoor, Heribert Vollmer:
    Quantified Constraints: The Complexity of Decision and Counting for Bounded Alternation.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  25. Zeev Dvir, Ran Raz:
    Analyzing Linear Mergers.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  26. Scott Aaronson:
    NP-complete Problems and Physical Reality.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  27. Daniel Rolf:
    Derandomization of PPSZ for Unique-k-SAT.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  28. Elmar Böhler:
    On the Lattice of Clones Below the Polynomial Time Functions.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  29. Frank Neumann, Marco Laumanns:
    Speeding Up Approximation Algorithms for NP-hard Spanning Forest Problems by Multi-objective Optimization.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  30. Evgeny Dantsin, Alexander Wolpert:
    An Improved Upper Bound for SAT.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  31. Carme Àlvarez, Joaquim Gabarró, Maria J. Serna:
    Pure Nash equilibria in games with a large number of actions.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  32. Gudmund Skovbjerg Frandsen, Peter Bro Miltersen:
    Reviewing Bounds on the Circuit Size of the Hardest Functions.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  33. Martin Fürer, Shiva Prasad Kasiviswanathan:
    Algorithms for Counting 2-SAT Solutions and Colorings with Applications.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  34. Luca Trevisan:
    Approximation Algorithms for Unique Games.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  35. Christian Glaßer, Stephen D. Travers, Klaus W. Wagner:
    A Reducibility that Corresponds to Unbalanced Leaf-Language Classes.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  36. Hubie Chen:
    Quantified Constraint Satisfaction, Maximal Constraint Languages, and Symmetric Polymorphisms.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  37. Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen:
    On the Complexity of Numerical Analysis.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  38. Ran Raz:
    Quantum Information and the PCP Theorem.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  39. Irit Dinur, Elchanan Mossel, Oded Regev:
    Conditional Hardness for Approximate Coloring.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  40. Scott Aaronson:
    Oracles Are Subtle But Not Malicious.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  41. Shengyu Zhang:
    (Almost) tight bounds for randomized and quantum Local Search on hypercubes and grids.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  42. Lance Fortnow, Adam R. Klivans:
    Linear Advice for Randomized Logarithmic Space.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  43. Emanuele Viola:
    Pseudorandom Bits for Constant-Depth Circuits with Few Arbitrary Symmetric Gates.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  44. Zeev Dvir, Amir Shpilka:
    Locally Decodable Codes with 2 queries and Polynomial Identity Testing for depth 3 circuits.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  45. Philippe Moser:
    Martingale Families and Dimension in P.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  46. Irit Dinur:
    The PCP theorem by gap amplification.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  47. Kooshiar Azimian, Mahmoud Salmasizadeh, Javad Mohajeri:
    Weak Composite Diffie-Hellman is not Weaker than Factoring.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  48. Moti Yung, Yunlei Zhao:
    Constant-Round Concurrently-Secure rZK in the (Real) Bare Public-Key Model.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  49. Joan Boyar, René Peralta:
    The Exact Multiplicative Complexity of the Hamming Weight Function.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  50. Uriel Feige, Eran Ofek:
    Finding a Maximum Independent Set in a Sparse Random Graph.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  51. Predrag T. Tosic:
    On Complexity of Counting Fixed Points in Certain Classes of Graph Automata.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  52. Grant Schoenebeck, Salil P. Vadhan:
    The Computational Complexity of Nash Equilibria in Concisely Represented Games.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  53. Paul Beame, Toniann Pitassi, Nathan Segerlind:
    Lower bounds for Lovasz-Schrijver systems and beyond follow from multiparty communication complexity.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  54. Konstantin Pervyshev:
    Time Hierarchies for Computations with a Bit of Advice.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  55. Bruno Codenotti, Amin Saberi, Kasturi R. Varadarajan, Yinyu Ye:
    Leontief Economies Encode Nonzero Sum Two-Player Games.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  56. Alexis C. Kaporis, Efpraxia Politopoulou, Paul G. Spirakis:
    The Price of Optimum in Stackelberg Games.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  57. Venkatesan Guruswami, Valentine Kabanets:
    Hardness amplification via space-efficient direct products.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  58. Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra:
    On Non-Approximability for Quadratic Programs.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  59. Víctor Dalmau, Ricard Gavaldà, Pascal Tesson, Denis Thérien:
    Tractable Clones of Polynomials over Semigroups.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  60. Philippe Moser:
    Generic Density and Small Span Theorem.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  61. Ronen Gradwohl, Guy Kindler, Omer Reingold, Amnon Ta-Shma:
    On the Error Parameter of Dispersers.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  62. Aduri Pavan, N. V. Vinodchandran:
    2-Local Random Reductions to 3-Valued Functions.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  63. Bodo Manthey, Rüdiger Reischuk:
    Smoothed Analysis of the Height of Binary Search Trees.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  64. Howard J. Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani:
    On earthmover distance, metric labeling, and 0-extension.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  65. Alexander I. Barvinok, Alex Samorodnitsky:
    Random Weighting, Asymptotic Counting, and Inverse Isoperimetry .
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  66. Jakob Nordström:
    Narrow Proofs May Be Spacious: Separating Space and Width in Resolution.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  67. Zeev Dvir, Amir Shpilka:
    An Improved Analysis of Mergers.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  68. Christian Glaßer, Aduri Pavan, Alan L. Selman, Liyu Zhang:
    Redundancy in Complete Sets.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  69. Piotr Berman, Marek Karpinski:
    8/7-Approximation Algorithm for (1,2)-TSP.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  70. Mahdi Cheraghchi:
    On Matrix Rigidity and the Complexity of Linear Forms.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  71. Marius Zimand:
    Simple extractors via constructions of cryptographic pseudo-random generators.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  72. Christian Glaßer, Alan L. Selman, Liyu Zhang:
    Survey of Disjoint NP-Pairs and Relations to Propositional Proof Systems.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  73. Oded Goldreich, Dana Ron:
    Approximating Average Parameters of Graphs.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  74. Li-Sha Huang, Xiaotie Deng:
    On Complexity of Market Equilibria with Maximum Social Welfare.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  75. Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum:
    Dobrushin conditions and Systematic Scan.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  76. Dima Grigoriev, Edward A. Hirsch, Konstantin Pervyshev:
    Time hierarchies for cryptographic function inversion with advice.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  77. Zenon Sadowski:
    On a D-N-optimal acceptor for TAUT.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  78. Kooshiar Azimian, Javad Mohajeri, Mahmoud Salmasizadeh, Siamak Fayyaz Shahandashti:
    A Verifiable Partial Key Escrow, Based on McCurley Encryption Scheme.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  79. Stasys Jukna:
    Expanders and time-restricted branching programs.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  80. Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider:
    Proving NP-hardness for clique-width I: non-approximability of sequential clique-width.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  81. Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider:
    Proving NP-hardness for clique-width II: non-approximability of clique-width.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  82. Jorge Castro:
    On the Query Complexity of Quantum Learners.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  83. Olaf Beyersdorff:
    Disjoint NP-Pairs from Propositional Proof Systems.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  84. Mickey Brautbar, Alex Samorodnitsky:
    Approximating the entropy of large alphabets.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  85. Asaf Shapira, Noga Alon:
    Homomorphisms in Graph Property Testing - A Survey.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  86. Dana Moshkovitz, Ran Raz:
    Sub-Constant Error Low Degree Test of Almost Linear Size.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  87. Alexander Healy, Emanuele Viola:
    Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  88. Jan Arpe:
    Learning Juntas in the Presence of Noise.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  89. Xiaoyang Gu, Jack H. Lutz, Philippe Moser:
    Dimensions of Copeland-Erdös Sequences.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  90. Paul W. Goldberg, Christos H. Papadimitriou:
    Reducibility Among Equilibrium Problems.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  91. Predrag T. Tosic:
    Counting Fixed Points and Gardens of Eden of Sequential Dynamical Systems on Planar Bipartite Graphs .
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  92. Eyal Rozenman, Salil P. Vadhan:
    Derandomized Squaring of Graphs.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  93. Daniele Micciancio, Shien Jin Ong, Amit Sahai, Salil P. Vadhan:
    Concurrent Zero Knowledge without Complexity Assumptions.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  94. Michal Parnas, Dana Ron:
    On Approximating the Minimum Vertex Cover in Sublinear Time and the Connection to Distributed Algorithms.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  95. Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, Nikolai K. Vereshchagin:
    Partitioning multi-dimensional sets in a small number of ``uniform'' parts.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  96. Boaz Barak, Amit Sahai:
    How To Play Almost Any Mental Game Over The Net - Concurrent Composition via Super-Polynomial Simulation.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  97. Jens Groth, Rafail Ostrovsky, Amit Sahai:
    Perfect Non-Interactive Zero Knowledge for NP.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  98. Oded Goldreich:
    Bravely, Moderately: A Common Theme in Four Recent Results.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  99. Leslie G. Valiant:
    Holographic Algorithms.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  100. David Zuckerman:
    Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  101. Guy Kindler, Ryan O'Donnell, Subhash Khot, Elchanan Mossel:
    Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  102. Evgeny Dantsin, Edward A. Hirsch, Alexander Wolpert:
    Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  103. Leonid Gurvits:
    A proof of hyperbolic van der Waerden conjecture : the right generalization is the ultimate simplification.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  104. Don Coppersmith, Atri Rudra:
    On the Robust Testability of Product of Codes.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  105. Lance Fortnow, John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran, Fengming Wang:
    Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  106. Anup Rao:
    Extractors for a Constant Number of Polynomial Min-Entropy Independent Sources.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  107. Avi Wigderson, David Xiao:
    A Randomness-Efficient Sampler for Matrix-valued Functions and Applications.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  108. Ariel Gabizon, Ran Raz:
    Deterministic Extractors for Affine Sources over Large Fields.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  109. Ariel Gabizon, Ran Raz, Ronen Shaltiel:
    Deterministic Extractors for Bit-fixing Sources by Obtaining an Independent Seed.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  110. Saurabh Sanghvi, Salil P. Vadhan:
    The Round Complexity of Two-Party Random Selection.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  111. Dieter van Melkebeek, Konstantin Pervyshev:
    A Generic Time Hierarchy for Semantic Models With One Bit of Advice.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  112. Eran Ofek:
    On the expansion of the giant component in percolated (n,d,lambda) graphs.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  113. Bernhard Fuchs:
    On the Hardness of Range Assignment Problems.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  114. Boaz Barak, Shien Jin Ong, Salil P. Vadhan:
    Derandomization in Cryptography.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  115. Konstantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou:
    The complexity of computing a Nash equilibrium.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  116. Alex Samorodnitsky, Luca Trevisan:
    Gowers Uniformity, Influence of Variables, and PCPs.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  117. Piotr Indyk, David P. Woodruff:
    Polylogarithmic Private Approximations and Efficient Matching.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  118. Jin-yi Cai, Vinay Choudhary:
    Valiant's Holant Theorem and Matchgate Tensors.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  119. Nadia Creignou, Phokion G. Kolaitis, Bruno Zanuttini:
    Preferred representations of Boolean relations.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  120. Sashka Davis, Russell Impagliazzo:
    Models of Greedy Algorithms for Graph Problems.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  121. Martin E. Dyer, Leslie Ann Goldberg, Mike Paterson:
    On counting homomorphisms to directed acyclic graphs.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  122. Pavel Pudlák:
    A nonlinear bound on the number of wires in bounded depth circuits.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  123. Olaf Beyersdorff:
    Tuples of Disjoint NP-Sets.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  124. Kooshiar Azimian:
    Breaking Diffie-Hellman is no Easier than Root Finding.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  125. Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Amir Shpilka, Adam Smith:
    Sublinear Algorithms for Approximating String Compressibility and the Distribution Support Size.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  126. Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks:
    Minimizing DNF Formulas and AC0 Circuits Given a Truth Table.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  127. Vitaly Feldman:
    Hardness of Approximate Two-level Logic Minimization and PAC Learning with Membership Queries.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  128. Miroslava Sotáková:
    The normal form of reversible circuits consisting of CNOT and NOT gates.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  129. Scott Aaronson:
    QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  130. Ahuva Mu'alem:
    A Note on Testing Truthfulness.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  131. Don Coppersmith, Lisa Fleischer, Atri Rudra:
    Ordering by weighted number of wins gives a good ranking for weighted tournaments.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  132. Venkatesan Guruswami:
    Algebraic-geometric generalizations of the Parvaresh-Vardy codes.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  133. Venkatesan Guruswami, Atri Rudra:
    Explicit Capacity-Achieving List-Decodable Codes.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  134. Xi Chen, Xiaotie Deng:
    3-NASH is PPAD-Complete.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  135. Iftach Haitner, Danny Harnik, Omer Reingold:
    On the Power of the Randomized Iterate.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  136. Anna Gál, Michal Koucký, Pierre McKenzie:
    Incremental branching programs.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  137. Emanuele Viola:
    On Probabilistic Time versus Alternating Time.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  138. Peter Bürgisser, Felipe Cucker:
    Exotic quantifiers, complexity classes, and complete problems.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  139. Konstantinos Daskalakis, Christos H. Papadimitriou:
    Three-Player Games Are Hard.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  140. Xi Chen, Xiaotie Deng:
    Settling the Complexity of 2-Player Nash-Equilibrium.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  141. Amos Beimel, Paz Carmi, Kobbi Nissim, Enav Weinreb:
    Private Approximation of Search Problems.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  142. Vadim Lyubashevsky, Daniele Micciancio:
    Generalized Compact Knapsacks are Collision Resistant.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  143. Parikshit Gopalan:
    Constructing Ramsey Graphs from Boolean Function Representations.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  144. Lance Fortnow, Luis Antunes:
    Time-Bounded Universal Distributions.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  145. Ronen Shaltiel:
    How to get more mileage from randomness extractors.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  146. Gábor Erdélyi, Tobias Riege, Jörg Rothe:
    Quantum Cryptography: A Survey.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  147. Christian Glaßer, Stephen D. Travers:
    Machines that can Output Empty Words.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  148. Eric Allender, Samir Datta, Sambuddha Roy:
    The Directed Planar Reachability Problem.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  149. Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy:
    Grid Graph Reachability Problems.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  150. Neeraj Kayal, Nitin Saxena:
    Polynomial Identity Testing for Depth 3 Circuits.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  151. Magnus Bordewich, Martin E. Dyer, Marek Karpinski:
    Metric Construction, Stopping Times and Path Coupling.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  152. Oded Lachish, Ilan Newman:
    Languages that are Recognized by Simple Counter Automata are not necessarily Testable.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  153. Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur:
    Testing Orientation Properties.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  154. Albert Atserias:
    Non-Uniform Hardness for NP via Black-Box Adversaries.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  155. Amir Shpilka:
    Constructions of low-degree and error-correcting epsilon-biased sets.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  156. Jonathan A. Kelner, Daniel A. Spielman:
    A Randomized Polynomial-Time Simplex Algorithm for Linear Programming (Preliminary Version).
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  157. Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo:
    Points on Computable Curves.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  158. Chris Peikert, Alon Rosen:
    Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  159. Daniel Rolf:
    Improved Bound for the PPSZ/Schöning-Algorithm for 3-SAT.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  160. Xiaoyang Gu, Jack H. Lutz:
    Dimension Characterizations of Complexity Classes.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  161. John M. Hitchcock:
    Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  162. Yunlei Zhao, Jesper Buus Nielsen, Robert H. Deng, Dengguo Feng:
    Generic yet Practical ZK Arguments from any Public-Coin HVZK.
    Electronic Edition CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
  163. Dvir Falik, Alex Samorodnitsky:
    Edge-isoperimetric inequalities and influences.
    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)