Reading Group on TCS Fall 2025

Overview

Welcome to our reading group exploring Theoretical Computer Science (TCS) in all its breadth. Everyone is invited: students and faculty from any department (and visitors from outside UIUC are welcome, too). TCS has deep ties to Math, ECE, Physics, and many other areas. If you wouldd like to give a talk, please let the organizers know. If you are a student interested in helping lead and organize the group, please reach out to Fernando.

Tentative Format

The format is flexible. For instance, we can have usual ~1 hour talks, or, ideally, more intense (and fun ;) ~2-3 hours gatherings depending on the speaker interests. A suggestion for longer talks is the following.

First Part (~1 hour): general presentation about the work with context, motivation, and overview of technical results possibly with some simpler proofs.
Break (~30 minutes): recharge and socialize.
Second Part (~1 hour + x minutes): present (some of) the technical part and proofs in more detail.
Final Part (~30- x minutes): more questions, free speculations, and socialization.

Tentative Schedule

A tentative schedule with speakers is given below. Please note that this is under construction.

An edge-colored graph is said to be rainbow if no color appears more than once. Extremal problems involving rainbow objects have been the focus of much research over the last decade, as they capture the essence of a variety of interesting problems across different areas such as coding theory and additive number theory. A particularly intensively studied question due to Keevash, Mubayi, Sudakov and Verstraëte from 2007 asks for the maximum possible average degree of a properly edge-coloured graph on n vertices without a rainbow cycle. Recently, Alon, Bucić, Sauermann, Zakharov, and Zamir established an essentially tight bound of (log(n))^{1+o(1)} for the maximum possible average degree when rainbow cycles are forbidden using the technique of robust sublinear expander.

This talk will give a gentle introduction to robust sublinear expanders and sketch the main ideas behind this result. For pedagogical reasons, we will also present a detailed proof of a weaker result obtained through a similar high-level approach. In addition, we will briefly discuss algorithmic aspects of sublinear expanders. The talk will assume only minimal background in graph theory.

NP-hard problems are (probably) infeasible in the worst case. However, we do not live in a worst case world, and such problems can still be easy on "most" instances, i.e., virtually all instances that arise in practice. To truly capture "real world" computational infeasibility, we must turn to average case hardness. Additionally, for computational hardness to be useful for cryptography, average case hardness is not enough; one needs to be able to sample hard instances along with their solutions.

While there are serious barriers to proving the existence of such hardness, recent breakthroughs in metacomplexity have brought this goal closer than ever before. This talk will give a brief overview of how Kolmogorov complexity offers a path towards bridging the gaps between worst-case hardness, average-case hardness, and cryptographic hardness.

Kolmogorov Complexity is an important notion of randomness in computability theory. Along with the Minimum Circuit Size problem (MCSP), it constitutes Meta-Complexity theory - the study of complexity of computational problems that are themselves about (some measure of) complexity.

We will introduce meta-complexity and discuss the complexity of MCSP and a brief history of attempts to characterize Kolmogorov complexity that culminate in a successful characterization of Statistical Zero Knowledge (SZK) and its non-interactive counterpart NISZK. (We will assume zero knowledge about these classes or Kolmogorov Complexity)