University of Cambridge > Talks.cam > Probability > Learning low-degree functions from few random queries

  Browse A-Z

Log in

University Account External (via Google)

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹ️ Information

Learning low-degree functions from few random queries

Download to your calendar using vCal

If you have a question about this talk, please contact Perla Sousi .

Let f be an unknown function on the n-dimensional discrete hypercube. How many values of f do we need in order to approximately reconstruct the function? In this talk we shall discuss the random query model for this fundamental problem from computational learning theory. We will explain a newly discovered connection with a family of polynomial inequalities going back to Littlewood (1930) which will in turn allow us to derive sharper estimates for the query complexity of this model, exponentially improving those which follow from the classical Low-Degree Algorithm of Linial, Mansour and Nisan (1989). Based on joint work with Paata Ivanisvili (UC Irvine).

This talk is part of the Probability series.

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

Seminar Room 2, Clinical School, Addenbrookes Hospital, Cambridge. Robinson Auditorium, Grange Road, Cambridge, CB3 9AN Prioress's Room, Jesus College

Other talks

Task performance predicts the substitution of feedforward by feedback drive in visual cortex Thelocactus Ensemble inequivalence for systems with long-range interactions Argentina 2005 The “Art” and the “Easy”: Nicolò Pasquali’s Keyboard World Rethinking Egyptian Writing in the Bronze Age Levant: Towards a Model of Adaptive Innovation for the Umm el-Marra Cylinders and Anra Scarabs
 

© 2006-2025 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity