17 citations · 29 across the 5 of their papers we have counts for
4 papers · 1 filter
Beyond Natural Proofs: Hardness Magnification and Locality
Lijie Chen, Shuichi Hirahara, Igor C. Oliveira +3
Hardness magnification reduces major complexity separations (such as ) to proving lower bounds for some natural problem against…
Classical Algorithms from Quantum and Arthur-Merlin Communication Protocols
Lijie Chen, Ruosong Wang
The polynomial method from circuit complexity has been applied to several fundamental problems and obtains the state-of-the-art running times. As observed in [Alman and Williams, S…
Toward Super-Polynomial Size Lower Bounds for Depth-Two Threshold Circuits
Lijie Chen
Proving super-polynomial size lower bounds for , the class of constant-depth, polynomial-size circuits of Majority gates, is a notorious open problem in complexity t…
On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product
Lijie Chen
In this paper we study the (Bichromatic) Maximum Inner Product Problem (Max-IP), in which we are given sets and of vectors, and the goal is to find and …