research
∙
08/02/2023
Optimal Online Discrepancy Minimization
We prove that there exists an online algorithm that for any sequence of ...
share
research
∙
07/30/2023
Polytopes with Bounded Integral Slack Matrices Have Sub-Exponential Extension Complexity
We show that any bounded integral function f : A × B ↦{0,1, …, Δ} with r...
research
∙
03/26/2023
The Subspace Flatness Conjecture and Faster Integer Programming
In a seminal paper, Kannan and Lovász (1988) considered a quantity μ_KL(...
research
∙
11/07/2022
From approximate to exact integer programming
Approximate integer programming is the following: For a convex body K ⊆ℝ...
research
∙
10/29/2022
The Vector Balancing Constant for Zonotopes
The vector balancing constant vb(K,Q) of two symmetric convex bodies K,Q...
research
∙
07/07/2022
Approximate Carathéodory bounds via Discrepancy Theory
The approximate Carathéodory problem in general form is as follows: Give...
research
∙
10/05/2021
Approximate CVP in time 2^0.802 n – now in any norm!
We show that a constant factor approximation of the shortest and closest...
research
∙
07/13/2021
Tight bounds on the Fourier growth of bounded functions on the hypercube
We give tight bounds on the degree ℓ homogenous parts f_ℓ of a bounded f...
research
∙
04/30/2021
On the Hardness of Scheduling With Non-Uniform Communication Delays
In the scheduling with non-uniform communication delay problem, the inpu...
research
∙
07/10/2020
Vector Balancing in Lebesgue Spaces
A tantalizing conjecture in discrete mathematics is the one of Komlós, s...
research
∙
04/21/2020
Scheduling with Communication Delays via LP Hierarchies and Clustering
We consider the classic problem of scheduling jobs with precedence const...
research
∙
07/03/2019
Linear Size Sparsifier and the Geometry of the Operator Norm Ball
The Matrix Spencer Conjecture asks whether given n symmetric matrices in...
research
∙
07/19/2018
A Tale of Santa Claus, Hypergraphs and Matroids
A well-known problem in scheduling and approximation algorithms is the S...
research
∙
06/12/2018