Events

Filters
Export this event to calendar
iCal
RSS
RSS
Close X

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:
Thursday, July 30, 2026 2:30 pm - 3:30 pm EDT (GMT -04:00)

Algebraic and Enumerative combinatorics seminar -Maryam Yekta-New bounds for integer flows and Verma modules via denormalized Lorentzian Laurent series

Speaker: Maryam Yekta
Affiliation: University of Waterloo
Location: MC 5479

Abstract: The theory of log concave polynomials has recently been developed to study objects and problems in combinatorics and other subfields in mathematics. Particular classes of log concave polynomials called Lorentzian polynomials and denormalized and dually Lorentzian polynomials have been used to prove log concavity statements for various combinatorial sequences. This includes the strongest form of Mason's log concavity conjecture on the independent sets of matroids and the log concavity of sequences of Kostka numbers.
In this talk, we develop an analogous class of power series called denormalized Lorentzian (DL) Laurent series. This class is the natural generalization of DL polynomials to homogeneous power series with the benefit of capturing a number of combinatorial generating series including the Kostant partition function for integer flows of directed graphs. We then analyze specific DL Laurent series to obtain new bounds for integral flows on general directed acyclic graphs and new bounds for the dimensions of weight spaces of parabolic 𝔰𝔩ₙ₊₁(ℂ) Verma modules.

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

Friday, July 31, 2026 3:30 pm - 4:30 pm EDT (GMT -04:00)

Tutte Colloquium -Kanstantsin Pashkovich-Simple and Almost Non-Adaptive 1/2-Approximation for Matroid Prophet Inequalities

Speaker: Kanstantsin Pashkovich
Affiliation: University of Waterloo
Location: MC 5501

Abstract: Prophet inequalities are a fundamental model for online decision-making under uncertainty. For matroid constraints, Kleinberg and Weinberg gave a tight 1/2-approximation, but their algorithm uses adaptive thresholds that depend on the previously accepted elements. Specifically, the mechanism of Kleinberg and Weinberg accepts an arriving element if and only if it is feasible to add with respect to the matroid constraint and the value of the arriving element passes its threshold; but this threshold depends on the elements accepted so far and on the arriving element itself. Later, Feldman, Svensson, and Zenklusen showed that one can give a 1/4-approximation for general matroids. Their algorithm is almost non-adaptive, i.e., it uses non-adaptive thresholds but changes the underlying matroid to another ``stricter'' matroid. Feldman, Svensson, and Zenklusen also showed that no constant approximation is possible in general matroids using non-adaptive thresholds if one does not change the underlying matroid.

We give a new almost non-adaptive algorithm for matroid prophet inequalities that achieves a 1/2 guarantee. We change the underlying matroid to a ``stricter'' new matroid that is a direct sum of several matroids. For each part of the new matroid, we precompute a single non-adaptive threshold. Once the elements start to arrive, we accept an arriving element as long as it is feasible with respect to the new ``stricter'' matroid and its value passes the precomputed threshold. In addition, we guarantee that our algorithm achieves the 1/2 guarantee not simply with respect to the prophet's expected gain, but with respect to the stronger ex-ante relaxation value.
Thus, we provide the first almost non-adaptive algorithm for the matroid prophet inequality that achieves the best-possible approximation guarantee of 1/2. If time permits, we will also discuss how we used LLM in this project.