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

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

Copyright © Thu Aug 7 21:01:14 2008 by Michael Ley (ley@uni-trier.de)