Tuesday, June 3
Location: Calvin Lab (Directions)
5:30pm Registration and reception
7:00pm Introduction and playback with Omer Reingold and group
Wednesday, June 4
Location: Calvin Lab (Directions)
8:30 — 9:30am Breakfast at Simons
9:30am – 10:30am Ronitt Rubinfeld (MIT): Efficient 2-coloring of random uniform hypergraphs via fast coloring oracles
10:30am – 11:00am Break
11:00am – 12:00 pm Lydia Liu (Princeton): Human-AI Decision Making
12:00pm – 2:00pm Lunch at 2F
2:00pm – 3:00pm Laura Kray (Hass Schools of Business, UC Berkeley)
3:00pm — 3:30pm Break
3:30pm Student rump sessions, 3 min per presentation
3:30pm – 4:15pm Rump session 1 (3 minutes per talk)
4:15pm – 4:45pm Ice Cream Sundae Bar
4:45pm – 5:30pm Rump session 2 (3 minutes per talk)
Dinner on your own
Thursday, June 5
Location: Calvin Lab (Directions)
8:30 — 9:30am Breakfast at Simons
9:30am – 10:30am Mary Wooters (Stanford): List-Recovery and (Non)-Applications
10:30am –11:00am Break
11:00am – 12:00pm Rachel Cummings (Columbia): Differential Privacy: State of the Art and Challenges
12:00pm – 2:00 pm Lunch at 2F
2:00pm – 3:00pm Shuchi Chawla (UT Austin): Combinatorial Selection with Costly Information
3:00pm — 3:15pm Break
3:15pm – 5:30pm Panel
6:00pm Banquet at UC Berkeley Faculty Club (Minor Ln, Berkeley, CA 94720)
Friday, June 6
Location: Calvin Lab (Directions) and Googleplex in Mountain View
8:00 — 8:30am Breakfast at Simons
8:30am – 9:30am Tal Malkin (Columbia): Black-Box Separations in Cryptography
9:30am Bus to Googleplex in Mountain View
11:00am – 3:00pm Industry Day at Googleplex
Sara Ahmadian Best of both worlds: Achieving scalability and quality in text clustering
Kshipra Bhawalkar Lane Auctions with LLM Summaries and Equilibria in Modular
Marketplaces: Economic Design in Language-Enabled Ecosystems
Lynn Chua Bridging the Privacy Accounting Gap in Private Model Training
Apoorvaa Deshpande From Theory to Privacy Engineering
Yangsibo Huang Can We Reliably Evaluate Progress of LLMs?
Isabelle Stanton From Theory to Practice: A Career in Google Search
3:00pm — 4:30 Bus back to Simons Institute
5:00pm Depart Simons Institute”
Abstracts
Ronitt Rubinfeld (MIT): Efficient 2-coloring of random uniform hypergraphs via fast coloring oracles
Abstract: Hypergraph 2-colorability is one of the classical NP-hard problems. However, recent work has given algorithms with polynomial expected running time for 2-coloring random 2-colorable hypergraphs. These works depend on heavy machinery from combinatorics, namely the Szemeredi Regularity Lemma, and thus have constants that are not practical.
We give a new simple and elementary deterministic 2-coloring algorithm that reproves prior results, while avoiding the use of the Regularity Lemma. We also show how to turn our new algorithm into a randomized one with average expected running time of only O(n), which is sublinear in the input size and optimal.
Our algorithm is based on providing a “coloring oracle” which, given vertex v, assigns color red/blue to v while inspecting as few edges as possible, so that the answers to any sequence of queries to the oracle are consistent with a single legal 2-coloring of the input. Surprisingly, we show that there is a coloring oracle that, on average, can answer *every* vertex query in constant time. Such a coloring oracle is an example of a local computation algorithm (LCA). We will give a short survey of LCAs and their uses.
Joint work with Cassandra Marcussen, Ted Pyne, Asaf Shapira and Shlomo Tauber.
Lydia Liu (Princeton): Human-AI Decision Making
Abstract: As algorithmic decision systems become increasingly integrated into high-stakes domains like education, understanding their real-world impact requires moving beyond predictive accuracy. This talk bridges AI and human expertise through the lens of causal inference and decision-making. We combine causal theory with empirical analyses of a randomized controlled trial of algorithm-assisted college advising to investigate how advisors use discretion to target interventions. We introduce a notion of non-algorithmic expert interventions based on structural causal modeling and develop a quantitative and qualitative framework to test for the value of human judgment in algorithm-supported contexts. Then, we explore how human behavioral responses to predictive models can shape outcomes in experimental evaluations of ADS. We show that design choices may induce cognitive biases and distort treatment effect estimates. Together, these studies highlight the importance of modeling both human behavior and causal mechanisms when deploying and evaluating AI systems for decision making in the real world. Based on joint work with Inioluwa Deboraji Raji, Sofiia Druchyna, Kara Schechtman, and Hannah Li.
Rachel Cummings (Columbia): Differential Privacy: State of the Art and Challenges
Abstract: Privacy concerns are becoming a major obstacle to using data in the way that we want. It’s often unclear how current regulations should translate into technology, and the changing legal landscape surrounding privacy can cause valuable data to go unused. In this talk, we will explore differential privacy as a tool for providing strong privacy guarantees, while still making use of potentially sensitive data. Differential privacy is a parameterized notion of database privacy that gives a mathematically rigorous worst-case bound on the maximum amount of information that can be learned about an individual’s data from the output of a computation. In the past decade, the privacy community has developed algorithms that satisfy this privacy guarantee and allow for accurate data analysis in a wide variety of computational settings, including machine learning, optimization, statistics, and economics. This talk will first give an introduction to differential privacy, and then survey recent advances and future challenges in the field of differential privacy.
Mary Wooters (Stanford): List-Recovery and (Non)-Applications
Abstract: Coding theory is the study of error-correcting codes, a fundamental tool used to protect data from noise. In coding theory, list-recovery refers to the ability to correct from a certain type of uncertainty, where multiple possibilities are received for each symbol that is sent. List-recovery has found many applications throughout computer science (and not just for protecting data from noise), for example in algorithm design, group testing, pseudorandomness, and cryptography. In this lecture, I’ll give an overview of list-recovery in coding theory and discuss some constructions as well as some applications. I’ll also discuss open problems and mention some motivating non-applications: That is, things that would be applications, if only we could solve some open problems about list-recovery!
Shuchi Chawla (UT Austin): Combinatorial Selection with Costly Information
Abstract: Many decision making settings call for upfront investment in information acquisition before optimizing over multiple possible solutions. This intertwining of information acquisition and optimization presents a trade-off: information is costly but can lead to improved outcomes in the downstream task. Imagine, for example, trying to recruit a graduate student for your group. You may read through many CVs and interview a few candidates before selecting one candidate. Acquiring information about the candidates takes time, so it is important to determine which information is worthwhile to obtain and in what order. The challenge is that the process of information acquisition can change adaptively — new information you gain can affect what you choose to do next. We model this as an optimization problem where the goal is to maximize the value of the selected candidate minus the cost (e.g. time spent) of information acquisition.
This problem has a long history going back to the work of Weitzman (1979) on the so-called “Pandora’s Box” problem and a broader model called a “bandit superprocess” introduced by Nash in 1973. In the last 5-10 years, this area has seen much progress in the form of new techniques, approximation algorithms, and applications. In this talk, we will review this literature, describe the main techniques and conclude with open directions.
Women in Theory 