Events

Title: Positivity and sums of squares in products of free algebras

Abstract: A noncommutative polynomial is said to be positive relative to some constraints if plugging matrices (or more generally, operators on a Hilbert space) satisfying the constraints into the polynomial always yields a positive operator. It is a natural problem to determine whether or not a given polynomial is positive, and if it is, to find some certificate of positivity. This problem is closely connected with noncommutative polynomial optimization, where we want to find matrices or operators that maximize the operator norm of some polynomial, subject to the constraint that some other polynomials in the operators are positive or vanish. When the algebra cut out by the constraints is a free algebra, free group algebra, or similar algebra, it's well-known that a polynomial is positive on operators satisfying the constraints if and only if it's a sum of Hermitian squares in the algebra.

Title: New Characterizations of Distance-Biregular Graphs

Abstract: Fiol, Garriga, and Yebra introduced the notion of pseudo-distance-regular vertices, and were able to use this notion to come up with a characterization of when a graph is distance-regular. Subsequently, Fiol and Garriga were able to use pseudo-distance-regular vertices and a bound on the excess of a vertex to come up with another characterization of distance-regular graphs. We will present an overview of their results, as well as recent extensions to distance-biregular graphs.

Title: High-Rank Matroids and Unavoidable Flats

Abstract: We discuss a variety of questions and results pertaining to conjectures of Geelen from 2021 on the unavoidable flats in matroids of sufficiently high rank. We will also explore the differences in how such questions are posed for various classes of matroids, why such differences are necessary, and how they could potentially be reconciled. A result for the class of binary matroids and an outline of its proof will be discussed in detail. Joint work with Jim Geelen.

Title: Strongly regular graphs with a regular point 

Abstract:  Arising from Hoffman and Singleton's study of Moore graphs, strongly regular graphs play an important role in algebraic graph theory. Strongly regular graphs can be construct from geometric objects, such as generalized quadrangles and certain geometric properties, such as having a regular point, can be studied in the context of graphs.

Title: Thresholds

Abstract: 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 present recent progress on this topic. Based on joint work with Huy Tuan Pham.

Title: Non-realizability of polytopes via linear programming

Abstract: A classical question in polytope theory is whether an abstract polytope can be realized as a concrete convex object. Beyond dimension 3, there seems to be no concise answer to this question in general. In specific instances, answering the question in the negative is often done via “final polynomials” introduced by Bokowski and Sturmfels. This method involves finding a polynomial which, based on the structure of a polytope if realizable, must be simultaneously zero and positive, a clear contradiction.

Title: Bipartite Matching in Almost-Linear Time and More

Abstract:  This talk will present an algorithm that computes maximum bipartite matchings in m^{1 + o(1)} time, and discuss its connections with optimization, graph algorithms, and data structures.

Title: Integer programs with bounded subdeterminants and two nonzeros per row

Abstract: Determining the complexity of integer linear programs with integer coefficient matrices whose subdeterminants are bounded by a constant is currently a very actively discussed question in the field. In this talk, I will present a strongly polynomial-time algorithm for such integer programs with the further requirement that every constraint contains at most two variables. The core of our approach is the first polynomial-time algorithm for the weighted stable set problem on graphs that do not contain more than k vertex-disjoint odd cycles, where k is any constant. Previously, polynomial-time algorithms were only known for k = 0 (bipartite graphs) and for k = 1.

This is joint work with Samuel Fiorini, Gwenaël Joret, and Yelena Yuditsky, which recently appeared at FOCS this year.

Titile: Global geometric reductions for some bottleneck questions in hardness of approximation

Abstract: I will describe the classical "local gadget reduction" paradigm for proving hardness of approximation results and then list some important optimization problems that resist all such attacks. With a focus on problems that can be cast as quadratic maximization over convex sets, I will describe some successes in bypassing the aforementioned bottleneck using ideas from geometry. Time permitting I will also describe some compelling new frontiers where answering some questions in convex geometry could be the path forward.

Title: Probabilistic root finding in code-based cryptography

Abstract: Factorization of polynomials over finite fields, and the particular subproblem of finding roots of polynomials, have many applications in diverse areas such as computer algebra, cryptography and coding theory, among many others. In practice, fast factorization algorithms are probabilistic.