Sum-of-squares proofs for the trace power method

Speaker: 

Jonathan Shi

Speaker Link: 

https://www.jshi.science/

Institution: 

UCSD

Time: 

Wednesday, May 3, 2023 - 1:00pm to 2:00pm

Host: 

Yizhe Zhu

Location: 

440R Rowland Hall

The sum-of-squares framework converts proofs into algorithms so long as those proofs can be formulated as sum-of-squares proofs—proofs that demonstrate their conclusions via the non-negativity of square polynomials. This is a powerful framework that captures many inequalities known in analysis. We formulate sum-of-squares proofs for the trace power method by giving sum-of-squares proofs for non-commutative (matrix) inequalities including the Araki-Lieb-Thirring inequality and Holder's inequality for Schatten norms, and sketch how one might use these proofs to obtain algorithms to constructively find solutions to random optimization problems whose upper bounds can be proven by techniques in random matrix and spin glass theory. Based on work in progress with Juspreet Singh Sandhu.

Amalgamated finite free convolutions: Towards a unified theory for proving root bounds

Speaker: 

Jorge Garza Vargas

Speaker Link: 

https://jgarzavargas.people.caltech.edu/

Institution: 

Caltech

Time: 

Wednesday, April 19, 2023 - 1:00pm to 2:00pm

Host: 

Yizhe Zhu

Location: 

440R Rowland Hall

Between 2013 and 2015, Marcus, Spielman and Srivastava wrote a sequence of papers where they famously solved the Kadison-Singer problem and proved the existence of Ramanujan graphs of all sizes. For the latter, they used a convolution of polynomials introduced by Walsh, which they showed to have surprising connections to free probability theory. This discovery gave rise to finite free probability, which studies polynomial convolutions from a free probability perspective. With the aim of unifying the results of Marcus, Spielman and Srivastava, and developing general machinery for deducing root bounds, we extend the framework of finite free probability to multivariate polynomials. We show that this extended framework has interesting parallels with the theory of freeness with amalgamation, and can potentially be used to obtain important results in diverse areas, ranging from algebraic combinatorics to operator theory. This is work in progress with Nikhil Srivastava.

The Smith normal form of a polynomial of a random integral matrix

Speaker: 

Gilyoung Cheong

Speaker Link: 

https://sites.google.com/view/gcheong/

Institution: 

UCI

Time: 

Wednesday, April 5, 2023 - 1:00pm to 2:00pm

Host: 

Yizhe Zhu

Location: 

440R Rowland Hall
Given a prime $p$, let $P(t)$ be a non-constant monic polynomial in $t$ over the ring $\mathbb{Z}_{p}$ of $p$-adic integers. Let $X_n$ be the $n \times n$ uniformly random (0,1)-matrix over $\mathbb{Z}_{p}$. We compute the asymptotic distribution of the cokernel of $P(X_n)$ as $n$ goes to infinity. When $P(t)$ is square-free modulo $p$, this lets us compute the asymptotic distribution of the Smith normal form of $P(X_n)$. In fact, we shall consider the same problem with a more general random matrix $X_n$, which also includes the example of a Haar-random matrix. Our work crucially uses a recent work of W. Sawin and M. M. Wood which shows that the moments of finite size modules over any ring determine their distribution. This is joint work with Myungjun Yu. https://arxiv.org/abs/2303.09125

The characteristic polynomial of sums of random permutations

Speaker: 

Yizhe Zhu

Speaker Link: 

https://sites.google.com/uci.edu/yizhezhu

Institution: 

UCI

Time: 

Wednesday, January 18, 2023 - 2:00pm to 3:00pm

Location: 

510R Rowland Hall

Let $A_n$ be the sum of $d$ permutation matrices of size $n\times n$, each drawn uniformly at random and independently. We prove that the normalized characteristic polynomial  $\frac{1}{\sqrt{d}}\det(I_n - z A_n/\sqrt{d})$ converges when $n\to \infty$ towards a random analytic function on the unit disk. As an application, we obtain an elementary proof of the spectral gap of random regular digraphs. Our results are valid both in the regime where $d$ is fixed and for $d$ slowly growing with $n$.

Joint work with Simon Coste and Gaultier Lambert. https://arxiv.org/abs/2204.00524

Robustness of graph theory theorems

Speaker: 

Jie Han

Speaker Link: 

https://jiehan773.github.io/

Institution: 

Beijing Institute of Technology

Time: 

Wednesday, February 1, 2023 - 2:00pm to 3:00pm

Host: 

Asaf Ferber

Location: 

510R Rowland Hall

