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 2026, this event is held at the University of Rochester.
Dates and Location
- October 17th (Saturday), 2026, 1:30pm - 5:30pm.
- October 18th (Sunday), 2026, 9:30am-4:30pm.
The conference is held at Wegmans Hall, University of Rochester, Rochester, NY.
Registration
Registration is free, but required. Please register here by October 1st so that we can plan accordingly.
Speakers
- Josh Alman, Columbia University
- Sepehr Assadi, University of Waterloo
- Mark Braverman, Princeton University
- Constantinos Daskalakis, MIT
- Anupam Gupta, NYU
- Tal Malkin, Columbia University
- Daniel Wichs, Northeastern University
Workshop Schedule
The workshop will feature talks by the speakers and a student poster session. Click a talk title to expand or collapse its abstract.
October 17th (Saturday)
-
1:30pm - 2:30pm: Anupam Gupta —
Abstract:
Suppose jobs arrive over time and have to be scheduled on a single server. Jobs can be paused and then resumed. We want to minimize the average response time (aka flow time). It is not difficult to show that the Shortest Remaining Processing Time (SRPT) strategy is optimal for this problem. But SRPT requires each job to accurately declare the amount of processing it needs (aka its size) when it arrives. And this "clairvoyance" may not always be reasonable to assume. E.g., what if we are only given noisy estimates of the size? Alternatively, what if we only learn the size once we have processed the job to some extent? In this talk, I will discuss two "robust" algorithms which address these extensions.
This talk is based on joint works with Amit Kumar, Debmalya Panigrahi, and Zhaozi Wang (at SODA 26), and with Haim Kaplan, Alexander Lindermayr, Jens Schloeter, and Sorrachai Yingchareonthawornchai (at FOCS 25), respectively.
- 2:30pm - 3:00pm: Break
-
3:00pm - 4:00pm: Tal Malkin —
Abstract:
Position verification schemes are interactive protocols where entities prove their physical location to others; this enables interactive proofs for statements of the form “I am at a location L.” Although secure position verification cannot be achieved with classical protocols (even with computational assumptions), they are feasible e.g. with quantum protocols.
Position verification opens the door to a new kind of cryptography, where your credential is your physical position at a certain point in time. In this talk I will discuss some intriguing questions and potential applications that position based cryptography gives rise to. I will focus on a recent work (joint with Girish, Gluch, Goldwasser, Orshansky and Yuen) that introduces the notion of zero-knowledge position verification for arbitrary regions of spacetime. For example, this allows entities to prove statements such as “I was NOT near location L at noon yesterday”, while hiding all other information.
- 4:00pm - 4:30pm: Break
-
4:30pm - 5:30pm: Constantinos Daskalakis —
Abstract:
Applications in computer science and machine learning motivate the study of games with large strategy spaces and complex payoff functions, which make it challenging to apply standard equilibrium concepts and/or computational methods. We overview these challenges, presenting some novel work at the edge of tractability. We start with a computationally friendly version of Sion’s minimax theorem, showing its surprising effectiveness in applications including the computation of correlated equilibria in all convex games as well as the efficient computation of fixed points of ell_p contractions under even p. On the non-convex side of things, we consider games with non-concave utilities, presenting relaxations of standard equilibrium and fixed point notions that recover existence and tractability.
October 18th (Sunday)
- 9:00am - 9:30am: Coffee
-
9:30am - 10:30am: Daniel Wichs —
Abstract:
This talk surveys recent results constructing error-correcting codes with better parameters than what is information-theoretically possible when the error pattern is adversarial but polynomial-time computable. We focus on codes over the binary alphabet and show how to achieve the following:
- Unique decoding with essentially the same parameters as the best information-theoretic list-decodable codes, under standard cryptographic assumptions (EUROCRYPT 2025; FOCS 2025).
- Unique decoding at Shannon capacity R = 1 - H(p) for a p < 1/4 fraction of errors (and list-decoding for p < 1/2 fraction of errors), under strong but plausible cryptographic assumptions (CRYPTO 2026).
Based on joint work with Jad Silbak and George Lu.
- 10:30am - 11:00am: Break
-
11:00am - 12:00pm: Josh Alman —
Abstract:
I'll talk about new faster algorithms for 3SUM, APSP, and many more related problems. They all follow from one new algorithm for quickly computing certain entries of a matrix product. That algorithm was found by Anthropic using an internal model of Claude. They then contacted me and Virginia Vassilevska Williams to understand and properly write up the algorithm. I'll talk about the algorithm itself, what it means for fine-grained complexity, and the whole experience of being contacted by Anthropic and putting this paper together.
- noon - 1:30pm: Lunch (provided)
-
1:30pm - 2:30pm: Mark Braverman —
Abstract:
Modern optimization achieves remarkable results, but it consistently breaks down when inputs come from strategic, self-interested agents—the fundamental challenge of mechanism design. Strategic manipulation cannot be solved simply by scaling up compute or applying gradient descent. Without formal mathematical frameworks for incentives, systems like social media ranking often rely on deliberate opacity to deter gaming. Unfortunately, this opacity breeds unintended consequences, such as content farms, rather than solving the core issue.
Building transparent mechanisms to align these incentives is famously difficult, heavily constrained by classical impossibility theorems and computational hardness. We will discuss the theoretical background behind these roadblocks and explore recent approaches to bypassing them. Specifically, we will look at how bridging optimization with online learning can help us build general-purpose mechanism design tools that scale alongside modern computational methods.
-
3:00pm - 4:00pm: Sepehr Assadi —
Abstract:
We prove that no single-pass semi-streaming algorithm (deterministic or randomized) can achieve a better-than-half approximation to the maximum matching problem. This implies the optimality of the naive greedy algorithm, answering a longstanding open question in graph streaming literature since the introduction of the model. Our proof consists of two main parts:
- Blueprint framework: reducing the problem of proving lower bounds for semi-streaming matching to constructing certain combinatorial objects which we call blueprints; and
- Blueprint construction: an optimal construction of such blueprints usable within this framework.
Putting these two parts together then implies our semi-streaming matching lower bound.
Based on joint work with Max Jiang and Mars Xiang in arXiv:2607.14644 (STOC 2026) and arXiv:2607.14656 (arXiv; July 2026).
- 4:00pm - 5:00pm: Poster Session
Accommodation
Suggested hotels:
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
Previous EaGL workshops
