research
∙
05/03/2021
Distributional Collision Resistance Beyond One-Way Functions
Distributional collision resistance is a relaxation of collision resista...
share
research
∙
01/22/2021
Adversarial Laws of Large Numbers and Optimal Regret in Online Classification
Laws of large numbers guarantee that given a large enough sample from so...
research
∙
03/31/2020
A Framework for Adversarially Robust Streaming Algorithms
We investigate the adversarial robustness of streaming algorithms. In th...
research
∙
06/26/2019
The Adversarial Robustness of Sampling
Random sampling is a fundamental primitive in modern algorithms, statist...
research
∙
04/16/2019
Parallel Balanced Allocations: The Heavily Loaded Case
We study parallel algorithms for the classical balls-into-bins problem, ...
research
∙
12/28/2018
The Power of Distributed Verifiers in Interactive Proofs
We explore the power of interactive proofs with a distributed verifier. ...
research
∙
12/09/2018
Low Congestion Cycle Covers and their Applications
A cycle cover of a bridgeless graph G is a collection of simple cycles i...
research
∙
05/14/2018
Congested Clique Algorithms for Graph Spanners
Graph spanners are sparse subgraphs that faithfully preserve the distanc...
research
∙
12/04/2017
Distributed Computing Made Secure: A New Cycle Cover Theorem
In the area of distributed graph algorithms a number of network's entiti...
research
∙
11/01/2016