Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR00-062 | 25th August 2000
Venkatesan Guruswami, Johan HÃ¥stad, Madhu Sudan

Hardness of approximate hypergraph coloring

We introduce the notion of covering complexity of a probabilistic
verifier. The covering complexity of a verifier on a given input is
the minimum number of proofs needed to ``satisfy'' the verifier on
every random string, i.e., on every random string, at least one of the
given proofs must be ... more >>>


TR00-061 | 14th August 2000
Prahladh Harsha, Madhu Sudan

Small PCPs with low query complexity

Most known constructions of probabilistically checkable proofs (PCPs)
either blow up the proof size by a large polynomial, or have a high
(though constant) query complexity. In this paper we give a
transformation with slightly-super-cubic blowup in proof size, with a
low query complexity. Specifically, the verifier probes the proof ... more >>>


TR00-060 | 17th August 2000
Uri Zwick

All Pairs Shortest Paths using Bridging Sets and Rectangular Matrix Multiplication

We present two new algorithms for solving the {\em All
Pairs Shortest Paths\/} (APSP) problem for weighted directed
graphs. Both algorithms use fast matrix multiplication algorithms.

The first algorithm
solves the APSP problem for weighted directed graphs in which the edge
weights are integers of small absolute value in ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint