COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

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

## Learning low-degree functions from few random queriesAdd to your list(s) Download to your calendar using vCal - Alexandros Eskenazis (Cambridge)
- Tuesday 02 November 2021, 15:30-16:30
- MR12 Centre for Mathematical Sciences.
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:- All CMS events
- All Talks (aka the CURE list)
- CMS Events
- DPMMS Lists
- DPMMS info aggregator
- DPMMS lists
- Hanchen DaDaDash
- Interested Talks
- MR12 Centre for Mathematical Sciences
- Probability
- School of Physical Sciences
- Statistical Laboratory info aggregator
- bld31
Note that ex-directory lists are not shown. |
## Other listsWolfson Research Event 2016 Type the title of a new list here Confirm List Here## Other talksOptimizing Quantum Hardware Resources with Classical Stochastic Methods Why Johnny doesnâ€™t write secure software? Constraining the composition of exo-planetary material around white dwarf stars Novel Phases of Elemental Sulfur under Extreme Compression Learning and Extrapolation in Graph Neural Networks |