Seminars and Colloquia by Series

Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums

Series
Algebra Seminar
Time
Tuesday, January 11, 2022 - 12:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Yue RenDurham University

We present results on the number of linear regions of the functions that can be represented by artificial feedforward neural networks with maxout units. A rank-k maxout unit is a function computing the maximum of k linear functions. For networks with a single layer of maxout units, the linear regions correspond to the regions of an arrangement of tropical hypersurfaces and to the (upper) vertices of a Minkowski sum of polytopes. This is joint work with Guido Montufar and Leon Zhang.

Thresholds

Series
Job Candidate Talk
Time
Wednesday, December 15, 2021 - 11:00 for 1 hour (actually 50 minutes)
Location
https://bluejeans.com/487699041/8823
Speaker
Jinyoung ParkStanford University

Thresholds for increasing properties of random structures are a central concern in probabilistic combinatorics and related areas. In 2006, Kahn and Kalai conjectured that for any nontrivial increasing property on a finite set, its threshold is never far from its "expectation-threshold," which is a natural (and often easy to calculate) lower bound on the threshold. In this talk, I will first introduce the Kahn-Kalai Conjecture with some motivating examples and then talk about the recent resolution of a fractional version of the Kahn-Kalai Conjecture due to Frankston, Kahn, Narayanan, and myself. Some follow-up work, along with open questions, will also be discussed.

A proof of the Erdős–Faber–Lovász conjecture and related problems

Series
Graph Theory Seminar
Time
Tuesday, December 14, 2021 - 11:00 for 1 hour (actually 50 minutes)
Location
ONLINE
Speaker
Abhishek MethukuUniversity of Birmingham

Please Note: Note the unusual time!

The famous Erdős–Faber–Lovász conjecture (posed in 1972) states that the chromatic index of any linear hypergraph on n vertices is at most n. In this talk, I will briefly sketch a proof of this conjecture for every large n. If time permits, I will also talk about our solution to a problem of Erdős from 1977 about chromatic index of hypergraphs with bounded codegree. Joint work with D. Kang, T. Kelly, D.Kuhn and D. Osthus.

Regularity lemma: discrete and continuous perspectives

Series
Job Candidate Talk
Time
Monday, December 13, 2021 - 11:00 for 1 hour (actually 50 minutes)
Location
https://bluejeans.com/774516207/3993
Speaker
Fan WeiPrinceton University

Szemerédi's regularity lemma is a game-changer in extremal combinatorics and provides a global perspective to study large combinatorial objects. It has connections to number theory, discrete geometry, and theoretical computer science. One of its classical applications, the removal lemma, is the essence for many property testing problems, an active field in theoretical computer science. Unfortunately, the bound on the sample size from the regularity method typically is either not explicit or enormous. For testing natural permutation properties, we show one can avoid the regularity proof and yield a tester with polynomial sample size. For graphs, we prove a stronger, "L_\infty'' version of the graph removal lemma, where we conjecture that the essence of this new removal lemma for cliques is indeed the regularity-type proof. The analytic interpretation of the regularity lemma also plays an important role in graph limits, a recently developed powerful theory in studying graphs from a continuous perspective. Based on graph limits, we developed a method combining with both analytic and spectral methods, to answer and make advances towards some famous conjectures on a common theme in extremal combinatorics: when does randomness give nearly optimal bounds? 

These works are based on joint works with Jacob Fox, Dan Kral',  Jonathan Noel, Sergey Norin, and Jan Volec.

 

Open sets of partially hyperbolic systems having a unique SRB measure

Series
CDSNS Colloquium
Time
Friday, December 10, 2021 - 13:00 for 1 hour (actually 50 minutes)
Location
Zoom (see additional notes for link)
Speaker
Davi ObataU Chicago

Please Note: https://us06web.zoom.us/j/83392531099?pwd=UHh2MDFMcGErbzFtMHBZTmNZQXM0dz09

For a dynamical system, a physical measure is an ergodic invariant measure that captures the asymptotic statistical behavior of the orbits of a set with positive Lebesgue measure. A natural question in the theory is to know when such measures exist.

