Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure

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

• Guy Bresler (Massachusetts Institute of Technology)
• Tuesday 26 June 2018, 09:00-09:45
• Seminar Room 1, Newton Institute.

If you have a question about this talk, please contact INI IT.

STSW04 - Future challenges in statistical scalability

The prototypical high-dimensional statistics problem entails finding a structured signal in noise. Many of these problems exhibit a curious phenomenon: the amount of data needed by all known computationally efficient algorithms far exceeds what is needed for inefficient algorithms that search over all possible structures. A line of work initiated by Berthet and Rigollet in 2013 has aimed to explain these gaps by reducing from conjecturally hard problems in computer science. However, the delicate nature of average-case reductions has limited the applicability of this approach. In this work we introduce several new techniques to give a web of average-case reductions showing strong computational lower bounds based on the planted clique conjecture. These include tight lower bounds for Planted Independent Set, Planted Dense Subgraph, Sparse Spiked Wigner, Sparse PCA , as well as for new models that we introduce. Joint work with Matthew Brennan and Wasim Huleihel.

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

• All CMS events
• Featured lists
• INI info aggregator
• Isaac Newton Institute Seminar Series
• School of Physical Sciences
• Seminar Room 1, Newton Institute
• bld31

Note that ex-directory lists are not shown.