Data Structures and Algorithms
Covers data structures and analysis of algorithms. Roughly includes material in ACM Subject Classes E.1, E.2, F.2.1, and F.2.2.
Amplifying a hard Tarski family by dimension and width yields a (k/log k)^{Ω(log k)} lower bound, ruling out black-box Tarski solvers for…
· “Bootstrapping Classical and Quantum Query Lower Bounds for Finding Tarski Fixed Points”
A randomized algorithm matches a conditional lower bound for dense graphs, answering two-decade-old questions.
· “Incremental Exact Vertex Connectivity”
When an IBLT fails to decode, its count measurement shifts by a predictable amount that reverses direction between k=4 and k=5
· “Decoding Failure Biases IBLT Count Measurements: A Gaussian-Selection Law at the Peeling Threshold”
