6th Eastern Great Lakes (EaGL) Theory of Computation Workshop

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, noon - 5:30pm.
  • October 1st (Sunday), 2023, 9:30am-4pm.

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

  • 12:00pm - 1:20pm: Lunch at Douglas Dining
  • 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

Sunday, October 1

  • 8:00am - 9:20am: Breakfast at Douglas Dining
  • 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 - 12:00pm: 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.
  • 12:00pm - 1:20pm: Lunch at Douglas Dining
  • 1:30pm - 2:30pm: 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.
  • 2:30pm - 4:00pm: Poster Session

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

  • Eshan Chattopadhyay (Cornell University) email
  • Kaave Hosseini (University of Rochester) email
  • Anson Kahng(University of Rochester) email
  • Noah Stephens-Davidowitz (Cornell University) email

image

image

image