The background of this website consists of some equations, excerpt from some of my favourite papers.

$\phi(G) = O(k) \frac{\lambda_2}{\sqrt{\lambda_k}}$

This is the first theory paper. Cheeger inequality is a fundamental result in spectral graph theory. This inequality is not tight in many graphs appear in practice. In the paper, we refined the inequality and used it to provide theoretical justifications of spectral partitioning algorithm.


I have been fascinated by the wide applicability of the maximum flow problem since undergraduate. In the paper, we showed that one can solve the maximum flow problem on undirected graphs in almost linear time by “correctly” apply Frank Wolfe algorithm on the equation above.


My usual strategy to solve a problem is by playing around formulas. Aaron and I came up with this formula and used that solve linear programs faster. At that time we had no idea of the meaning of such formula. A few years later, we noticed from a paper by Richard and Michael that the maximizer $w$ is exactly the $\ell_p$ Lewis weight of the matrix $A_x$ which is defined in Banach space theory many decades ago!

$\mathbf{M}\approx_{\gamma}\left[\begin{array}{cc} \mathbf{I} & \mathbf{0}\\\mathbf{Z}_ {FF}^{(k)}\mathbf{M}_{FC} & \mathbf{I}\end{array}\right]\left[\begin{array}{cc}\mathbf{M}_{FF} & \mathbf{0}\\\mathbf{0} & \widetilde{\mathrm{Sc}}(\mathbf{M},F)\end{array}\right]\left[\begin{array}{cc}\mathbf{I} & \mathbf{M}_{CF}\mathbf{Z}_{FF}^{(k)}\\0 & \mathbf{I}\end{array}\right]$

The problem of solving symmetric diagonally dominant matrix has been studied for many centuries. In 2003, Spielman and Teng showed how to solve such matrix in nearly linear time. Ever since we have been asking what makes these matrices easy to solve. One explanation is that the family of such matrices is closed under Schur complement and can be represented by a sum of PSD matrices with small support. Using this, we showed how to solve such matrix in linear time with nearly linear time preprocessing.

$D_{t}\frac{dx}{dt} =-\frac{1}{2}g(x)^{-1}\mathrm{Tr}\left(g(x)^{-1}Dg(x)\right)$

Sampling from the uniform distribution of a given convex set is a fundamental problem in convex geometry. Many existing algorithms take at least linear number of iterations to generate a sample and hence impractical for large-scale problem. It turns out. one can generate random sample very efficiently using the Riemannian Hamiltonian dynamic.

$\mathbb{P}_{x\sim p}(f(x)\geq\mathbb{E}f(x)+t)\leq e^{-O(t^{2})/(t+\sqrt{n})}$

A few years ago, I was told that one may win a Fields medal by solving Kannan-Lovász-Simonovits Conjecture, a problem that has deep connections in algorithmic convex geometry and concentration of measure. This is how I got interested in the problems. Despite I am not able to solve the problem, Santosh and I got the best estimate on the problem and gave a tight estimate for a stronger statement. The equation above is a corollary of that result, which shows any 1-Lipschitz function $f$ concentrates around its mean under any isotropic log-concave distribution $p$.

$\sum_{u\in T}w_{u}\sum_{i\geq1}(x_{u,i}+\delta)\log(x_{u,i}+\delta)$

To be honest, I still don’t understand this equation and I hope someone can explain this to me for general graphs. Maybe this is simply a wrong direction.