Electronic Colloquium on Computational Complexity, Volume 13, 2006

Volume 13, 2006

1. Ran Raz, Iddo Tzameret:
   The Strength of Multilinear Proofs.
   Electronic Edition (link) BibTeX
2. Eyal Kaplan, Moni Naor, Omer Reingold:
   Derandomized Constructions of k-Wise (Almost) Independent Permutations.
   Electronic Edition (link) BibTeX
3. Joshua Buresh-Oppenheim, Rahul Santhanam:
   Making Hard Problems Harder.
   Electronic Edition (link) BibTeX
4. Jesper Torp Kristensen, Peter Bro Miltersen:
   Finding small OBDDs for incompletely specified truth tables is hard.
   Electronic Edition (link) BibTeX
5. Edith Elkind, Leslie Ann Goldberg, Paul W. Goldberg:
   Nash Equilibria in Graphical Games on Trees Revisited.
   Electronic Edition (link) BibTeX
6. Alexander Shen:
   Multisource algorithmic information theory.
   Electronic Edition (link) BibTeX
7. Mohammad Taghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour:
   Approximating Buy-at-Bulk k-Steiner trees.
   Electronic Edition (link) BibTeX
8. Mohammad Taghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour:
   Polylogarithmic Approximation Algorithm for Non-Uniform Multicommodity Buy-at-Bulk.
   Electronic Edition (link) BibTeX
9. Nutan Limaye, Meena Mahajan, Jayalal M. N. Sarma:
   Evaluating Monotone Circuits on Cylinders, Planes and Tori.
   Electronic Edition (link) BibTeX
10. Réka Albert, Bhaskar DasGupta, Riccardo Dondi, Eduardo D. Sontag:
    Inferring (Biological) Signal Transduction Networks via Transitive Reductions of Directed Graphs.
    Electronic Edition (link) BibTeX
11. Yijia Chen, Martin Grohe:
    An Isomorphism between Subexponential and Parameterized Complexity Theory.
    Electronic Edition (link) BibTeX
12. Bruno Codenotti, Mauro Leoncini, Giovanni Resta:
    Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Games .
    Electronic Edition (link) BibTeX
13. Luca Trevisan:
    Pseudorandomness and Combinatorial Constructions.
    Electronic Edition (link) BibTeX
14. Argimiro Arratia, Carlos E. Ortiz:
    On a syntactic approximation to logics that capture complexity classes.
    Electronic Edition (link) BibTeX
15. Tomás Feder, Carlos S. Subi:
    On Barnette's conjecture.
    Electronic Edition (link) BibTeX
16. Tomás Feder, Carlos S. Subi:
    Partition into k-vertex subgraphs of k-partite graphs.
    Electronic Edition (link) BibTeX
17. Toshiya Itoh:
    Improved Lower Bounds for Families of epsilon-Approximate k-Restricted Min-Wise Independent Permutations.
    Electronic Edition (link) BibTeX
18. Jin-yi Cai, Vinay Choudhary:
    On the Theory of Matchgate Computations.
    Electronic Edition (link) BibTeX
19. Janka Chlebíková, Miroslav Chlebík:
    Hardness of asymptotic approximation for orthogonal rectangle packing and covering problems.
    Electronic Edition (link) BibTeX
20. Akinori Kawachi, Tomoyuki Yamakami:
    Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding.
    Electronic Edition (link) BibTeX
21. Tomás Feder:
    Constraint satisfaction: a personal perspective.
    Electronic Edition (link) BibTeX
22. Danny Harnik, Moni Naor:
    On the Compressibility of NP Instances and Cryptographic Applications.
    Electronic Edition (link) BibTeX
23. Xi Chen, Xiaotie Deng, Shang-Hua Teng:
    Computing Nash Equilibria: Approximation and Smoothed Complexity.
    Electronic Edition (link) BibTeX
24. Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, Nikolai K. Vereshchagin:
    Inverting onto functions might not be hard.
    Electronic Edition (link) BibTeX
25. Leonid Gurvits:
    Hyperbolic Polynomials Approach to Van der Waerden/Schrijver-Valiant like Conjectures : \\ Sharper Bounds , Simpler Proofs and Algorithmic Applications.
    Electronic Edition (link) BibTeX
26. Ronen Gradwohl, Salil P. Vadhan, David Zuckerman:
    Random Selection with an Adversarial Majority.
    Electronic Edition (link) BibTeX
