19 citations · 36 across the 15 of their papers we have counts for
21 papers
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…
A threshold for online balancing of sparse i.i.d. vectors
Dylan J. Altschuler, Konstantin Tikhomirov
Consider the task of \textit{online} vector balancing for stochastic arrivals , where the time horizon satisfies , and the are i.i.d uniform -…
Metric Poincaré inequalities for graphs
Dylan J. Altschuler, Pandelis Dodos, Konstantin Tikhomirov +1
This article obtains purely metric counterparts of cornerstone results in the theory of embedding graphs into normed spaces. Our first main result is a metric analogue of Matoušek'…
Metric dimension reduction modulus for superlogarithmic distortion
Dylan J. Altschuler, Konstantin Tikhomirov
The metric dimension reduction modulus is the smallest such that every --point metric space can be embedded into some -dimensional normed space, with…
Discrete Poincaré inequalities and universal approximators for random graphs
Dylan J. Altschuler, Pandelis Dodos, Konstantin Tikhomirov +1
Nonlinear Poincaré inequalities are indispensable tools in the study of dimension reduction and low-distortion embeddings of graphs into metric spaces, and have found remarkable al…
A universal threshold for geometric embeddings of trees
Dylan J. Altschuler, Pandelis Dodos, Konstantin Tikhomirov +1
A graph is geometrically embeddable into a normed space when there is a mapping such that if and only if , for…
Universal geometric non-embedding of random regular graphs
Dylan J. Altschuler, Konstantin Tikhomirov
Let be fixed, be a large integer. It is a classical result that --regular expanders on vertices are not embeddable as geometric (distance) graphs into E…
Locally seeded embeddings, and Ramsey numbers of bipartite graphs with sublinear bandwidth
Dylan J. Altschuler, Han Huang, Konstantin Tikhomirov
A seminal result of Lee asserts that the Ramsey number of any bipartite -degenerate graph satisfies . In particular, this bound applies to every b…
A combinatorial approach to nonlinear spectral gaps
Dylan J. Altschuler, Pandelis Dodos, Konstantin Tikhomirov +1
A seminal open question of Pisier and Mendel--Naor asks whether every degree-regular graph which satisfies the classical discrete Poincaré inequality for scalar functions, also sat…
On spectral outliers of inhomogeneous symmetric random matrices
Dylan J. Altschuler, Patrick Oliveira Santos, Konstantin Tikhomirov +1
Sharp conditions for the presence of spectral outliers are well understood for Wigner random matrices with iid entries. In the setting of inhomogeneous symmetric random matrices (i…
A note on the capacity of the binary perceptron
Dylan J. Altschuler, Konstantin Tikhomirov
Determining the capacity of the Binary Perceptron is a long-standing problem. Krauth and Mezard (1989) conjectured an explicit value of , approximately equal to .833, an…
Zero-One Laws for Random Feasibility Problems
Dylan J. Altschuler
We introduce a general random model of a combinatorial optimization problem with geometric structure that encapsulates both linear programming and integer linear programming. Let $…
Critical Window of The Symmetric Perceptron
Dylan J. Altschuler
We study the critical window of the symmetric binary perceptron, or equivalently, combinatorial discrepancy. Consider the problem of finding a binary vector satisfying $\|Aσ\|_…
Localized radial roll patterns in higher space dimensions
Jason J. Bramburger, Dylan Altschuler, Chloe I. Avery +4
Localized roll patterns are structures that exhibit a spatially periodic profile in their center. When following such patterns in a system parameter in one space dimension, the len…
The Discrepancy of Random Rectangular Matrices
Dylan J. Altschuler, Jonathan Niles-Weed
A recent approach to the Beck-Fiala conjecture, a fundamental problem in combinatorics, has been to understand when random integer matrices have constant discrepancy. We give a com…
The Zoo of Solitons for Curve Shortening in
Dylan J. Altschuler, Steven J. Altschuler, Sigurd B. Angenent +1
We provide a detailed description of solutions of Curve Shortening in that are invariant under some one-parameter symmetry group of the equation, paying particular attention…