Dirac's theorem says that any n-vertex graph with minimum degree at least n/2 contains a Hamiltonian cycle. A robust version of Dirac's theorem was obtained by Krivelevich, Lee and Sudakov: for such graphs, if we take a random subgraph where every edge is included with probability Clog(n)/n, for some large fixed constant C, then whp the resulting graph is still Hamiltonian. We will discuss some recent results along this line.

Learning quantum observables of low degrees from a logarithmic number of random queries

Speaker: 

Haonan Zhang

Speaker Link: 

https://sites.google.com/view/haonanzhangmathsearch-console/home

Institution: 

UCI

Time: 

Wednesday, January 11, 2023 - 2:00pm to 3:00pm

Host: 

Yizhe Zhu

Location: 

510R Rowland Hall

A fundamental problem from computational learning theory is to well-reconstruct an unknown function on the discrete hypercubes. One classical result of this problem for the random query model is the low-degree algorithm of Linial, Mansour and Nisan in 1993. This was improved exponentially by Eskenazis and Ivanisvili in 2022 using a family of polynomial inequalities going back to Littlewood in 1930. Recently, quantum analogs of such polynomial inequalities were conjectured by Rouzé, Wirth and Zhang (2022). This conjecture was resolved by Huang, Chen and Preskill (2022) without knowing it when studying learning problems of quantum dynamics. In this talk, I will discuss another proof of this conjecture that is simpler and gives better estimates. As an application, it allows us to recover the low-degree algorithm of Eskenazis and Ivanisvili in the quantum setting. This is based on arXiv:2210.14468, joint work with Alexander Volberg (MSU).

Robustness of graph/hypergraph properties

Speaker: 

Asaf Ferber

Speaker Link: 

https://faculty.sites.uci.edu/asaff/

Institution: 

UCI

Time: 

Wednesday, March 1, 2023 - 2:00pm to 3:00pm

Location: 

510R Rowland Hall

In this talk we will consider some notions of `robustness' of graph/hypergraph properties. We will survey some existing results and will try to emphasize the following new result (joint with Adva Mond and Kaarel Haenni): The binomial random digraph $D_{n,p}$
typically contains the minimum between the minimum out- and in-degrees many edge-disjoint Hamilton cycles, given that $p\geq \log^C n/n$, which is optimal up to log factors.

On higher dimensional point sets in general position

Speaker: 

Andrew Suk

Speaker Link: 

https://mathweb.ucsd.edu/~asuk/

Institution: 

UCSD

Time: 

Wednesday, March 15, 2023 - 2:00pm to 3:00pm

Host: 

Asaf Ferber

Location: 

RH 510

An old question of Erdos asks: Given a set of $N$ points in $R^d$ with no $d+2$ members on a common hyperplane, what is the size of the largest subset of points in general position (i.e., no $d+1$ members on a hyperplane)?  In 2018, Balogh and Solymosi showed that one can use the hypergraph container method to tackle this problem in the plane.  In this talk, I will show how to use the container method to tackle Erdos' question in any dimension.  This is joint work with Ji Zeng.

Nonbacktracking Eigenvector Method for Hypergraph Community Detection

Speaker: 

Jamie Haddock

Speaker Link: 

https://jamiehaddock.com/

Institution: 

Harvey Mudd College

Time: 

Wednesday, February 22, 2023 - 2:00pm to 3:00pm

Host: 

Anna Ma (she/her/hers)

Location: 

510R Rowland Hall

The hypergraph community detection problem asks us to find groups of related or similar entities in hypergraph data. While there are many approaches to this problem, this talk will focus on a spectral method that utilizes information from the eigenvectors of the nonbacktracking or Hashimoto matrix. The Hashimoto operator can be shown to be related to belief-propagation for statistical inference, and using this relationship we obtain a performant hypergraph community detection algorithm with well-understood regions of success and failure for the hypergraph stochastic block model. The talk will additionally pose some conjectures on the fundamental limits of community detection in hypergraphs.

Sharp density bounds on the finite field Kakeya problem

Speaker: 

Boris Bukh

Speaker Link: 

http://www.borisbukh.org/

Institution: 

Carnegie Mellon University

Time: 

Wednesday, March 8, 2023 - 2:00pm to 3:00pm

Host: 

Asaf Ferber

Location: 

RH 510R

 A set is Kakeya if it contains a line in every direction. We prove that every Kakeya set in the $n$-space over $F_q$ has at least
$2^{-n+1}*q^n$ elements. This is sharp up to the lower-order terms. Joint work with Ting-Wei Chao.

Pages

Subscribe to RSS - Combinatorics and Probability