27. Hermann Gruber, Markus Holzer:
    Finding Lower Bounds for Nondeterministic State Complexity is Hard.
    Electronic Edition (link) BibTeX
28. Jonathan Katz, Chiu-Yuen Koo:
    On Expected Constant-Round Protocols for Byzantine Agreement.
    Electronic Edition (link) BibTeX
29. Deeparnab Chakrabarty, Nikhil R. Devanur, Vijay V. Vazirani:
    Eisenberg-Gale Markets: Rationality, Strongly Polynomial Solvability, and Competition Monotonicity.
    Electronic Edition (link) BibTeX
30. Piotr Berman, Jieun K. Jeong, Shiva Prasad Kasiviswanathan, Bhuvan Urgaonkar:
    Packing to angles and sectors.
    Electronic Edition (link) BibTeX
31. Li-Sha Huang, Shang-Hua Teng:
    On the Approximation and Smoothed Complexity of Leontief Market Equilibria.
    Electronic Edition (link) BibTeX
32. Vitaly Feldman:
    Optimal Hardness Results for Maximizing Agreements with Monomials.
    Electronic Edition (link) BibTeX
33. Amit Agarwal, Elad Hazan:
    Efficient Algorithms for Online Game Playing and Universal Portfolio Management.
    Electronic Edition (link) BibTeX
34. Moni Naor, Guy N. Rothblum:
    The Complexity of Online Memory Checking.
    Electronic Edition (link) BibTeX
35. Till Tantau:
    The Descriptive Complexity of the Reachability Problem As a Function of Different Graph Parameters.
    Electronic Edition (link) BibTeX
36. Tobias Riege, Jörg Rothe:
    Completeness in the Boolean Hierarchy: Exact-Four-Colorability, Minimal Graph Uncolorability, and Exact Domatic Number Problems.
    Electronic Edition (link) BibTeX
37. Xi Chen, Xiaotie Deng:
    On the Complexity of 2D Discrete Fixed Point Problem.
    Electronic Edition (link) BibTeX
38. David Doty, Jack H. Lutz, Satyadev Nandakumar:
    Finite-State Dimension and Real Arithmetic.
    Electronic Edition (link) BibTeX
39. John M. Hitchcock, Aduri Pavan:
    Comparing Reductions to NP-Complete Sets.
    Electronic Edition (link) BibTeX
40. Tomás Feder, Gagan Aggarwal, Rajeev Motwani, An Zhu:
    Channel assignment in wireless networks and classification of minimum graph homomorphism.
    Electronic Edition (link) BibTeX
41. Tomás Feder, Rajeev Motwani, An Zhu:
    k-connected spanning subgraphs of low degree.
    Electronic Edition (link) BibTeX
42. Amit Deshpande, Santosh Vempala:
    Adaptive Sampling and Fast Low-Rank Matrix Approximation.
    Electronic Edition (link) BibTeX
43. Eran Ofek, Uriel Feige:
    Random 3CNF formulas elude the Lovasz theta function.
    Electronic Edition (link) BibTeX
44. Andreas Björklund, Thore Husfeldt:
    Inclusion-Exclusion Based Algorithms for Graph Colouring.
    Electronic Edition (link) BibTeX
45. Jan Arpe, Bodo Manthey:
    Approximability of Minimum AND-Circuits.
    Electronic Edition (link) BibTeX
46. Dima Grigoriev, Edward A. Hirsch, Konstantin Pervyshev:
    A Complete Public-Key Cryptosystem.
    Electronic Edition (link) BibTeX
47. María López-Valdés:
    Scaled Dimension of Individual Strings.
    Electronic Edition (link) BibTeX
48. Jin-yi Cai, Vinay Choudhary:
    Some Results on Matchgates and Holographic Algorithms.
    Electronic Edition (link) BibTeX
49. Guy Wolfovitz:
    The Complexity of Depth-3 Circuits Computing Symmetric Boolean Functions.
    Electronic Edition (link) BibTeX
50. Alexander A. Razborov, Sergey Yekhanin:
    An Omega(n^{1/3}) Lower Bound for Bilinear Group Based Private Information Retrieval.
    Electronic Edition (link) BibTeX
51. Alan Nash, Russell Impagliazzo, Jeffrey B. Remmel:
    Infinitely-Often Universal Languages and Diagonalization.
    Electronic Edition (link) BibTeX
