Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Fengming Wang:

TR11-083 | 22nd May 2011
Eric Allender, Fengming Wang

On the power of algebraic branching programs of width two

We show that there are families of polynomials having small depth-two arithmetic circuits that cannot be expressed by algebraic branching programs of width two. This clarifies the complexity of the problem of computing the product of a sequence of two-by-two matrices, which arises in several

more >>>

TR11-017 | 8th February 2011
Fengming Wang

NEXP does not have non-uniform quasi-polynomial-size ACC circuits of o(loglog n) depth

$\mbox{ACC}_m$ circuits are circuits consisting of unbounded fan-in AND, OR and MOD_m gates and unary NOT gates, where m is a fixed integer. We show that there exists a language in non-deterministic exponential time which can not be computed by any non-uniform family of $\mbox{ACC}_m$ circuits of quasi-polynomial size and ... more >>>

TR10-069 | 17th April 2010
Eric Allender, Vikraman Arvind, Fengming Wang

Uniform Derandomization from Pathetic Lower Bounds

Revisions: 1 , Comments: 1

A recurring theme in the literature on derandomization is that probabilistic
algorithms can be simulated quickly by deterministic algorithms, if one can obtain *impressive* (i.e., superpolynomial, or even nearly-exponential) circuit size lower bounds for certain problems. In contrast to what is
needed for derandomization, existing lower bounds seem rather pathetic ... more >>>

TR05-105 | 24th September 2005
Lance Fortnow, John Hitchcock, A. Pavan, N. V. Vinodchandran, Fengming Wang

Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws

We apply recent results on extracting randomness from independent
sources to ``extract'' Kolmogorov complexity. For any $\alpha,
\epsilon > 0$, given a string $x$ with $K(x) > \alpha|x|$, we show
how to use a constant number of advice bits to efficiently
compute another string $y$, $|y|=\Omega(|x|)$, with $K(y) >
(1-\epsilon)|y|$. ... more >>>

ISSN 1433-8092 | Imprint