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

Electronic Colloquium on Computational Complexity, Volume 10, 2003

Volume 10, 2003

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

Home | Conferences | Journals | Series | FAQ — Search: Faceted | Complete | Author
Copyright © Sat May 16 23:57:49 2009 by Michael Ley (ley@uni-trier.de)