Lower Bounds and Open Problems in Streams
Talkat Computational Complexity of Low-Polynomial Time Problems (Simons Institute workshop, 2015) · on Tuesday, 2015-12-08
summary
Proves unconditional streaming lower bounds in the cell-probe model: online convolution requires Ω(Δ·log n / w) amortized cell probes per output (Δ = bits per symbol), matching a known FFT-based offline→online conversion that yields O(log^2 n) time when w ≈ Δ ≈ log n. Main tool is the information transfer method and an information-transfer tree; for binary or rearrangement-style pattern matching a new gap + hard-distribution trick gives stronger Ω(log^2 n / (w log log n)) bounds. Leaves open the entropy question for consecutive inner products (Toeplitz matrix rows).
AI-written summary · about