Statistical algorithms and planted satisfiability problems

Add to your list(s) Download to your calendar using vCal

• Will Perkins (Birmingham)
• Friday 05 February 2016, 16:00-17:00
• MR12, Centre for Mathematical Sciences, Wilberforce Road, Cambridge..

If you have a question about this talk, please contact Quentin Berthet.

I will discuss a general framework originating in learning theory for proving average-case algorithmic lower bounds for the class of “statistical algorithms”. I will give an overview of the types of algorithmic approaches that can be implemented in this framework, and then discuss the example of planted random satisfiability problems, for which we can identify a tractability threshold for statistical algorithms. Based on joint work with Vitaly Feldman and Santosh Vempala.

This talk is part of the Statistics series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge Forum of Science and Humanities
• Cambridge Language Sciences
• Cambridge talks
• Chris Davis' list
• DPMMS Lists
• DPMMS info aggregator
• DPMMS lists
• Guy Emerson's list
• Hanchen DaDaDash
• Interested Talks
• MR12, Centre for Mathematical Sciences, Wilberforce Road, Cambridge.
• Machine Learning
• School of Physical Sciences
• Statistical Laboratory info aggregator
• Statistics
• Statistics Group
• Trust & Technology Initiative - interesting events
• bld31
• custom
• ndk22's list
• ob366-ai4er
• rp587

Note that ex-directory lists are not shown.