# Research

## Publications/Manuscripts

(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs with Boaz Barak, Zhixian Lei, Tselil Schramm, Yueqi Sheng - [arxiv]

On the Algorithmic Power of Spiking Neural Networks
with Kai-Min Chung, Chi-Jen Lu
- [arxiv]

Some Closure Results for Polynomial Factorization and Applications
with Mrinal Kumar, Noam Solomon
- Conference version: Proc. 33st Computational Complexity Conference (CCC), 2018
- [arxiv] [eccc]

## Current interest

My current research interest mainly lies in the following three directions: algebraic complexity, sum-of-squares hierarchy, and unique games conjecture.

### Algebraic complexity

Algebraic complexity concerns computational problems under algebraic models where arithmetic computations are allowed. One of the ultimate goal is to resolve the problem analogous to the $\P$ versus $\NP$ problem in the boolean world, i.e., the $\VP$ versus $\VNP$ problem.

My interest lies in the lower bounds problems in algebraic complexity. Specifically, I concerns the lower bounds for restricted arithmetic circuit classes such as depth four powering circuits, non-homogeneous depth three circuits, and elementary symmetric circuits of linear forms.

### Sum-of-squres hierarchy

Sum-of-squres (SoS) hierarchy is one of the most powerful convex relaxation hierarchy and provides many state-of-the-art algorithms for problems in approximation algorithms, machine learning, or even quantum computation. I strongly recommend the amazing lecture notes by Boaz Barak and David Steurer.

As SoS has been shown to be very powerful, some fundamental issues are still highly open. Here I list several of them that I concern: the optimality of SoS, better SoS rounding algorithm (say for polynomial optimization), SoS lower bounds for Max-Cut, etc.

### Unique games conjecture

Unique games conjecture (UGC) is one of the central problems in theoretical computer science. UGC captures the optimality of many hardness of approximation problems such as Max-Cut and Vertex-Cover.

Recently, there are some exciting progresses in proving 2-to-2 games conjecture. See the following papers.