116:20 — An Introduction to Circuit Walks

We provide an introduction to the studies of circuit walks and review the past decade of research on circuit diameters and augmentation. We connect the field to classical topics such as conformal sums, combinatorial diameters, and vertex enumeration, discuss the efficient computation of improving circuits, and end with some open questions.

216:50 — A Yannakakis-type theorem for affine semigroups

The seminal result on lifts of polyhedral cones is the theorem of Yannakakis that relates lifts of cones with nonnegative factorizations of their slack matrices. In this talk we generalize the notion of slack matrices to affine semigroups - a discrete analog of polyhedral cones - and present the corresponding result relating lifts of affine semigroups to nonnegative integer factorizations of their slack matrices. We use these generalizations to present new results on nonnegative integer rank of integer matrices.

317:20 — Hypergraph Transversal Pairs Near the Fredman-Khachiyan Bound

The Fredman-Khachiyan algorithm generates the transversal of a hypergraph in incremental quasi-polynomial time. It is a recursive algorithm which focuses on the most frequent vertex in terms of the number of edges in either the hypergraph or its transversal. Hypergraphs where this maximum frequency is low are therefore of interest. This gives a group of related optimization questions for hypergraph-transversal pairs. Here we present some preliminary extremal results.

Besides using classic combinatorial constructions, we adapt Wagner's deep reinforcement learning scheme from graphs to hypergraphs to help find some unexpected examples.

Joint work with Parsa Salimi.