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 NPhard problems exist, the study of averagecase complexity asks whether
“typical” or random instances of NPhard 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 exdirectory lists are not shown.
