��ݮ��Ƶ

Title:Benign Optimization Landscape of Formulations for Time-of-Arrival-Based Source Localization Problem

�������ٰ�������:��: In this talk, we will address the maximum-likelihood (ML) formulation and a least-squares (LS) formulation of the time-of-arrival (TOA)-based source localization problem. Although both formulations are generally non-convex, we will show that they both possess benign optimization landscape. First, we consider the ML formulation of the TOA-based source localization problem. Under standard assumptions on the TOA measurement model, we will show a bound on the distance between an optimal solution and the true target position and establish the local strong convexity of the ML function at its global minima. Second, we consider the LS formulation of the TOA-based source localization problem. We will show that the LS formulation is globally strongly convex under certain condition on the geometric configuration of the anchors and the source and on the measurement noise. We will then derive a characterization of the critical points of the LS formulation, which leads to a bound on the maximum number of critical points under a very mild assumption on the measurement noise and a sufficient condition for the critical points of the LS formulation to be isolated. The said characterization also leads to an algorithm that can find a global optimum of the LS formulation by searching through all critical points. Lastly, we will discuss some possible future directions.

��

��

Title:��Covers of the complete graph, equiangular lines, and the absolute bound

Abstract: We discuss equiangular lines and covers of the complete graph. The relationship between these objects dates to at least 1992, when Godsil and Hensel showed that any distance-regular antipodal cover of the complete graph (DRACKN) produces an ensemble of equi-isoclinic subspaces. In the case of a regular abelian DRACKN, this produces equiangular lines.
In the first part of the talk, we combine Godsil and Hensel's theorem with a 2017 observation of Waldron to explain why (with a single exception) there DO NOT exist regular abelian DRACKNs that would create d^2 equiangular lines in d-dimensional complex space, to achieve Gerzon's "absolute bound". This rules out a family of otherwise feasible DRACKN parameters that were enunciated in a 2016 paper of Coutinho, Godsil, Shirazi, and Zhan.
In the second part of the talk, we introduce "roux", a slight generalization of regular abelian DRACKNs. Roux are covers of the complete graph that produce equiangular lines. They come up naturally in the classification of doubly transitive lines, all of which arise from roux. Keeping hope alive for the present, we enunciate an infinite family of feasible roux parameters that would produce equiangular lines achieving Gerzon's absolute bound.
Based on joint work with Dustin Mixon.

Title:��Sequential Contracts on Matroids

Abstract: First, I will talk about the well-known pandora’s box problem, and then I will introduce the generalization of pandora’s box to matroids. We call this problem “sequential contracts on matroids” and we will discuss some recent results about this problem. In particular, we will look at complexity results of the problem. This is joint work with Kanstantsin Pashkovich and Jacob Skitsko for my URA project in Spring 2024.

Title: Positivity of P-Recursive Sequences Satisfying Linear Recurrences

���������ٰ�������:��Whether it is decidable to determine when sequences satisfying linear recurrences with constant coefficients have all positive terms is a notorious problem in enumerative combinatorics that has essentially been open for around 90 years. Nevertheless, a "meta-principle" states that all such sequences arising from combinatorial counting problems belong to a special class where positivity (and more general asymptotic

behaviour) is decidable. Here we discuss new software for determining positivity for sequences satisfying linear recurrences with *polynomial* coefficients. Originally motivated by a novel approach to proving genus one solution uniqueness for the Canham model for biomembrane shapes, our algorithm combines rigorous numeric analytic continuation of functions satisfying linear ODEs with singularity analysis techniques from analytic combinatorics. The main talk will be presented using a live Sage Jupyter notebook, and audience members who have access to Sage with a recent version of the ore_algebra package installed (available at

) will be able to follow along and play with the package during the talk.

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1pm,

Title:A bound on the quantum value of all compiled nonlocal games

Abstract: Nonlocal games provide valuable insights into quantum entanglement and even enable a classical verifier to confirm and control the behavior of entangled quantum provers. However, an issue with this approach has always been the necessity of two non-communicating quantum provers. To address this issue, a group of researchers recently introduced a "compilation procedure" that reduces the need for multiple provers and enforces non-communication through cryptographic methods. In this talk, we will show that even in this single prover "compiled setting," the prover remains fundamentally constrained. Specifically, we show that any polynomial-time quantum prover cannot win the "compiled game" with a higher probability than any quantum commuting provers could win the original nonlocal game. Our result is derived through a novel combination of techniques from cryptography and operator algebras and allows us to recover several important self-testing results in the "compiled setting".

