Trevisan and Vadhan (FOCS 2000) introduced the notion of (seedless) extractors for samplable distributions. They showed that under a very strong complexity theoretic hardness assumption (specifically, that there exists a problem in $\E=\DTIME(2^{O(n)})$ that cannot be computed by size $2^{\Omega(n)}$ circuits that have an oracle to $\Sigma_6^{\P}$) there are extractors ... more >>>

Motivated by questions concerning the multilinear and homogeneous complexity of the elementary symmetric polynomials, we prove the following results:

We first show that by making small modifications to the nonzero coefficients of the degree-$K$, $N$-variate elementary symmetric polynomial $\sigma_{N,K}$, one obtains a polynomial that can be computed by a monotone ... more >>>

In this paper, we initiate the study of deterministic PIT for $\Sigma^{[k]}\Pi\Sigma\Pi^{[\delta]}$ circuits over fields of any characteristic, where $k$ and $\delta$ are bounded. Our main result is a deterministic polynomial-time black-box PIT algorithm for $\Sigma^{[3]}\Pi\Sigma\Pi^{[\delta]}$ circuits, under the additional condition that one of the summands at the top $\Sigma$ ... more >>>