A deterministic algorithm for sparse multivariate polynomial interpolation

Michael Ben-Or, Prasoon Tiwari · 1988

1 Pith paper cite this work. Polarity classification is still indexing.

1 Pith paper citing it

browse 1 citing papers

representative citing papers

cs.DS · 2025-09-09 · conditional · novelty 8.0

The optimal one-pass space for (1±ε)-estimating F2 in the low-error regime ε < 1/√n is Θ(n log(1/(ε^2 n))) bits.

Showing 1 of 1 citing paper.

Tight Bounds for Low-Error Frequency Moment Estimation and the Power of Multiple Passes cs.DS · 2025-09-09 · conditional · none · ref 8
The optimal one-pass space for (1±ε)-estimating F2 in the low-error regime ε < 1/√n is Θ(n log(1/(ε^2 n))) bits.