52. Wenbin Chen, Jiangtao Meng:
    Inapproximability Results for the Closest Vector Problem with Preprocessing over infty Norm.
    Electronic Edition (link) BibTeX
53. Eldar Fischer, Orly Yahalom:
    Testing Convexity Properties of Tree Colorings.
    Electronic Edition (link) BibTeX
54. Alex Samorodnitsky:
    Low-degree tests at large distances.
    Electronic Edition (link) BibTeX
55. Scott Aaronson, Greg Kuperberg:
    Quantum Versus Classical Proofs and Advice.
    Electronic Edition (link) BibTeX
56. Salil P. Vadhan:
    An Unconditional Study of Computational Zero Knowledge.
    Electronic Edition (link) BibTeX
57. Adam R. Klivans, Alexander A. Sherstov:
    Cryptographic Hardness Results for Learning Intersections of Halfspaces.
    Electronic Edition (link) BibTeX
58. Alexander Healy:
    Randomness-Efficient Sampling within NC^1.
    Electronic Edition (link) BibTeX
59. Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami:
    New Results for Learning Noisy Parities and Halfspaces.
    Electronic Edition (link) BibTeX
60. Ran Raz, Amir Shpilka, Amir Yehudayoff:
    A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits.
    Electronic Edition (link) BibTeX
61. Venkatesan Guruswami, Prasad Raghavendra:
    Hardness of Learning Halfspaces with Noise.
    Electronic Edition (link) BibTeX
62. Subhas Kumar Ghosh:
    Unique k-SAT is as Hard as k-SAT.
    Electronic Edition (link) BibTeX
63. Moses Charikar, Konstantin Makarychev, Yury Makarychev:
    Approximation Algorithm for the Max k-CSP Problem.
    Electronic Edition (link) BibTeX
64. Moses Charikar, Konstantin Makarychev, Yury Makarychev:
    Note on MAX 2SAT.
    Electronic Edition (link) BibTeX
65. Jan Arpe, Rüdiger Reischuk:
    When Does Greedy Learning of Relevant Features Succeed? --- A Fourier-based Characterization ---.
    Electronic Edition (link) BibTeX
66. Vitaly Feldman:
    On Attribute Efficient and Non-adaptive Learning of Parities and DNF Expressions.
    Electronic Edition (link) BibTeX
67. Heiner Ackermann, Heiko Röglin, Berthold Vöcking:
    On the Impact of Combinatorial Structure on Congestion Games.
    Electronic Edition (link) BibTeX
68. Patrick Briest, Piotr Krysta:
    Buying Cheap is Expensive: Hardness of Non-Parametric Multi-Product Pricing.
    Electronic Edition (link) BibTeX
69. Christian Glaßer, Alan L. Selman, Stephen D. Travers, Klaus W. Wagner:
    The Complexity of Unions of Disjoint Sets.
    Electronic Edition (link) BibTeX
70. Ludwig Staiger:
    The Kolmogorov complexity of infinite words.
    Electronic Edition (link) BibTeX
71. John M. Hitchcock, Aduri Pavan:
    Hardness Hypotheses, Derandomization, and Circuit Complexity.
    Electronic Edition (link) BibTeX
72. Henning Fernau:
    Parameterized Algorithms for Hitting Set: the Weighted Case.
    Electronic Edition (link) BibTeX
73. Andrej Bogdanov, Luca Trevisan:
    Average-Case Complexity.
    Electronic Edition (link) BibTeX
74. Shahar Dobzinski, Noam Nisan:
    Approximations by Computationally-Efficient VCG-Based Mechanisms.
    Electronic Edition (link) BibTeX
75. Minh-Huyen Nguyen, Shien Jin Ong, Salil P. Vadhan:
    Statistical Zero-Knowledge Arguments for NP from Any One-Way Function.
    Electronic Edition (link) BibTeX
76. Noam Nisan:
    A Note on the computational hardness of evolutionary stable strategies.
    Electronic Edition (link) BibTeX
77. María López-Valdés:
    Lempel-Ziv Dimension for Lempel-Ziv Compression.
    Electronic Edition (link) BibTeX
78. Tobias Riege, Jörg Rothe:
    Improving Deterministic and Randomized Exponential-Time Algorithms for the Satisfiability, the Colorability, and the Domatic Number Problem.
    Electronic Edition (link) BibTeX
79. Kristoffer Arnsfelt Hansen:
    Lower Bounds for Circuits with Few Modular Gates using Exponential Sums.
    Electronic Edition (link) BibTeX
