University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

Department Seminar by Matthew BrennanExport this event to calendar

Wednesday, November 25, 2020 — 11:00 AM EST

Please Note: This seminar will be given online.

Probability Seminar Series

Matthew Brennan, Ph.D. Student

MIT EECS

Link to join seminar: Hosted on Webex.

Reducibility and Statistical-Computational Gaps from Secret Leakage.


Inference problems with conjectured statistical-computational gaps are ubiquitous throughout modern statistics, computer science and statistical physics. While there has been success evidencing these gaps from the failure of restricted classes of algorithms, progress towards a more traditional reduction-based approach to computational complexity in statistical inference has been limited. Existing reductions have largely been limited to inference problems with similar structure -- primarily mapping among problems representable as a sparse submatrix signal plus a noise matrix, which are similar to the common hardness assumption of planted clique.


The insight in this work is that a slight generalization of the planted clique conjecture -- secret leakage planted clique -- gives rise to a variety of new average-case reduction techniques, yielding a web of reductions among problems with very different structure. Using variants of the planted clique
conjecture for specific forms of secret leakage planted clique, we deduce tight statistical-computational tradeoffs for a diverse range of problems including robust sparse mean estimation, mixtures of sparse linear regressions, robust sparse linear regression, tensor PCA, variants of dense $k$-block stochastic block models, negatively correlated sparse PCA, semirandom planted dense subgraph, detection in hidden partition models and a universality principle for learning sparse mixtures. This work suggests that an expanded set of hardness assumptions, such as for secret leakage planted clique, may be a first step towards a more complete theory of reductions among statistical problems.

This is based on joint work with Guy Bresler.

S M T W T F S
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
4
5
  1. 2021 (12)
    1. May (1)
    2. April (5)
    3. March (4)
    4. February (2)
  2. 2020 (72)
    1. December (3)
    2. November (13)
    3. October (16)
    4. September (7)
    5. August (5)
    6. July (3)
    7. June (2)
    8. May (1)
    9. March (4)
    10. February (4)
    11. January (14)
  3. 2019 (65)
    1. December (3)
    2. November (8)
    3. October (8)
    4. September (4)
    5. August (2)
    6. July (2)
    7. June (2)
    8. May (6)
    9. April (7)
    10. March (6)
    11. February (4)
    12. January (13)
  4. 2018 (44)
  5. 2017 (55)
  6. 2016 (44)
  7. 2015 (38)
  8. 2014 (44)
  9. 2013 (46)
  10. 2012 (44)