국윤범

Graph compression or sparsification is a basic information-theoretic and computational question. A major open problem in this research area is whether $(1+\epsilon)$-approximate cut-preserving vertex sparsifiers with size close to the number of terminals exist. As a step towards this goal, we initiate the study of a thresholded version of the problem: for a given parameter $c$, …

Since the development of the first randomized polynomial-time algorithm for volume computation by Dyer, Frieze, and Kannan in 1989, convex-body sampling has been a central problem at the intersection of algorithms, geometry, and probability. A major milestone came in 1997, when Kannan, Lovász, and Simonovits analyzed the Ball Walk and formulated the influential KLS conjecture. …