1.6k citations · 2.5k across the 77 of their papers we have counts for
10 papers · 1 filter
Faster Matroid Intersection
Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford +2
In this paper we consider the classic matroid intersection problem: given two matroids $\M_{1}=(V,\I_{1})$ and $\M_{2}=(V,\I_{2})$ defined over a common ground set , compute a s…
Strong Self-Concordance and Sampling
Aditi Laddha, Yin Tat Lee, Santosh Vempala
Motivated by the Dikin walk, we develop aspects of an interior-point theory for sampling in high dimension. Specifically, we introduce a symmetric parameter and the notion of stron…
Computing Circle Packing Representations of Planar Graphs
Sally Dong, Yin Tat Lee, Kent Quanrud
The Circle Packing Theorem states that every planar graph can be represented as the tangency graph of a family of internally-disjoint circles. A well-known generalization is the Pr…
Solving Linear Programs with Sqrt(rank) Linear System Solves
Yin Tat Lee, Aaron Sidford
We present an algorithm that given a linear program with variables, constraints, and constraint matrix , computes an -approximate solution in $\tilde{O}(\sqrt{rank(A)…
A Generalized Central Limit Conjecture for Convex Bodies
Haotian Jiang, Yin Tat Lee, Santosh S. Vempala
The central limit theorem for convex bodies says that with high probability the marginal of an isotropic log-concave distribution along a random direction is close to a Gaussian, w…
The Randomized Midpoint Method for Log-Concave Sampling
Ruoqi Shen, Yin Tat Lee
Sampling from log-concave distributions is a well researched problem that has many applications in statistics and machine learning. We study the distributions of the form $p^{*}\pr…