80. David Doty:
    Dimension Extractors.
    Electronic Edition (link) BibTeX
81. Spyros C. Kontogiannis, Panagiota N. Panagopoulou, Paul G. Spirakis:
    Polynomial Algorithms for Approximating Nash Equilibria of Bimatrix Games.
    Electronic Edition (link) BibTeX
82. Prabhu Manyem:
    Polynomial-Time Maximisation Classes: Syntactic Hierarchy.
    Electronic Edition (link) BibTeX
83. Nils Hebbinghaus, Benjamin Doerr, Frank Neumann:
    Speeding up Evolutionary Algorithms by Restricted Mutation Operators.
    Electronic Edition (link) BibTeX
84. Frank Neumann, Carsten Witt:
    Runtime Analysis of a Simple Ant Colony Optimization Algorithm.
    Electronic Edition (link) BibTeX
85. Andreas Jakoby, Maciej Liskiewicz, Aleksander Madry:
    Using Quantum Oblivious Transfer to Cheat Sensitive Quantum Bit Commitment.
    Electronic Edition (link) BibTeX
86. Dmitry Gavinsky, Julia Kempe, Ronald de Wolf:
    Exponential Separation of Quantum and Classical One-Way Communication Complexity for a Boolean Function.
    Electronic Edition (link) BibTeX
87. Iordanis Kerenidis, Ran Raz:
    The one-way communication complexity of the Boolean Hidden Matching Problem.
    Electronic Edition (link) BibTeX
88. Per Austrin:
    Balanced Max 2-Sat might not be the hardest.
    Electronic Edition (link) BibTeX
89. Sofya Raskhodnikova, Adam Smith:
    A Note on Adaptivity in Testing Properties of Bounded Degree Graphs.
    Electronic Edition (link) BibTeX
90. Christian Glaßer, Alan L. Selman, Stephen D. Travers, Liyu Zhang:
    Non-Mitotic Sets.
    Electronic Edition (link) BibTeX
91. Felix Brandt, Felix A. Fischer, Markus Holzer:
    Symmetries and the Complexity of Pure Nash Equilibrium.
    Electronic Edition (link) BibTeX
92. Matthias Englert, Heiko Röglin, Berthold Vöcking:
    Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP.
    Electronic Edition (link) BibTeX
93. Takeshi Koshiba, Yoshiharu Seri:
    Round-Efficient One-Way Permutation Based Perfectly Concealing Bit Commitment Scheme.
    Electronic Edition (link) BibTeX
94. Parikshit Gopalan, Phokion G. Kolaitis, Elitza N. Maneva, Christos H. Papadimitriou:
    The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies.
    Electronic Edition (link) BibTeX
95. Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti:
    Concurrent Non-Malleable Witness Indistinguishability and its Applications.
    Electronic Edition (link) BibTeX
96. Iftach Haitner, Omer Reingold:
    A New Interactive Hashing Theorem.
    Electronic Edition (link) BibTeX
97. Emanuele Viola:
    New correlation bounds for GF(2) polynomials using Gowers uniformity.
    Electronic Edition (link) BibTeX
98. Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani:
    A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover.
    Electronic Edition (link) BibTeX
99. Oded Goldreich:
    On Expected Probabilistic Polynomial-Time Adversaries -- A suggestion for restricted definitions and their benefits.
    Electronic Edition (link) BibTeX
100. Meena Mahajan, Jayalal M. N. Sarma:
     On the Complexity of Rank and Rigidity.
     Electronic Edition (link) BibTeX
101. Wenceslas Fernandez de la Vega, Marek Karpinski:
     Approximation Complexity of Nondense Instances of MAX-CUT.
     Electronic Edition (link) BibTeX
102. Luis Rademacher, Santosh Vempala:
     Dispersion of Mass and the Complexity of Randomized Geometric Algorithms.
     Electronic Edition (link) BibTeX
103. Oded Lachish, Ilan Newman, Asaf Shapira:
     Space Complexity vs. Query Complexity.
     Electronic Edition (link) BibTeX
104. Wenceslas Fernandez de la Vega, Marek Karpinski:
     On the Sample Complexity of MAX-CUT.
     Electronic Edition (link) BibTeX
105. Avi Wigderson, David Xiao:
     Derandomizing the AW matrix-valued Chernoff bound using pessimistic estimators and applications.
     Electronic Edition (link) BibTeX
106. Scott Aaronson:
     The Learnability of Quantum States.
     Electronic Edition (link) BibTeX
