Harvard TGINF

TGINF ("Theory Graduate students and INdian Food") is a seminar for students and postdocs in the Theory of Computation group at Harvard. Our weekly meetings consist of one-hour talks given by theory group members.

Please add this to your calendar and email Cassandra at cmarcussen@g.harvard.edu if you want to join the mailing list!

Fall 2025

Coming soon!

Spring 2025

February 3

Speaker: Reid

Title: Bridging the Gap Between Artificial and Human Intelligence

Time: 4:30 - 6pm

Location: SEC 1.412

Food: Indian

Abstract: The Dartmouth Workshop formalized the goals of Artificial Intelligence (AI) in 1956 and in the following half century many of the goals have been achieved. We have learning algorithms that can surpass human skill level on a variety of tasks, from language comprehension to image recognition and game playing. These AI systems excel at solving well-prescribed problems. But, those that are vaguely defined, such as 'pick the best job candidate' or 'teach me to play chess' still prove to be challenging to state of the art AI systems. To bridge this gap we need to build from both sides---create AI systems that are more useful to humans, and improve AI systems to solve problems that people want solved. In this talk I will discuss my work on both these themes, starting with how large language models (LLMs) struggle to interpret text in ways that are intuitive for humans, along with my recent work on solving this problem. I will then discuss my work using chess as a model system, on making superhuman AI systems that are understandable to humans, so they can act as partners or teachers. Finally, I will discuss how this work informs broader analysis of AI's impacts on an increasingly technical society.

February 10

Speaker: Prashanth

Title: A quantitative Sylvester-Gallai theorem

Time: 4:30 - 6pm

Location: SEC 3rd floor common area

Food: Indian

Abstract: Given a finite set of points in Euclidean space that are not all collinear, the Sylvester-Gallai (SG) theorem states that there always exists a line passing through exactly two of them. We will discuss a “quantitative” version of the SG theorem due to Barak, Dvir, Wigderson and Yehudayoff (STOC 2011). In order to prove it, we will introduce some tools from matrix scaling theory. In particular, we will see that all matrices of certain non-zero patterns (called “design matrices”) must have a large rank. We will end by arguing that the quantitative SG theorem is very closely related to the notion of “2-query locally correctable codes” from coding theory.

February 28

Speaker: Jamie

Title: Spot the Difference: Lower Bounds Against Symmetric Circuits

Time: 4 - 5:15pm

Location: SEC 3rd floor common area

Food: Pizza

Abstract: One way to phrase the celebrated 2-2 Games Theorem is that there is no P-uniform family of circuits distinguishing 2-2 Games instances with satisfiability less than ε from those with satisfiability at least 1 - ε, assuming P != NP. A brand new result by Dawar and Molnár proves a similar statement, with the following modifications:

- The circuits are required to be symmetric with respect to structural automorphisms of the input encoding induced by permuting the vertices.

- We no longer have to assume P ≠ NP.

- We also get perfect completeness, i.e., an (ε, 1) gap rather than an (ε, 1 - ε) gap.

I will discuss an earlier, weaker result of mine that established a (2/3 + ε, 1) gap. Such statements are proved by combining a long chain of theorems, but I'm just going to focus the part that I worked on, which actually has nothing to do with circuits. Ultimately, it boils down to showing that a certain player has a winning strategy in a game played on graphs called the k-pebble bijective game. Playing this game will be the main focus of the talk.

March 3

Speaker: Ted

Title: Collapsing Catalytic Classes

Time: 4:45 - 6:15pm

Location: SEC 3rd floor common area

Food: Chinese

Abstract: Because of my advisor, people care a lot about catalytic computing now. I’ll talk about the model, and give a short and simple proof that non-determinism is not so useful, with access to someone else’s hard drive.

March 10

Speaker: Louie

Title: Desparsification

Time: 4:30 - 6pm

Location: SEC 3rd floor common area

Food: Indian

Abstract: Correlation clustering is a widely-used approach for clustering large data sets based only on pairwise similarity information. In recent years, there has been a steady stream of better and better classical algorithms for approximating this problem. Meanwhile, another line of research has focused on porting the classical advances to various sublinear algorithm models. Yet, these latter works typically rely on ad-hoc approaches that do not necessarily keep up with advances in improved approximation ratios achieved by classical algorithms. This raises the following natural question: can the gains made by classical algorithms for correlation clustering be ported over to sublinear algorithms in a black-box manner? We answer this question in the affirmative by introducing the paradigm of graph de-sparsification.

March 24

Speaker: Weiyuan

Title: Learning in the quantum world

Time: 4:45- 6:15pm

Location: SEC 3rd floor common area

Food: Chinese

Abstract: Given the quantum nature of our physical world and the remarkable recent advances in quantum information, proposing algorithms and understanding the limitations of learning from quantum data has been an emerging subfield. In this talk, I am going to introduce the setting and motivation for learning properties of quantum states. I will recap some interesting results in the field where we can see how the tools from (learning) theory can be used to analyze the performance of algorithms dealing with quantum data. Finally, I am going to introduce some recent advances in understanding the optimal tradeoffs on the statistical complexity under some restricted settings in near-term quantum labs.

March 31

Speaker: Jake

Title: Testing linear maps via additive combinatorics

Time: 4:30 - 6pm

Location: SEC 3rd floor common area

Food: Dig

Abstract: Given black box access to a function f: \F^n_2 \to \F^m_2, can you efficiently determine whether f is a linear function or far from linear? This is a fundamental problem in TCS known as linearity testing originally considered by Blum, Luby, Rubinfeld. For general m this problem is known to be equivalent to a famous problem in additive combinatorics known as the polynomial Freiman-Ruzsa conjecture in characteristic 2, which was recently settled by Gowers, Green, Manners, Tao. In this talk I'll give a brief introduction to additive combinatorics and use the polynomial Freiman-Ruzsa conjecture to show the linear maps from f: \F^n_2 \to \F^m_2 (developed by Samorodnitsky).

