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