Events

Title: On the complexity of quantum partition functions

Abstract: Quantum complexity theory has been intertwined with the study of quantum many-body systems ever since Kitaev's insight that computing their ground energies is an intractable quantum constraint satisfaction problem that is complete for a quantum generalization of NP.

Title: Quantum walk state transfer on a hypercube

Abstract: We investigate state transfer on a hypercube by means of a quantum walk where the sender and the receiver vertices are marked by weighted loops.

Title: Extended Formulations for the Colonel Blotto Game

Abstract: Suppose you want to replace Doug Ford as premier. To beat him, you need to win as many seats as possible. You have some finite amount of resources to allocate across all seats - if you spend more on a seat than Ford does, you will win that seat. How should you allocate your resources to maximize your expected number of seats?

Title: Online Unrelated-Machine Load Balancing and Generalized Flow with Recourse

Abstract: I will present the online algorithms for unrelated-machine load balancing problem with recourse.  First, we shall present a (2+\epsilon)-competitive algorithm for the problem with O_\epsilon(\log n) amortized recourse per job.

Title: L-systems and the Lovasz number

Abstract: For positive integers n and k, an L-system is a collection of k-uniform subsets of a set of size n whose pairwise intersection sizes all lie in in the set L. The maximum size of an L-system is equal to the independence number of a certain union of graphs in the Johnson scheme. The Lovasz number is a semidefinite programming approximation of the independence number of a graph. In this talk, we survey the relationship between the maximum size of an L-system and the Lovasz number, illustrating examples both where the Lovasz number is a good approximation and where it is a bad approximation.

Title: Monomial ideals, Galois closures, and Hilbert schemes of points

Abstract: Manjul Bhargava and the speaker introduced a functorial Galois closure operation for finite-rank ring extensions, generalizing constructions of Grothendieck and Katz-Mazur. In this talk, we use Galois closures to construct new components of Hilbert schemes of points, which are fundamental objects in algebraic geometry whose component structure is largely mysterious. We answer a 35 year old open problem posed by Iarrobino by constructing an infinite family of low dimensional components. This talk is based on joint work with Andrew Staal. No prior knowledge of Hilbert schemes will be assumed.

Title: To be announced

Title: Error bounds for conic feasibility problems: case studies on the exponential cone

Abstract: Conic feasibility problems naturally arise from linear conic programming problems. An understanding of error bounds for these problems is instrumental in the design of termination criteria for conic solvers and the study of convergence rate of algorithms.

Title: Partial geometric designs, directed strongly regular graphs, and association scheme

Abstract: A partial geometric design with parameters $(v, b, k, r; \alpha, \beta)$ is a tactical configuration $(P, \mathcal{B})$ (with $|P|=v$, $|\mathcal{B}|=b$, every point $p\in P$ belonging to $r$ blocks, and every block $B\in\mathcal{B}$ consisting of $k$ points) satisfying the property:

{for any pair $(p, B)\in P\times \mathcal{B}$, the number of flags $(q, C)$ with $q\in B$ and $C\ni p$ equals to $\alpha  \mbox{ if } p\notin B$ and to $\beta  \mbox{ if } p\in B$.}

Neumaier studied partial geometric designs in detail in his article, ``$t\frac12$-designs," [JCT A {\bf 28}, 226-248 (1980)]. He investigated their connection with strongly-regular graphs and gave various characterizations of partial geometries, bipartite graphs, symmetric 2-designs, and transversal designs in terms of partial geometric designs.

Title: A Primal-Dual Extension of the Goemans--Williamson Algorithm for the Weighted Fractional Cut Covering Problem

Abstract:

A cut in a graph \(G = (V, E)\) is a set of edges which has precisely one endpoint in \(S\), for a given subset \(S\) of \(V\). The fractional cut-covering number is the optimal value of a linear programming relaxation for the problem of covering each edge by a set of cuts. We define a semidefinite programming relaxation of fractional cut covering whose approximate optimal solutions may be rounded into a fractional cut cover via a randomized algorithm.