
PreviousNext
Matroid intersection has a known polynomial time algorithm using an
oracle. We generalize this result to delta-matroids that do not have
equality as a restriction, and give a polynomial time algorithm for
delta-matroid intersection on delta-matroids without equality using an
oracle. We note that when equality is present, delta-matroid intersection
more >>>
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 >>>
PreviousNext