All reports by Author Lijie Chen:

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