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

__
TR11-017
| 8th February 2011
__

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

__
TR10-069
| 17th April 2010
__

Eric Allender, Vikraman Arvind, Fengming Wang#### Uniform Derandomization from Pathetic Lower Bounds

Revisions: 1
,
Comments: 1

__
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

Eric Allender, Fengming Wang

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

settings.

Fengming Wang

$\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 >>>

Eric Allender, Vikraman Arvind, Fengming Wang

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 >>>

Lance Fortnow, John Hitchcock, A. Pavan, N. V. Vinodchandran, Fengming Wang

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 >>>