19 citations · 36 across the 15 of their papers we have counts for
6 papers · 1 filter
Satisfiability and freezing in random integer programs
Dylan J. Altschuler, Ruben Ascoli, Will Perkins
We study a model of a random centrally symmetric polytope and ask about the existence of points in the polytope with non-zero, integer coordinates. Our main results are the locatio…
Improved Algorithms for Beck--Fiala with Bounded Sets
Dylan J. Altschuler
We give an efficient algorithm with improved algorithmic guarantees for the (offline) Beck--Fiala problem when the sets have bounded size. Let be an arbitrary matrix $A\in\{0,1…
The threshold for online balancing of i.i.d. binary vectors
Dylan J. Altschuler, Konstantin Tikhomirov
Consider the task of online vector balancing for stochastic arrivals , where the are independent uniformly random --sparse binary vectors in .…
Long-range expanders: construction and cutoff
Dylan J. Altschuler
Long-range expansion is a combinatorial graph property introduced to construct metric spaces with strong quantitative obstructions to low-distortion embeddings. Such extremal const…
Online Permutation Embedding: Optimal Stopping and Scaling Laws
Dylan J. Altschuler, Quentin Dubroff, Konstantin Tikhomirov
We study optimal online algorithms for embedding a permutation of into an iid stream of uniform random variables. This problem is a broad generalization of the cl…
Online Beck--Fiala Down to Logarithmic Sparsity
Dylan J. Altschuler, Konstantin Tikhomirov
The Beck--Fiala conjecture asserts that every matrix with at most nonzero entries in each column has discrepancy . A major breakthrough re…