April 7

Speaker: Quynh

Title: Learning Markov random fields

Time: 4:30 - 6pm

Location: SEC 3rd floor common area

Food: Vietnamese

Abstract: A Markov random field (MRF) is a probability distribution on a graph, that has certain conditional independence property (the Markov property). The Hammersley-Clifford theorem states that such MRFs are equivalent to Gibbs distributions. I will describe the proof of this theorem and how to use this Markov property to learn the underlying Hamiltonian corresponding to the Gibbs distribution. If time permits I will describe the quantum version of these concepts.

April 14

Speaker: Yichen

Title: Metric Embeddings into HSTs

Time: 4:30 - 6pm

Location: SEC 3rd floor common area

Food: Chinese

Abstract: Metric embeddings into hierarchically well-separated trees (HSTs) have demonstrate extensive application in approximation algorithms and online algorithms. Offline, the seminal work by Fakcharoenphol, Rao, and Talwar achieves an offline probabilistic embedding of n points with distortion O(log n). However, online embedding turns out to be much harder with an Omega(n) lower bound. I will first recap these results, and then present a simple yet powerful relaxation—allowing distances within the embedding to decrease over time—and show how this approach achieves exponential improvements in distortion, together with motivations and applications for this relaxed embedding model. If time permits, I will briefly talk about dynamic scenario, where the points can both arrive and depart and a bound exists on how many points may appear simultaneously. Finally, I will illustrate how these insights open new avenues for addressing notoriously difficult online problems, such as the k-taxi problem.

April 28

Meeting: Open Problem Session

Time: 4:30 - 6pm

Location: SEC 3rd floor common area

Food: Dig

Abstract: We will be splitting into several groups, each of which will learn about and work on an open problem. The main purpose of the open problem session is to let people get to know each other's research interests. It is totally fine and normal if in the end more new problems are proposed than those that are solved!

Fall 2024

September 9

Meeting: We'll discuss the plans for the semester and have dinner.

Time: 4:30 - 6pm

Food: Dig Inn

Location: SEC Level 3 NW Terrace

September 16

Speaker: Zach

Title: Timing-Private Differential Privacy

Time: 4:30 - 6pm

Location: SEC 3rd floor common area

Food: Tacos