��

��

Title:��Symmetric and Skew-Symmetric Signing for Graphs

Abstract:

We consider symmetric and skew-symmetric signings for graphs. A signing for a graph G = (V, E) is a mapping σ : (x, y) | x, y in V \} to {0, ± 1} with the following properties:

• σ(x, y) ≠ 0 if and only if {x, y} in E,
• σ(x, y) = σ(y, x) for any distinct x, y in V with {x, y} in E.

For a signing σ of a graph, we define the signed adjacency matrix A_σ of the graph, where the (x, y)-entry of A_σ is equal to σ(x, y). We study the problem of finding lower bounds for the spectral radius of A_σ and aim to determine a signing for a given graph such that its spectral radius is the smallest among all possible signings of that graph. A signing of a small spectral radius plays an important role in constructing Ramanujan graphs.�� Additionally, we consider a variation of signing, which we call skew-symmetric signing for graphs.

This talk is based on joint work with Jack Koolen and Hadi Kharaghani.

Title:New results on the complexity of edge-modification problems

Abstract:

For a k-uniform hypergraph H, the H-freeness edge modification problem is the algorithmic problem of finding, for a given k-uniform input G, the distance of G from H-freeness, i.e., the minimum number of edges that need to be deleted from G in order to obtain an H-free hypergraph. I will present new results on the computational complexity of this general problem. In particular, I will show that if H is not k-partite, then it is NP-hard to compute the distance to H-freeness,��and��even to approximate this distance up to an additive error of n^{k-delta} for any fixed delta > 0. This resolves a special case of a problem raised by Ailon��and��Alon.

This is a joint work with Yevgeny Levanzov��and��Asaf Shapira.

Title:��Schubert calculus by counting puzzles

���������ٰ�������:��There are three rings-with-bases whose multiplicative structure constants are computed by the same rule: the cohomology ring of the Grassmannian Gr(k,n), the representation ring of GL_k (made by stabilizing the previous in n), and one made by summing all representation rings of the symmetric groups (made by stabiliizing the previous in k). The most famous rules, typically involving counting Young tableaux, are for the most stable version, but the unstable version admits the most generalizations, to K-theory, equivariant cohomology, quantum cohomology, and to other homogeneous varieties. I'll explain how to compute the multiplication in many of these cases by counting "puzzles".

This work is joint with Terry Tao and Paul Zinn-Justin.

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1pm,

Title:The mathematics of juggling

Abstract: I'll explain how to associate to any matrix a juggling pattern, with many examples demonstrated. This will give a decomposition of the Grassmannian Gr(k,n), of k-planes in n-space, into pieces indexed by juggling patterns. I'll explain how this "positroid decomposition" arises in (1) the very classical theory of "totally positive (real) matrices" (2) the characteristic p theory of "Frobenius splitting" and (3) Poisson geometry.

��

��

Title:��Euclidean and projective rigidity of hypergraphs

Abstract: The mathematical theory of structural rigidity has a long history. In the nineteenth century, Cauchy studied rigidity of polyhedra, and Maxwell studied graph frameworks. The rigidity theory of graph frameworks has since been studied extensively. Pollaczek-Geiringer, and later Laman, proved a combinatorial characterization of the minimally rigid graphs in the plane.

Combinatorial rigidity theory is also concerned with geometric realizations of other combinatorial structures. In this talk, we will focus on rigidity of realizations of hypergraphs as points and straight lines. We will discuss how to determine whether a realization of a hypergraph is rigid, in the sense that there are no motions of the realization that preserve the incidences of points and lines, and the distance between any pair of points that lie on a line.

We will also discuss motions of realizations of hypergraphs that preserve only the incidences between points and lines. We will see that classical theorems in incidence geometry, such as Pascal's theorem, make determining rigidity with respect to such motions a difficult problem.

The talk will be based on joint work with K.Stokes and L-D. Öhman, as well as work in progress, joint with L.Berman, B.Schulze, B.Servatius, H.Servatius, K.Stokes and W.Whiteley.