(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
My current research interest mainly lies in the following three directions: algebraic complexity, sum-of-squares hierarchy, and unique games conjecture.
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 (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 (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.
During my undergraduate study at National Taiwan University and research assistanship in Academia Sinica, I was mostly interested in computational complexity and computational tradeoffs in statistical problems. The followings is the introduction to some of my work. Feel free to leave any comments and corrections!