463 citations · 1k across the 47 of their papers we have counts for
3 papers · 1 filter
It'll probably work out: improved list-decoding through random operations
Atri Rudra, Mary Wootters
In this work, we introduce a framework to study the effect of random operations on the combinatorial list-decodability of a code. The operations we consider correspond to row and c…
Sparse Approximation, List Decoding, and Uncertainty Principles
Mahmoud Abo Khamis, Anna C. Gilbert, Hung Q. Ngo +1
We consider list versions of sparse approximation problems, where unlike the existing results in sparse approximation that consider situations with unique solutions, we are interes…
Joins via Geometric Resolutions: Worst-case and Beyond
Mahmoud Abo Khamis, Hung Q. Ngo, Christopher Ré +1
We present a simple geometric framework for the relational join. Using this framework, we design an algorithm that achieves the fractional hypertree-width bound, which generalizes…