Abstract: I will discuss a model of differential privacy (DP) where both the algorithm's output and runtime are observable to an adversary. I'll present recent results from Ben Dov, David, Naor, and Tzalik (FORC '23), highlighting the conditions under which privacy can be achieved in this model. If time permits, I'll also discuss recent progress on achieving "pure" timing privacy in the unbounded DP model.

September 23

Speaker: Yeongwoo

Title: The Pursuit of Uniqueness

Time: 4:30 - 6pm

Location: SEC 3rd floor common area

Food: Sushi

Abstract: In this talk I'll discuss a result by Valiant and Vazirani, who show that (under randomized reductions), one can reduce NP to the class unique NP, the set of languages which have a unique witness in the YES case. This result has connections to the complexity of approximate counting and in areas such as average case complexity. A natural question is whether the Valiant-Vazirani result can be de-randomized; this has several obstacles, the first being an oracle separation between Unique NP and NP. If time permits, I'll also discuss some interesting recent works on defining quantum versions of these classes, and related results.

September 30

Speaker: Alvan

Title: Monsky's Theorem

Time: 4:30 - 6pm

Location: SEC 3rd floor common area

Food: Sushi

Abstract: In 1965, Fred Richman wrote a problem for the final exam of his graduate class: prove/disprove the existence of odd equidissections of the square. Realizing its difficulty, Richman posted to AMS Monthly, and after five years of failed attempts by geometers, Paul Monsky proved the result in 1970. Today, Monsky's Theorem, and its generalizations, demonstrate the powerful connection between p-adic evaluations, Sperner's Lemma, and Euclidean geometry.

October 7

Speaker: Cassandra

Title: Distinguishing Between Distributions

Time: 4:30 - 6pm

Location: SEC 3rd floor common area

Food: Dig

Abstract: Given a sequence of samples promised to be drawn from one of two distributions X_0, X_1, how many samples (k) are needed to determine which distribution you’re sampling from? This is well-understood from an information-theoretic perspective. However, when moving from information-theoretic bounds to efficient distinguishers, bounding the number of samples needed becomes more complicated. I’ll discuss this problem and highlight new perspectives.

October 21

Meeting: Open Problem Session

Time: 4:30 - 6pm

Location: SEC 3rd floor common area

Food: Indian

October 28

Speaker: Unai Fischer Abaigar (LMU Munich)

Title: Algorithmic Decision-Making in the Public Sector

Time: 4:30 - 6pm

Location: SEC 3rd floor common area

Food: Indian

Abstract: In this talk, I’ll explore the promises and pitfalls of algorithmic decision-making (ADM) in the public sector. I'll discuss types of automation, motivations, and real-world case studies that highlight the challenge of aligning machine learning (ML) models with the complex realities of public sector decision-making.

November 4

Speaker: Jamie

Title: Floating bodies

Time: 4:30 - 6pm

Location: SEC 3rd floor common area

Food: Pizza

Abstract: I will explain what the image below is. I will then state a really cool theorem about it that is not very well-known and more people should know about. As an application, I will present an FPRAS algorithm for optimal cake-cutting.

November 11

Speaker: Dashiell

Title: Knowledge with Errors

Time: 4:30 - 6pm

Location: SEC 3rd floor common area

Food: Indian

Abstract: Given a process representing evolving graphs of knowledge flow with errors, what can we determine about the effect of local error checking? In the special case of trees of knowledge, nice properties of monotonicity allow us to throw out the structure of a graph entirely and instead formulate the problem as the convergence of an operator over a high dimensional space, giving some stronger bounds on when error can be controlled.

November 18

Speaker: Prashanth

Title: The polynomial method

Time: 4:30 - 6pm

Location: SEC 3rd floor common area

Food: Dig

Abstract: I will talk about a method to solve problems such as the following (maybe more or less depending on time): Given L lines in 3-D space, how many joints can they form (where a joint is a point lying on three non-coplanar lines)? Given a collection of polynomials with a common root, is there always one more common root? How many lines do you need to cover all points of a n x n grid of uniformly spaced points, except one point? I will highlight some key facts about polynomials while discussing the solutions to the above problems.

November 25

Speaker: Jake

Title: The Rank and Slice Rank Methods

Time: 4:30 - 6pm

Location: SEC 3rd floor common area

Food: Dig

Abstract: I will introduce two general methods for solving combinatorial problems known as the rank and slice rank methods. As an application I'll discuss the breakthrough of Ellenberg and Gijswit (2017) on the cap-set problem.

December 2

Meeting: Social dinner

Spring 2024

February 1

Speaker: Jamie

Title: Random Spanning Forests of Grids

Time: 4pm - 5:30pm

Location: SEC 3rd floor common area

Food: Pizza

Abstract: I will prove the following theorem: For any fixed constant k, at least a 1/(poly(n)) fraction of the set of k-component spanning forests on an n x n grid graph have exactly equal numbers of vertices in each component (for n divisible by k). I will also explain how this result establishes the first provably polynomial-time algorithm for sampling grid graph partitions from the "spanning tree distribution," a well-studied distribution in the literature on algorithms for political redistricting. I will also briefly discuss extensions to other families of grid-like graphs. Based on the following paper: https://arxiv.org/abs/2310.15152

February 8

Speaker: Juanky

Title: Performative Prediction

Time: 4pm - 5:30pm

Location: SEC 3rd floor common area

Food: Indian

Abstract: When predictions are used to inform decisions, they don't just forecast the future: They actively shape it. This idea has recently been formalized in context of machine learning by PZMH20 through the framework of performative prediction. In this talk, I will give a brief overview of the main ideas and results in this line of work.

February 22

Speaker: Eran

Title: Transformers are better than state space models at copying

Time: 4pm - 5:30pm

Location: SEC 3rd floor common area

Food: Indian

Abstract: Transformers are the dominant architecture for sequence modeling, but there is growing interest in state space models (SSMs) that use a fixed-size latent state that does not depend on the sequence length. We show that while SSMs are promising in terms of inference-time efficiency, they are limited compared to transformer models on tasks that require copying from the input context. We start with a theoretical analysis of the simple task of string copying and prove that a two layer transformer can copy strings of exponential length while SSMs are fundamentally limited by their fixed-size latent state. Empirically, we find that transformers outperform GSSMs in terms of efficiency and generalization on synthetic tasks that require copying the context. Finally, we evaluate pretrained large language models and find that transformer models dramatically outperform state space models at copying and retrieving information from context.

February 29

Speaker: Sahil

Title: Connectivity in Tournaments

Time: 4pm - 5:30pm

Location: SEC 3rd floor common area

Food: Thai

Abstract: I will show the following (perhaps surprising) result: given nothing but the degrees of the vertices in a tournament graph, one can determine whether there is a path from an arbitrary vertex s to an arbitrary vertex t. To do so, I will show that the degree information is sufficient to determine the SCC graph of a tournament.

March 7

Speaker: Ted

Title: The Power of Staring at Yao's Lemma

Time: 4pm - 5:30pm

Location: SEC 3rd floor common area

Food: Chinese

Abstract: Yao's Lemma (the one that relates distinguishers to predictors) implies nice proofs of some classic results (that I found relatively opaque in CS221).

March 21

Speaker: Rana

Title: When to Invest in Predictions for Scheduling

Time: 4pm - 5:30pm

Location: SEC 3rd floor common area

Food: Indian

Abstract: In light of recent work on scheduling with predicted job sizes, we consider the effect of the cost of predictions in queueing systems, removing the assumption in prior research that predictions are external to the system’s resources and/or cost-free. In particular, we introduce a novel approach to utilizing predictions, SkipPredict, designed to address their inherent cost. Rather than uniformly applying predictions to all jobs, we propose a tailored approach that categorizes jobs based on their prediction requirements. We examine the effect of this cost for two distinct models. In the external cost model, predictions are generated by some external method without impacting job service times but incur a cost. In the server time cost model, predictions themselves require server processing time, and are scheduled on the same server as the jobs.

March 28

Speaker: Cassandra

Title: Finding the root in random growing trees

Time: 4pm - 5:30pm

Location: SEC 3rd floor common area

Food: Dig Inn

Abstract: Suppose one person starts a rumor, which is slowly communicated to many individuals in a population. At each time step, a new person hears the rumor from somebody who has already heard the rumor. Suppose you have access to the communication network for the rumor (“who talked to who” as undirected edges) after T people have heard the rumor, but have no further information (e.g. you don’t know when each person joined the communication network). Can you detect who started the rumor? More precisely, can you return a short list (independent of the size T of the network, but dependent on the error probability) that includes the person who started the rumor with high probability as T goes to infinity?

This is the type of question that is addressed in papers studying root-finding in randomly growing trees. In this talk, I will introduce the problem of root-finding and present upper and lower bounds on the list size for uniform attachment trees and preferential attachment trees (as well as corresponding proofs). Most of the talk will be based on the paper “Finding Adam in random growing trees” by Bubeck, Devroye, and Lugosi.

April 11

Meeting: Open Problem Session

Time: 4:30pm - 6pm

Location: SEC 3rd floor common area

Food: Indian

April 18

Speaker: Louie

Title: Random Contractions

Time: 4pm - 5:30pm

Location: SEC 3rd floor common area

Food: Indian

Abstract: Karger first introduced the notion of random contractions in a seminal 1993 paper for computing minimum cuts in RNC, and ever since it has been an important staple in algorithm design. We will re-derive this method in graphs, seeing how it can be used to compute minimum cuts and more generally, counting bounds for the number of small cuts in any graph. If time permits, we will see how this yields cut-sparsifiers for graphs as well as certain linear algebraic generalizations of the contraction procedure for error-correcting codes.

April 25

Speaker: Elbert

Title: Debiasing Functions of Private Statistics in Postprocessing

Time: 4pm - 5:30pm

Location: SEC 3rd floor common area

Food: Chinese

Abstract: In this work we will introduce the deconvolution method used for unbiased estimation in the statistical literature and adapt it to be used for differential privacy. Additionally, we will apply this method to derive unbiased estimators of polynomials when the noise is drawn from a Laplace distribution, a novel result. Finally, we present an idea for which a small modification may generalize to unbiased estimation for all continuous functions with bounded domain.

Fall 2023

September 14

Speaker: Prashanth

Title: Low-degree testing over grids

Time: 4pm - 5:30pm

Location: Level 3 NW Terrace for food and 3rd floor common area for talk.

Food: Honeygrow

Abstract: I will talk about a very fast algorithm to test if a given black-box is a low-degree polynomial. I will introduce the low-degree testing problem as it has been classically studied and talk about a generalization of it. I will also discuss a lower bound on the number of queries one needs to make to the black-box.

September 21

Speaker: Sahil

Title: Graph streaming: Minimum FAS on tournaments

Time: 4:30pm - 6pm

Location: Level 3 NW Terrace for food and 3rd floor common area for talk.

Food: Indian

Abstract: I will discuss approximation algorithms for the minimum feedback arc set (FAS) problem on tournaments in the streaming setting. I will start by introducing the streaming model, after which I will explain the simple 5-approximation single-pass algorithm given by https://cse.buffalo.edu/faculty/atri/papers/algos/FAS-journal-final.pdf. I will then discuss a (1+\eps)-approximation single-pass algorithm given by https://arxiv.org/pdf/2105.08215.pdf, with the trade-off of exponential time. Finally, if time permits, I will introduce some of the multi-pass algorithms and lower bounds.

September 28

Speaker: Pranay

Title: Private High-Dimensional Statistics

Time: 4:30pm - 6pm

Location: SEC 3rd floor common area

Food: Indian

Abstract: In this talk, I will survey one recent line of work on differentially private (DP) high-dimensional statistics. Focusing on the problem of high-dimensional mean estimation under pure DP, I will present and analyze some of the basic algorithmic techniques that arise in the literature, such as the "clip-and-noise" framework, private histograms, and outlier-robust estimators. Time permitting, we will also touch on the topic of private and robust covariance estimation under stronger distributional assumptions (https://arxiv.org/abs/2212.08018).

October 5

Speaker: Cassandra

Title: Combinative Cumulative Knowledge Processes

Time: 4pm - 5:30pm

Location: SEC 3rd floor common area

Food: Thai

Abstract: Societal knowledge accumulation is a complex process in which new units of knowledge are generated from old units of knowledge by applying reasoning. Without checking mechanisms in place, errors in societal knowledge can result in the development of future erroneous knowledge and slow-downs in the knowledge accumulation process. In this talk, I will present results regarding when and how errors can be eliminated in networks of knowledge accumulation, as well as impossibility results about when errors cannot be eliminated (https://arxiv.org/abs/2309.05638).

October 12

Speaker: Elbert

Title: Private Probit Regression

Time: 4pm - 5:30pm

Location: SEC 3rd floor common area

Food: Sushi

Abstract: Probit Regression is a parametric form of regression in which the dependent variable is assumed to be a function of the independent variables and gaussian noise. We take advantage of this assumption to show that in the same model, adding gaussian noise for privacy results in a computable likelihood function which we can optimize to obtain good asymptotic results. In this talk, I will compare this result to existing results in the synthetic data regime and general private optimization.

October 19

Meeting: Open Problem Session

Time: 4pm - 5:30pm

Location: SEC 3rd floor common area

Food: Moldovan

About: We will be splitting into several groups, each of which will learn about and work on an open problem. The main purpose of the open problem session is to let people get to know each other's research interests. We stress the importance of having a friendly and respectful environment, and it is totally fine and normal if in the end more new problems are proposed than those that are solved!

October 26

Speaker: David

Title: Evolutionary graph theory

Time: 4pm - 5:30pm

Location: SEC 3rd floor common area

Food: Thai

Abstract: Evolution occurs in populations of reproducing individuals. The structure of a population can affect evolutionary trajectories. Evolutionary graph theory is a framework for modeling evolutionary dynamics with population structure. In this framework, individuals occupy vertices and edges denote possible interactions. During this survey talk, I will discuss key quantities in evolutionary dynamics such as fixation probability and fixation time, describe how certain graph families affect these quantities, and classify the computational complexity of approximating such quantities in various scenarios.

November 2

Speaker: Sid Devic (USC)

Title: Regularization and Optimal Multiclass Learning

Time: 4pm - 5:30pm

Location: SEC 3rd floor common area

Food: Indian

Abstract: Joint with Julian Asilis, Shaddin Dughmi, Vatsal Sharan, and Shang-Hua Teng. The quintessential learning algorithm of empirical risk minimization (ERM) is known to fail in various settings for which uniform convergence does not characterize learning. It is therefore unsurprising that the practice of machine learning is rife with considerably richer algorithmic techniques for successfully controlling model capacity. Perhaps the most notable such technique is "regularization," which trades off empirical risk with some measure of hypothesis complexity, though the term is applied liberally to a variety of explicit and implicit approaches with similar effect. Nevertheless, no such algorithmic technique or principle has broken away from the pack to characterize optimal learning in these more general settings.

The purpose of this work is to precisely characterize the role of regularization in perhaps the simplest setting for which ERM fails: multiclass learning with arbitrary label sets. Using one-inclusion graphs (OIGs), we exhibit optimal learning algorithms that dovetail with tried-and-true algorithmic principles: Occam's Razor as embodied by structural risk minimization (SRM), the principle of maximum entropy, and Bayesian reasoning. Most notably, we introduce an optimal learner which relaxes structural risk minimization on two dimensions: it allows the regularization function to be "local" to datapoints, and uses an unsupervised learning stage to learn this regularizer at the outset. We justify these relaxations by showing that they are necessary: removing either dimension fails to yield a near-optimal learner. We also extract from OIGs a combinatorial sequence we term the Hall complexity, which is the first to characterize a problem's transductive error rate exactly.

Lastly, we introduce a generalization of OIGs and the transductive learning setting to the agnostic case, where we show that optimal orientations of Hamming graphs --- judged using nodes' outdegrees minus a system of node-dependent credits --- characterize optimal learners exactly. We demonstrate that an agnostic version of the Hall complexity again characterizes error rates exactly, and exhibit an optimal learner using maximum entropy programs.

November 9

Speaker: Louie

Title: Code Sparsification

Time: 4pm - 5:30pm

Location: SEC 3rd floor common area

Food: Tacos

Abstract: We introduce a notion of code sparsification that generalizes the notion of cut sparsification in graphs. For a (linear) code $\mathcal{C} \subseteq \mathbb{F}_q^n$ of dimension $k$ a $(1 \pm \epsilon)$-sparsification of size $s$ is given by a weighted set $S \subseteq [n]$ with $|S| \leq s$ such that for every codeword $c \in \mathcal{C}$ the projection $c|_S$ of $c$ to the set $S$ has (weighted) hamming weight which is a $(1 \pm \epsilon)$ approximation of the hamming weight of $c$. We show that for every code there exists a $(1 \pm \epsilon)$-sparsification of size $s = \widetilde{O}(k \log (q) / \epsilon^2)$. This immediately implies known results on graph and hypergraph cut sparsification up to polylogarithmic factors (with a simple unified proof).

One application of our result is near-linear size sparsifiers for constraint satisfaction problems (CSPs) over $\mathbb{F}_p$-valued variables whose unsatisfying assignments can be expressed as the zeros of a linear equation modulo a prime $p$. Building on this, we obtain a complete characterization of ternary Boolean CSPs that admit near-linear size sparsification. Finally, by connections between the eigenvalues of the Laplacians of Cayley graphs over $\mathbb{F}_2^k$ to the weights of codewords, we also give the first proof of the existence of spectral Cayley graph sparsifiers over $\mathbb{F}_2^k$ by Cayley graphs, i.e., where we sparsify the set of generators to nearly-optimal size.

November 16

Speaker: Jessie

Title: An introduction to property elicitation for supervised machine learning

Time: 4pm - 5:30pm

Location: SEC 3rd floor common area

Food: Pizza

Abstract: We often use machine learning algorithms to make predictions about some outcome distribution. Realistically, though, we often can't learn an entire (nonparametric) outcome distribution, nor do we want to. Instead, we focus on the choice of certain summary statistics, such as the mean, median, variance, etc. We can learn these statistics by using a smarter choice of loss function. This talk will motivate why we use some of our favorite losses, develop some geometric intuition for thinking about these summary statistics, and introduce some cool (IMHO) open problems involving how to learn various statistics.

November 30

Speaker: Jake

Title: Triangles and Equations

Time: 4pm - 5:30pm

Location: SEC 3rd floor common area

Food: Sushi

Abstract: In an attempt to prove Fermat's Last Theorem (FLT), mathematicians tried reducing it to the finite field setting. In 1909 Dickson proved this is impossible by showing FLT is false over finite fields using a tedious combinatorial and number theoretic argument. In 1916, Schur gave a much simpler combinatorial proof. Showing that this seemingly number theoretic problem is actually a combinatorial problem in disguise. The goal of this talk is to cover Schur's proof and introduce the connection between extremal graph theory and additive combinatorics.

December 7

Speaker: Quynh

Title: Quantum NP

Time: 4pm - 5:30pm

Location: SEC 3rd floor common area

Food: Vietnamese

Abstract: I will describe the canonical quantum generalization of NP: Quantum Merlin-Arthur (QMA) and Alexei Kitaev’s proof of the QMA-completeness of quantum constraint satisfaction problem (QCSP), also known in condensed matter physics as the local Hamiltonian ground state problem. If there is interest and time permits, I will describe 4 other reasonable quantum generalizations of NP, and where people think these 5 quantum NP classes lie (relative to each other) in the complexity landscape.

Spring 2023

January 26

Meeting: We'll discuss the plans for the semester and have dinner.

Time: 5:30 - 7pm

Food: Thai

Location: SEC Level 3 NW Terrace

February 2

Speaker: Jamie

Title: Pseudorandom Graphs for Logical Adversaries

Time: 5:30 - 7pm

Location: SEC Level 3 NW Terrace

Food: Pizza

Abstract: I will present my recent work (with Jan Dreier at TU Wien) on explicitly constructing graphs (and hypergraphs) that are pseudorandom in the sense that they are indistinguishable from Erdős–Rényi graphs by testing for properties that are expressible in a primitive logic. For first order logic, this amounts to constructing existentially-closed graphs, a notoriously difficult problem from graph theory. I will explain what these graphs are, mention some interesting open questions about them, and briefly describe our new technique based on existing theorems in the derandomization literature. I will then talk about how to implement such constructions for hypergraphs by applying simple transformations of random graphs, where these transformations must themselves be definable in a primitive logic as well. This amounts to an interesting analog of pseudorandom generators that becomes equivalent to the standard model in cryptography when we consider an extension of first order logic called fixed point logic with parity.

February 13

Speaker: Prayaag

Title: Fitting ellipsoids to random points

Time: 4:30 - 6pm

Location: SEC Level 3 NW Terrace

Food: Pizza

Abstract: Given independent standard Gaussian points $v_1, \ldots, v_n$ in dimension $d$, for what values of $(n, d)$ does there exist with high probability an origin-symmetric ellipsoid that simultaneously passes through all of the points? This basic problem of fitting an ellipsoid to random points has connections to low-rank matrix decompositions, independent component analysis, and principal component analysis. Based on strong numerical evidence, it is conjectured that the ellipsoid fitting problem transitions from feasible to infeasible as the number of points $n$ increases, with a sharp threshold at $n \sim d^2/4$. In this talk, I will discuss recent progress on this conjecture based on joint work with Aaron Potechin, Paxton Turner and Alex Wein.

February 21

Speaker: Yeongwoo

Title: Max Cut and Hardness of Approximation

Time: 4:30 - 6pm

Location: SEC Level 3 NW Terrace

Food: Ethiopian

Abstract: I'll be talking about a series of works which showed that the Goemans-Williamson algorithm for Max-Cut is in fact the optimal algorithm under the Unique Games Conjecture. This will include a discussion on the GW algorithm itself, integrality gaps, and the result of Khot-Kindler-Mossel-O'Donnell which establishes the matching hardness results. If there is time, I'll also introduce the Quantum variant of Max-Cut as well as my collaborators' and my result on its hardness.

February 27

Speaker: Yihui

Title: The true hardness of quantum error mitigation

Time: 4:30 - 6pm

Location: SEC Room 1.412

Food: Thai

Abstract: Quantum error mitigation has been proposed as a `near-term’ surrogate to quantum error correction. Requiring no or few additional quantum resources, the premise of quantum error mitigation is that you can remove quantum noise from the result of a calculation using only classical post-processing. Algorithms for this are being intensely developed as we speak, but there are heuristic signs that they don’t scale, often requiring exorbitant sample complexities. We put these observations on solid theoretical ground by constructing rapidly mixing quantum circuits that show that exponential-in-system-size sample complexities are needed for error mitigation. Our results imply that, while improvements in quantum hardware will push noise levels down, if error mitigation is used for certain near-term applications, ultimately this can only lead to an exponential time algorithm with a better exponent when compared with classical algorithms, putting up a strong obstruction to the hope for exponential quantum speedups in this setting.

March 6

Speaker: Zach

Title: Techniques for private resource allocation

Time: 4:30 - 6pm

Location: SEC Room 1.412

Food: Tacos

Abstract: I will discuss a cryptographic primitive called a private resource allocator (PRA). PRAs can allocate resources to a set of clients without revealing to those clients whether anyone else received a share of the resources. I'll show some constructions of PRAs that provide guarantees ranging from information-theoretic to differential privacy, and discuss how they can be used to prevent a new class of attacks that we call allocation-based side-channel attacks. These attacks can be used, for example, to break the privacy guarantees of anonymous messaging systems that were designed specifically to defend against side-channels and traffic analysis. This was joint work with Sebastian Angel and Sampath Kannan.

March 20

Speaker: Ted

Title: Making Sense of Directed Graphs

Time: 4:30 - 6pm

Location: SEC Level 3 NW Terrace

Food: Chinese

Abstract: An undirected graph looks like this: [1 -1 \\ -1 1]. A directed graph looks like this: [1 0 \\ -1 0]. Even worse, the symmetrization of a directed graph can look like this: [1 -1/2 \\ -1/2 0]. I'll discuss why the third matrix is bad, and a surprising reduction (that forms a key component of the exciting line of work on the "directed Laplacian paradigm") that allows us to avoid it.

March 27

Meeting: Open Problem Session

Time: 4:30 - 6pm

Location: SEC Level 3 NW Terrace

Food: Dig Inn

April 3

Speakers: Jonathan Shi (UCSD) and Juspreet

Title: Sum-of-Squares Thermodynamics I: Spherical Spin Glasses.

Time: 4:30 - 6pm

Location: SEC Level 3 NW Terrace

Food: Sushi

Abstract: “Casual” talk on recent work [dSS23, In Submission] that gives a (non-standard) Semi-Definite Optimization algorithm for computing the maximum of random low-degree polynomials on the sphere. We will mainly spend time introducing the problem and discussing the semi-definite program (and interpreting it) in the context of how it “embeds” a key mathematical object (with delicate probabilistic and geometric structure) in the mathematical theory developed to study these objects.

April 17

Speaker: Wei-Kai Lin (NEU)

Title: Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation

Time: 4:30 - 6pm

Location: SEC Level 3 NW Terrace

Food: Thai

Abstract: Can we design a private variant of "Google search" that would enable users to search the Internet privately without revealing their queries to Google? Fully homomorphic encryption gives a solution to this problem, where users would send their search queries to Google encrypted in a way that allows Google to compute the encrypted search results, without learning anything about the query itself. However, this solution would require Google to run a huge computation that touches the entire content of the Internet to answer each encrypted search query, making it realistically infeasible! Is there a way for Google to preprocess the Internet content into a special data structure that would allow it to answer any encrypted query efficiently by only accessing some small number of locations in the data structure? We give a solution to this problem as a special case of our work.

Concretely, we construct the first schemes for "doubly efficient private information retrieval" and "fully homomorphic encryption in the RAM model" under standard cryptographic hardness assumptions (Ring Learning with Errors). Previously we only had heuristic candidate constructions that only satisfied relaxed variants of these primitives. Our new solutions combine tools from cryptography together with data structures for fast polynomial evaluation (Kedlaya and Umans '08).

Joint work with Ethan Mook and Daniel Wichs.

April 24

Speaker: Sidhant Saraogi (Georgetown)

Title: The evolving landscape of Range Avoidance

Time: 4:30 - 6pm

Location: SEC Level 3 NW Terrace

Food: Indian

Abstract: Range Avoidance (AVOID) is a total search problem where, given a Boolean circuit C:{0, 1}^n -> {0,1}^m (m > n), the task is to find a y in {0, 1}^m outside the range of C. In the first part of my talk, I will try to motivate the problem which can be used to solve explicit construction problems, for e.g. finding functions of high circuit complexity. I will also try to survey the various positive and negative results on this problem over the last couple of years.

In the second part of the talk, I will talk about a special case of AVOID, NC0-AVOID, where each output bit of C depends on only a constant number of input bits. We will see what kind of explicit construction problems can be reduced to solving NC0-AVOID and also see some algorithms for NC0-AVOID (albeit for easier stretch m).

Based on work with Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje.

May 1

Thesis defense: Chi-Ning Chou

Title: The Computational Lens: from Quantum Physics to Neuroscience

Time: 3:30 - 5pm

Location: SEC 1.413

Fall 2022

September 8

Speaker: Chi-Ning

Title: Are Matrices the Same as Vectors? Spencer's Theorem and Matrix Spencer Conjecture

Time: 5:30 - 7pm

Food: Indian

Location: SEC Level 3 NW Terrace for food and 3rd floor common area for talk.

Abstract: Spencer's theorem is a classic result in discrepancy theory where a cute existential proof (using entropy argument!) beats the probabilistic method. However, the same idea doesn't extend to the "matrix" version of Spencer's theorem (which is in a "vector" setting) and whether one can still beat the probabilistic method in the matrix case is then know as the "Matrix Spencer Conjecture".

In this talk, I will first talk about Spencer's theorem: its setup, its motivations, and the cute proof using entropy. In the second half of the talk, I'll talk about several recent progresses on proving Matrix Spencer Conjecture and my personal thought on it. Basic familiarity with discrete probability should be a sufficient background to follow the talk.

September 15

Speaker: Juspreet

Title: Random Max-CSPs inherit Algorithmic Hardness from Mixed Spin Glasses

Time: 5:30 - 7pm

Food: Thai

Location: SEC Level 3 NW Terrace for food and 3rd floor common area for talk.

Abstract: In this brief talk, we will give a story-like overview of a recent result (and some ongoing work) where we:

1) [Result 1] Connect any random Max-CSP to a corresponding "Spin Glass".

2) [Result 2] Show that the support of the distribution of "overlaps" of solutions are the same for both objects. Correspondingly, all families of algorithms that are "stable under noise" are obstructed on typical instances of many Max-CSPs.

3) [WIP] Obstruct a powerful family of algorithms called 'low-degree polynomials' on typical instances of many Max-CSPs using global hypercontractivity and martingales.

September 22

Speaker: Chin Ho

Title: The total influence of k-CNFs

Time: 5:30 - 7pm

Location: SEC Level 3 NW Terrace

Food: Pakistani

Abstract: I will introduce the important concept of total influence of a Boolean function, and give a simple randomized algorithm for SAT. Then I will show how it leads to a short proof that shows every width-w DNF has total influence at most w.

September 29

Speaker: Kai

Title: Regret bound in restless (state-dependent) multi-armed bandits

Time: 5:30 - 7pm

Location: SEC Level 3 NW Terrace

Food: Malaysian

Abstract: Upper confidence bound (UCB) style algorithm is commonly used in proving regret bounds in multi-armed bandits. One important assumption is that we can find the optimal arm (or combination) to pull within the confidence bounds. However, when arms' reward and transitions depend on the states, finding the optimal arms is computationally intractable. I will talk about how this computation issue affects the regret analysis in state-dependent multi-armed bandits, including comparison of UCB algorithms with Thompson sampling algorithms, frequentist regret v.s. Bayesian regret, and how Lagrangian relaxation can be used in state-dependent multi-armed bandits.

October 6

Meeting: Open Problem Session

Time: 5:30 - 7pm

Location: SEC Level 3 NW Terrace

Food: Indian

About: We will be splitting into 2 or 3 groups, each of which will learn about and work on an open problem related to theory/ML theory/EconCS. The main purpose of the open problem session is to let people get to know each other's research interests. We stress the importance of having a friendly and respectful environment, and it is totally fine and normal if in the end more new problems are proposed than those that are solved! We can discuss more logistics from 5:30 to 6 pm today.

October 13

Speaker: Jamie

Title: Descriptive Complexity

Time: 5:30 - 7pm

Location: SEC Level 3 NW Terrace

Food: Pizza

Abstract: I will give a gentle introduction to descriptive complexity theory, which measures complexity not by the resources required by a Turing machine to solve a given problem, but by the logical operators needed to formally define the problem. The theory gives a very interesting alternative perspective on what computation is, and illuminates some subtle distinctions that ordinary complexity theory is too coarse to capture. I'll introduce a handful of well-studied logics and talk about what resources they represent from a computational perspective, and how it is possible prove lower bounds against them. I'll explain two of the biggest results in descriptive complexity, namely, Fagin's Theorem and the Cai-Furer-Immerman construction. Finally, I'll discuss what is arguably the most important open problem: finding a logic that exactly captures polynomial time over unordered structures.

October 27

Speaker: Prashanth

Title: Recent progress on the VP vs VNP problem

Time: 5:30 - 7pm

Location: SEC 1.402

Food: Indian

Abstract: Is every polynomial that is easy to describe also easy to compute? I will begin this talk by giving a brief introduction to algebraic complexity theory and the VP vs VNP problem. Then we will discuss a recent result that gives superpolynomial lower bounds against constant-depth algebraic circuits (FOCS '21 best paper). This is analogous to the AC^0 lower bound of Hastad, but the proof approach is quite different (and simpler!). I will first present the lower bound for a toy model of depth-3 circuits and then make some modifications to get lower bounds for depth-5 (or in fact, any constant-depth) circuits. Link to the paper: https://eccc.weizmann.ac.il/report/2021/081/revision/1/download/

November 3

Speaker: Cassandra

Title: Testing properties of distributions

Time: 5:30 - 7pm

Location: SEC Level 3 NW Terrace

Food: Tacos

Abstract: Distribution testing is an area of research at the intersection of statistics and theoretical computer science that is concerned with testing properties of distributions using a small number of samples. Many applications today rely on a huge amount of data that is supported over a large domain. This motivates the design of sample-efficient algorithms to test specific properties of distributions, since standard algorithms from learning theory or statistics may be too costly in this setting. An example of a specific property someone may want to test is if their data is uniformly distributed.

In this talk, I will first introduce distribution testing, including the model, its relationship to learning, and how it compares to the general property testing framework. After this, I will introduce an algorithm for testing equality to the uniform distribution. I will present a proof that the uniform distribution is complete with respect to testing equality to a fixed distribution, which gives sample complexity bounds for testing equality to any fixed distribution. This talk includes content from Chapter 11 of “Introduction to Property Testing” by Goldreich.

November 10

Speaker: Jake

Title: Multicolor Ramsey Numbers for Double Stars

Time: 5:30 - 7pm

Location: SEC Level 3 NW Terrace

Food: Mediterranean

Abstract: The core idea of Ramsey theory is that complete disorder is impossible. Given a large structure, no matter how complex it is, we can always find a smaller substructure that has some sort of order. Despite active research for decades, very little is known about Ramsey numbers of graphs. This is especially true for when the number of colors is at least 3, also known as multicolor Ramsey numbers. In this talk, I will introduce Ramsey theory and discuss some classic results. I'll present a simple proof from one of my papers where we determine the k-color Ramsey number for the double star graph S(n,m) when n is sufficiently large compared to m,k and k is odd.

November 17

Speaker: Noah Singer

Title: A tale of two streaming CSPs

Time: 5:30 - 7pm

Location: SEC 1.402

Food: Chinese

Abstract: I’ll discuss recent progress on understanding the space complexity of approximating constraint satisfaction problems (CSPs) in various streaming models through the lens of the two simplest CSPs, Max-CUT and Max-DICUT.

I’ll first walk through several prior results in the setting of o(sqrt n)-space algorithms with worst-case input ordering. First, for Max-CUT, I’ll show how natural streaming-to-communication reductions rule out all nontrivial approximations (Kapralov-Khanna-Sudan’15). On the other hand, for Max-DICUT, I’ll discuss a quantity called “total bias”, which can be measured using well-known “norm sketching” algorithms in O(log n) space, and in turn yields a provably optimal 4/9-approximation algorithm (Chou-Golovnev-Velusamy’20, with subsequent simplifications). This highlights the difference between Max-CUT’s inherent “symmetry”, which makes it amenable to strong hardness results, and Max-DICUT’s “asymmetry”, which leaves room for interesting algorithms.

Finally, we’ll think about extending hardness results beyond the above setting. I’ll argue that, in comparison to Max-CUT, the proof of the Max-DICUT lower bound is seemingly “brittle”, and I’ll sketch how our recent works confirm this by giving improved approximations for Max-DICUT when either (i) the input stream is randomly ordered or (ii) we’re given slightly more than o(sqrt n) space.

Based on joint works with Joanna Boyland, Michael Hwang, Tarun Prasad, Raghuvansh R. Saxena, Madhu Sudan, and Santhoshini Velusamy.

November 21

Title: Open problem session

Time: 5:30 - 7pm

Location: SEC Level 3 NW Terrace

Food: Japanese

November 29

Speaker: Miryam Mi-Ying Huang

Title: Public verifiability in the quantum setting

Time: 5:45 - 7:15pm

Location: SEC Level 3 NW Terrace

Food: Thai

Abstract: In this talk, I will discuss some theoretical interests of public variability by starting with a classical toy example, called delivery man problem. Then, I will transform the delivery man problem into a quantum message transmission problem and then discuss the difficulty of doing this in the quantum world. Finally, I will present a cryptographic primitive Auditable Quantum Authentication (AQA) to deal with the quantum-version delivery man problem.

December 1

Speaker: David

Title: Derandomization using Random Strings

Time: 5:45 - 7:15pm

Location: SEC Level 3 NW Terrace

Food: Vegan

Abstract: Many algorithms use randomness. The process of showing that a problem with a fast randomized algorithm has a fast deterministic algorithm is a type of "derandomization": a complete reduction of its randomness complexity without noticeably disturbing its time complexity. Results of this flavor are satisfying for various philosophical reasons. Attempts to derandomize broad classes of problems typically start by cleverly constructing some deterministic object that acts like a random object under a smaller probability distribution. In this TGINF talk, I will present a derandomization result from Buhrman et. al (2005) and Allender et. al (2006) that uses "pseudorandom" objects but makes no reference to a distribution. In particular, the proof exploits different meanings of the term "random": something that happens by chance versus something without a concise theory.

December 8

Speaker: Aaron Berger

Title: What's so great about triangle removal?

Time: 5:30 - 7pm

Location: SEC Level 3 NW Terrace

Food: Indian

Abstract: Triangles hate him! Mathematician reveals one weird trick to remove all triangles from graphs that didn't even have many triangles to begin with. In this talk I'll discuss graph regularity and the triangle removal lemma, two foundational results in the field of analytic combinatorics. We'll see some cool applications (property testing, 3-term arithmetic progressions, counting triangle-free graphs) time permitting. Rudimentary knowledge of graph theory encouraged. Epsilons and deltas will be provided free of charge.

December 15

Meeting: TCS Trivia Night

Time: 5:30 - 7pm

Location: SEC Level 3 NW Terrace

Food: Thai

Previous semesters

Information about talks from previous semesters can be found on the previous TGINF website.

Page updated

Google Sites

Report abuse