About the Workshop
The purpose of this annual workshop is to bring together researchers in theoretical computer science, who work in the vicinity of the eastern great lakes region. For 2025, this event is held at the University of Rochester.
Dates and Location
- October 11th (Saturday), 2025, 1:30pm - 5:30pm.
- October 12th (Sunday), 2025, 9:30am-3pm.
The conference is held at Wegmans Hall, University of Rochester, Rochester, NY.
Registration
Registration is free and required for attendace. Registration deadline is September 20, 2025
Here is the registration link.
Please register as soon as possible so that we plan accordingly.
Speakers
- Yael T Kalai, MIT
- Dakshita Khurana, UIUC
- Bobby Kleinberg, Cornell University
- Swastik Kopparty, University of Toronto
- Ryan O'Donnell, Carnegie Mellon University
- Rocco Servedio, Columbia University
Workshop Schedule
The workshop will feature talks by the speakers and a student poster session.
October 11th (Saturday)
- 1:30pm - 2:30pm:
Talk by Bobby Kleinberg: Near-Optimal Algorithms for Omniprediction
Abstract: Machine learning models can be trained to predict probabilities of uncertain events. A standard application of this paradigm requires obtaining training data, training a model to optimize the utility of a decision maker or agent, and deploying the model to make predictions optimized for that agent. An alternative is to train an agent-agnostic “prediction service” to forecast probabilities of events, and let different agents best-respond to the forecasts. This alternative, first put forward by Gopalan et al. in 2022, is known as "omniprediction". It has clear advantages in terms of model reuse and privacy, but what is lost in terms of efficiency? Can omnipredictors be trained to provide predictions that are nearly as trustworthy as if each agent used the same amount of training data to optimize their own utility? We will describe some settings in which, surprisingly, the answer is yes. Underlying these results is a new measure of forecast calibration called "proper calibration" that is weak enough to be achievable using only logarithmically more samples than the easiest statistical learning tasks, yet strong enough to provide near-optimal guarantees on agents’ regret.
This is joint work with Princewill Okoroafor and Michael P. Kim, to appear in FOCS 2025.
- 2:30pm - 3:00pm: Break
- 3:00pm - 4:00pm:
Talk by Dakshita Khurana: How Low Can We Go? Exploring Minimal Assumptions in Quantum Cryptography
Abstract: In this talk, I will explore the fascinating landscape of minimal assumptions in quantum cryptography—how little we need to assume to build secure quantum protocols. We will cover key cryptographic primitives including quantum encryption, signatures, and money, and show how these primitives imply the existence of one-way puzzles, a quantum analogue of classical one-way functions. I will also highlight the utility of one-way puzzles and discuss concrete assumptions that enable their realization, revealing intriguing connections to quantum advantage.
- 4:00pm - 4:30pm: Break
- 4:30pm - 5:30pm:
Talk by Rocco Servedio: Is nasty noise actually harder than malicious noise?
Abstract: We study the relative abilities and limitations of computationally efficient algorithms for learning in the presence of noise, under two well-studied and challenging adversarial noise models for learning Boolean functions:
* malicious noise, in which an adversary can arbitrarily corrupt a random subset of examples given to the learner; and
* nasty noise, in which an adversary can arbitrarily corrupt an adversarially chosen subset of examples given to the learner.
We consider both the distribution-independent and fixed-distribution settings. Our main results are as follows:
* For distribution-independent learning, we prove a strong equivalence between the two noise models: If a class of functions is efficiently learnable in the presence of η-rate malicious noise, then it is also efficiently learnable in the presence of η-rate nasty noise.
* For the fixed-distribution setting, we show that the relationship is far more subtle. We give both positive results, showing that for a broad and natural class of algorithms malicious noise and nasty noise are equivalent up to a factor of two in the noise rate, as well as negative results establishing separations. Our separations are based on cryptography.
Joint work with Guy Blanc (Stanford), Yizhi Huang (Columbia), and Tal Malkin (Columbia)
October 12th (Sunday)
- 9:00am - 9:30am: Coffee
- 9:30am - 10:30am:
Talk by Swastik Kopparty: Improved Private Information Retrieval Schemes from Matching
Vectors and Derivatives
Abstract: Private Information Retrieval (PIR) is a method for a user to interact
with t non-colluding servers and read some entry of a database of size
n without revealing to the servers anything about which entry of the
database was read. After a long line of work, including breakthroughs
by Yekhanin (2007), Efremenko (2009) and Dvir-Gopi (2014), we know
that for any t >= 2, t-server PIR is possible with n^{o(1)}
communication.
In this talk, I will describe some ideas that go into these PIR
schemes, and give a new, simpler PIR scheme for t = 2 based on a
slightly different viewpoint on them. This simpler scheme generalizes
well, and gives superpolynomial improvements to
the best known communication for all but finitely many t. Notably, we
get a 3-server PIR scheme with communication
exp((log n)^(1/3)), improving upon the previously best-known
communication of exp((log n)^(1/2)) due to Efremenko.
Joint work with Fatemeh Ghasemi and Madhu Sudan.
- 10:30am - 11:00am: Break
- 11:00am - 12:00pm:
Talk by Yael T Kalai: Classical Verification of Quantum Computations
Abstract: When a user claims to have performed a quantum computation and obtained a result, how can a purely classical verifier be convinced of its correctness? This talk surveys recent progress on this fundamental question.
- noon - 1:00pm: Lunch (provided)
- 1:00pm - 2:00pm: Poster Session
- 2:00pm - 3:00pm:
Talk by Ryan O'Donnell: No exponential quantum speedup for ℓ_∞-SIS anymore
Abstract: There is an exciting new paradigm for exponential quantum speedups in town (Regev's reduction)! It provably works in the black-box model for some problems (Yamakawa--Zhandry), and it seems to work for other natural problems too ("Optimal Polynomial Interpolation"). Unfortunately, we show that for the original application to the "Short Integer Solution" problem (Chen--Liu--Zhandry), there is a classical algorithm that is just as good. Darn!
Accommodation
Suggested hotels:
Hilton Garden Inn Rochester/University and Medical Center
To obtain the 20% UR discount, the guest must book the reservation under one of our flexible rates. Once the reservation is made, the guest can call our hotel directly and our front desk will apply the 20% discount to the reservation.
Staybridge Suites Rochester University, an IHG Hotel
Parking
Over the weekend, there is free street parking on Wilson Bulevard near Wegmans Hall. Also the closest free parking lot is Intercampus Drive Lot.
Dining
Douglas Dining Hall on campus offers breakfast, lunch, and dinner.
Organizers
- Eshan Chattopadhyay (Cornell University) email
- Venkata (GV) Gandikota (Syracuse University) email
- Kaave Hosseini (University of Rochester) email
- Anson Kahng (University of Rochester) email
- Noah Stephens-Davidowitz (Cornell University) email