107. Arkadev Chattopadhyay:
     An improved bound on correlation between polynomials over Z_m and MOD_q.
     Electronic Edition (link) BibTeX
108. Dan Gutfreund, Amnon Ta-Shma:
     New connections between derandomization, worst-case complexity and average-case complexity.
     Electronic Edition (link) BibTeX
109. Julia Chuzhoy, Sanjeev Khanna:
     Hardness of Directed Routing with Congestion.
     Electronic Edition (link) BibTeX
110. Nishanth Chandran, Ryan Moriarty, Rafail Ostrovsky, Omkant Pandey, Amit Sahai:
     Improved Algorithms for Optimal Embeddings.
     Electronic Edition (link) BibTeX
111. Artur Czumaj, Miroslaw Kowaluk, Andrzej Lingas:
     Faster algorithms for finding lowest common ancestors in directed acyclic graphs.
     Electronic Edition (link) BibTeX
112. Xin Han, Kazuo Iwama, Deshi Ye, Guochuan Zhang:
     Strip Packing vs. Bin Packing.
     Electronic Edition (link) BibTeX
113. Peter Bürgisser:
     On defining integers in the counting hierarchy and proving lower bounds in algebraic complexity.
     Electronic Edition (link) BibTeX
114. Carl Bosley, Yevgeniy Dodis:
     Does Privacy Require True Randomness?.
     Electronic Edition (link) BibTeX
115. Artur Czumaj, Artur Czumaj, Andrzej Lingas:
     Finding a Heaviest Triangle is not Harder than Matrix Multiplication.
     Electronic Edition (link) BibTeX
116. Amin Coja-Oghlan:
     Graph partitioning via adaptive spectral techniques.
     Electronic Edition (link) BibTeX
117. Arkadev Chattopadhyay, Michal Koucký, Andreas Krebs, Mario Szegedy, Pascal Tesson, Denis Thérien:
     Languages with Bounded Multiparty Communication Complexity.
     Electronic Edition (link) BibTeX
118. Irit Dinur, Madhu Sudan, Avi Wigderson:
     Robust Local Testability of Tensor Products of LDPC Codes.
     Electronic Edition (link) BibTeX
119. Noga Alon, Oded Schwartz, Asaf Shapira:
     An Elementary Construction of Constant-Degree Expanders.
     Electronic Edition (link) BibTeX
120. Leslie G. Valiant:
     Evolvability.
     Electronic Edition (link) BibTeX
121. Charanjit S. Jutla:
     A Simple Biased Distribution for Dinur's Construction.
     Electronic Edition (link) BibTeX
122. Noam Livne:
     All Natural NPC Problems Have Average-Case Complete Versions.
     Electronic Edition (link) BibTeX
123. Venkatesan Guruswami:
     Iterative Decoding of Low-Density Parity Check Codes (A Survey).
     Electronic Edition (link) BibTeX
124. Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski:
     Approximation of Global MAX-CSP Problems.
     Electronic Edition (link) BibTeX
125. Luis Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto:
     Low-Depth Witnesses are Easy to Find.
     Electronic Edition (link) BibTeX
126. Piotr Indyk:
     Uncertainty Principles, Extractors, and Explicit Embeddings of L2 into L1.
     Electronic Edition (link) BibTeX
127. Sergey Yekhanin:
     New Locally Decodable Codes and Private Information Retrieval Schemes.
     Electronic Edition (link) BibTeX
128. Shankar Kalyanaraman, Christopher Umans:
     On obtaining pseudorandomness from error-correcting codes..
     Electronic Edition (link) BibTeX
129. Manindra Agrawal, Thanh Minh Hoang, Thomas Thierauf:
     The polynomially bounded perfect matching problem is in NC^2.
     Electronic Edition (link) BibTeX
130. Tanmoy Chakraborty, Samir Datta:
     One-input-face MPCVP is Hard for L, but in LogDCFL.
     Electronic Edition (link) BibTeX
131. Konstantin Pervyshev:
     On Heuristic Time Hierarchies.
     Electronic Edition (link) BibTeX
132. Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani:
     Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut.
     Electronic Edition (link) BibTeX
133. Alexander Hertel, Alasdair Urquhart:
     The Resolution Width Problem is EXPTIME-Complete.
     Electronic Edition (link) BibTeX
134. Venkatesan Guruswami, Christopher Umans, Salil P. Vadhan:
     Extractors and condensers from univariate polynomials.
     Electronic Edition (link) BibTeX
