Jason Li

Publications

• Anupam Gupta, Euiwoong Lee, Jason Li. Faster Exact and Approximate Algorithms for $k$-Cut. Submitted. (abstract)
  In the \kcut problem, we are given an edge-weighted graph $G$ and an integer $k$, and have to remove a set of edges with minimum total weight so that $G$ has at least $k$ connected components. The best current algorithms are an $O(n^{(2-o(1))k})$ randomized algorithm due to Karger and Stein (\emph{JACM '96)}), and an $\tilde{O}(n^{2k})$ deterministic algorithm due to Thorup (\emph{STOC '08}). Moreover, several $2$-approximation algorithms are known for the problem (due to Saran and Vazirani, Naor and Rabani, and Ravi and Sinha). It has remained an open problem to (a) improve the runtime of exact algorithms, and (b) to get better approximation algorithms. In this paper we show an $O(k^{O(k)} \, n^{(2\omega/3 + o(1))k})$-time algorithm for $k$-cut. Moreover, we show an $(1+\e)$-approximation algorithm that runs in time $O((k/\e)^{O(k)} \,n^{k + O(1)})$, and a $1.81$-approximation in fixed-parameter time $O(k^{O(k)}\,\poly(n))$.
• Anupam Gupta, Euiwoong Lee, Jason Li, Pasin Manurangsi, Michał Włodarczyk. Losing Treewidth by Separating Subsets. Submitted. (arXiv)
• Mohsen Ghaffari, Jason Li. New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms Submitted. (arXiv)
• Bernhard Haeupler, Jason Li. Faster Distributed Shortest Path Approximations via Shortcuts. Submitted. (arXiv)
• John Augustine, Mohsen Ghaffari, Robert Gmyr, Kristian Hinnenthal, Fabian Kuhn, Jason Li, Christian Scheideler. Distributed Computation in the Node-Congested Clique. Submitted. (abstract)
  In this paper, we introduce the \emph{Node-Congested Clique} as a general communication network model. Here, the nodes of a network are connected as a clique and messages are sent in synchronous communication rounds. In each round, every node can send and receive at most $O(\log n)$ many messages of size $O(\log n)$. This constitutes the main difference from the Node-Congested Clique model to similar models such as the Congested Clique model or the $k$-machine model, where bandwidth restrictions are typically posed on the networks \emph{links}. To initiate the research on this network model, we consider how to compute a \emph{Minimum Spanning Tree}, \emph{Single-Source Shortest Paths}, a \emph{Maximal Independent Set}, a \emph{Maximal Matching}, and a small \emph{Coloring} of a given subgraph $G$. We first present a set of communication primitives that make use of the fact that communication can be efficiently distributed among the network's nodes. We then apply these primitives to a combination of well-known graph algorithms to efficiently solve the above-mentioned problems. In the case of minimum spanning tree, our runtime is polylogarithmic. In all other cases, up to logarithmic factors, the runtime of our algorithms almost exclusively relies on the graph's \emph{arboricity}. We note that the arboricity is upper bounded by the degree of $G$, but it is only a constant for many important graph families such as planar graphs.
• Bernhard Haeupler, Jason Li, Goran Zuzic. Minor Excluded Network Families Admit Fast Distributed Algorithms. PODC 2018. (arXiv)
• Anupam Gupta, Amit Kumar, Jason Li. Non-Preemptive Flow-Time Minimization via Rejections. ICALP 2018. (abstract)
  We consider the online problem of minimizing weighted flow-time on unrelated machines. Although much is known about this problem in the resource augmentation setting, these results assume that jobs can be preempted. We give the first constant competitive algorithm for the non-preemptive setting in the rejection model where we are allowed to reject $\eps$-fraction of the total weight of jobs, but we compare with the offline optimum which is required to schedule all jobs. This is arguably the weakest assumption in which such a result is known for weighted flow-time on unrelated machines. Although we rely on dual fitting techniques, we need more machinery to carefully reject jobs which have low weight and yet can certify that the cost of our algorithm is within a constant of the optimum.
• Mohsen Ghaffari, Jason Li. Improved Distributed Algorithms for Exact Shortest Paths. STOC 2018. (arXiv)
• Anupam Gupta, Euiwoong Lee, Jason Li. An FPT Algorithm Beating 2-Approximation for k-Cut. SODA 2018. (arXiv)

Older Publications

• Jason Li, Ryan O'Donnell. Bounding laconic proof systems by solving CSPs in parallel. SPAA 2017.
• S Bhupatiraju, P Etingof, D Jordan, W Kuszmaul, J Li. Lower central series of a free associative algebra over the integers and finite fields. Journal of Algebra (2012). (arXiv)