Events

Abstract: Conic geometry encodes combinatorial properties of a convex program. Under a probabilistic model of the data, these combinatorial properties become random events. Their likelihood is the measure of a cone. We illustrate this view with a dual pair of questions. First, how much can a linear program be regularized before its solution changes? With random costs, the answer turns on the Gaussian measure of the solution's normal cone. Second, how many measurements are needed to separate a superposition of structured signals? Here, each signal's complexity is the statistical dimension of its descent cone. A convex program recovers the components once the measurement count exceeds the total complexity.

Abstract: 

A tournament $\T=(V,A)$ on $n$ vertices is an orientation of the complete graph $K_n$. The backedge graph of $T$ with respect to an ordering of $V$ is the undirected graph on vertex set $V$ whose edge set corresponds to the arcs directed from a later vertex to an earlier vertex in the ordering. Backedge graphs provide concise representations of the tournament. The algorithmic problem of determining whether a tournament admits a backedge graph in a given class of undirected graphs varies in complexity, and is often equivalent to computing parameters of tournaments, such as degreewidth when the backedge graph has bounded maximum degree \cite{Davot et al., 2023}. We extend the notion of degreewidth by introducing directional degreewidth, which separately bounds the left-degrees and right-degrees of vertices in addition to bounding the total degrees. We obtain an algorithm for verifying bounds on the directional degreewidth of the tournament, whose runtime is polynomial time when the total degree is unbounded, or fixed-parameter tractable time with respect to the total degree bound otherwise. We also provide a polynomial-time algorithm for computing a $P_3$-free backedge graph of a tournament, if it exists. Together with existing results, the latter result settles the complexity of determining whether a tournament admits an $H$-free backedge graph when $H$ is any graph on three vertices.

Abstract: 

In 2019, Google announced the demonstration of quantum supremacy by performing a computational task known as random circuit sampling on their 53-qubit quantum computer Sycamore. In their paper, they claimed that it would take classical computers 10000 years to perform the same task. Almost seven years has passed, and what happened to this claim since then? In this talk, I will provide a high-level update on the subsequent developments in quantum hardware experiments, classical simulation software, asymptotic classical simulation algorithms, and proving the hardness of classical simulation. This talk is aimed at a non-quantum computing audience, and no prior background in quantum computing is assumed.

Abstract: This term we are running a learning seminar on homology and cohomology, following Chapters 2 and 3 of Hatcher.  In this first meeting, we will briefly talk about our plans for the seminar, and then will jump right into simplicial homology. All are welcome!