All reports by Author Ce Jin:

__
TR20-065
| 2nd May 2020
__

Lijie Chen, Ce Jin, Ryan Williams#### Sharp Threshold Results for Computational Complexity

__
TR19-118
| 5th September 2019
__

Lijie Chen, Ce Jin, Ryan Williams#### Hardness Magnification for all Sparse NP Languages

Lijie Chen, Ce Jin, Ryan Williams

We establish several ``sharp threshold'' results for computational complexity. For certain tasks, we can prove a resource lower bound of $n^c$ for $c \geq 1$ (or obtain an efficient circuit-analysis algorithm for $n^c$ size), there is strong intuition that a similar result can be proved for larger functions of $n$, ... more >>>

Lijie Chen, Ce Jin, Ryan Williams

In the Minimum Circuit Size Problem (MCSP[s(m)]), we ask if there is a circuit of size s(m) computing a given truth-table of length n = 2^m. Recently, a surprising phenomenon termed as hardness magnification by [Oliveira and Santhanam, FOCS 2018] was discovered for MCSP[s(m)] and the related problem MKtP of ... more >>>