All reports by Author Jiatu Li:

__
TR21-023
| 20th February 2021
__

Jiatu Li, Tianqi Yang#### $3.1n - o(n)$ Circuit Lower Bounds for Explicit Functions

Jiatu Li, Tianqi Yang

Proving circuit lower bounds has been an important but extremely hard problem for decades. Although one may show that almost every function $f:\mathbb{F}_2^n\to\mathbb{F}_2$ requires circuit of size $\Omega(2^n/n)$ by a simple counting argument, it remains unknown whether there is an explicit function (for example, a function in $NP$) not computable ... more >>>