We propose a model called priority branching trees (pBT ) for backtracking and dynamic
programming algorithms. Our model generalizes both the priority model of Borodin, Nielson
and Rackoff, as well as a simple dynamic programming model due to Woeginger, and hence
spans a wide spectrum of algorithms. After witnessing the ... more >>>

We consider the problem of amplifying uniform average-case hardness
of languages in $\NP$, where hardness is with respect to $\BPP$
algorithms. We introduce the notion of \emph{monotone}
error-correcting codes, and show that hardness amplification for
$\NP$ is essentially equivalent to constructing efficiently
\emph{locally} encodable and \emph{locally} list-decodable monotone
codes. The ... more >>>

We consider a general approach to the hoary problem of (im)proving circuit lower bounds. We define notions of hardness condensing and hardness extraction, in analogy to the corresponding notions from the computational theory of randomness. A hardness condenser is a procedure that takes in a Boolean function as input, as ... more >>>

We consider Total Functional $\NP$ ($\TFNP$) search problems. Such problems are based on combinatorial principles that guarantee, through locally checkable conditions, that a solution to the problem exists in an exponentially-large domain, and have the property that any solution has a polynomial-size witness that can be verified in polynomial time. ... more >>>

We prove exponential separations between the sizes of
particular refutations in negative, respectively linear, resolution and
general resolution. Only a superpolynomial separation between negative
and general resolution was previously known. Our examples show that there
is no strong relationship between the size and width of refutations in
negative and ... more >>>