Autumn 2021

Seminar time: Thursdays 10:20-11:15am.

 

September 23: Francisco Martinez Figueroa (Ohio State)

Title: Chromatic number of generalized Borsuk Graphs.

 Abstract: The Borsuk graph is the graph with vertex set the sphere S^d, and edges {x,y} whenever x and y are epsilon-almost antipodal. It is well known that when epsilon is small, its chromatic number is d+2, which follows from the topology of S^2 via Borsuk-Ulam’s Theorem. Given a finite group G acting freely over a compact space X via isometries, we define the G-Borsuk graph to be the graph with vertex set X and edges {x,y} whenever there exists a non-identity g in G such that d(x,gy)<epsilon. The chromatic number of such graph is determined by the topology of X. In this talk we’ll show some upper bounds for this chromatic number depending only on |G| and dim(X). Our bounds are tight when dim(X)=1, and we exhibit some tight results in dimensions 2 and 3 when G=Z_m, for small values of m. We will also discuss random G-Borsuk graphs, which are finite induced subgraphs by choosing n i.i.d. uniform vertices on X. For these, we exhibit a tight threshold for epsilon (up to a constant) such that a.a.s. the chromatic number of the random subgraph coincides with that of the whole G-Borsuk graph. This is joint work in progress with Matthew Kahle.

 

 

September 30: Miklos Racz (Princeton)

Title: Correlated stochastic block models: graph matching and community recovery

Abstract: I will discuss statistical inference problems on edge-correlated stochastic block models. We determine the information-theoretic threshold for exact recovery of the latent vertex correspondence between two correlated block models, a task known as graph matching. As an application, we show how one can exactly recover the latent communities using multiple correlated graphs in parameter regimes where it is information-theoretically impossible to do so using just a single graph. This is based on joint work with Anirudh Sridhar.

 

October 7: Nicholas Cook (Duke)

Title: Large deviations and regularity method for sparse random hypergraphs

Abstract: The “infamous upper tail” problem for subgraph counts in Erdős–Rényi graphs has received considerable attention since it was popularized by Janson and Rucinski, and has connections with questions in graph limit theory and statistical physics. I will survey work in this area and discuss a new approach for the more general setting of hypergraphs, based on an extension of the regularity method to sparse hypergraphs. In particular, we develop a sparse counting lemma and decomposition theorem for tensors under a novel class of norms that generalize the matrix cut norm. Time permitting, I will discuss applications to the analysis of exponential random graph models. Based on joint work with Amir Dembo and Huy Tuan Pham.

 

October 14: Fall Break (No seminar).

 

October 21: Pooya Hatami (CSE, Ohio State University)

Title: Dimension-free bounds in Communication Complexity and Idempotents of Schur Multipliers

Abstract: We discuss whether dimension-free relations exist between various communication and query measures and various norms associated with Boolean matrices and functions. In other words, we ask, whether it is possible to obtain inequalities that bound one parameter solely as a function of another parameter, without any dependence on the dimensions of the matrix.

Dimension-free bounds are also closely related to structural results, where one seeks to find local or global structural properties of Boolean matrices and functions that have low complexity. We discuss such theorems for several communication and query complexity measures as well as various matrix and operator norms. In several other cases, we show that such bounds do not exist.

We propose several open problems that in addition to applications in complexity theory, are central to the characterization of the idempotents of the algebra of Schur multipliers, and could lead to new extensions of Cohen’s celebrated idempotent theorem regarding the Fourier algebra.

Based on joint work with Lianna Hambardzumyan (McGill University) and Hamed Hatami (McGill University)

 

October 28: Boris Hanin (Princeton University)

Title: Random Neural Networks at Finite Width and Large Depth

Abstract: Deep neural networks are often considered to be complicated “black boxes,” for which a full systematic analysis is not only out of reach but also impossible. In this talk, which is based in part on joint work with Sho Yaida and Daniel Adam Roberts, I will make the opposite claim. Namely, that deep neural networks with random weights and biases (i.e. networks at the start of training) are solvable models. Our approach applies to networks at finite width n and large depth L, the regime in which they are used in practice. A key point will be the emergence of a notion of “criticality,” which involves a finetuning of model parameters (weight and bias variances). At criticality, neural networks are particularly well-behaved but still exhibit a tension between large values for n and L, with large values of n tending to make neural networks more like Gaussian processes and large values of L amplifying higher cumulants. Our analysis at initialization has a number of consequences for networks during and after training, which I will discuss if time permits.

 

November 4: Yeor Hafuta (Ohio State)

 

November 11: Veterans day (No seminar)

 

November 18: Yufei Zhao (MIT, in-person talk)

 

December 2: Kristina Wicke (Ohio State)

 

December 9: Chris Janjigian (Purdue)

 

December 16: Kasun Fernando (University of Toronto and Scuola Normale Superiore di Pisa)

Title: The bootstrap for dynamical systems