Date: November 17, 2025
Time: 3:45-5 p.m.
Location: Gates 310 or via Zoom
Speaker: Renato Paes Leme, Google Research New York
Title: Graphic Matroid Secretary without the Graph
Abstract: The matroid secretary problem (MSP) is one of the cleanest, and most captivating open problems in online algorithms. The famous MSP conjecture stipulates that there exists a constant competitive algorithm, yet to date the best-known algorithms are O(log log(rank)) competitive. It is widely believed that all information that an algorithm for the MSP should use is information that is available through an independence oracle on the already arrived elements. Despite this, there are natural classes of matroids where a constant-competitive algorithm is known if we are given additional upfront information about the matroid; while no such algorithm is known if all the algorithm can use is an independence oracle on the arrived elements. In this work, we tackle the perhaps most appealing such class of matroids, graphic matroids, and develop the first constant-competitive algorithm with access to an independence oracle only. Joint work with Paul Dutting and Neel Patel.
Bio: Renato is a research scientist at Google Research New York. He is broadly interested in algorithm design, specially for problems on the interface between Economics and Computation. Currently his main interests are: dynamic mechanism design (how to design good auctions over time for settings like internet advertisement), machine learning in economic environments (e.g. online learning for pricing and learning when feedback is given by strategic agents) and applications of convex programming to market optimization.