7th Eastern Great Lakes 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 2024, this event is held at University at Buffalo's Department of Computer Science.

Dates and Location

October 5th (Saturday), 2024, 1:30pm - 5:30pm.
October 6th (Sunday), 2024, 9:30am-3pm.

The conference is held at Davis Hall, University at Buffalo (North Campus), Buffalo, NY.

Registration

Registration deadline is September 15, 2024

Speakers

Jon Kleinberg, Cornell University
Pravesh Kothari, Princeton University
Sushant Sachdeva, University of Toronto
Nisarg Shah, University of Toronto
Madhu Sudan, Harvard University
Avi Wigderson, Institute for Advanced Study

Workshop Schedule

The workshop will feature talks by the speakers and a student poster session.

October 5th (Saturday)

1:30pm - 2:30pm: Talk by Madhu Sudan Recording

Title: Sparsification: Graphs, CSPs, and Codes

Abstract: The seminal works of Karger and Benczur and Karger from the 90s showed how graphs can be "sparsified" to size nearly linear in the number of vertices, so that the size of every cut is preserved to arbitrarily small multiplicative factors. This work motivates the general notion of the ``sparsification of a structure with respect to a class of queries'' which should roughly produce a compressed representation of the structure while answering every query in the class approximately correctly. One may ask what else beyond "graphs with respect to cut queries" can be so sparsified, and the ensuing years have discovered many new structures and sparsifications and derived potent applications. In 2015, Kogan and Krauthgamer suggested an umbrella to unify some of this quest by investigating CSP (Constraint Satisfaction Problem) sparsification: --- here the structure to be compressed is an instance of the CSP on n variables and a query is an assignment to the n variables, and the goal is to approximately determine the number of constraints satisfied by the queried assignment. This naturally captures graph sparsification, but also hypergraph sparsifications and many natural variants. Several follow up works gave some non-trivial CSPs that allow for near linear (in n) sparsifications, including classification of all binary CSPs (where each constraint applies to two variables) that allow such sparsification, but the general picture remains wide open.
In our works we introduce a new class of sparsification problems, namely code sparsification, where the structure to be preserved is a linear error correcting code; the query is a message, and the goal is to compute the approximate weight of the encoding of the message. We show that this class of problems gives the right language to abstract the techniques of Karger and Benczur and Karger --- and indeed all codes can be sparsified to length nearly linear in the number of message bits. This generalization already resolves some basic questions in CSP sparsification. A further generalization to additive codes over finite abelian groups gives even more powerful results and in particular completely classifies the class of symmetric Boolean CSPs that allow nearly linear sized sparsification. (Prior to our work even the case of sparsification of 3-XOR constraints was open.)
Based on joint works with Sanjeev Khanna (U. Penn.) and Aaron (Louie) Putterman (Harvard).
2:30pm - 3:00pm: Break
3:00pm - 4:00pm: Talk by Nisarg Shah Recording

Title: Algorithmic Fairness via Social Choice

Abstract: Today, algorithmic decision-making is becoming prevalent at an unprecedented rate. This has naturally raised questions regarding whether such decision-making treats individuals or groups fairly. But first, we have to answer what we really mean when we say "fair".
In this talk, I will discuss mathematical notions of algorithmic fairness emerging from the computational social choice literature, which sits at the intersection of economics, theoretical computer science, and AI, and demonstrate their applicability to a variety of decision-making domains ranging from resource allocation and voting to AI paradigms such as classification, clustering, and recommender systems.
4:00pm - 4:30pm: Break
4:30pm - 5:30pm: Talk by Pravesh Kothari Recording

Title: Hypergraph Rainbow Problems, Local Codes, and the Kikuchi Matrix Method

