[Theory] [TTIC Talks] 3/24 Research at TTIC: Aaron Potechin, University of Chicago

[Brandie Jones]

*When:*         Friday, March 24th* at 12:30pm CT  *


*Where:*        Talk will be given *live, in-person* at

                       TTIC, 6045 S. Kenwood Avenue

                        5th Floor, Room 530


*Virtually:*     via Panopto (Livestream
<https://uchicago.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=40cc785c-ef33-484a-a4ad-af3f01413b95>
)



*Who:*           Aaron Potechin, University of Chicago



*Title:*           Graph Matrices and the Ellipsoid Fitting Conjecture


*Abstract:   *Graph matrices are a type of matrix whose entries are
functions of a random input such as a G(n, 1/2) graph or a random m × n
matrix. Graph matrices have entries which are random but are generally not
independent, which makes their behavior different than the behavior of
random matrices with independent random entries. Graph matrices are crucial
for analyzing the sum of squares hierarchy on average case problems and are
also useful for analyzing other methods which use higher moments of the
input.

The ellipsoid fitting problem is as follows. Given n random vectors v1, . .
. , vn ∈ Rd, is there a matrix X such that X ⪰ 0 and viTMvi = 1 for all i ∈
[n]? Saunderson, Parrilo, and Willsky conjectured that for all ϵ > 0, for
all sufficiently large d, the answer to the ellipsoid fitting conjecture is
yes with high probability when n ≤ (1−ϵ)d24and no with high probability
when n ≥ (1 + ϵ)d24.

In this talk, I will describe graph matrices and describe how they can be
used to resolve the ellipsoid fitting conjecture up to a polylogarithmic
factor.




***********************************************************************************************

*Masks are optional in all common areas. **Full visitor guidance is
available at ttic.edu/visitors <http://ttic.edu/visitors>.*

***********************************************************************************************

*Research at TTIC Seminar Series*



TTIC is hosting a weekly seminar series presenting the research currently
underway at the Institute. Every week a different TTIC faculty member will
present their research.  The lectures are intended for students seeking
research topics and advisors and for the general TTIC and University of
Chicago communities interested in hearing what their colleagues are up to.



-- 
*Brandie Jones *
*Executive **Administrative Assistant*
Toyota Technological Institute
6045 S. Kenwood Avenue
Chicago, IL  60637
www.ttic.edu
Working Remotely on Tuesdays
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20230317/8f2fc95b/attachment.html>