4 papers
Near-Optimal Oracle Bounds for Isotropic Rounding
Yang P. Liu, Richard Peng, Alicia Stepin +1
We give optimal bounds, up to polylogarithmic factors, for rounding convex bodies to near-isotropic position. A convex body in can be rou…
Faster high-accuracy multicommodity flow in dense graphs
Chenxin Dai, Alicia Stepin, Colin Tang
We give a fast algorithm for solving min-cost -commodity flow. The basic idea is to construct an auxiliary linear program that has low rank and whose minimum value is at most $1…
On the Structure of Bad Science Matrices
Alex Albors, Hisham Bhatti, Lukshya Ganjoo +5
The bad science matrix problem consists in finding, among all matrices with rows having unit norm, one that maximizes $β(A) = \frac{1}{2^n}…
On the Power of Learning-Augmented Search Trees
Jingbang Chen, Xinyuan Cao, Alicia Stepin +1
We study learning-augmented binary search trees (BSTs) via Treaps with carefully designed priorities. The result is a simple search tree in which the depth of each item is dete…