research
∙
11/10/2022
The Randomized k-Server Conjecture is False!
We prove a few new lower bounds on the randomized competitive ratio for ...
share
research
∙
02/13/2022
Generalized Unrelated Machine Scheduling Problem
We study the generalized load-balancing (GLB) problem, where we are give...
research
∙
02/09/2022
Shortest Paths without a Map, but with an Entropic Regularizer
In a 1989 paper titled "shortest paths without a map", Papadimitriou and...
research
∙
12/22/2021
Identifying Mixtures of Bayesian Network Distributions
A Bayesian Network is a directed acyclic graph (DAG) on a set of n rando...
research
∙
07/15/2021
A Refined Approximation for Euclidean k-Means
In the Euclidean k-Means problem we are given a collection of n points D...
research
∙
12/29/2020
Source Identification for Mixtures of Product Distributions
We give an algorithm for source identification of a mixture of k product...
research
∙
11/24/2020
Min-Sum Clustering (with Outliers)
We give a constant factor polynomial time pseudo-approximation algorithm...
research
∙
07/16/2020
The Sparse Hausdorff Moment Problem, with Application to Topic Models
We consider the problem of identifying, from its first m noisy moments, ...
research
∙
06/25/2020
Approximation Algorithms for Clustering with Dynamic Points
In many classic clustering problems, we seek to sketch a massive data se...
research
∙
04/15/2020
Online Multiserver Convex Chasing and Optimization
We introduce the problem of k-chasing of convex functions, a simultaneou...
research
∙
07/11/2019
Proportional Dynamics in Exchange Economies
We study the Proportional Response dynamic in exchange economies, where ...
research
∙
04/08/2019