research
∙
04/04/2023
Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
We investigate one of the most basic problems in streaming algorithms: a...
share
research
∙
03/16/2020
Beyond Alice and Bob: Improved Inapproximability for Maximum Independent Set in CONGEST
By far the most fruitful technique for showing lower bounds for the CONG...
research
∙
11/26/2019
Pseudo-deterministic Streaming
A pseudo-deterministic algorithm is a (randomized) algorithm which, when...
research
∙
11/15/2019
Strategy-Stealing is Non-Constructive
In many combinatorial games, one can prove that the first player wins un...
research
∙
05/19/2019
Broadcast Congested Clique: Planted Cliques and Pseudorandom Generators
We develop techniques to prove lower bounds for the BCAST(log n) Broadca...
research
∙
08/02/2018
Algorithms for Noisy Broadcast under Erasures
The noisy broadcast model was first studied in [Gallager, TranInf'88] wh...
research
∙
03/11/2018