Electronic Colloquium on Computational Complexity, Volume 12, 2005

Volume 12, 2005

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