We show that if an NP-complete problem has a non-adaptive
self-corrector with respect to a samplable distribution then
coNP is contained in NP/poly and the polynomial
hierarchy collapses to the third level. Feigenbaum and
Fortnow (SICOMP 22:994-1005, 1993) show the same conclusion
under the stronger assumption that an
more >>>

We survey known results regarding locally testable codes
and locally testable proofs (known as PCPs),
with emphasis on the length of these constructs.
Locally testability refers to approximately testing
large objects based on a very small number of probes,
each retrieving a single bit in the ... more >>>

We introduce the notion of width bounded geometric separator,
develop the techniques for its existence as well as algorithm, and
apply it to obtain a $2^{O(\sqrt{n})}$ time exact algorithm for the
disk covering problem, which seeks to determine the minimal number
of fixed size disks to cover $n$ points on ... more >>>