Electronic Colloquium on Computational Complexity, Volume 10, 2003

Volume 10, 2003

1. Vince Grolmusz:
   Near Quadratic Matrix Multiplication Modulo Composites.
   
2. Stefan Szeider:
   Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable.
   
3. Fahiem Bacchus, Shannon Dalmao, Toniann Pitassi:
   DPLL with Caching: A new algorithm for #SAT and Bayesian Inference.
   
4. Eli Ben-Sasson, Prahladh Harsha:
   Lower Bounds for Bounded-Depth Frege Proofs via Buss-Pudlack Games.
   
5. Scott Aaronson:
   Quantum Certificate Complexity.
   
6. Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova:
   3CNF Properties are Hard to Test.
   
7. Olivier Dubois, Yacine Boufkhad, Jacques Mandler:
   Typical random 3-SAT formulae and the satisfiability threshold.
   
8. Piotr Berman, Marek Karpinski:
   Improved Approximation Lower Bounds on Small Occurrence Optimization.
   
9. Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey:
   Private Computation - k-connected versus 1-connected Networks.
   
10. Sven Baumer, Rainer Schuler:
    Improving a probabilistic 3-SAT Algorithm by Dynamic Search and Independent Clause Pairs.
    
11. Christian Glaßer, Alan L. Selman, Samik Sengupta, Liyu Zhang:
    Disjoint NP-Pairs.
    
12. Edward A. Hirsch, Arist Kojevnikov:
    Several notes on the power of Gomory-Chvatal cuts.
    
13. Luca Trevisan:
    An epsilon-Biased Generator in NC0.
    
14. Avrim Blum, Ke Yang:
    On Statistical Query Sampling and NMR Quantum Computing.
    
15. Shafi Goldwasser, Yael Tauman:
    On the (In)security of the Fiat-Shamir Paradigm .
    
16. Dimitrios Koukopoulos, Marios Mavronicolas, Paul G. Spirakis:
    FIFO is Unstable at Arbitrarily Low Rates.
    
17. Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener:
    On Converting CNF to DNF.
    
18. Matthias Galota, Heribert Vollmer:
    Functions Computable in Polynomial Space.
    
19. Eli Ben-Sasson, Oded Goldreich, Madhu Sudan:
    Bounds on 2-Query Codeword Testing.
    
20. Elad Hazan, Shmuel Safra, Oded Schwartz:
    On the Hardness of Approximating k-Dimensional Matching.
    
21. Mikhail N. Vyalyi:
    QMA=PP implies that PP contains PH.
    
22. Piotr Berman, Marek Karpinski, Alex D. Scott:
    Approximation Hardness and Satisfiability of Bounded Occurrence Instances of SAT.
    
23. Anna Palbom:
    On Spanning Cacti and Asymmetric TSP.
    
24. Till Tantau:
    Weak Cardinality Theorems for First-Order Logic.
    
25. Kristoffer Arnsfelt Hansen:
    Constant width planar computation characterizes ACC0.
    
26. Janka Chlebíková, Miroslav Chlebík:
    Inapproximability results for bounded variants of optimization problems.
    
27. Christian Glaßer, Alan L. Selman, Samik Sengupta:
    Reductions between Disjoint NP-Pairs.
    
28. Olivier Powell:
    PSPACE contains almost complete problems.
    
29. Philippe Moser:
    BPP has effective dimension at most 1/2 unless BPP=EXP.
    
30. Amin Coja-Oghlan, Andreas Goerdt, André Lanka, Frank Schädlich:
    Certifying Unsatisfiability of Random 2k-SAT Formulas using Approximation Techniques.
    
31. Birgit Schelm:
    Average-Case Complexity Theory of Approximation Problems.
    
32. Andreas Björklund, Thore Husfeldt, Sanjeev Khanna:
    Approximating Longest Directed Path.
    
33. Meir Feder, Dana Ron, Ami Tavory:
    Bounds on Linear Codes for Network Multicast.
    
34. Arnold Beckmann:
    Height restricted constant depth LK.
    
35. Eran Halperin, Guy Kortsarz, Robert Krauthgamer:
    Tight lower bounds for the asymmetric k-center problem.
    
36. Bruce E. Litow:
    Polynomial equation elimination via Tarski Algebra.
    
37. Ziv Bar-Yossef:
    Sampling Lower Bounds via Information Theory.
    
38. Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Joseph Naor:
    Asymmetric k-center is log^*n-hard to Approximate.
    
39. Judy Goldsmith, Robert H. Sloan, Balázs Szörényi, György Turán:
    Theory Revision with Queries: Horn, Read-once, and Parity Formulas.
    
40. Philippe Moser:
    RP is Small in SUBEXP else ZPP equals PSPACE and NP equals EXP.
    
41. Albert Atserias, Maria Luisa Bonet, Jordi Levy:
    On Chvatal Rank and Cutting Planes Proofs.
    
42. Luca Trevisan:
    List Decoding Using the XOR Lemma.
    
43. Elchanan Mossel, Amir Shpilka, Luca Trevisan:
    On epsilon-Biased Generators in NC0.
    
