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 2023, this event is held at University of Rochester's department of Computer Science.
Dates and Venue
The workshop is held on a weekend:- September 30th (Saturday), 2023, 1:30pm - 5:30pm.
- October 1st (Sunday), 2023, 9:30am-3pm.
The conference is held in Rochester, NY, at Univeristy of Rochester's river campus, Wegmans hall, Room 1400.
Registration
Registration is required for attendance. Please register before September 15th as soon as possible so that we plan accordingly. There are no registration fees.
You can register here.
Speakers
- Shubhangi Saraf, University of Toronto
- Gautam Kamath, University of Waterloo
- Eva Tardos, Cornell University
- Henry Yuen, Columbia University
- Mark Bun, Boston University
- Nikhil Bansal, Univerity of Michigan
Workshop Schedule
The workshop will feature talks by the speakers and a student poster session. Please refer to the detailed schedule below:
Saturday, September 30
- 1:30pm - 2:30pm: Talk by Henry Yuen: A Complexity Theory for the Quantum Age?
Abstract:
How hard is it to compress quantum information? To produce a counterfeit quantum money state? To unscramble the Hawking radiation of a black hole? Traditional complexity theory -- which is centered around decision problems and tasks with classical inputs and outputs -- appears inadequate for reasoning about the complexity of such tasks involving quantum inputs and outputs.
In this talk I will discuss why we need a "fully quantum" complexity theory, and will describe some facets of such a theory. As a key illustration I will explain how a "fully quantum" task called the Uhlmann Transformation Problem characterizes the complexity of seemingly unrelated problems, such as decoding noisy quantum channels, performing the Harlow-Hayden black hole radiation decoding task, and breaking the security of quantum bit commitment schemes. Along the way I will describe many open problems and directions to explore in the world of fully quantum complexity theory.
No prior quantum background will be assumed. Joint work with John Bostanci, Yuval Efron, Tony Metger, Alexander Poremba, and Luowen Qian (Link to Paper).
- 2:30pm - 3:00pm: Break
- 3:00pm - 4:00pm: Talk by Eva Tardos: Stability and Learning in Strategic Interaction
Abstract: No-regret learning has been celebrated as the right behavioral assumption for learning in strategic interactions. Most price of anarchy proofs extend to repeated interactions assuming all participants use strategies that satisfy the no-regret assumption. A very strong assumption in this line of work is that the subsequent rounds of the repeated games are independent beyond any influence on play from past history. In this talk we consider two classes of games when the parameters of the games themselves change due to the actions of the participants: queuing systems and auctions with budgets. We discuss the effect of the no-regret learning assumption on outcomes in these games, including possible limitations of the assumption in this context.
- 4:00pm - 4:30pm: Break
- 4:30pm - 5:30pm: Talk by Mark Bun: Unifying Replicability, Differential Privacy, and Adaptive Generalization in Learning
Abstract: Replicability is the principle that the findings of an empirical study should remain the same when it is repeated on new data. Motivated by the difficulty of ensuring replicability in today’s complex data generation and analysis processes, Impagliazzo, Lei, Pitassi, and Sorrell recently put forth an algorithmic definition that serves as a general sufficient condition for replicability. This definition isn't the first notion of algorithmic stability aimed at ensuring the utility and safety of modern data analysis. Others are central to relatively mature areas such as differential privacy and adaptive data analysis. In this talk, I'll describe algorithmic transformations that together paint a clear picture of the relationships between replicability, differential privacy, and generalization in adaptive data analysis for statistical learning problems. I'll also describe some (surprising!) implications of this picture to differentially private algorithm design.
Sunday, October 1
- 9:00am - 9:30am: Light breakfast (provided)
- 9:30am - 10:30am: Talk by Shubhangi Saraf: Survey on locally decodable codes
Abstract: I will give an introduction to locally decodable codes and the closely related locally correctable codes. I will survey some of the known upper bounds and lower bounds, both in the low query regime as well as the high rate (and high query) regime. I will also highlight some of the most interesting challenges that remain. No background will be assumed.
- 10:30am - 11:00am: Break
- 11:00am - noon: Talk by Nikhil Bansal: An almost logarithmic approximation for cutwidth
Abstract: In the cutwidth problem, aka minimum cut linear arrangement, we are given a graph G and the goal is to order the vertices in a line such that the maximum number of edges crossing any point is minimized. Since the seminal work of Leighton and Rao, the best known LP-based approximation for the problem is O(log^2 n), based on recursively finding balanced separators. This directly improves to O(log^1.5 n) if we use the ARV algorithm to find the balanced separators. In this talk, I will give a gentle introduction to algorithmic techniques for graph partitioning and layout problems, and describe a recent O(log^{1+o(1)} n) LP-based approximation for cutwidth.
- noon - 2:00pm: Lunch (provided) and Poster Session
- 2:00pm - 3:00pm: Talk by Gautam Kamath: Differentially Private Mean Estimation
Abstract: Mean estimation is one of the most basic statistical problems, and in many cases, is solved by considering elementary statistics like the empirical mean. I will overview the surprisingly intricate world of mean estimation under the constraint of differential privacy, wherein both the results and the requisite algorithmic techniques become much more complex. Along the way, we will see connections with classic techniques in Statistics, robust estimation, and sum-of-squares optimization.
Student Support
A limited amount of support for travel and accomodation is available for students. Please indicate in registration form wether you are a student, and would need travel support.
Accommodation
There are two hotels near the University of Rochester.- Hilton Garden Inn Rochester/University and Medical Center
- Staybridge Suites Rochester University, an IHG Hotel
Parking
Over the weekend, there is plenty of free street parking. Also the closest free parking lot is Intercampus Drive Lot.
Organizers
