Time-Space Tradeoffs for Learning Finite Functions from Random Evaluations, with Applications to Polynomials.

Paul Beame, Shayan Oveis Gharan, Xin Yang

Browse the full COLT paper archive.