Events

Title: Approximation algorithms for dense quantum Hamiltonians using convex relaxations

Abstract: Computing ground-state energy and partition functions for quantum Hamiltonian systems are problems of broad applicability in physics. These are also natural generalizations of well-studied classical computational tasks such as maximum constraint satisfaction and computing partition functions of Ising models. In this talk, I will present new classical approximation algorithms for these problems in the case of dense quantum Hamiltonians.

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: Research in Applications

Abstract: In this talk I will present my personal experiences in doing research involving applications. I will go over some of my work, presenting some of the key aspects that are involved, and trying to take stock of a few lessons learned.

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.