
PreviousNext
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 >>>
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 >>>
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 >>>
PreviousNext