research
∙
06/30/2023
Analyzing Generalized Pólya Urn Models using Martingales, with an Application to Viral Evolution
The randomized play-the-winner (RPW) model is a generalized Pólya Urn pr...
share
research
∙
02/16/2023
THC: Accelerating Distributed Deep Learning Using Tensor Homomorphic Compression
Deep neural networks (DNNs) are the de-facto standard for essential use ...
research
∙
06/30/2022
Proteus: A Self-Designing Range Filter
We introduce Proteus, a novel self-designing approximate range filter, w...
research
∙
05/26/2022
QUIC-FL: Quick Unbiased Compression for Federated Learning
Distributed Mean Estimation (DME) is a fundamental building block in com...
research
∙
04/29/2022
FRANCIS: Fast Reaction Algorithms for Network Coordination In Switches
Distributed protocols are widely used to support network functions such ...
research
∙
03/05/2022
Tabula: Efficiently Computing Nonlinear Activation Functions for Secure Neural Network Inference
Multiparty computation approaches to secure neural network inference tra...
research
∙
02/11/2022
Incentive Compatible Queues Without Money
For job scheduling systems, where jobs require some amount of processing...
research
∙
02/04/2022
Direct Telemetry Access
The emergence of programmable switches allows operators to collect a vas...
research
∙
10/11/2021
Zero-CPU Collection with Direct Telemetry Access
Programmable switches are driving a massive increase in fine-grained mea...
research
∙
10/01/2021
Uniform Bounds for Scheduling with Job Size Estimates
We consider the problem of scheduling to minimize mean response time in ...
research
∙
08/19/2021
Communication-Efficient Federated Learning via Robust Distributed Mean Estimation
Federated learning commonly relies on algorithms such as distributed (mi...
research
∙
06/10/2021
Gradient Disaggregation: Breaking Privacy in Federated Learning by Reconstructing the User Participant Matrix
We show that aggregated model updates in federated learning may be insec...
research
∙
05/18/2021
DRIVE: One-bit Distributed Mean Estimation
We consider the problem where n clients transmit d-dimensional real-valu...
research
∙
02/24/2021
SALSA: Self-Adjusting Lean Streaming Analytics
Counters are the fundamental building block of many data sketching schem...
research
∙
01/18/2021
Dynamic Longest Increasing Subsequence and the Erdös-Szekeres Partitioning Problem
In this paper, we provide new approximation algorithms for dynamic varia...
research
∙
11/21/2020
Erdös-Szekeres Partitioning Problem
In this note, we present a substantial improvement on the computational ...
research
∙
10/05/2020
How to send a real number using a single bit (and some shared randomness)
We consider the fundamental problem of communicating an estimate of a re...
research
∙
07/07/2020
PINT: Probabilistic In-band Network Telemetry
Commodity network devices support adding in-band telemetry measurements ...
research
∙
06/27/2020
Queues with Small Advice
Motivated by recent work on scheduling with predicted job sizes, we cons...
research
∙
06/16/2020
Algorithms with Predictions
We introduce algorithms that use predictions from machine learning appli...
research
∙
06/05/2020
Partitioned Learned Bloom Filter
Bloom filters are space-efficient probabilistic data structures that are...
research
∙
04/21/2020
Faster and More Accurate Measurement through Additive-Error Counters
Counters are a fundamental building block for networking applications su...
research
∙
03/13/2020
Joint Alignment From Pairwise Differences with a Noisy Oracle
In this work we consider the problem of recovering n discrete random var...
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
∙
09/21/2019
Optimal Learning of Joint Alignments with a Faulty Oracle
We consider the following problem, which is useful in applications such ...
research
∙
05/23/2019
The Supermarket Model with Known and Predicted Service Times
The supermarket model typically refers to a system with a large number o...
research
∙
02/02/2019
Scheduling with Predictions and the Price of Misprediction
In many traditional job scheduling settings, it is assumed that one know...
research
∙
01/30/2019
Online Pandora's Boxes and Bandits
We consider online variations of the Pandora's box problem (Weitzman. 19...
research
∙
01/03/2019
A Model for Learned Bloom Filters, and Optimizing by Sandwiching
Recent work has suggested enhancing Bloom filters by using a pre-filter,...
research
∙
07/25/2018
Robust Set Reconciliation via Locality Sensitive Hashing
We consider variations of set reconciliation problems where two parties,...
research
∙
07/25/2018
Directory Reconciliation
We initiate the theoretical study of directory reconciliation, a general...
research
∙
07/24/2018
Metric Sublinear Algorithms via Linear Sampling
In this work we provide a new technique to design fast approximation alg...
research
∙
03/05/2018
Optimizing Learned Bloom Filters by Sandwiching
We provide a simple method for improving the performance of the recently...
research
∙
02/03/2018
A Model for Learned Bloom Filters and Related Structures
Recent work has suggested enhancing Bloom filters by using a pre-filter,...
research
∙
12/05/2017
Arithmetic Progression Hypergraphs: Examining the Second Moment Method
In many data structure settings, it has been shown that using "double ha...
research
∙
09/19/2017
Predicting Positive and Negative Links with Noisy Queries: Theory & Practice
Social networks and interactions in social media involve both positive a...
research
∙
09/03/2017
Simulated Annealing for JPEG Quantization
JPEG is one of the most widely used image formats, but in some ways rema...
research
∙
02/21/2016
2-Bit Random Projections, NonLinear Estimators, and Approximate Near Neighbor Search
The method of random projections has become a standard tool for machine ...
research
∙
01/27/2013