Stanford WTF

Women in Theory Forum

Welcome to the Stanford Women in Theory Forum (WTF). We are group of women-identifying CS-theorist-identifying (and theory-adjacent) folks who meet monthly-ish for socializing, snacks, and a research talk. If you'd like to join our mailing list, please email the organizers, or sign up here: https://mailman.stanford.edu/mailman/listinfo/womens-theory-forum

Organizers: Tselil Schramm (tselil-at-stanford-dot-edu) and Mary Wootters (marykw-at-stanford-dot-edu)

Schedule

AY 2022-2023

If the weather is nice, we will meet outside in the engineering quad (in the treepit with the whiteboards). If the weather is not so nice, we'll meet inside, probably Gates 415. Join the mailing list for announcements about locations.

  • Wednesday October 19, 3:30pm: Ellen Vitercik

    • Title: Theoretical Foundations of Machine Learning for Cutting Plane Selection

    • Abstract: Cutting-plane methods have enabled remarkable successes in integer programming over the last few decades. State-of-the-art solvers integrate a myriad of cutting-plane techniques to speed up the underlying tree search algorithm used to find optimal solutions. In this talk, we provide sample complexity guarantees for learning high-performing cut-selection policies tailored to the instance distribution at hand. This talk is based on joint work with Nina Balcan, Siddharth Prasad, and Tuomas Sandholm from NeurIPS'21.

  • Wednesday November 16, 3:30pm: Sumegha Garg

    • Title: Memory requirements for detecting bias of a coin

    • Abstract: Given a sequence of n independent tosses of a coin biased towards either heads or tails with probability 1/2 + β, the aim is to determine which way the coin is biased. Let's call this the coin problem. We study the memory required to detect the bias in the streaming setting. Note that the coin problem becomes more difficult as β becomes smaller. Statistically, it can be solved whenever β = Ω(1/√n), using counting. We first show that for β = O(1/√n), counting is essentially optimal, that is, \Omega(log n) memory is necessary, using an information-theoretic proof [BGW’20]. Then, we will see how O(log log n) memory suffices to solve the coin problem for β = O(1/n^{-1/3}) [BGZ'21]. Based on joint works with Mark Braverman, David Woodruff and Or Zamir.

AY 2021-2022

The schedule has been lost to time.