University of Birmingham > Talks@bham > Theoretical computer science seminar > Algorithms and barriers for random instances of computational problems

  Browse A-Z

Log in

System Admin (disabled)details Birmingham usersdetails No account?details

Information on

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

Algorithms and barriers for random instances of computational problems

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

If you have a question about this talk, please contact Paul Taylor.

While P vs NP asks whether hard instances of NP-hard problems exist, the study of average-case complexity asks whether “typical” or random instances of NP-hard problems are hard. I’ll describe two classes of random computational problems: random satisfiability and the community detection problem and explain how ideas from statistical physics have led to new algorithms and an understanding of algorithmic barriers for these problems.

This talk is part of the Theoretical computer science seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

Molecular and Medical Physics Seminar Series http://talks.bham.ac.uk/show/index/1942 Artificial Intelligence and Natural Computation seminars

Other talks

An introduction to τ-exceptional sequences Waveform modelling and the importance of multipole asymmetry in Gravitational Wave astronomy Ultrafast Spectroscopy and Microscopy as probes of Energy Materials Life : it’s out there, but what and why ? TBA The tragic destiny of Mileva Marić Einstein
 

Talks@bham, University of Birmingham. Contact Us | Help and Documentation | Privacy and Publicity.
talks@bham is based on talks.cam from the University of Cambridge.