research
∙
04/23/2023
Robust and differentially private stochastic linear bandits
In this paper, we study the stochastic linear bandit problem under the a...
share
research
∙
03/21/2023
Optimal Fully Dynamic k-Center Clustering for Adaptive and Oblivious Adversaries
In fully dynamic clustering problems, a clustering of a given data set i...
research
∙
02/20/2023
Replicable Clustering
In this paper, we design replicable algorithms in the context of statist...
research
∙
10/21/2022
Anonymous Bandits for Multi-User Systems
In this work, we present and study a new framework for online learning i...
research
∙
10/04/2022
Reproducible Bandits
In this paper, we introduce the notion of reproducible policies in the c...
research
∙
07/13/2022
Smooth Anonymity for Sparse Binary Matrices
When working with user data providing well-defined privacy guarantees is...
research
∙
05/20/2022
Tackling Provably Hard Representative Selection via Graph Neural Networks
Representative selection (RS) is the problem of finding a small subset o...
research
∙
04/11/2022
Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Sets
Motivated by data analysis and machine learning applications, we conside...
research
∙
12/13/2021
Optimal Fully Dynamic k-Centers Clustering
We present the first algorithm for fully dynamic k-centers clustering in...
research
∙
10/22/2021
Tight and Robust Private Mean Estimation with Few Users
In this work, we study high-dimensional mean estimation under user-level...
research
∙
10/05/2021
Label differential privacy via clustering
We present new mechanisms for label differential privacy, a relaxation o...
research
∙
07/14/2021
Online Allocation and Display Ads Optimization with Surplus Supply
In this work, we study a scenario where a publisher seeks to maximize it...
research
∙
07/05/2021
Feature Cross Search via Submodular Optimization
In this paper, we study feature cross search as a fundamental primitive ...
research
∙
07/01/2021
Almost Tight Approximation Algorithms for Explainable Clustering
Recently, due to an increasing interest for transparency in artificial i...
research
∙
09/24/2020
Parallel Graph Algorithms in Constant Adaptive Rounds: Theory meets Practice
We study fundamental graph problems such as graph connectivity, minimum ...
research
∙
02/20/2020
Contextual Reserve Price Optimization in Auctions
We study the problem of learning a linear model to set the reserve price...
research
∙
11/09/2019
Adaptivity in Adaptive Submodularity
Adaptive sequential decision making is one of the central challenges in ...
research
∙
10/28/2019
Locality-Sensitive Hashing for f-Divergences: Mutual Information Loss and Beyond
Computing approximate nearest neighbors in high dimensional spaces is a ...
research
∙
10/11/2019
Near-Optimal Massively Parallel Graph Connectivity
Identifying the connected components of a graph, apart from being a fund...
research
∙
10/11/2019
Batched Multi-Armed Bandits with Optimal Regret
We present a simple and efficient algorithm for the batched stochastic m...
research
∙
10/09/2019
Prophets, Secretaries, and Maximizing the Probability of Choosing the Best
Suppose a customer is faced with a sequence of fluctuating prices, such ...
research
∙
10/02/2019
Streaming Balanced Clustering
Clustering of data points in metric space is among the most fundamental ...
research
∙
05/18/2019
Massively Parallel Computation via Remote Memory Access
We introduce the Adaptive Massively Parallel Computation (AMPC) model, w...
research
∙
05/10/2019
Seeding with Costly Network Information
The spread of behavior over social networks depends on the contact struc...
research
∙
04/30/2019
Categorical Feature Compression via Submodular Optimization
In the era of big data, learning from categorical features with very lar...
research
∙
01/30/2019
Online Pandora's Boxes and Bandits
We consider online variations of the Pandora's box problem (Weitzman. 19...
research
∙
08/07/2018
Parallel and Streaming Algorithms for K-Core Decomposition
The k-core decomposition is a fundamental primitive in many machine lear...
research
∙
07/24/2018
Metric Sublinear Algorithms via Linear Sampling
In this work we provide a new technique to design fast approximation alg...
research
∙
11/15/2017