We present a new framework for the study of search problems and their
definability in bounded arithmetic. We identify two notions of
complexity of search problems: verification complexity and
computational complexity. Notions of exact solvability and exact
reducibility are developed, and exact $\Sigma^b_i$-definability of
search problems in bounded arithmetic ... more >>>

We introduce the idea of pushdown automata with the ability to flip
its stack. By bounding the number of times the stack can be flipped
we obtain a hierarchy of language classes from the context free
languages to the recursively enumerable languages. We show that each
class in ... more >>>

We prove that if a linear error correcting code
$\C:\{0,1\}^n\to\{0,1\}^m$ is such that a bit of the message can
be probabilistically reconstructed by looking at two entries of a
corrupted codeword, then $m = 2^{\Omega(n)}$. We also present
several extensions of this result.

We show a reduction from the ... more >>>