All reports by Author Fu Li:

__
TR18-110
| 4th June 2018
__

Fu Li, David Zuckerman#### Improved Extractors for Recognizable and Algebraic Sources

Revisions: 1

__
TR15-134
| 19th August 2015
__

Fu Li, Iddo Tzameret, Zhengyu Wang#### Characterizing Propositional Proofs as Non-Commutative Formulas

__
TR13-185
| 24th December 2013
__

Fu Li, Iddo Tzameret#### Generating Matrix Identities and Proof Complexity Lower Bounds

Revisions: 3

Fu Li, David Zuckerman

We study the task of seedless randomness extraction from recognizable sources, which are uniform distributions over sets of the form {x : f(x) = v} for functions f in some specified class C. We give two simple methods for constructing seedless extractors for C-recognizable sources.

Our first method shows that ...
more >>>

Fu Li, Iddo Tzameret, Zhengyu Wang

Does every Boolean tautology have a short propositional-calculus proof? Here, a propositional-calculus (i.e., Frege) proof is any proof starting from a set of axioms and deriving new Boolean formulas using a fixed set of sound derivation rules. Establishing any super-polynomial size lower bound on Frege proofs (in terms of the ... more >>>

Fu Li, Iddo Tzameret

Motivated by the fundamental lower bounds questions in proof complexity, we investigate the complexity of generating identities of matrix rings, and related problems. Specifically, for a field $\mathbb{F}$ let $A$ be a non-commutative (associative) $\mathbb{F}$-algebra (e.g., the algebra Mat$_d(\mathbb{F})\;$ of $d\times d$ matrices over $\mathbb{F}$). We say that a non-commutative ... more >>>