Algorithms and barriers for random instances of computational problems
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:
Note that ex-directory lists are not shown.
Other listsFeatured talks BritGrav 15 EPS - College Research and KT Support Activities
Other talksOpen slot Growth of homology torsion Joint BSN and MSC Seminar Broadband molecular fingerprinting with laser frequency combs Online Ensemble Learning of Data Streams with Gradually Evolved Classes The 2017 Haworth Lecture