44. Juan Luis Esteban, Jacobo Torán:
    A Combinatorial Characterization of Treelike Resolution Space.
    
45. Oded Goldreich, Shafi Goldwasser, Asaf Nussboim:
    On the Implementation of Huge Random Objects .
    
46. Philippe Moser:
    Locally Computed Baire's Categories on Small Complexity Classes.
    
47. Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton:
    Symmetric Polynomials over Z_m and Simultaneous Communication Protocols.
    
48. Stefan Droste, Thomas Jansen, Ingo Wegener:
    Upper and Lower Bounds for Randomized Search Heuristics in Black-Box Optimization.
    
49. Piotr Berman, Marek Karpinski, Alex D. Scott:
    Approximation Hardness of Short Symmetric Instances of MAX-3SAT .
    
50. Daniel Král:
    Locally satisfiable formulas.
    
51. Tsuyoshi Morioka:
    The Relative Complexity of Local Search Heuristics and the Iteration Principle.
    
52. Stanislav Busygin, Dmitrii V. Pasechnik:
    On ~chi(G)-alpha(G)>0 gap recognition and alpha(G)-upper bounds.
    
53. Kazuo Iwama, Suguru Tamaki:
    Improved Upper Bounds for 3-SAT.
    
54. Daniel Rolf:
    3-SAT in RTIME(O(1.32793ⁿ)) - Improving Randomized Local Search by Initializing Strings of 3-Clauses.
    
55. Jan Krajícek:
    Implicit proofs.
    
56. Piotr Berman, Marek Karpinski:
    Approximability of Hypergraph Minimum Bisection .
    
57. Scott Aaronson:
    Lower Bounds for Local Search by Quantum Arguments.
    
58. Vince Grolmusz:
    Defying Dimensions Modulo 6.
    
59. Harumichi Nishimura, Tomoyuki Yamakami:
    Polynomial time quantum computation with advice.
    
60. Danny Harnik, Moni Naor, Omer Reingold, Alon Rosen:
    Completeness in Two-Party Secure Computation - A Computational View.
    
61. Jan Kára, Daniel Král:
    Free Binary Decision Diagrams for Computation of EAR_n.
    
62. Andrei A. Krokhin, Peter Jonsson:
    Recognizing Frozen Variables in Constraint Satisfaction Problems.
    
63. John M. Hitchcock:
    The Size of SPP.
    
64. Vikraman Arvind, Piyush P. Kurur:
    Upper Bounds on the Complexity of some Galois Theory Problems.
    
65. Hoeteck Wee:
    Compressibility Lower Bounds in Oracle Settings.
    
66. Daniele Micciancio:
    Almost perfect lattices, the covering radius problem, and applications to Ajtai's connection factor.
    
67. Ran Raz:
    Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size.
    
68. Matthias Homeister:
    Lower Bounds for the Sum of Graph--driven Read--Once Parity Branching Programs.
    
69. Elmar Böhler, Christian Glaßer, Daniel Meister:
    Small Bounded-Error Computations and Completeness.
    
70. Amit Chakrabarti, Oded Regev:
    An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching.
    
71. Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey:
    Privacy in Non-Private Environments.
    
72. Evgeny Dantsin, Edward A. Hirsch, Alexander Wolpert:
    Algorithms for SAT based on search in Hamming balls.
    
73. Amin Coja-Oghlan:
    The Lovasz number of random graph.
    
74. Vince Grolmusz:
    Sixtors and Mod 6 Computations.
    
75. Agostino Capponi:
    A tutorial on the Deterministic two-party Communication Complexity.
    
76. Michael Langberg:
    Testing the independence number of hypergraphs.
    
77. Till Tantau:
    Logspace Optimisation Problems and their Approximation Properties.
    
78. Fan R. K. Chung, Ronald L. Graham, Jia Mao, Andrew Chi-Chih Yao:
    Finding Favorites.
    
79. Scott Aaronson:
    Multilinear Formulas and Skepticism of Quantum Computing.
    
80. Venkatesan Guruswami:
    Better Extractors for Better Codes?
    
81. Valentin E. Brimkov, Bruno Codenotti, Valentino Crespi, Reneta P. Barneva, Mauro Leoncini:
    Computation of the Lovász Theta Function for Circulant Graphs.
    
82. Andris Ambainis, Ke Yang:
    Towards the Classical Communication Complexity of Entanglement Distillation Protocols with Incomplete Information.
    
83. Jan Arpe, Andreas Jakoby, Maciej Liskiewicz:
    One-Way Communication Complexity of Symmetric Boolean Functions.
    
84. Josh Buresh-Oppenheim, Tsuyoshi Morioka:
    Relativized NP Search Problems and Propositional Proof Systems.
    
85. Ke Yang:
    On the (Im)possibility of Non-interactive Correlation Distillation.
    
86. Amos Beimel, Tal Malkin:
    A Quantitative Approach to Reductions in Secure Computation.
    
87. Richard Beigel, Lance Fortnow, William I. Gasarch:
    A Nearly Tight Bound for Private Information Retrieval Protocols.