University of Cambridge > Talks.cam > Statistics > Statistical algorithms and planted satisfiability problems

  Browse A-Z

Log in

Googledetails Microsoftdetails

🔐 Log In

Information on

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

ℹ️ Information

Statistical algorithms and planted satisfiability problems

Download to your calendar using vCal

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:

Note that ex-directory lists are not shown.

Other lists

Geometry and Topology colloquium Peterhouse Theatre, dinner in Hall in Pembroke Seminar Room (Level 2), Dept of Pharmacology or Join online: https://zoom.us/j/93332623395?pwd=ejMrUUhHOG1qK2N6dzg3ZStmQXdHQT09 Meeting ID: 933 3262 3395 Passcode: v1SSfY1xB3

Other talks

Title TBC Why people with schizophrenia die earlier? Mortality and accelerated ageing CONFERENCE: Chemical and material sciences enabled by AI and automation Title to be confirmed Title TBC The elephant in the room: Machine Learning directly into physical models
 

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