[Sds-seminars] S&DS Seminar, Alex Wein, 2/12/24, 4pm-5pm, KT, "Fine-Grained Extensions of the Low-Degree Testing Framework"

[elizavette.torres at yale.edu]

 <https://statistics.yale.edu/>     <https://statistics.yale.edu/>
Department of Statistics and Data Science  

 

 <https://statistics.yale.edu/seminars/alex-wein-0> Alex Wein, University of
California, Davis

 

Date: Monday, February 12, 2024

Time: 4:00PM to 5:00PM

Location: Kline Tower
<http://maps.google.com/?q=219+Prospect+Street%2C+13+Floor%2C+Rm+1327%2C+New
+Haven%2C+CT%2C+06511%2C+us> see map 

219 Prospect Street, 13 Floor, Rm 1327

New Haven, CT 06511

Zoom Link: https://yale.zoom.us/j/94223816617 Meeting ID: 942 2381 6617

 <https://www.alex-wein.com/> Website

 

 

Fine-Grained Extensions of the Low-Degree Testing Framework

 

Information and Abstract:  The low-degree polynomial framework has emerged
as a versatile tool for probing the computational complexity of statistical
problems by studying the power and limitations of a restricted class of
algorithms: low-degree polynomials. Focusing on the setting of hypothesis
testing, I will discuss some extensions of this method that allow us to
tackle finer-grained questions than the standard approach.

 

First, for the task of detecting a planted clique in a random graph, we ask
not merely when this can be done in polynomial time O(n^c), but seek the
optimal exponent c as a function of the clique size. To this end, we
consider algorithms that make non-adaptive edge queries and then apply a
low-degree test, and we determine the number of queries required. This is
joint work with Jay Mardia and Kabir Verchand.

Second, in the spiked Wigner model with any iid spike prior, we seek the
precise optimal tradeoff curve between type I and type II error rates.
Conditional on an appropriate strengthening of the "low-degree conjecture,"
we show that tests based on the spectrum achieve the best possible tradeoff
curve among poly-time algorithms, while exponential-time non-spectral tests
can do better. This is joint work with Ankur Moitra.

3:30pm - Pre-talk meet and greet teatime - 219 Prospect Street, 13 floor,
there will be light snacks and beverages in the kitchen area.

For more details and upcoming events visit our website at
<http://statistics.yale.edu/> http://statistics.yale.edu/

 

Department of Statistics and Data Science

Yale University

Kline Tower
219 Prospect Street
New Haven, CT 06511

t 203.432.0666
f 203.432.0633

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.yale.edu/pipermail/sds-seminars/attachments/20240212/f279e1ad/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 2925 bytes
Desc: not available
URL: <http://mailman.yale.edu/pipermail/sds-seminars/attachments/20240212/f279e1ad/attachment.jpg>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image002.jpg
Type: image/jpeg
Size: 47293 bytes
Desc: not available
URL: <http://mailman.yale.edu/pipermail/sds-seminars/attachments/20240212/f279e1ad/attachment-0001.jpg>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image003.jpg
Type: image/jpeg
Size: 6214 bytes
Desc: not available
URL: <http://mailman.yale.edu/pipermail/sds-seminars/attachments/20240212/f279e1ad/attachment-0002.jpg>