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

## Algorithms and barriers for random instances of computational problemsAdd to your list(s) Download to your calendar using vCal - Will Perkins (Dept of Mathematics, University of Birmingham)
- Friday 19 May 2017, 11:00-12:00
- Computer Science Sloman Lounge.
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. ## This talk is included in these lists:- Computer Science Departmental Series
- Computer Science Distinguished Seminars
- Computer Science Sloman Lounge
- Theoretical computer science seminar
Note that ex-directory lists are not shown. |
## Other listsIMA West Midlands Branch Reading Group in Combinatorics and Probability http://talks.bham.ac.uk/show/index/1942## Other talksVerification of Byzantine Fault Tolerant Systems RSC 2019 Dalton Emerging Researcher Award Lecture RSC S F Boys-A Rahman Award Lecture Privileged side-channel attacks for enclave adversaries First and second order shape optimization based on restricted mesh deformations An attack on ECDSA using lattice techniques |