A theory, in this context, is a Boolean formula; it is
used to classify instances, or truth assignments. Theories
can model real-world phenomena, and can do so more or less
correctly.
The theory revision, or concept revision, problem is to
correct a given, roughly correct concept.
This problem is ... more >>>

We show that the asymmetric $k$-center problem is
$\Omega(\log^* n)$-hard to approximate unless
${\rm NP} \subseteq {\rm DTIME}(n^{poly(\log \log n)})$.
Since an $O(\log^* n)$-approximation algorithm is known
for this problem, this essentially resolves the approximability
of this problem. This is the first natural problem
whose approximability threshold does not polynomially ... more >>>

We present a novel technique, based on the Jensen-Shannon divergence
from information theory, to prove lower bounds on the query complexity
of sampling algorithms that approximate functions over arbitrary
domain and range. Unlike previous methods, our technique does not
use a reduction from a binary decision problem, but rather ... more >>>