135. Jin-yi Cai, Pinyan Lu:
     On Symmetric Signatures in Holographic Algorithms.
     Electronic Edition (link) BibTeX
136. Mihir Bellare, Oded Goldreich:
     On Probabilistic versus Deterministic Provers in the Definition of Proofs Of Knowledge.
     Electronic Edition (link) BibTeX
137. Wolfgang Maass, Prashant Joshi, Eduardo D. Sontag:
     Computational aspects of feedback in neural circuits.
     Electronic Edition (link) BibTeX
138. Wolfgang Maass, Kei Uchizawa, Rodney J. Douglas:
     Energy Complexity and Entropy of Threshold Circuits.
     Electronic Edition (link) BibTeX
139. Shien Jin Ong, Salil P. Vadhan:
     Zero Knowledge and Soundness are Symmetric.
     Electronic Edition (link) BibTeX
140. Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind:
     Formula Caching in DPLL.
     Electronic Edition (link) BibTeX
141. Venkatesan Guruswami, Kunal Talwar:
     Hardness of Low Congestion Routing in Directed Graphs.
     Electronic Edition (link) BibTeX
142. Olaf Beyersdorff:
     On the Deduction Theorem and Complete Disjoint NP-Pairs.
     Electronic Edition (link) BibTeX
143. Frank Neumann, Carsten Witt:
     Ant Colony Optimization and the Minimum Spanning Tree Problem.
     Electronic Edition (link) BibTeX
144. Claire Kenyon-Mathieu, Warren Schudy:
     How to rank with few errors: A PTAS for Weighted Feedback Arc Set on Tournaments.
     Electronic Edition (link) BibTeX
145. Jin-yi Cai, Pinyan Lu:
     Holographic Algorithms: From Art to Science.
     Electronic Edition (link) BibTeX
146. Christoph Buchheim, Peter J. Cameron, Taoyang Wu:
     On the Subgroup Distance Problem.
     Electronic Edition (link) BibTeX
147. Chris Peikert, Alon Rosen:
     Lattices that Admit Logarithmic Worst-Case to Average-Case Connection Factors.
     Electronic Edition (link) BibTeX
148. Chris Peikert:
     Limits on the Hardness of Lattice Problems in $\ell_p$ Norms.
     Electronic Edition (link) BibTeX
149. Lance Fortnow, Rakesh Vohra:
     The Complexity of Forecast Testing.
     Electronic Edition (link) BibTeX
150. Patrick Briest:
     Towards Hardness of Envy-Free Pricing.
     Electronic Edition (link) BibTeX
151. Prahladh Harsha, Rahul Jain, David A. McAllester, Jaikumar Radhakrishnan:
     The communication complexity of correlation.
     Electronic Edition (link) BibTeX
152. Konstantinos Georgiou, Avner Magen, Toniann Pitassi, Iannis Tourlakis:
     Tight integrality gaps for Vertex Cover SDPs in the Lovasz-Schrijver hierarchy.
     Electronic Edition (link) BibTeX
153. Michael Bauland, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer:
     The Complexity of Generalized Satisfiability for Linear Temporal Logic.
     Electronic Edition (link) BibTeX
154. Joshua Buresh-Oppenheim, Valentine Kabanets, Rahul Santhanam:
     Uniform Hardness Amplification in NP via Monotone Codes.
     Electronic Edition (link) BibTeX
155. Wenceslas Fernandez de la Vega, Marek Karpinski:
     Trading Tensors for Cloning: Constant Time Approximation Schemes for Metric MAX-CSP.
     Electronic Edition (link) BibTeX
156. Tomás Feder, Rajeev Motwani:
     Finding large cycles in Hamiltonian graphs.
     Electronic Edition (link) BibTeX
157. Lance Fortnow, Rahul Santhanam:
     Fixed-Polynomial Size Circuit Bounds.
     Electronic Edition (link) BibTeX
158. Gyula Györ:
     Representing Boolean OR function by quadratic polynomials modulo 6.
     Electronic Edition (link) BibTeX
159. Predrag T. Tosic:
     Computational Complexity of Some Enumeration Problems About Uniformly Sparse Boolean Network Automata.
     Electronic Edition (link) BibTeX
160. Tomás Feder, Phokion G. Kolaitis:
     Closures and dichotomies for quantified constraints.
     Electronic Edition (link) BibTeX