Silvio Lattanzi

research

∙ 08/20/2023

Improved Differentially Private Densest Subgraph: Local and Purely Additive

We study the Densest Subgraph problem under the additional constraint of...

0 Michael Dinitz, et al. ∙

research

∙ 05/31/2023

Fully Dynamic Submodular Maximization over Matroids

Maximizing monotone submodular functions under a matroid constraint is a...

0 Paul Dütting, et al. ∙

research

∙ 10/25/2022

Efficient and Stable Fully Dynamic Facility Location

We consider the classic facility location problem in fully dynamic data ...

0 Sayan Bhattacharya, et al. ∙

research

∙ 09/08/2022

Active Learning of Classifiers with Label and Seed Queries

We study exact active learning of binary and multiclass classifiers with...

4 Marco Bressan, et al. ∙

research

∙ 08/16/2022

Deletion Robust Non-Monotone Submodular Maximization over Matroids

Maximizing a submodular function is a fundamental task in machine learni...

0 Paul Dütting, et al. ∙

research

∙ 06/17/2022

Scalable Differentially Private Clustering via Hierarchically Separated Trees

We study the private k-median and k-means clustering problem in d dimens...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 03/02/2022

Near-Optimal Correlation Clustering with Privacy

Correlation clustering is a central problem in unsupervised learning, wi...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 01/31/2022

Deletion Robust Submodular Maximization over Matroids

Maximizing a monotone submodular function is a fundamental task in machi...

0 Paul Dütting, et al. ∙

research

∙ 12/01/2021

Efficient and Local Parallel Random Walks

Random walks are a fundamental primitive used in many machine learning a...

0 Michael Kapralov, et al. ∙

research

∙ 06/15/2021

Correlation Clustering in Constant Many Parallel Rounds

Correlation clustering is a central topic in unsupervised learning, with...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 06/09/2021

On Margin-Based Cluster Recovery with Oracle Queries

We study an active cluster recovery problem where, given a set of n poin...

0 Marco Bressan, et al. ∙

research

∙ 01/31/2021

Exact Recovery of Clusters in Finite Metric Spaces Using Oracle Queries

We investigate the problem of exact cluster recovery using oracle querie...

5 Marco Bressan, et al. ∙

research

∙ 01/14/2021

Spectral Clustering Oracles in Sublinear Time

Given a graph G that can be partitioned into k disjoint expanders with o...

0 Grzegorz Głuch, et al. ∙

research

∙ 12/22/2020

Fast and Accurate k-means++ via Rejection Sampling

k-means++ <cit.> is a widely used clustering algorithm that is easy to i...

0 Vincent Cohen-Addad, et al. ∙

research

∙ 11/13/2020

Consistent k-Clustering for General Metrics

Given a stream of points in a metric space, is it possible to maintain a...

0 Hendrik Fichtenberger, et al. ∙

research

∙ 11/13/2020

Secretaries with Advice

The secretary problem is probably the purest model of decision making un...

0 Paul Dütting, et al. ∙

research

∙ 10/22/2020

On Mean Estimation for Heteroscedastic Random Variables

We study the problem of estimating the common mean μ of n independent sy...

0 Luc Devroye, et al. ∙

research

∙ 10/14/2020

InstantEmbedding: Efficient Local Node Representations

In this paper, we introduce InstantEmbedding, an efficient method for ge...

25 Ştefan Postăvaru, et al. ∙

research

∙ 06/10/2020

Sliding Window Algorithms for k-Clustering Problems

The sliding window model of computation captures scenarios in which data...

0 Michele Borassi, et al. ∙

research

∙ 06/08/2020

Fully Dynamic Algorithm for Constrained Submodular Optimization

The task of maximizing a monotone submodular function under a cardinalit...

0 Silvio Lattanzi, et al. ∙

research

∙ 06/08/2020

Exact Recovery of Mangled Clusters with Same-Cluster Queries

We study the problem of recovering distorted clusters in the semi-superv...

0 Marco Bressan, et al. ∙

research

∙ 05/22/2019

Dynamic Algorithms for the Massively Parallel Computation Model

The Massive Parallel Computing (MPC) model gained popularity during the ...

0 Giuseppe F. Italiano, et al. ∙

research

∙ 05/05/2019

MapReduce Meets Fine-Grained Complexity: MapReduce Algorithms for APSP, Matrix Multiplication, 3-SUM, and Beyond

Distributed processing frameworks, such as MapReduce, Hadoop, and Spark ...

0 MohammadTaghi Hajiaghayi, et al. ∙

research

∙ 05/02/2019

Submodular Streaming in All its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity

Streaming algorithms are generally judged by the quality of their soluti...

4 Ehsan Kazemi, et al. ∙

research

∙ 08/07/2018

Parallel and Streaming Algorithms for K-Core Decomposition

The k-core decomposition is a fundamental primitive in many machine lear...

0 Hossein Esfandiari, et al. ∙

research

∙ 02/15/2018

Fair Clustering Through Fairlets

We study the question of fair clustering under the disparate impact doc...

0 Flavio Chierichetti, et al. ∙

research

∙ 12/28/2017

ASYMP: Fault-tolerant Mining of Massive Graphs

We present ASYMP, a distributed graph processing system developed for th...

0 Eduardo Fleury, et al. ∙

research

∙ 11/27/2017

One-Shot Coresets: The Case of k-Clustering

Scaling clustering algorithms to massive data sets is a challenging task...

0 Olivier Bachem, et al. ∙

research

∙ 04/30/2013

Local Graph Clustering Beyond Cheeger's Inequality

Motivated by applications of large-scale graph clustering, we study rand...

0 Zeyuan Allen-Zhu, et al. ∙

Silvio Lattanzi

Featured Co-authors