All reports by Author Lijie Chen:

__
TR20-150
| 7th October 2020
__

Lijie Chen, Xin Lyu, Ryan Williams#### Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization

__
TR20-148
| 28th September 2020
__

Lijie Chen, Roei Tell#### Simple and fast derandomization from very hard functions: Eliminating randomness at almost no cost

__
TR20-065
| 2nd May 2020
__

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

__
TR20-010
| 12th February 2020
__

Lijie Chen, Hanlin Ren#### Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization

Revisions: 1

__
TR19-169
| 21st November 2019
__

Lijie Chen, Ron Rothblum, Roei Tell, Eylon Yogev#### On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds

Revisions: 1

__
TR19-168
| 20th November 2019
__

Igor Carboni Oliveira, Lijie Chen, Shuichi Hirahara, Ján Pich, Ninad Rajgopal, Rahul Santhanam#### Beyond Natural Proofs: Hardness Magnification and Locality

__
TR19-118
| 5th September 2019
__

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

__
TR19-075
| 25th May 2019
__

Lijie Chen, Dylan McKay, Cody Murray, Ryan Williams#### Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems

__
TR19-072
| 17th May 2019
__

Lijie Chen, Ofer Grossman#### Broadcast Congested Clique: Planted Cliques and Pseudorandom Generators

__
TR19-031
| 4th March 2019
__

Lijie Chen#### Non-deterministic Quasi-Polynomial Time is Average-case Hard for ACC Circuits

Revisions: 1

__
TR18-199
| 24th November 2018
__

Lijie Chen, Roei Tell#### Bootstrapping Results for Threshold Circuits “Just Beyond” Known Lower Bounds

__
TR18-026
| 7th February 2018
__

Lijie Chen#### On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product

Revisions: 1

__
TR16-200
| 18th December 2016
__

Scott Aaronson, Lijie Chen#### Complexity-Theoretic Foundations of Quantum Supremacy Experiments

Revisions: 1

__
TR16-140
| 9th September 2016
__

Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan#### On SZK and PP

Revisions: 3

Lijie Chen, Xin Lyu, Ryan Williams

In certain complexity-theoretic settings, it is notoriously difficult to prove complexity separations which hold almost everywhere, i.e., for all but finitely many input lengths. For example, a classical open question is whether $\mathrm{NEXP} \subset \mathrm{i.o.-}\mathrm{NP}$; that is, it is open whether nondeterministic exponential time computations can be simulated on infinitely ... more >>>

Lijie Chen, Roei Tell

Extending the classical ``hardness-to-randomness'' line-of-works, Doron et al. (FOCS 2020) recently proved that derandomization with near-quadratic time overhead is possible, under the assumption that there exists a function in $\mathcal{DTIME}[2^n]$ that cannot be computed by randomized SVN circuits of size $2^{(1-\epsilon)\cdot n}$ for a small $\epsilon$.

In this work we ... more >>>

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, Hanlin Ren

We prove that for all constants a, NQP = NTIME[n^{polylog(n)}] cannot be (1/2 + 2^{-log^a n})-approximated by 2^{log^a n}-size ACC^0 of THR circuits (ACC^0 circuits with a bottom layer of THR gates). Previously, it was even open whether E^NP can be (1/2+1/sqrt{n})-approximated by AC^0[2] circuits. As a straightforward application, ... more >>>

Lijie Chen, Ron Rothblum, Roei Tell, Eylon Yogev

The Exponential-Time Hypothesis ($ETH$) is a strengthening of the $\mathcal{P} \neq \mathcal{NP}$ conjecture, stating that $3\text{-}SAT$ on $n$ variables cannot be solved in time $2^{\epsilon\cdot n}$, for some $\epsilon>0$. In recent years, analogous hypotheses that are ``exponentially-strong'' forms of other classical complexity conjectures (such as $\mathcal{NP}\not\subseteq\mathcal{BPP}$ or $co\text{-}\mathcal{NP}\not\subseteq \mathcal{NP}$) have ... more >>>

Igor Carboni Oliveira, Lijie Chen, Shuichi Hirahara, Ján Pich, Ninad Rajgopal, Rahul Santhanam

Hardness magnification reduces major complexity separations (such as $EXP \not\subseteq NC^1$) to proving lower bounds for some natural problem $Q$ against weak circuit models. Several recent works [OS18, MMW19, CT19, OPS19, CMMW19, Oli19, CJW19a] have established results of this form. In the most intriguing cases, the required lower bound is ... 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 >>>

Lijie Chen, Dylan McKay, Cody Murray, Ryan Williams

Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems

A frontier open problem in circuit complexity is to prove P^NP is not in SIZE[n^k] for all k; this is a necessary intermediate step towards NP is not in P/poly. Previously, for several classes containing P^NP, including NP^NP, ZPP^NP, and ... more >>>

Lijie Chen, Ofer Grossman

Consider the multiparty communication complexity model where there are n processors, each receiving as input a row of an n by n matrix M with entries in {0, 1}, and in each round each party can broadcast a single bit to all other parties (this is known as the BCAST(1) ... more >>>

Lijie Chen

Following the seminal work of [Williams, J. ACM 2014], in a recent breakthrough, [Murray and Williams, STOC 2018] proved that NQP (non-deterministic quasi-polynomial time) does not have polynomial-size ACC^0 circuits.

We strengthen the above lower bound to an average case one, by proving that for all constants c, ...
more >>>

Lijie Chen, Roei Tell

The best-known lower bounds for the circuit class $\mathcal{TC}^0$ are only slightly super-linear. Similarly, the best-known algorithm for derandomization of this class is an algorithm for quantified derandomization (i.e., a weak type of derandomization) of circuits of slightly super-linear size. In this paper we show that even very mild quantitative ... more >>>

Lijie Chen

In this paper we study the (Bichromatic) Maximum Inner Product Problem (Max-IP), in which we are given sets $A$ and $B$ of vectors, and the goal is to find $a \in A$ and $b \in B$ maximizing inner product $a \cdot b$. Max-IP is very basic and serves ...
more >>>

Scott Aaronson, Lijie Chen

In the near future, there will likely be special-purpose quantum computers with 40-50 high-quality qubits. This paper lays general theoretical foundations for how to use such devices to demonstrate "quantum supremacy": that is, a clear quantum speedup for some task, motivated by the goal of overturning the Extended Church-Turing Thesis ... more >>>

Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan

In both query and communication complexity, we give separations between the class NISZK, containing those problems with non-interactive statistical zero knowledge proof systems, and the class UPP, containing those problems with randomized algorithms with unbounded error. These results significantly improve on earlier query separations of Vereschagin [Ver95] and Aaronson [Aar12] ... more >>>