A Uniform Generation procedure for $NP$ is an
algorithm which given any input in a fixed NP-language, outputs a uniformly
distributed NP-witness for membership of the input in the language.
We present a Uniform Generation procedure for $NP$ that runs in probabilistic
polynomial-time with an NP-oracle. This improves upon ... more >>>

We give a randomized approximation algorithm taking
$O(k^{O(k)}n^{b+O(1)})$ time to count the number of copies of a
$k$-vertex graph with treewidth at most $b$ in an $n$ vertex graph
$G$ with approximation ratio $1/k^{O(k)}$ and error probability
inverse exponential in $n$. This algorithm is based on ... more >>>

We describe a deterministic algorithm that, for constant k,
given a k-DNF or k-CNF formula f and a parameter e, runs in time
linear in the size of f and polynomial in 1/e and returns an
estimate of the fraction of satisfying assignments for f up to ... more >>>

We study computational procedures that use both randomness and nondeterminism. Examples are Arthur-Merlin games and approximate counting and sampling of NP-witnesses. The goal of this paper is to derandomize such procedures under the weakest possible assumptions.

Our main technical contribution allows one to ``boost'' a given hardness assumption. One special ... more >>>

We study the compression of polynomially samplable sources. In particular, we give efficient prefix-free compression and decompression algorithms for three classes of such sources (whose support is a subset of {0,1}^n).

1. We show how to compress sources X samplable by logspace machines to expected length H(X)+O(1).

Our next results ... more >>>

The notion of promise problems was introduced and initially studied
by Even, Selman and Yacobi
(Information and Control, Vol.~61, pages 159-173, 1984).
In this article we survey some of the applications that this
notion has found in the twenty years that elapsed.
These include the notion of ... more >>>

Let $X$ be randomly chosen from $\{-1,1\}^n$, and let $Y$ be randomly
chosen from the standard spherical Gaussian on $\R^n$. For any (possibly unbounded) polytope $P$
formed by the intersection of $k$ halfspaces, we prove that
$$\left|\Pr\left[X \in P\right] - \Pr\left[Y \in P\right]\right| \leq \log^{8/5}k \cdot ... more >>>

We show that if Arthur-Merlin protocols can be derandomized, then there is a Boolean function computable in deterministic exponential-time with access to an NP oracle, that cannot be computed by Boolean circuits of exponential size. More formally, if $\mathrm{prAM}\subseteq \mathrm{P}^{\mathrm{NP}}$ then there is a Boolean function in $\mathrm{E}^{\mathrm{NP}}$ that requires ... more >>>

We give a deterministic, polynomial-time algorithm for approximately counting the number of {0,1}-solutions to any instance of the knapsack problem. On an instance of length n with total weight W and accuracy parameter eps, our algorithm produces a (1 + eps)-multiplicative approximation in time poly(n,log W,1/eps). We also give algorithms ... more >>>

We show that the promise problem of distinguishing $n$-bit strings of hamming weight $\ge 1/2 + \Omega(1/\log^{d-1} n)$ from strings of weight $\le 1/2 - \Omega(1/\log^{d-1} n)$ can be solved by explicit, randomized (unbounded-fan-in) poly(n)-size depth-$d$ circuits with error $\le 1/3$, but cannot be solved by deterministic poly(n)-size depth-$(d+1)$ circuits, ... more >>>