It is expected that a "typical" system with enough hyperbolicity (such as partial hyperbolicity) should have such measures. A special type of physical measure is the so-called hyperbolic SRB (Sinai-Ruelle-Bowen) measure. Since the 70`s the study of SRB measures has been a very active topic of research. 

In this talk, we will see a new example of open sets of partially hyperbolic systems with two dimensional center having a unique SRB measure.  One of the key features for these examples is a rigidity result for a special type of measure (the so-called u-Gibbs measure) which allows us to conclude the existence of the SRB measures.

Statistical and computational limits for sparse graph alignment

Series
Stochastics Seminar
Time
Thursday, December 9, 2021 - 15:30 for 1 hour (actually 50 minutes)
Location
Online
Speaker
Luca GanassaliINRIA

Graph alignment refers to recovering the underlying vertex correspondence between two random graphs with correlated edges. This problem can be viewed as an average-case and noisy version of the well-known graph isomorphism problem. For correlated Erdős-Rényi random graphs, we will give insights on the fundamental limits for the planted formulation of this problem, establishing statistical thresholds for partial recovery. From the computational point of view, we are interested in designing and analyzing efficient (polynomial-time) algorithms to recover efficiently the underlying alignment: in a sparse regime, we exhibit an local rephrasing of the planted alignment problem as the correlation detection problem in trees. Analyzing this related problem enables to derive a message-passing algorithm for our initial task and gives insights on the existence of a hard phase.

Based on joint works with Laurent Massoulié and Marc Lelarge: 

https://arxiv.org/abs/2002.01258

https://arxiv.org/abs/2102.02685

https://arxiv.org/abs/2107.07623

Canonical measures and equidistribution in the arithmetic of forward orbits

Series
Job Candidate Talk
Time
Thursday, December 9, 2021 - 11:00 for 1 hour (actually 50 minutes)
Location
online
Speaker
Nicole LooperBrown University

This talk is about the arithmetic of points of small canonical height relative to dynamical systems over number fields, particularly those aspects amenable to the use of equidistribution techniques. Past milestones in the subject include the proof of the Bogomolov Conjecture given by Ullmo and Zhang, and Baker-DeMarco's work on the finiteness of common preperiodic points of unicritical maps. Recently, quantitative equidistribution techniques have emerged both as a way of improving upon some of these old results, and as an avenue to studying previously inaccessible problems, such as the Uniform Boundedness Conjecture of Morton and Silverman. I will describe the key ideas behind these developments, and raise related questions for future research. 

https://bluejeans.com/788895268/8348

Density and graph edge coloring

Series
Graph Theory Seminar
Time
Tuesday, December 7, 2021 - 15:45 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Guangming JingAugusta University

Given a multigraph $G=(V,E)$, the chromatic index $\chi'(G)$ is the minimum number of colors needed to color the edges of $G$ such that no two incident edges receive the same color. Let $\Delta(G)$ be the maximum degree of $G$ and let  $\Gamma(G):=\max \big\{\frac{2|E(U)|}{|U|-1}:\,\, U \subseteq V, \,\, |U|\ge 3 \hskip 2mm
{\rm and \hskip 2mm odd} \big\}$. $\Gamma(G)$ is called the density of $G$. Clearly, the density is a lower bound for the chromatic index $\chi'(G)$. Moreover, this value can be computed in polynomial time. Goldberg and Seymour in the 1970s conjectured that $\chi'(G)=\lceil\Gamma(G)\rceil$ for any multigraph $G$ with $\chi'(G)\geq\Delta(G)+2$, known as the Goldberg-Seymour conjecture. In this talk we will discuss this conjecture and some related open problems. This is joint work with Guantao Chen and Wenan Zang.

A Taste of Extremal Combinatorics in AG

Series
Algebra Seminar
Time
Tuesday, December 7, 2021 - 10:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Robert WalkerUniversity of Wisconsin, Madison

In this talk, we survey known results and open problems tied to the dual graph of a projective algebraic F-scheme over a field F, a construction that apparently Janos Kollar is familiar with. In particular one can use this construction to answer the following question: if you consider the 27 lines on a cubic surface in P^3, how many lines meet a given line? The dual graph can answer this and more questions in enumerative geometry and intersection theory easily, based on work of Benedetti -- Varbaro and others.

Non-Parametric Estimation of Manifolds from Noisy Data

Series
Applied and Computational Mathematics Seminar
Time
Monday, December 6, 2021 - 14:00 for 1 hour (actually 50 minutes)
Location
https://bluejeans.com/457724603/4379
Speaker
Yariv AizenbudYale University
A common task in many data-driven applications is to find a low dimensional manifold that describes the data accurately. Estimating a manifold from noisy samples has proven to be a challenging task. Indeed, even after decades of research, there is no (computationally tractable) algorithm that accurately estimates a manifold from noisy samples with a constant level of noise.
 
In this talk, we will present a method that estimates a manifold and its tangent in the ambient space. Moreover, we establish rigorous convergence rates, which are essentially as good as existing convergence rates for function estimation.

Pages