research
∙
07/26/2023
On Minimizing Generalized Makespan on Unrelated Machines
We consider the Generalized Makespan Problem (GMP) on unrelated machines...
share
research
∙
11/10/2022
DrawMon: A Distributed System for Detection of Atypical Sketch Content in Concurrent Pictionary Games
Pictionary, the popular sketch-based guessing game, provides an opportun...
research
∙
09/17/2022
A Nearly Tight Lower Bound for the d-Dimensional Cow-Path Problem
In the d-dimensional cow-path problem, a cow living in ℝ^d must locate a...
research
∙
08/24/2022
Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank
We give a simple proof of the matrix Spencer conjecture up to poly-logar...
research
∙
05/13/2022
Balanced Allocations: The Heavily Loaded Case with Deletions
In the 2-choice allocation problem, m balls are placed into n bins, and ...
research
∙
05/02/2022
A Unified Approach to Discrepancy Minimization
We study a unified approach and algorithm for constructive discrepancy m...
research
∙
04/25/2022
Smoothed Analysis of the Komlós Conjecture
The well-known Komlós conjecture states that given n vectors in ℝ^d with...
research
∙
03/01/2022
Influence in Completely Bounded Block-multilinear Forms and Classical Simulation of Quantum Algorithms
The Aaronson-Ambainis conjecture (Theory of Computing '14) says that eve...
research
∙
02/04/2022
Flow Time Scheduling and Prefix Beck-Fiala
We relate discrepancy theory with the classic scheduling problems of min...
research
∙
11/30/2021
Online metric allocation
We introduce a natural online allocation problem that connects several o...
research
∙
11/13/2021
Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing
A well-known result of Banaszczyk in discrepancy theory concerns the pre...
research
∙
06/10/2021
Well-Balanced Allocation on General Graphs
We study the graphical generalization of the 2-choice balls-into-bins pr...
research
∙
11/18/2020
Scale-Free Allocation, Amortized Convexity, and Myopic Weighted Paging
Inspired by Belady's optimal algorithm for unweighted paging, we conside...
research
∙
11/13/2020
Some remarks on hypergraph matching and the Füredi-Kahn-Seymour conjecture
A classic conjecture of Füredi, Kahn and Seymour (1993) states that give...
research
∙
08/16/2020
k-Forrelation Optimally Separates Quantum and Classical Query Complexity
Aaronson and Ambainis (SICOMP `18) showed that any partial function on N...
research
∙
07/30/2020
An Asymptotic Lower Bound for Online Vector Bin Packing
We consider the online vector bin packing problem where n items specifie...
research
∙
07/21/2020
Online Discrepancy Minimization for Stochastic Arrivals
In the stochastic online vector balancing problem, vectors v_1,v_2,…,v_T...
research
∙
07/17/2020
Improved Approximations for Min Sum Vertex Cover and Generalized Min Sum Set Cover
We study the generalized min sum set cover (GMSSC) problem, wherein give...
research
∙
12/06/2019
Online Vector Balancing and Geometric Discrepancy
We consider an online vector balancing question where T vectors, chosen ...
research
∙
07/11/2019
Geometry of Scheduling on Multiple Machines
We consider the following general scheduling problem: there are m identi...
research
∙
05/04/2019
New Notions and Constructions of Sparsification for Graphs and Hypergraphs
A sparsifier of a graph G (Benczúr and Karger; Spielman and Teng) is a s...
research
∙
03/16/2019
On-Line Balancing of Random Inputs
We consider an online vector balancing game where vectors v_t, chosen un...
research
∙
12/19/2018
Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems
Semidefinite programming is a powerful tool in the design and analysis o...
research
∙
11/05/2018
On a generalization of iterated and randomized rounding
We give a general method for rounding linear programs that combines the ...
research
∙
10/08/2018
On the discrepancy of random low degree set systems
Motivated by the celebrated Beck-Fiala conjecture, we consider the rando...
research
∙
09/12/2018
Packing Sporadic Real-Time Tasks on Identical Multiprocessor Systems
In real-time systems, in addition to the functional correctness recurren...
research
∙
12/13/2017
Potential-Function Proofs for First-Order Methods
This note discusses proofs for convergence of first-order methods based ...
research
∙
08/11/2017