À¶Ý®ÊÓƵ

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

ÌýAbstract:Ìý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.

Title:ÌýAsymptotic count of edge-bicolored graphs

ÌýAbstract: I will talk about recent joint work with Chiara Meroni and Max Wiesmann, where we showed that specific exponential bivariate integrals serve as generating functions of labeled edge-bicolored graphs. Based on this, we prove an asymptotic formula for the number of regular edge-bicolored graphs with arbitrary weights assigned to different vertex structures.

The asymptotic behavior is governed by the critical points of a polynomial. An interesting application of this purely combinatorial work to mathematical physics is the Ising model on a random graph. I will explain how its phase transitions arise from our formula.

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

Title:The Inexact Augmented Lagrangian Method: Optimal Complexity Bounds and Applications to Solving Huge SDPs

Abstract:In the first part of this talk, we present optimal and nearly-optimal parameter-free augmented Lagrangian (AL) methods for convex and strongly optimization with linear constraints. Our AL methods employ tractable inexact criteria for solving their inner subproblems, which accelerated methods can be shown to achieve in a finite number of iterations that depends on the target accuracy.

In the second part of this talk, we present a new inexact augmented Lagrangian method, namely, HALLaR, that employs a Burer-Monteiro style low-rank factorization for solving large-scale semidefinite programs (SDPs). The AL subproblems are solved by a hybrid low-rank method, which is based on a combination of a low-rank Frank-Wolfe method and a nonconvex accelerated inexact proximal point method. In contrast to the classical low-rank method by Burer and Monteiro, HALLaR finds a near-optimal solution (with provable complexity bounds) of SDP instances satisfying strong duality. Computational results comparing HALLaR to state-of-the-art solvers on several large SDP instances show that the former finds higher accurate solutions in substantially less CPU time than the latter ones. For example, in less than 20 minutes, HALLaR can solve (on a personal laptop) a maximum stable set SDP with 1 million vertices and 10 million edges within 1e-5 relative accuracy.

This talk is based on joint work with Saeed Ghadimi and Henry Wolkowicz from University of À¶Ý®ÊÓƵ and Diego Cifuentes and Renato Monteiro from Georgia Tech.

Ìý

Ìý

Title:ÌýFinite bivariate Tratnik functions

Abstract: In the context of algebraic combinatorics, P- and Q-polynomial association schemes are important objects and are closely related to distance-regular graphs. The polynomials appearing in these structures are classified by Leonard's theorem, and they belong to the discrete part of the (q-)Askey scheme. Relatively recently, the notions of P- and Q-polynomial association schemes as well as of distance-regular graphs have been generalized to the multivariate case. There is however no multivariate analog of Leonard's theorem. With the purpose of progressing in that direction, I will discuss ongoing work concerning certain finite families of bivariate functions, said of Tratnik type, which are expressed as an intricate product of univariate polynomials of the (q-)Askey scheme. The goal is to classify such functions which satisfy some generalized bispectral properties, that is, two recurrence relations and two (q-)difference equations of certain types.

Title: The quasisymmetric Macdonald polynomials are quasi-Schur positive at t = 0

ÌýAbstract: The quasisymmetric Macdonald polynomials G_\gamma (X; q, t) are a quasisymmetric refinement of the symmetric Macdonald polynomials that specialize to the quasisymmetric Schur functions QS_\alpha (X). We study the t = 0 specialization G_\gamma (X; q,0), which can be described as a sum over weighted multiline queues. We show that G_\gamma (X; q, 0) expands positively in the quasisymmetric Schur basis and give a charge formula for the quasisymmetric Kostka-Foulkes polynomials K_{\gamma,\alpha}(q) in the expansion G_\gamma (X; q, 0) = \sum K_{\gamma,\alpha}(q) QS_\alpha(X). The proof relies heavily on crystal operators, and if you do not know what that means, come find out! This is joint work with Olya Mandelshtam.

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