Events

Title: Log-concavity of random Radon partitions

 Abstract: Over one hundred years ago, Radon proved that any set of d+2 points in R^d can be partitioned into two sets whose convex hulls intersect. I will talk about Radon partitions when the points are selected randomly. In particular, if the points are independent normal random vectors, let p_k be the probability that the Radon partition has size (k, d+2-k). Answering a conjecture of Kalai and White, we show that the sequence (p_k) is ultra log-concave and that, in fact, a balanced partition is the most likely. Joint work with Swee Hong Chan, Gil Kalai, Bhargav Narayanan, and Moshe White.

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

Title: Exact algorithms for combinatorial interdiction problems

Abstract: Typical optimization paradigms involve a single decision maker that can control all variables involved. However, several practical situations involve multiple (potentially adversarial) decision makers. Bilevel optimization is a field that involves two decision makers. The key paradigm is that an upper-level decision maker acts first and after observing the upper-level decisions, a lower level decision maker optimizes their own objective. One particular important instance of such problems are so-called interdiction problems, where the upper-level decision is to try and forbid access to some decisions by the lower level and the goal of the upper level is to make the most impact into the lower-level decisions. These problems are, in general $\Sigma^P_2$-hard (likely harder than NP-hard). 

In this talk I will present recent work on improving significantly on state-of-the-art exact algorithms to obtain optimal solutions to some combinatorial interdiction problems. Despite the hardness results, our algorithm can solve instances consistently in a short amount of time. We also generalize our algorithms to propose a framework that could be applied to other similar problems, by deriving relaxations based on looking at these problems as games and performing operations on such games. 

This is joint work with Noah Weninger.

Title: Quantum Search with the Signless Laplacian

Abstract: Continuous-time quantum walks are typically effected by either the discrete Laplacian or the adjacency matrix. In this paper, we explore a third option: the signless Laplacian, which has applications in algebraic graph theory and may arise in layered antiferromagnetic materials. We explore spatial search on the complete bipartite graph, which is generally irregular and breaks the equivalence of the three quantum walks for regular graphs, and where the search oracle breaks the equivalence of the Laplacian and signless Laplacian quantum walks on bipartite graphs without the oracle. We prove that a uniform superposition over all the vertices of the graph partially evolves to the marked vertices in one partite set, with the choice of set depending on the jumping rate of the quantum walk. We boost this success probability to 1 by proving that a particular non-uniform initial state completely evolves to the marked vertices in one partite set, again depending on the jumping rate. For some parameter regimes, the signless Laplacian yields the fastest search algorithm of the three, suggesting that it could be a new tool for developing faster quantum algorithms.

This is joint work with Molly McLaughlin.