Harvard TGINF
Theory Graduate students and INdian Food (TGINF) is a seminar at Harvard with a focus on theoretical aspects of computer science. As the name suggests, there will only be theory grad students/postdocs and Indian food in TGINF. Well... recently there are some other types of food but nothing beyond. The seminar currently takes place on every Thursday at 4:00pm-5:30pm ET with free food provided. Please add this to your calendar and email Cassandra at cmarcussen@g.harvard.edu if you want to join in the mailing list!
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
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!
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
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!
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.