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

Copyright © Mon Nov 2 21:34:17 2009 by Michael Ley (ley@uni-trier.de)