Our knowledge can only be finite, while our ignorance must necessarily be infinite.
- Karl Popper
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.