research
∙
06/27/2023
Randomized vs. Deterministic Separation in Time-Space Tradeoffs of Multi-Output Functions
We prove the first polynomial separation between randomized and determin...
share
research
∙
06/04/2023
Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries
A dictionary data structure maintains a set of at most n keys from the u...
research
∙
04/18/2023
Super-Logarithmic Lower Bounds for Dynamic Graph Problems
In this work, we prove a Ω̃(^3/2 n ) unconditional lower bound on the ma...
research
∙
12/30/2022
Detecting TCP Packet Reordering in the Data Plane
Network administrators want to detect TCP-level packet reordering to dia...
research
∙
11/08/2022
On the amortized complexity of approximate counting
Naively storing a counter up to value n would require Ω(log n) bits of m...
research
∙
09/29/2022
On Constructing Spanners from Random Gaussian Projections
Graph sketching is a powerful paradigm for analyzing graph structure via...
research
∙
08/23/2022
Strong XOR Lemma for Communication with Bounded Rounds
In this paper, we prove a strong XOR lemma for bounded-round two-player ...
research
∙
02/22/2021
Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs
For a directed graph G with n vertices and a start vertex u_ start, we w...
research
∙
10/05/2020
Optimal bounds for approximate counting
Storing a counter incremented N times would naively consume O(log N) bit...
research
∙
09/07/2020
Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems
Consider the following gap cycle counting problem in the streaming model...
research
∙
07/24/2020
Tight Distributed Sketching Lower Bound for Connectivity
In this paper, we study the distributed sketching complexity of connecti...
research
∙
04/26/2020
Succinct Filters for Sets of Unknown Sizes
The membership problem asks to maintain a set S⊆[u], supporting insertio...
research
∙
04/13/2020
Lower Bound for Succinct Range Minimum Query
Given an integer array A[1..n], the Range Minimum Query problem (RMQ) as...
research
∙
11/04/2019
Faster Update Time for Turnstile Streaming Algorithms
In this paper, we present a new algorithm for maintaining linear sketche...
research
∙
11/04/2019
Nearly Optimal Static Las Vegas Succinct Dictionary
Given a set S of n (distinct) keys from key space [U], each associated w...
research
∙
07/25/2019
How to Store a Random Walk
Motivated by storage applications, we study the following data structure...
research
∙
11/05/2018
Optimal Succinct Rank Data Structure via Approximate Nonnegative Tensor Decomposition
Given an n-bit array A, the succinct rank data structure problem asks to...
research
∙
07/13/2018
Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation
We show optimal lower bounds for spanning forest computation in two diff...
research
∙
12/23/2017