Abstract: The classical rainbow cycle conjecture of Keevash, Mubayi, Verstrate, and Sudakov says that every properly edge-colored graph of average degree \Omega(log n) contains a "rainbow" cycle, i.e., a cycle with edges of all distinct colors. Recent advances have almost resolved this conjecture up to an additional log log n factor.
In this talk, I will describe hypergraph variants of the graph rainbow problem and show how they are intimately related to the existence of (linear) locally decodable and locally correctable codes. I will then describe the "Kikuchi Matrix Method" to solve such problems - a general principle that converts hypergraph rainbow problems into related graph counterparts. Consequently, we obtain an exponential lower bound on linear 3 query locally correctable codes and a cubic lower bound on 3 query locally decodable codes.
For those familiar with the work in this area, this will be a combinatorial viewpoint on the spectral methods that yield similar results (but also extend to non-linear codes).
Based on joint works with Omar Alrabiah, David Munha-Correia, Venkat Guruswami, Tim Hsieh, Peter Manohar, Sidhanth Mohanty, Benny Sudakov

October 6th (Sunday)

9:00am - 9:30am: Coffee
9:30am - 10:30am: Talk by Avi Wigderson Recording

Title: Reading Alan Turing

Abstract: I will discuss some well-known and less-known papers of Turing, exemplify the scope of deep, prescient ideas he put forth, and mention follow-up work on these by the Theoretical CS community.
No special background will be assumed.
10:30am - 11:00am: Break
11:00am - 12:00pm: Talk by Jon Kleinberg Recording

Title: Language Generation in the Limit

Abstract: Although current large language models are complex, the most basic specifications of the underlying language generation problem itself are simple to state: given a finite set of training samples from an unknown language, produce valid new strings from the language that don't already appear in the training data. Here we ask what we can conclude about language generation using only this specification, without any further properties or distributional assumptions. In particular, we consider models in which an adversary enumerates the strings of an unknown target language that is known only to come from a possibly infinite list of candidate languages, and we show that it is possible to give certain non-trivial guarantees for language generation in this setting. The resulting guarantees contrast dramatically with negative results due to Gold and Angluin in a well-studied model of language learning where the goal is to identify an unknown language from samples; the difference between these results suggests that identifying a language is a fundamentally different problem than generating from it. (This is joint work with Sendhil Mullainathan.)
noon - 2:00pm: Poster Session and Lunch (provided)
2:00pm - 3:00pm: Talk by Sushant Sachdeva Slides (unfortunately recording is lost)

Title: Simpler and Faster Spectral Sparsification for Eulerian Directed Graphs

Abstract: While spectral sparsification is well understood for undirected graphs, developing efficient algorithms for spectral sparsification of Eulerian (directed) graphs has been challenging. We present a new framework for sparsifying Eulerian graphs that utilizes electrical routings to preserve Eulerianness, and exploits a simple effective resistance partitioning for improved sparsifier quality. Our approach yields state-of-the-art algorithms for constructing Eulerian sparsifiers, both in terms of running time and the resulting sparsity. As a consequence, we obtain significantly faster algorithms for solving directed Laplacian systems and computing stationary distributions of markov chains.
This is joint work with Arun Jambulapati, Aaron Sidford, Kevin Tian, and Yibin Zhao.

Accommodation

Suggested hotels:
StayBridge Suites Buffalo-Amherst
DoubleTree

Parking

The two closest lots to Davis hall (which is where the workshop will be held) are Furnas and Jarvis parking lots. Parking permits are not enforced over the weekends, so parking in Jarvis or Furnas on Saturday or Sunday would be fine.

Dining

Most of the restaurants in UB Commons will be open 11:30am-6pm on both Saturday and Sunday -- UB Commons is very close to Davis. Atri's favorite place in Commons is Poke Factory -- their Chicken Nasi Lemak is the closest to decent Indian chicken curry on campus.

There is another cluster of restaurants near the Staybridge Suites -- Atri's favorite places are China Taste and Forno Napoli. There is also a breakfast place and a bubble tea place in the same complex.

Buffalo has good food: if you have a car then Google is your friend. Generally speaking, a random Italian restaurant in Buffalo would be a reasonably safe bet. Most places are open on Saturday and Sunday but please double-check the hours of operation before going to a restaurant.

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