Events

Filter by:

Limit to events where the title matches:
Limit to events where the first date of the event:
Date range
Limit to events where the type is one or more of:
Limit to events tagged with one or more of:
Limit to events where the audience is one or more of:
Monday, November 23, 2026 11:00 am - 12:00 pm EST (GMT -05:00)

CombOpt Reading Group | Mahtab Alghasi, Dyadic Fractional Packings of T-Joins

Speaker:

Mahtab Alghasi

Affiliation: University of Waterloo
Room: MC 6029

Abstract: Let G be a graph and let T be a nonempty set of vertices of even cardinality. A T-join is an edge set whose odd-degree vertices are precisely T, and a T-cut is a cut with an odd number of terminals on each side. A classical consequence of the Edmonds–Johnson theorem is that the minimum cardinality of a T-cut equals the maximum value of a fractional packing of T-joins. An optimal packing need not be integral or even half-integral, but can its coefficients always be chosen with denominators that are powers of two?

I’ll present the affirmative answer of Ahmad Abdi, Gérard Cornuéjols, and Zuzanna Palion, which establishes Seymour’s Dyadic Conjecture for clutters of T-joins. I’ll outline how the proof combines Lovász’s matching-lattice theorem with dyadic feasibility and combinatorial contraction and gluing arguments.

*We switched to a closely related topic after learning that the author will present the work the following day, Tuesday, November 24, at 6:30 p.m. Eastern. For those interested you can also join the talk online. Sorry for any inconvenience caused by the change. https://researchseminars.org/seminar/SFUOR

Speaker: Hadas Barabash
Affiliation: Georgia Tech
Room: MC 6029

Abstract: We give an $O_{\mathcal{H}}(n^5)$-time algorithm to test whether an $n$-vertex labeled tour graph has a full immersion isomorphic to a labeled tour graph $\mathcal{H}$. A \emph{labeled tour graph} is a connected $4$-regular graph whose edges are labeled by binary vectors of fixed length. To obtain a \emph{full immersion}, a vertex may be removed only by pairing up its four incident edges and ``splitting off'' both pairs, summing the labels within each pair. Even for one-bit labels, no polynomial-time algorithm was previously known for arbitrary fixed $\mathcal{H}$. Our results have implications for \emph{vertex-minors}, whose study is motivated by applications in quantum networking.

Speaker: Rolfe Schmidt
Affiliation: Signal
Location: United College, Room 105

Abstract: In 2023 Signal deployed PQXDH, a small change to the handshake that protects new conversations against adversaries who record traffic today and decrypt it with a future quantum computer. Two gaps remain: post-compromise security in the ratchet and authentication in the handshake both still rely on elliptic curves. This talk describes how we closed the first and how we plan to close the second.

In the first part, we look at the challenge of building a post-quantum ratcheted messaging protocol in a bandwidth-constrained setting, and build up Signal’s Sparse Post-Quantum Ratchet, deployed in 2025, step by step through a series of simpler protocols.

In the second part, we look ahead to a new handshake that completes the transition of Signal’s 1:1 messaging with hybrid, deniable authentication. While the post-quantum ratchet feels like an engineering variation on the classical one, the post-quantum key agreement takes a very different shape. Our need to save bandwidth still drives plenty of engineering, including Merkle trees, Falcon signature recovery modes, and context-specific optimizations.

I’ll close with open questions and a brief look at what it will take to make the rest of the Signal app quantum safe.

Speaker: Houcine Ben Dali
Affiliation: Harvard & Center of Mathematical Sciences and Applications
Location: MC 5417

Abstract: Symmetric Koornwinder polynomials are a six-parameter family of multivariate orthogonal polynomials, which generalize the Askey–Wilson polynomials and specialize to Macdonald polynomials of types B, C, D and BC. Koornwinder ASEP polynomials form a nonsymmetric refinement of the symmetric Koornwinder polynomials, and under a specific specialization they give the stationary distribution of the multispecies asymmetric simple exclusion process with open boundaries.

There will be a pre-seminar presenting relevant background at beginning graduate level starting at 1:30pm in MC 5417.