Events

Title: Forcing Quasirandomness in Permutations

Abstract:

A striking result in graph theory is that the property of a graph being quasirandom (i.e. resembling a random graph) is characterized by the number of edges and the number of 4-cycles being close to the expected number in a random graph. Král’ and Pikhurko (2013) proved an analogous result for permutations; i.e. that quasirandom permutations are characterized by the densities of all permutations of length 4.

Title: Quantum information science for combinatorial optimization

Abstract:

Due to input-output bottlenecks, quantum computers are expected to be most applicable to problems for which the quantity of data specifying the instance is small but the computational cost of finding a solution is large. Aside from cryptanalysis and quantum simulation, combinatorial optimization provides some of the best candidates for problems of real-world impact fitting these criteria. Many of these problems are NP-hard and thus unlikely to be solvable on quantum computers with polynomial worst-case time complexity.

Title: Four families of polynomials in spectral graph theory

Abstract:

 In this talk we describe four families of polynomials related to the spectrum of a graph. First, some known main results involving such polynomials, such as the spectral excess theorem characterizing distance-regularity, are discussed. Second, some new results giving bounds for the $k$-independence number $\alpha_k$ of a graph are presented. In this context, we comment on some relationships between the inertia (Cvetkovi\`c) and ratio (Hoffman) bounds of $\alpha_k$.

Title: Newell-Littlewood numbers

Abstract:

The Newell-Littlewood numbers are defined in terms of the Littlewood-Richardson coefficients. Both arise as tensor product multiplicities for a classical Lie group. A. Klyachko connected eigenvalues of sums of Hermitian matrices to the saturated LR-cone and established defining linear inequalities.

Title: Induced subgraphs and treewidth

Abstract:

Treewidth, introduced by Robertson and Seymour in the graph minors series, is a fundamental measure of the complexity of a graph. While their results give an answer to the question, “what minors occur in graphs of large treewidth?,” the same question for induced subgraphs is still open. I will talk about some conjectures and recent results in this area.

Joint work with Tara Abrishami, Maria Chudnovsky, Cemil Dibek, Sepehr Hajebi, Pawel Rzazewski, Kristina Vuskovic.

Title: Dyadic Linear Programming

Abstract:

Most linear programming solvers use fixed-precision floating points to approximate the rational numbers. Though successful on most real-world instances, solvers sometimes run into serious issues when carrying out sequential floating-point arithmetic, due to compounded error terms. This practical limitation leads to the following theoretical problem:

Title: State transfer on graphs with twin vertices

Abstract:

In this talk, we discuss algebraic and spectral properties of graphs with twin vertices that are important in quantum state transfer. We give a characterization of strong cospectrality between twin vertices, and characterize some types of state transfer that occur between them.

Title: The results of a search for small association schemes with noncyclotomic eigenvalues

Abstract:

Title: On complete classes of valuated matroids

Abstract:

Valuated matroids were introduced by Dress and Wenzel in 1992. They are a central object in discrete convex analysis, and play important roles in other areas such as mathematical economics and tropical geometry. Finding a constructive characterization, i.e., showing that all valuated matroids can be derived from a simple class by some basic operations has been a natural question proposed in various contexts.

Title: Shorter Zero-Knowledge Proofs from MPC

Abstract:

In this talk I will review the MPC-in-the-head approach to constructing zero-knowledge proofs, then talk about some recent research results to make the proofs shorter.

In a zero-knowledge proof system, a prover wants to convince a verifier that they know a secret value, without revealing it. A common case involves a one-way function, where the prover wants to convince a verifier that they know a secret input corresponding to a public output.