Arithmetic circuits give us a model of computation that captures algebraic methods and allows us to use, and even extend tools, developed in Maths. A major reason for studying them also comes from the added algebraic structure in this model compared to their Boolean counterparts. In this talk, we will discuss some results where we are able to reduce the depth required for arithmetic circuits(even to depth3). We will mainly focus on a classic result (Valiant, Skyum, Berkowitz, Rackoff83) that for a degree d polynomial that can be computed by a size s circuit, gives a depth O(log d) arithmetic circuit of size poly(sd).

Imagine a store that wants to sell a set of goods to a set of agents. Each agent has a budget they can spend, and a utility function over the goods. When they enter the store, they will attempt to buy the bundle of goods within their budget that maximizes their utility. Are there prices the store can assign to each good so that the sum of the goods demanded by the agents exactly equals the supply of goods that the store has available? When such a set of prices does exist, they are said to induce equilibrium in the market. In this talk, I will give an introduction to General Equilibrium Theory, going over some classic results about existence of equilibrium prices. I will also discuss why the field is important to both economists and computer scientists, and its implications for the field of fair division.

Secure multiparty computation (MPC) is a subfield of cryptography. I will discuss the MPC protocol by Beaver, Micali, and Rogaway [BMR90]. For simplicity, we will focus on the two-party case. At the same time, we will show that the secure evaluation of an arbitrary function f can be reduced to the secure evaluation of degree-3 polynomials. This idea is generalized by Ishai and Kushilevitz, who refer to it as "randomizing polynomials" [IK00]. No prior knowledge of cryptography is required. (P.S. We do TSS at the end of a long day of hard work, so my goal is to make this as easy as possible for both the audience and myself.)

In this talk, we will look at a relatively new algorithmic framework based on continuous optimization and regularization for discrepancy minimization introduced by Pesenti and Vladu. I will outline their simple and elegant techniques and recover the classic Spencer's theorem.

In this talk, I will talk about the influence of coalitions. At a high level, the influence of a coalition on a particular voting rule is the probability that the coalition can force the outcome of an election to their desired outcome by manipulating their votes. There is naturally a tradeoff between the coalition’s size and its influence, and we will focus on this. I'll discuss what is known, about this problem, and highlight a work of Bourgain, Kahn, and Kalai of 2014 which studies the influence of linear sized coalitions on random CNFs. I'll conclude by stating some interesting open questions and the relationship between this problem and a problem that I am working on in projections. If this abstract sounds familiar, it might be because I gave a TSS on a famous lower bound (KKL) for the influence of \emph{individuals} last year.

In this talk, we will discuss the recent greedy approach for determining the rank of matrices whose entries are linear polynomials in commutative and non-commutative models, and further generalize this method to partially commutative setting. This approach forms the key idea used in [Ivanyos, Qiao, Subrahmanyam 2016] (for non-commutative rank computation), [Blaser, Jindal, Pandey 2017], [Bhargava, Blaser, Jindal, Pandey 2018] (for commutative rank approximation), and [Arvind, Chatterjee, Mukhopadhyay 2024] (for partially commutative rank computation).

I will do a recap on DP then I will introduce the factorization mechanism with some example algorithms.

Tensors, or equivalently multilinear forms have intimate relations to central problems in computer science and combinatorics. The complexity of matrix multiplication is captured by the rank of the matrix multiplication tensor. In arithmetic complexity, proving super-linear lower bounds for tensors is related to proving lower bounds for arithmetic circuits and formulas. A different notion of rank, analytic rank, was introduced by Gowers and Wolf in the context of higher-order Fourier analysis. In this talk we use this concept to prove the common roots of order-d tensors on a common input are always positively correlated.

Traditional analyses of differentially private gradient descent assume that each iteration of gradient descent publicly releases intermediate configurations, causing privacy cost to scale linearly with the number of iterations. We present an older work of Feldman, Mironov, Talwar, and Thakurta (2018) that, through a Renyi-DP analysis, shows that only outputting the final configuration (of model weights, regression parameters, etc.), we can obtain sub-linear privacy cost for gradient descent. If time permits, we may discuss work that builds on this result showing that under certain conditions, privacy costs converge even with an unbounded number of training iterations.

Private information retrieval (PIR) protocols, a cryptographic model defined by Chor, Goldreich, Kushilevitz, and Sudan at FOCS 1995, allows a client to retrieve an element from a database held by multiple servers, without revealing the index of the retrieved item. Over the last three decades, PIR protocols have been extensively studied, and many constructions, variants, and applications of PIR protocols were presented. In this talk I will discuss simple constructions of PIR protocols and connections between PIR protocols and other cryptographic primitives.

In this paper, we construct Error-Correcting Graph Codes. An error-correcting graph code of distance δ is a family C of graphs on a common vertex set of size n, such that if we start with any graph in C, we would have to modify the neighborhoods of at least δn vertices in order to obtain some other graph in C. This is a natural graph generalization of the standard Hamming distance error-correcting codes for binary strings. Yohananov and Yaakobi were the first to construct codes in this metric, constructing good codes for δ less than 1/2, and optimal codes for a large-alphabet analogue. We extend their work by showing a.) Combinatorial results determining the optimal rate vs. distance trade-off nonconstructively. b.) Graph code analogues of Reed-Solomon codes and code concatenation, leading to positive distance codes for all rates and positive rate codes for all distances. c.) Graph code analogues of dual-BCH codes, yielding large codes with distance δ = 1 − o(1). This gives an explicit “graph code of Ramsey graphs”.

We present an auction algorithm using multiplicative instead of constant weight updates to compute a (1-ε)-approximate maximum weight matching (MWM) in a bipartite graph with n vertices and m edges in time O(mε^{-1}), beating the running time of the fastest known approximation algorithm of Duan and Pettie [JACM '14] that runs in O(mε^{-1}\log ε^{-1}). Our algorithm is very simple and it can be extended to give a dynamic data structure that maintains a (1-ε)-approximate maximum weight matching under (1) one-sided vertex deletions (with incident edges) and (2) one-sided vertex insertions (with incident edges sorted by weight) to the other side. The total time used is O(mε^{-1}), where m is the sum of the number of initially existing and inserted edges.

Given a dataset of points in a metric space and a query point q, the nearest neighbour search (NNS) problem asks us to preprocess the dataset in a way that allows us to return a dataset point that is closest to q, as quickly as possible. NNS is a fundamental problem in computational geometry that finds countless applications in many areas, including databases, computer vision, and machine learning. In this talk, we will discuss the groundbreaking work of Indyk and Motwani (STOC 1998), who constructed efficient data structures for an approximate version of NNS over certain high-dimensional metric spaces, thereby making considerable progress towards removing the infamous “curse of dimensionality”. The main tool employed is locality-sensitive hashing, which is also of independent interest and has received significant attention over the years.

The backtracking line-search is an effective technique to automatically tune the step-size in smooth optimization. It guarantees similar performance to using the theoretically optimal step-size. Many approaches have been developed to instead tune per-coordinate step-sizes, also known as diagonal preconditioners, but none of the existing methods are provably competitive with the optimal per-coordinate stepsizes. We propose multidimensional backtracking, an extension of the backtracking line-search to find good diagonal preconditioners for smooth convex problems. Our key insight is that the gradient with respect to the step-sizes, also known as hypergradients, yields separating hyperplanes that let us search for good preconditioners using cutting-plane methods. As black-box cutting-plane approaches like the ellipsoid method are computationally prohibitive, we develop an efficient algorithm tailored to our setting. Multidimensional backtracking is provably competitive with the best diagonal preconditioner and requires no manual tuning.

Influence is an important topic in Boolean Function Analysis. Informally speaking, if f is a function with n boolean inputs, the influence of the ith input is the probability that if you randomly assign the other inputs, f is not yet determined (i.e., input i determines the output of f). In this talk, I’ll give an overview of influence and cover the seminal KKL theorem. In the proofs, we will see some key techniques in Boolean Function Analysis, such as Fourier Analysis and Hypercontractivity.

In the first part of the talk, we will show some intuitions on how to approach to a graph colouring problem using the probabilistic method. In the second part of the talk, we will briefly introduce the idea behind the Rodl nibble and see an application to proving the chromatic number of graphs with girth at least five. The original result was given by Kim J.H. in 1995. Here we present a version based on Chapter 12 of Molloy and Reed's book "Graph Colouring and the Probabilistic Method". No prior knowledge is assumed.

Connections between hardness and derandomization have been an area of great interest in Complexity theory. Polynomial Identity testing(PIT) is the problem of testing if an input arithmetic circuit computes the zero polynomial or not, and is known to be in coRP. In this talk, I will present a result by Kabanets and Impagliazzo, where they show that giving a deterministic polynomial time algorithm for PIT of poly-sized circuits will imply either permanent cannot be computed by low-degree poly-sized arithmetic circuits or NEXP is not contained in P/poly.

A family of [m] -> [n] mappings H is called "t-independent" if when the function h : [m] -> [n] is sampled from H uniformly at random, for any distinct x_1, x_2, ..., x_t in [m], we have that h(x_1), h(x_2), ..., h(x_t) are independent and uniform random variables in [n]. t-independent hash functions have applications in derandomization, complexity theory, randomized algorithms, etc. The construction of such objects with near optimal size is known where n is a prime power; remarkably, few constructions are known for arbitrary n. We provide constructions of such families with near optimal size for arbitrary parameters m, n and t. In contrast to previous results, our construction also yields a poly-time algorithm to build these objects.

I'll be giving a tutorial on word circuits, which are analogous to the standard circuit model except that the bandwidth of each edge is very large. This is an intriguing computational model that so far has defied attempts at concrete lower bounds. We'll see existential lower bounds, universal upper bounds, and consequences of super-constant lower bounds for an explicit function. If we have time, we'll take a brief look at the best-known explicit lower bound on word circuits: a function that requires at least 4 non-input gates to compute.

Spectral sparsification for directed Eulerian graphs is a key component in the design of fast algorithms for solving directed Laplacian linear systems. While spectral sparsification is well understood for undirected graphs and it is known that (1 + ε)-sparsifiers with O(nε^(−2) ) edges exist [BSS'09], the state-of-the-art Eulerian digraph sparsifier [CGPSSW'18] is still far from the theoretical optimal. In this talk, we will introduce a relatively new technique of leveraging matrix discrepancy theory for spectral sparsification. Specifically, I will start by recovering the optimal undirected graph sparsifers due to the work of Jambulapati, Reis and Tian'23 and gradually build towards better Eulerian sparsifiers using a recent advancement in matrix discrepancy by Bansal, Jiang and Meka'23. This talk is based on a joint work with Sachdeva and Thudi.

Quantum algorithms have shown promise to offer significant speedups on their classical counterparts for a growing number of problems. However, many of the most common classical algorithmic frameworks do not have direct quantum equivalents, making the development of new quantum algorithms more challenging. In this talk, we will be presenting a new, simpler approach to the famous Grover's algorithm for unstructured search based on a classical divide and conquer framework. We will further demonstrate that this method allows us to develop a broader category of quantum divide and conquer algorithms, with at minimum quadratic speedup over their classical counterparts.

Communication complexity is a central model in computational complexity theory, and sheds light on the relative power of various computational resources, such as randomness, quantum entanglement etc. A variety of techniques have been developed to prove lower bounds in communication complexity. I will overview the model of quantum communication complexity and Sherstov's pattern matrix method for proving lower bounds in quantum communication complexity (https://arxiv.org/abs/0906.4291). Some knowledge of Fourier analysis of Boolean functions will be assumed.

Abstract: In this talk, I will discuss coupling proofs of differential privacy for a particular limited program model. In particular, we will show that the power of the model can be completely captured through coupling proofs of privacy. After a quick introduction to/review of probabilistic couplings, approximate liftings, and how they connect to differential privacy, I will demonstrate how to build up a program model through the lens of regular languages. Viewing this program model as a regular language allows us to easily build tools that can automatically decide whether or not a given program is differentially private using probabilistic couplings.

In this work we investigate unbiased high-dimensional mean estimators in differential privacy. We give algorithms that compute the optimal covariance for the Gaussian noise for a given domain K under suitable assumptions, and prove a number of nice geometric properties of the optimal error. We also show that Gaussian noise mechanisms achieve nearly optimal error among all private unbiased mean estimation mechanisms in a very strong sense. We extend this result to local differential privacy, and to approximate differential privacy. I will be doing a 20min conference-style talk (so I will not cover proofs) and I would like to get feedbacks from audiences.

A k-bounded min register holds an integer value between 0 and k-1 inclusive, initially holding k-1. A minWrite(v) operation on the register updates the value to v if v is smaller than the current value of the register, whereas a minRead() operation retrieves the current value of the min register. In this talk we will discuss existing wait-free implementations of min registers in the literature and improvements to these implementations that Faith Ellen and I made in the past year. I will provide sketches of proofs of correctness and complexity analysis, and present some open questions.

Approximate agreement is a variant of consensus in which processes receive input values from a domain and must output values in that domain that are sufficiently close to one another. We study the problem when the input domain is the vertex set of a connected graph. In asynchronous systems where processes communicate using shared registers, there are wait-free approximate agreement algorithms when the graph is a path or a tree, but not when the graph is a cycle of length at least 4. For many graphs, it is unknown whether a wait-free solution for approximate agreement exists. We introduce a set of impossibility conditions and prove that approximate agreement on graphs satisfying these conditions cannot be solved in a wait-free manner. In particular, the graphs of all triangulated d-dimensional spheres that are not cliques, satisfy these conditions. The vertices and edges of an octahedron is an example of such a graph. We also present a family of reductions from approximate agreement on one graph to another graph. This allows us to extend known impossibility results to even more graphs.

In distributed computing, the notion of extension-based proofs classifies the proof technique in which one demonstrates the impossibility of solving a task in a wait-free manner by constructing an infinite execution. One such example is the famous impossibility proof of the consensus task. In recent years, it was shown that there are tasks with known impossibility results, where the proof of such results are out of reach by any extension-based proof. In a previous talk, using a combinatorial argument, I demonstrated the impossibility of solving approximate agreement on graphs that satisfies certain "impossibility conditions". We will continue our discussion on approximate agreement tasks and show that there is no extension-based impossibility proof of solving approximate agreement on any connected graph.

A b-frugal coloring of a graph is a proper coloring where no color appears more than b times in any neighborhood. The concept was first introduced by Hind, Molloy, and Reed in 1997. For a general graph with a maximum degree D, Molloy and Reed (2009) showed that there exists an O(log D / log log D)-frugal coloring using D+1 colors. The girth of a graph is the length of the shortest cycle in the graph. Kim (1995) proved that for any graph with girth at least five, its chromatic number is upper-bounded by (1 + o(1)) D / ln D. A natural question to ask is whether there exists an O(log D)-frugal coloring of graphs with girth at least five using (1 + o(1)) D / ln D colors. In this talk, I will demonstrate how to use the semi-random method, together with the Lovász Local Lemma, Talagrand's inequality, etc., to prove the existence of an O(log^2 D)-frugal coloring. The proof is an extension of Kim's proof as presented in the graph coloring book by Molloy and Reed.

In this talk, we give a brief introduction to one of the most important methods for bounding stochastic processes: chaining. We will derive a few fundamental results in chaining, including Dudley's bound, the generic chaining bound, and the majorizing measure theorem for Gaussian processes.

Have you ever said to yourself: "Cauchy Schwarz is perfect right now if only the inequality went the other way"? Well, in-fact it can! In this talk we will work through the conditions in which a Cauchy converse exists and its derivation. We follow an excerpt from The Cauchy Schwarz Master Class by Steele.

Given a graph, how long does it take to decompose this graph into a collection of short cycles? While a almost linear time(m^{1 + o(1)}) solution is known, it is open as to if this problem has a near linear time(m\polylog{m}) solution. In this talk, I will give a description of the relatively simple combinatorial algorithm that achieves almost linear time, talk about the classes of problem that are known to solve the short cycle decomposition if solved, as well as give a brief overview of the various uses of this subroutine.

Concentration of measure states that in many instances, a random variable will take on a value close to its mean with high probability. It has become an important tool used in probability and theoretical computer science. Levy's Lemma describes concentration of measure for the uniform spherical measure, and has become important for applications of the probabilistic method in quantum information theory. We will state and prove Levy's lemma, and use Levy's lemma to show the existence of highly entangled subspaces of large dimension.

Last month Hunter released a preprint which gives a construction for 3-AP-free sets. This represents the first improvement in the highest-order term of the lower bound since Behrend in 1946. In this seminar I'll present the elegant construction of Behrend as well as a different way of looking at Behrend's construction by Green and Wolf. I'll then show what needs to be changed to get the improvement shown by Hunter and, if time permits, discuss some of the details of the new paper.

A map f:{0,1}^n -> {0,1}^n has locality t if every output bit of f depends only on t input bits. We call an expander a Local Expander if it is a bounded-degree expander graph on 2^n nodes such that maps of constant locality can compute the neighbors of a node. I will discuss the results in [Viola Wigderson 18], where the authors explicitly construct such graphs with locality "one"! They also give a construction of 3-regular bipartite Ramanujan Graphs with constant locality. After these, I will talk about the construction of [Batra Saxena Shringi 23], which gives construction for bipartite Ramanujan graphs of degree q+1 with constant locality, for any prime power q.

One goal of TSS is to help people understand classic papers in theoretical computer science. Yao's millionaires' problem was introduced in 1982. The problem discusses that two millionaires want to figure out who is richer without revealing the exact amount of money they have. The problem is generalized to the problem of secure two-party computation. Two parties, Alice and Bob, want to jointly compute a function $f$, but they do not want to leak their private input or any information other than the final result to the other party. [Yao '86] presented a constant-round protocol for securely computing any two-party functionality. The protocol is secure against semi-honest adversaries and is based on a cryptography primitive called oblivious transfer (OT). This talk will be based on [Lindell-Pinkas '06'], a well-written paper that gives a clear explanation and proof of the garbled circuit.

Fair Division problems look at how to fairly divide a set of items among many agents with different utility functions. This involves defining formal notions of what it means for an allocation to be 'Fair', and designing algorithms that allocate the items in a way that meets these notions. This talk will explore the model of Temporal Fair Division, where items from a set are allocated in batches over a number of days. In this model, fairness properties are not only concerned about the total allocation over the set of items being fair, but are also concerned about the fairness of the partial allocations of items at any point in time. This talk will look at the possibilities, impossibilities, and open questions in the Temporal Fair Division model.

I will describe 3 well-known string searching algorithms: Knuth-Morris-Pratt algorithm, Aho-Corasick algorithm and Manacher's Algorithm. The KMP algorithm is the first linear time algorithm for searching a pattern string in a text string, and the AC algorithm is an extension of the KMP algorithm for the case where there are multiple pattern strings. Manacher's algorithm is a very elegant linear time algorithm for finding the longest palindromic substring.

I will talk about some error correcting code constructions obtained by evaluating polynomials. I'll show a variant of the classic Reed Muller codes and proof some properties about the code. Along the way I'll prove a slight generalization of the Schwartz-Zippel lemma, and a slight generalization of GMD decoding.

In the committee selection problem, we are given n voters who have ranked preferences over m candidates, and we want to select a committee of k candidates. One goal in the literature is to identify representative committees, where as many voters (and groups of voters) as possible are represented by the committee. In this talk, we will discuss a representation axiom called (local) stability and its probabilistic generalization termed stable lotteries [Aziz et al. 2017, Cheng et al. 2020]. Our goal is to prove the existence of stable lotteries for ranked preferences using von Neumann's minimax theorem, which is a result of Cheng, Jiang, Munagala, and Wang (EC'19).

Suppose that we have n agents and n items which lie in a shared metric space. We would like to match the agents to items such that the total distance from agents to their matched items is as small as possible. However, instead of having direct access to distances in the metric, we only have each agent’s ranking of the items in order of distance. Given this limited information, what is the minimum possible worst-case approximation ratio (known as the distortion) that a matching mechanism can guarantee? I’ll show why a simple mechanism like Serial Dictatorship gets exponential distortion and then go over the proof of Anari et al. to show how we can achieve O(n^2) distortion with a deterministic mechanism.

This work explores the connection between classical isoperimetric inequalities, their directed analogues, and monotonicity testing. We study the setting of real-valued functions $f : [0,1]^d \to \mathbb{R}$ on the solid unit cube, where the goal is to test with respect to the $L^p$ distance. Our goals are twofold: to further understand the relationship between classical and directed isoperimetry, and to give a monotonicity tester with sublinear query complexity in this setting. Our main results are 1) an $L^2$ monotonicity tester for $M$-Lipschitz functions with query complexity $\widetilde O(\sqrt{d} M^2 / \epsilon^2)$ and, behind this result, 2) the directed Poincaré inequality $\mathsf{dist}^{\mathsf{mono}}_2(f)^2 \le C\, \mathbb{E}[|\nabla^- f|^2]$, where the "directed gradient" operator $\nabla^-$ measures the local violations of monotonicity of $f$. To prove the second result, we introduce a partial differential equation (PDE), the directed heat equation, which takes a one-dimensional function $f$ into a monotone function $f^*$ over time and enjoys many desirable analytic properties. We obtain the directed Poincaré inequality by combining convergence aspects of this PDE with the theory of optimal transport. Crucially for our conceptual motivation, this proof is in complete analogy with the mathematical physics perspective on the classical Poincaré inequality, namely as characterizing the convergence of the standard heat equation toward equilibrium.

Spectral sparsification for directed Eulerian graphs is a key component in the design of fast algorithms for solving directed Laplacian linear systems [Peng-Song'22]. In this talk, we give a brief overview of new techniques and advancements for this question. In particular, we consider (1) leveraging matrix discrepancy theory for better sparsity, (2) bypassing specific graph structures (short cycles) using electrical circulations, and (3) regulating circulations using effective resistance partitioning introduced by [Alev-Anari-Lau-Oveis Gharan'18]. This talk is based on works with Jambulapati, Sachdeva, Sidford, Thudi, and Tian.

Private Information Retrieval (PIR) was first introduced in 1998. In a r-server PIR, we have n bits of data a = (a1,..., an) such that it's replicated among the servers. The goal for the user is to retrieve the i-th bit of data without revealing i to the servers. We want to minimize the communication cost which is the worst case number of bits transferred between the user and the servers in the protocol. One generation of designing such schemes is through using matching vector codes. There are several works which use matching vector codes to design PIR schemes. I am going to explain Efremenko's work for designing such a scheme.

The query model of computation is cartoonishly simple, making it much easier to reason about compared to other models of computation. At the same time the query model has been very significant. 1) It gives us insight into the relative powers of computational tools such as nondeterminism, randomness and more. 2) Certain approaches to computational tasks can naturally be phrased as query tasks. 3)The study of query complexity has helped us better understand the representations of functions by polynomials. In this talk I will give an introduction to query complexity touching on the above points. This will include a result about the optimality of gradient descent which was joint work with Ankit Garg, Robin Kothari and Praneeth Netrapalli.

The Exactly-N problem in the number-on-forehead setting asks k players, who can individually see all but one of the inputs, if the inputs add to N. In their paper first studying this problem, Chandra, Furst, and Lipton showed a deep connection between protocols for Exactly-N and the construction of large sets with no length-k arithmetic progressions (denoted k-AP-free sets). Their proof is existential and does not construct an explicit protocol. Linial, Pitassi, and Shraibman gave an explicit protocol for the case of k=3 that matches Behrend's construction of large 3-AP-free sets. In this work, we give an explicit protocol for k>3 that matches the asymptotic behavior of Rankin's construction of large k-AP-free sets, which generalizes Behrend's construction. This is ongoing work with Lianna Hambardzumyan, Toniann Pitassi, Suhail Sherif, and Adi Shraibman.

We say a mechanism is unbiased if it on average outputs the correct answer to the query. I will show our recent work on lower bounds on error of unbiased mechanisms. We build lower bounds in higher dimensions based on lower bounds in 1 dimension, and we use a HCR bound to obtain 1 dimensional lower bounds.

A symmetric matrix is called a Laplacian if it has nonpositive off-diagonal entries and zero row sums. Since the seminal work of Spielman and Teng (2004) on solving Laplacian linear systems in nearly linear time, several algorithms have been designed for the task. Yet, the work of Kyng and Sachdeva (2016) remains the simplest and most practical sequential solver. They presented a solver purely based on random sampling and without graph-theoretic constructions such as low-stretch trees and sparsifiers. In this work, we extend the result of Kyng and Sachdeva to a simple parallel Laplacian solver using the ideas of block Cholesky factorization from Kyng, Lee, Peng, Sachdeva, and Spielman (2016). Our proof is simple and based on standard matrix concentration inequalities.

For the allocation of goods, the state-of-the-art method provides two compelling guarantees: a fairness axiom (envy-freeness up to one item) and an efficiency axiom (Pareto optimality). For the allocation of chores, however, it has been a long-standing open problem whether such a division always exists. We answer this question affirmatively for the class of bivalued utilities, where each agent partitions the chores into easy and difficult ones, and has cost p > 1 for chores that are difficult for her and cost 1 for chores that are easy for her. Such an allocation can be found in polynomial time using an algorithm based on the Fisher market. This talk is based on a work with Dominik Peters and Nisarg Shah. (https://arxiv.org/abs/2110.11285)

For a matrix A of dimensions mxn, the discrepancy of A is disc(A) = \min_{\chi \in {+1, -1}^{n}}|A\chi|_{\infty}. disc(A) is a well studied property with a variety of applications e.g. additive approximations to bin packing, communication complexity, and rounding. The discrepancy of a matrix can be bounded below by what is known as the determinant lower bound. A classical result of Lovasz, Spencer, and Vesztergombi showed a constant lower bound on the ratio between discrepancy and the determinant lower bound. Matousek considered the upper bound and was able to show that the ratio is not more than O(sqrt(log n)log(mn)) though this was not believed to be tight. Recently, Jiang and Ries were able to show that the ratio is no more than O(sqrt(log nlog(mn))) which is tight when m is poly(n). This will serve as the introduction to the talk next week where we will consider examples which show that the bound is tight when m >> n.

For a matrix A of dimensions mxn, the discrepancy of A is disc(A) = \min_{\chi \in {+1, -1}^{n}}|A\chi|_{\infty}. disc(A) is a well studied property with a variety of applications e.g. additive approximations to bin packing, communication complexity, and rounding. The discrepancy of a matrix can be bounded below by what is known as the determinant lower bound. A classical result of Lovasz, Spencer, and Vesztergombi showed a constant lower bound on the ratio between discrepancy and the determinant lower bound. Matousek considered the upper bound and was able to show that the ratio is not more than O(sqrt(log n)log(mn)) though this was not believed to be tight. Recently, Jiang and Ries were able to show that the ratio is no more than O(sqrt(log nlog(mn))) which is tight when m is poly(n). This will serve as the introduction to the talk next week where we will consider examples which show that the bound is tight when m >> n.

I recently was part of a work that had applications in proof complexity. I had a lot of fun learning about the field, seeing as it (a) was full of fun and interesting puzzles for a theoretical computer scientist, and (b) had fascinating connections with various models of computation. In this talk, I will give an introduction to proof complexity more focused on what I as a novice find fun about proof complexity. If there's enough time I hope to lead up to the recent result that was joint work with Arkadev Chattopadhyay, Nikhil Mande and Swagato Sanyal.

In this talk, I will introduce the theory of balanced incomplete block designs (BIBDs). I'll show some of their basic properties, demonstrate an elegant construction through finite projective and affine planes, and use them to study three seemingly unrelated problems, one about a family card game, one about projection sizes of partitions of the unit square, and one about secure secret sharing. No prior knowledge about combinatorial designs is required.

We consider the $0$-$1$ Integer Programming problem, where we are given a collection of linear inequalities (with integer coefficients) on $n$ variables and the question is to check if there is a Boolean assignment to the variables that satisfies all of them. This problem generalizes the CNF-SAT problem since each clause of a CNF formula can be easily translated into a constraint of the above form. We will discuss a randomized algorithm that runs in time $2^{n - n/O(\log n)}$ when the coefficients in the linear constraints are allowed to be exponentially large I.e., in the range $[-2^{\poly(n)},2^{\poly(n)}]$. This matches the running time of the best CNF-SAT algorithm (due to Schuler (Journal of Algorithms, 2005)) in this range of parameters. If time permits, we will also see a derandomization of this algorithm. Our algorithm is obtained by a reduction to the Orthogonal Vectors problem, which has been studied extensively. The reduction is obtained via a simple $1$-sided error MA communication complexity protocol for any linear threshold function. In this talk, we will focus mainly on the description of this simple protocol. We also observe that any $2$-sided error MA protocol (and hence in particular $2$-sided error randomized communication complexity protocol) can be converted into a $1$-sided error MA protocol with only a slight degradation of parameters. In principle, this idea could be useful in obtaining satisfiability algorithms for more general classes of constraints. This is joint work with Srikanth Srinivasan from 2018. The independent work of Timothy Chan (SoCG 2017) implies the main result as well.

Three years ago Hao Huang proved the sensitivity conjecture with a very simple linear algebraic argument. A year later Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao and Avishay Tal delved into the linear algebraic argument and proved many other implications of it, the one most interesting to me being that for any total Boolean function f approx-degree(f) ≥ Ω(√degree(f)). It is a quite elementary proof taking advantage of intuitive linear algebraic manipulations. This is what I intend to present in the talk.

In this talk, I will present random graphs, highlighting a classic result of Erdos and Renyi known as the giant component threshold. The result says that if a graph is sampled by including each edge independently with probability $c/n$, if $c > 1$, a.a.s. there is a giant component of size \Theta(n), and if c < 1, a.a.s. largest component is of size \Theta(\log n). I will also talk about random graphs with fixed degree sequences, how to sample such graphs, some of their properties, and outline a giant component threshold in this model, which Molloy and Reed found in 1995.

When an agent votes, she typically ranks the set of available alternatives. Occasionally, she may also wish to report the intensity of her preferences by indicating adjacent pairs of alternatives in her ranking between which her preference is acutely decisive; for instance, she may suggest that she likes alternative "a" more than "b", but "b" much more than "c". We design near-optimal voting rules which aggregate such preference rankings with intensities using the recently-popular distortion framework. We also show that traditional voting rules, which aggregate preference rankings while ignoring (or not eliciting) intensities, can incur significant welfare loss. This is based on a work with Anson Kahng and Nisarg Shah that appeared in AAAI 23.

In this talk I'll first introduce Bernoulli Factories and then sketch the edge sampling algorithm.

Sortition is a form of democracy built on random selection of representatives. Two of the key arguments in favor of sortition are representation (a random panel reflects the composition of the population) and fairness (everyone has a chance to participate). Uniformly random selection is perfectly fair, but is it representative? To answer this question, we introduce the notion of a representation metric on the space of individuals, and assume that the cost of an individual for a panel is determined by the q-th closest representative. We identify cases where uniformly random selection is also representative in addition to being fair, and in other cases, design a new random selection algorithm that sheds light on the tradeoff between representation and fairness. This is based on joint work with Gregory Kehne, Evi Micha, Ariel D. Procaccia, and Nisarg Shah, published at NeurIPS’22. Link: https://openreview.net/forum?id=l7aekTjF6CO

I will show a lower bound on error for Unbiased ADP Mechanisms which is close to upper bound. We used dimension reduction, HCR bound, and properties of the Gamma-p function we defined to obtain this bound. I will define the Gamma-p function and prove properties of it.

Reconstruction is the problem where given black-box access to a polynomial (its evaluations), we have to construct an explicit arithmetic circuit computing the polynomial. In this talk, I will present a recent result, in Sinha 22, giving efficient reconstruction of depth-3 arithmetic circuits $\Sigma\Pi\Sigma$ with the restriction where the top fan-in is 2. I intend to give a brief insight into several algebraic and geometric techniques that are used in the proof.

The semi-random graph process is an example of an adaptive process for constructing a graph in which random edges are added step by step. It is adaptive in that there is an online algorithm which has partial control over which random edges are added. Through intelligent decision-making, the objective of the algorithm is to force the graph to satisfy a fixed graph property with high probability in as few rounds as possible. We first provide upper and lower bounds on the performance of an optimal algorithm when the property corresponds to being Hamiltonian or to containing a perfect matching. This part of the talk is based on joint works with Pawel Pralat and Jane Gao. Afterwards, we introduce a formal definition of an adaptive random graph process which generalizes both the semi-random graph process, as well as the Achlioptas process. In this model, we define a condition called edge-replaceability which we prove is sufficient for a property to have a sharp threshold. Intuitively, a propertyhas a sharp threshold if the optimal algorithm's ``success probability'' transitions from almost $0$ to almost $1$ in a negligible number of steps. We apply our result to the semi-random graph process to show that the properties of being Hamiltonian and of containing a perfect matching each have a sharp threshold. This part of the talk is based on a joint work with Erlang Surya.

Sampling uniform random spanning trees in a graph is a fundamental problem in computer science and statistical science that dates back to 1847. It has various applications in network design and has recently found its way to fast algorithm design, including the travelling salesman problem and graph sparsifications. In this talk, we will discuss two different approaches, namely random walks and determinantal point processes (DPPs), that independently achieved the recent breakthrough of nearly linear time samplers. Specifically, we will present Wilson's cycle-popping random walks algorithm and the Transfer Current Theorem that connects sampling random spanning trees to DPPs.

Couplings are a powerful tool for analyzing random processes. In this talk, I will give a brief overview of probabilistic couplings and some interesting properties they have. I will also present approximate liftings, a generalization of couplings that is particularly useful for proving that programs are differentially private. Using approximate liftings, I will reprove the standard composition theorem of differential privacy and also show that the Sparse Vector Technique algorithm is epsilon-DP.

In 2021, this was the title of Alweiss, Liu, and Sawhney's STOC best student paper. We will describe the problem, their elegant solution, and an alternate proof-of-correctness using subgaussian random variables. Hopefully, this presentation will inspire within the audience a glimmer of hope that problems which stump the likes of Bansal have clean resolutions and that their next best student paper is only a simple algorithm and slightly tricky analysis away (?).

We will discuss a classical construction of a pseudo-random generator which fools two-party communication protocols, due to Impagliazzo, Nisan and Wigderson from 1994. This construction relies on the explicit construction of spectral expander graphs. We will discuss these as well as introduce the theory of unconditional pseudorandomness - no prior background will be assumed.

In this talk, I will first introduce the idea behind the probabilistic method, which was pioneered by Erdős in the 1940’s. I will mention the most useful tool in the probabilistic method --- Lovász Local Lemma and give one short example to see how it is applied. Then I will present the Entropy Compression technique, which was introduced by Moser in his Master’s thesis in 2009, and the technique gained a lot of popularity in the past few years in giving existence proofs. We will focus on the basic example of k-SAT to see how entropy compression is applied.

In this talk, I will be looking at the classic cake-cutting problem in an online setting. This is equivalent to the problem of allocating cake with the minimal number of cuts. I will be covering content introduced in a paper by Toby Walsh from 2011 and other related papers that followed. I will look at some notions of fairness and a simple impossibility result in the online setting. Following this, we shall discuss relaxing the notions of fairness, and look at a few simple algorithms, their complexity and their limitations, and verify which notions of fairness are satisfied by which algorithms. There will be no actual cake provided during the talk.

A common issue in designing shared memory algorithms is ABA detection, wherein a process accesses an object twice, observes the same values in both accesses, but the process needs to determine whether the value of the object was modified in the meantime. A natural question is: how much extra space is required to allow processes to detect ABAs in an asynchronous shared memory system? Motivated by this question, Ellen, Gelashvili, Woelfel, and Zhu defined the signal detection problem, which is a restricted version of the ABA detection problem designed to study the information theoretic requirements of detecting ABAs. In the signal detection problem, 1 signaller and n readers communicate with each other using a shared blackboard. Every time a process takes a step, it reads the value of the blackboard and then may or may not change its value. When a reader takes a step, it must determine whether the signaller has taken a step since that reader's last step. The space complexity of a signal detection algorithm is the domain size of the blackboard. In this talk, I will discuss the best known upper and lower bounds on the space complexity of solving signal detection. I will also present a new space complexity lower bound on a restricted version of the signal detection problem in which readers have only finitely many local states.

Large scale graph networks are big enough that they cannot be fit on a single machine, and instead are processed by a cluster of machines. These graphs are also constantly changing, with edges being added and deleted as the network evolves. In this talk, we describe how to efficiently maintain a Minimum Spanning Tree in this model, and show that we can in fact handle many updates to the graph in O(1) communication rounds.

Envy-free allocations are a well studied problem in the area of computational social choice. We consider a variant called envy-free partitions. Here utilities are over other agents and the utility functions are boolean and symmetric. We present a well known result of Steibitz and also some new result on trees.

Based on the recent paper at https://arxiv.org/abs/2203.17207

We'll discuss a gem in the field of discrepancy theory, namely Roth's lower bound for the \(L_2\)-discrepancy for corners.

I will present an overview of my PhD research which focuses on the local model of differential privacy. I will talk about results of ours which demonstrate that, under non-interactive local DP, "approximate factorization" is nearly optimal for answering linear queries - which captures a wide range of common statistical tasks - as well as for agnostic learning. The sample complexity for these tasks is characterized in terms of the well-studied "\(\gamma_2\)-norm". Meanwhile, we introduce a new matrix norm which is shown to characterize realizable learning under non-interactive local DP. I will discuss a result of ours which shows a sample-complexity equivalence between agnostic learning under non-interactive LDP and agnostic learning under the CSQ model of machine learning. Finally, I will discuss a result which shows a sample-complexity equivalence between non-interactive LDP and single-intrusion pan-privacy.

Range searching is a well-studied problem in data structures. In this talk we'll look at lower bounds for range searching in the so-called group model. Specifically, I will present a 2011 paper of Kasper Green Larsen, in which he proves lower bounds for range searching using combinatorial discrepancy. This talk will mostly focus on background: an exposition of the problem and important techniques used in the paper. If time permits, I will present some details of Larsen's lower bound proof.

In this talk I'll give a brief introduction to electrical circuits, and how they can be used to solve max flow, in preparation for the two upcoming theory seminars on this topic. I will give a brief overview on electrical circuits, their relation to Laplacian solvers, and give some intuition as to its relation to random walks and flows in graphs. We will also take a closer look at the work by Christiano, Kelner, Madry, Spielman, Teng, demonstrating how electrical flows can be used to approximate maximum flow in \(\tilde{O}(n^{4/3})\) time in sparse graphs.

In this talk I'll present the Satisfiability Coding Lemma of Ramamohan Paturi, Pavel Pudlak, and Francis Zane. In particular, we'll see the surprising fact that an encoding of satisfying assignment gives rise to fast(ish) algorithms for $k$-SAT, and information about the structure of satisfying assignments of $k$-CNFs. Time permitting, we'll draw connections between coding and related fundamental problems such as finding the smallest equivalent DNF and the structure of prime implicants of $k$-CNFs.

In this talk, we will overview the relationship between property testing of Boolean functions and Fourier expansions of Boolean functions. We apply these notions to develop a theory for hardness of approximation of constraint satisfication problems. This talk will be based on Ryan O'Donnell's textbook in analysis of boolean functions.

An m-catalytic branching program (Girard, Koucky, McKenzie 2015) is a set of m distinct branching programs for f which are permitted to share internal (i.e. non-source non-sink) nodes. While originally introduced as a non-uniform analogue to catalytic space, this also gives a natural notion of amortized non-uniform space complexity for f, namely the smallest value \(\frac{|G|}{m}\) for an m-branching program G for f (Potechin 2017). Potechin (2017) showed that every function f has amortized size \(O(n)\), witnessed by an m-catalytic branching program where \(m = 2^{2^n−1}\). We recreate this result by defining a catalytic algorithm for evaluating polynomials using a large amount of space but \(O(n)\) time. This allows us to balance this with previously known algorithms which are efficient with respect to space at the cost of time (Cook, Mertz 2020, 2021). We show that for any \(\epsilon \geq 2n - 1\) , every function f has an m-catalytic branching program of size \(O_\epsilon(mn)\), where m = \(2^{2^{\epsilon n}}\). We similarly recreate an improved result due to Robere and Zuiddam (2021), and show that for \(d \leq n\) and \(\epsilon \geq 2d−1\), the same result holds for \(m = 2^{\binom{n}{\epsilon d}}\) as long as f is a degree-d polynomial over \(F_2\). We also show that for certain classes of functions, m can be reduced to poly(n) while still maintaining linear or quasi-linear amortized size. In the other direction, we bound the necessary length, and by extension the amortized size, of any permutation branching program for an arbitrary function between 3n and 4n − 4.

The analysis of Boolean functions using their Fourier expansions have become an important tool in theoretical computer science and combinatorics. I will introduce some basic notions in this area, including influences of variables and noise stability. We will apply these notions as well as some basic probabilistic techniques to the analysis of the Condorcet paradox, which is related to voting and computational social choice. This talk will be based on Chapters 1 and 2 from Ryan O'Donnell's textbook on analysis of Boolean functions and no prior knowledge should be necessary.

Let \(X_1, X_2, ...\) be a sequence of independent Rademacher random variables, i.e. \(PP(X_i = 1) = PP(X_i = -1) = 1/2\), and let \(S_n = \sum_{i=1}^{n} X_i\) be their partial sums. Such simple random walks have many applications in CS research. We will present two properties of such walks: (1) a lower-bound on the probability \(PP(\max_{1\leq i\leq n} |S_i| > c\sqrt{n})\) for any constant c (probability that the walk stays within the strip \(\pm c\sqrt{n}\)) and (2) the Arcsine law for \(PP(a \leq L_{2n}/2n \leq b)\) where \(L_{2n} = sup\{m\leq 2n: S_m = 0\}\) (last visit to 0 in the interval 0, ..., 2n).

In this talk, we will marvel at its simplicity and far-reaching consequences.

Pseudorandom generators are a central object in the study of randomized computation, both for derandomization and for cryptography. We will discuss a classic result [Nisan'90] showing the existence of a PRG which is exp(-S)-close to uniform for SPACE(S) machines which uses O(S log n) random bits. We also review some follow-up work [David-Papakonstantinou-Sidiropoulos'10] analyzing Nisan's PRG when multiple passes over the random string are allowed.

I'll be giving an introduction to linear algebra lower bounds on communication complexity. The focus will be on the gamma-2 factorization norm and its uses. If time permits, I will talk a bit about my recent research on restricted versions of gamma-2 and their equivalences to (somewhat) natural communication classes.

ACC0[m] circuits are constant-depth boolean circuits with unbounded-fanin AND, OR and MOD_m gates as well as NOT gates. It was proved in the 1980s that when m is prime, polynomial-size ACC0[m] circuits cannot compute certain symmetric functions (such as MAJORITY). Whether this statement holds for composite m is an open problem; currently the only known lower bounds for general ACC0 circuits are for functions whose complexity is in QuasiNP or higher.

I will present the paper "Smaller ACC0 Circuits for Symmetric Functions" by Chapman and Williams, which proves what the title suggests. More specifically, at any constant depth d the upper bounds are still of the form exp(n^{constant depending on m and d}), but with small enough constants to give examples where ACC0[composite number] circuits are more powerful than ACC0[prime number] circuits. The authors give a conditional lower bound as well.

Lifting theorems are an important class of techniques which can transform functions which are hard for weak computation models into functions which are hard for strong computation models. Starting with Raz and McKenzie (1999), there has been a flurry of work proving query-to-communication lifting theorems, which translate lower bounds on query complexity to lower bounds for the corresponding communication model. In this talk I will present a simplified proof of deterministic query-to-communication lifting. Our proof uses elementary counting together with a novel connection to the sunflower lemma.

"Width-reduction" is a technique that has proven immensely useful in the context of maximum flow [Christiano et al., STOC’11] and, more recently, \(l_p\) regression [Adil et al., SODA’19], in terms of improving the iteration complexity from \(O(m^{1/2})\) to \(O(m^{1/3})\), where m is the number of rows of the design matrix, and where each iteration amounts to a linear system solve. However, a considerable drawback is that these methods require both problem-specific potentials and individually tailored analyses. In this talk, I will talk about our recent result (to appear in NeurIPS'21), which gives the first unified approach to achieving \(m^{1/3}\)-type rates. Notably, our method goes beyond these previously considered problems to more broadly capture quasi-self-concordant losses, a class which has recently generated much interest and includes the well-studied problem of logistic regression, among others. In order to do so, we develop a unified width reduction method for carefully handling these losses based on a more general set of potentials. Additionally, we directly achieve \(m^{1/3}\) - type rates in the constrained setting without the need for any explicit acceleration schemes, thus naturally complementing recent work based on a ball-oracle approach [Carmon et al., NeurIPS’20].

The talk will be accessible to all and I will assume no prior knowledge in the field. It is based on our recent paper: https://arxiv.org/pdf/2107.02432.pdf

The relationship between counting problems (#P problems) and other problems was not known until the discovery of Toda’s theorem, for which Toda received the 1998 Gödel Prize. The theorem states that every problem in the polynomial hierarchy can be solved by a polynomial time algorithm with a #P oracle. I will sketch the proof of the theorem and outline some of its applications. No prior knowledge about #P should be necessary.

The differential equation method was originally used to study continuous time stochastic processes. In the famous KVV online matching algorithm, Karp et al. used the method to analyze a hardness example for their Ranking algorithm. This approach was then formalized by Nick Wormald in the 1990's, and has become a fundamental tool for analyzing discrete time stochastic processes. In this talk, I will go over the method, and use it to analyze a simple greedy algorithm for bipartite matching on G(n,n,p).

A Boolean circuit is a natural syntactic object for computing a function in which we start with our input variables and then compose gates corresponding to basic binary functions (e.g. AND, OR, NOT), in a dag-like fashion until we reach the unique sink, with the value at that sink being computed by the inputs in the natural way. Likewise an arithmetic circuit is similarly defined for computing polynomials, where now our gates compute basic arithmetic primitives (e.g. \(+,\times\)).

The two most important notions of efficiency for circuits is the size, defined as the number of gates in the circuit, and the depth, defined as the longest path from an input to the output sink. For arithmetic circuits we have a third measure, namely the formal degree of the polynomial computed by the circuit (before cancellations). With these notions in hand we get some obvious and natural questions: how related can these quantities be made to be, and can we trade one for the other?

First we go through the basics of depth reduction, where our goal is to make a small size circuit into a low-depth circuit without blowing up the size. We will cover the 1/3-2/3 trick for balancing Boolean formulas, but our main focus will be on arithmetic circuits. We show that a size s arithmetic circuit with formal degree d can be simulated by a size \(poly(s,d)\) depth \(O(\log sd)\) circuit, first shown non-uniformly by [Valiant-Skyum-Berkowitz-Rackoff'83] and later made uniform by [Allender-Jiao-Mahajan-Vinay'98].

Second, we go through the basics of depth compression, where our goal is to get even lower depth in exchange for blowing up the size. We focus on circuits with MOD gates, also known as ACC. We show that any depth d size s ACC circuit can be simulated by a depth 2 circuit—more specifically \(SYM \circ AND\)—of size \(2^{O(log^{O(d)} s}\) for both prime and composite moduli, due to [Allender-Hertrampf'94] and [Chen-Papakonstantinou'14] respectively.

In this talk I will give an introduction to the number-on-forehead communication model. In particular, I will speak about the exactly-N problem which, despite being one of the most basic problems in the model, is not well-understood. I will present an \(O(\sqrt{\log N})\) upper bound for this problem, first shown by Chandra, Furst, and Lipton and later made explicit by Linial, Pitassi, and Shraibman. If time permits, we will also discuss the (very weak) lower bound.

In 1972, Charles Stein, dissatisfied with the existing proof of the Central Limit Theorem, devised an alternative. We discuss his method and compare it to the standard Fourier Analysis approach. Central to this method is a characterization of the standard Gaussian random variable \(Z\) as one which satisfies: \(\mathbb{E}[f'(Z)] = \mathbb{E}[Zf(Z)]\) for all well-behaved functions \(f\) (bounded and smooth). Any other random variable \(Y\) which approximately satisfies this identity is then close to \(Z\) in probability metric. We demonstrate some application of the method as well as its variants --- such as the Method of Exchangeable Pairs --- to various problems as time permits.

We will discuss a Toronto classic from the 80s: that the class SAC1 (aka LogCFL, the class of languages log-space reducible to context-free languages) is closed under complementation. The proof is a beautiful application of the "inductive counting" technique that was initially developed to prove NL = co-NL. No prior background in circuit complexity will be assumed!

In this talk, we will go over all classes of algorithms for optimizing convex functions and will look into the various methods used to accelerate these algorithms. We will work with a geometric intuitive picture of all these algorithms and hope to obtain an understanding of what parameters of the algorithm cause acceleration and how these different methods are connected.

For a data structure implementing some abstract data type, in the cell probe model of computation we measure the performance of the data structure solely by the (amortized) number of cells it reads and writes during updates and queries. By allowing the data structure to perform arbitrary calculations and only charging it for the amount of memory it's required to access, a lower bound in the cell probe model is a lower bound on both time and space in any reasonable model of computation.

On the other hand, the strength of the model makes proving lower bounds quite challenging. A breakthrough result by Fredman and Saks (1989) gave an Omega(logn/loglogn) lower bound on the amortized complexity of either updates or queries for the prefix sum abstract data type, introducing a technique called the chronogram technique which has formed the backbone of most breakthrough cell probe since. In particular, the next work on prefix sum lower bounds came over 15 years later when Pătraşcu and Demaine (2006) showed a (tight) lower bound of Omega(logn), which stood as the frontier until the last five years. In this talk we prove the result of Pătraşcu and Demaine.

In a recent paper, Chen, Valiant, and Valiant introduce a framework for learning problems in the setting where the sampling bias is known. They analyze the performance of a certain subclass of estimators for this model, with interesting connections to the Grothendieck problem.

Following a period of rapid progress on circuit lower bounds, Razborov and Rudich published their famous Natural Proofs barrier. This showed that, under a widely held cryptographic assumption, almost all of the lower bound methods used to obtain known circuit lower bounds cannot be used to prove super-polynomial lower bounds on general circuits. In this talk I will present the natural proofs framework and the proof of this result.

I will talk about my paper "Bounds on the \(QAC^0\) Complexity of Approximating Parity" (https://arxiv.org/abs/2008.07470). The Q stands for "quantum", though I aim to make the talk accessible even without a quantum background.

The study of proof complexity was initiated by Cook and Reckhow in the 1970s as a possible way to resolve the P versus NP problem. In this talk, I will introduce the proof complexity program, and the Resolution proof system. I will then present a proof of Haken's seminal result that the pigeonhole principle requires exponential length refutations in Resolution. The presentation will largely be based on the chapter on Resolution in Jukna's "Boolean Function Complexity".

Voting is perhaps the most basic aspect of a well functioning society. How one aggregates the preferences of the members of a group into a single decision has been a fundamental issue to human society for millenia. Today many countries use voting at all levels of their society. It can be used to pick political leaders at various levels of government. Members of admission and hiring committees use it to decide which candidates advance to subsequent rounds. Even mundane tasks like deciding what a group should have for dinner often come down to a vote. How one aggregates, or even elicits, the often conflicting preferences of the members of society is thus critical to how that society functions. Thus it should be clear who designs these preference aggregation procedures can greatly influence the direction of society. Furthermore, how the members of society decide to interact with the procedures can cause far reaching and often unintended outcomes. In this work we will examine voting, and its impacts on society, through the view of both the members of society who have their preferences aggregated and the actors who decide how they are aggregated. What sets this work aside from political science and instead places it in the computer science community is the application of analysis and techniques commonly found in artificial intelligence works. Indeed this work, while written to be broadly approachable and readable for anyone possessing a basic understanding of mathematics, is still a work that is intended for the artificial intelligence researcher. Finally we mention this thesis is a broad look at various topics in voting, and while we go into some depth on each individual topic we stress that entire research careers could be devoted to their individual study. This thesis merely scratches the surface of each of these potential directions.

But really just how difficult is not-too-difficult? Fine-grained complexity is an attempt to stratify the inherent hardness of problems quantitatively, as opposed to say NP-completeness, which "simply" classifies problems according to whether or not they are tractable.

In this elementary talk introducing the Orthogonal Vectors problem, we shall see why one can think of it as the quintessential quadratic-time problem. We do so by describing a host of problems that arise from computational geometry and biology that are related to OV in a very concrete sense, and also by describing its connection to the popular hardness assumption SETH. The equivalences themselves employ interesting tools from communication complexity and locality-sensitive hashing (LSH) families.

Talk primarily based on the work of Chen and Williams (SODA '19).

We show that Cutting Planes proofs are hard to find: Given an unsatisfiable formula \(F\), (1) it is NP-hard to find a CP refutation of \(F\) in time polynomial in the length of the shortest such refutation; and (2) unless Gap-Hitting-Set admits a nontrivial algorithm, one cannot find a tree-like CP refutation of F in time polynomial in the length of the shortest such refutation. The first result extends the recent breakthrough of Atserias and Muller (FOCS 2019) that established an analogous result for Resolution. Our proofs rely on two new lifting theorems: (1) dag-like lifting for gadgets with many output bits; and (2) tree-like lifting that simulates an \(r\)-round protocol with gadgets of query complexity \(O(r)\).

In 2004, Herlihy, Saks, Shavit, and Zaharoglou won the Godel Prize for their application of topology to the theory of distributed computing. In this talk, we will focus on how their techniques from topology can be used to show the impossibility of solving certain problems in distributed systems.

We introduce the Iterated Immediate Snapshot (IIS) model of shared memory, and what it means for an algorithm to solve a task in this model. We define the notions of a simplex and a simplicial complex, both in the abstract sense and in terms of their geometric realization. The link between distributed computing and topology is that computation in the IIS model can be interpreted in terms of simplicial complexes and maps between them. We show that the solvability of a task in the IIS model is equivalent to the existence of a continuous function between topological spaces. This equivalence is then used to prove that in the IIS model there can be no algorithm that solves the consensus task.

The study of the Tree Evaluation Problem (TEP), introduced by S. Cook et al. (TOCT 2012), is a promising approach to separating L from P. Given a label in \([k]\) at each leaf of a complete binary tree and an explicit function in \([k]^2 \rightarrow [k]\) for recursively computing the value of each internal node from its children, the problem is to compute the value at the root node. A simple recursive algorithm can solve this using \(\Theta(h \log k)\) memory, where \(h\) is the tree height and \(k\) is the size of the alphabet. Unitl now, no better deterministic algorithm was known.

We present a new algorithm which uses less memory when \(k\) is not too big compared to \(h\), inspired by a surprising result from Buhrman et al. about "catalytic space" computation (STOC 2012). Ours is the first algorithm to beat the simple recursive algorithm, and also the first non-trivial approach to proving a deterministic upper bound for TEP.

Given a graph G the list coloring number of G, denoted \(\chi_{l}(G)\), generalizes the chromatic number of G first explored by Erdos, Rubin, and Taylor in their 1976 work. We consider list coloring results as related to bipartite graphs. In particular we present a from-the-book proof by Galvin of Dinitz' conjecture having to do with the list chromatic number of the line graph of bipartite graphs and lower bounds on the list chromatic number of bipartite graphs with respect to the minimum degree of G by Alon.

Quantum advantage, also known as quantum supremacy, refers to the idea that a quantum computer can perform a computational task that would otherwise be impossible for classical computers in reasonable time. Providing rigorous proofs that quantum advantage is possible continues to be an active area of research that uses various techniques in mathematics and computational complexity theory. One proposal for a task that could demonstrate quantum advantage is called "boson sampling", which was first proposed by Aaronson and Arkhipov in 2011. I will define "boson sampling" and outline Aaronson and Arkhipov's argument that it could be used to demonstrate quantum advantage. Prior exposure to quantum computing will be helpful but should not be necessary to understand the talk.

Stochastic probing is an area of optimization in which the algorithms are given imperfect probabilistic information regarding the inputs they execute on. In the context of graphs, the edges are unknown to the algorithm. Instead, the algorithm is only aware of the various probabilities for which the edges exist. A probing algorithm is then allowed to query or probe a limited number of edges, thus determining their status. Using this restricted information, the probing algorithm then attempts to optimize some combinatorial parameter.

We consider the stochastic rewards problem; that is, the one sided bipartite matching problem where the probing algorithm is passed a bipartite graph with various edge probabilities between its offline and online partite sets. We consider the case when each online node can make at most one probe, and no limitation is placed on the offline nodes. In this setting, a primal-dual LP based analysis can be used to show that a simple deterministic probing algorithm yields a competitive ratio of \(1-1/e\), provided the online nodes arrive in a uniformly at random order. As a corollary, we get a competitive ratio of \(1-1/e)\ for the simple greedy algorithm in the classical (non-stochastic) random order model of bipartite matching.

Nesterov's accelerated gradient descent has very little geometric interpretation and there is not much intuitive understanding. This is a new method for unconstrained optimization of a smooth and strongly convex function, which attains the optimal rate of convergence of Nesterov's accelerated gradient descent. The new algorithm has a simple geometric interpretation, loosely inspired by the ellipsoid method.

In the standard model of voting, it is assumed that a voting rule observes the ranked preferences of each individual over a set of alternatives and makes a collective decision. In practice, however, not every individual votes. Is it possible to make a good collective decision for a group given the preferences of only a few of its members? We propose a framework in which we are given the ranked preferences of k out of n individuals sampled from a distribution, and the goal is to predict what a given voting rule would output if applied on the underlying preferences of all n individuals. We focus on the family of positional scoring rules, derive a strong negative result when the underlying preferences can be arbitrary, and discover interesting phenomena when they are generated from a known distribution.

We prove a Chernoff-like large deviation bound on the sum of non-independent random variables that have the following dependence structure. The variables \(Y_1,\ldots,Y_r\) are arbitrary Boolean functions of independent random variables \(X_1,\ldots,X_m\), modulo a restriction that every \(X_i\) influences at most k of the variables \(Y_1,\ldots,Y_r\).

I will give a seminar on local differential privacy, with a survey of techniques for proving sample complexity lower bounds against this model. This will include connections to information theory and communication complexity.

Complete subgraphs, not contained in any other, or cliques, define an intuitive notion of maximal connectedness within portions of a graph. Finding the locally-largest, or maximal, clique is an \(\mathsf{NP}\)-hard problem. I will discuss a branch-and-bound method for the maximal clique problem. Then, I will describe ways of encoding this problem, as well as related graph colouring, into a maximum satisfiability (\(\mathsf{MaxSAT}\)) framework. I will then introduce temporal graphs and extensions of cliques to them, focusing on applications to genomic datasets.

We consider the problem of outputting succinct encodings of lists of generators for invariant rings. Mulmuley conjectured that there are always polynomial sized such encodings for all invariant rings. We provide simple examples that disprove this conjecture (under standard complexity assumptions).

Talk is geared towards a general graduate student audience. No previous background on GCT or any other possibly scary word required.

Dynamic graph algorithms are algorithms in which edges, and in some models vertices, can be added or removed, and after some updates the algorithm is asked one or more queries about some function of the graph. We present examples of a) dynamic graph algorithms, b) a SETH-hardness result for a dynamic graph problem, and c) an example in which a dynamic graph algorithm is used as a subroutine of a polynomial-time static graph algorithm.

I will be presenting a theorem by Rao that bounds how large a family of sets must be before it is guaranteed to contain a sunflower with a certain number of petals. The bound that is obtained is similar to the recent result of Alweiss, Lovett, Wu, and Zhang, but the proof is simpler.

We introduce a family of non-local games and see how it helps us better understand this concept called self-testing. Self-testing has been a rich area of study in quantum information theory. It allows an experimenter to interact classically with a black box quantum system and to test that a specific entangled state was present and a specific set of measurements were performed. Recently, self-testing has been central to high-profile results in complexity theory as seen in the work on entangled games PCP of Natarajan and Vidick (FOCS 2018), iterated compression by Fitzsimons et al.\ (STOC 2019), and NEEXP in MIP* due to Natarajan and Wright (FOCS 2019).

Random walks on graphs have a fascinating theory and have become a common tool for sampling algorithms. The idea of a random walk on a graph has been generalized to the quantum setting, particularly since they are useful for quantum search algorithms. I will overview some recent results on hitting times and mixing times of quantum random walks. I will introduce all necessary ideas from quantum computing during the talk so no prior knowledge of quantum computing should be necessary.

LLL is a powerful tool for proving the existence of combinatorial objects meeting a prescribed collection of critera. Unfortunately, the original 1975 proof by Erdos and Lovasz is non-constructive. Since then many have tried to come up with a constructive alternative. Moser's 2009 result (later improved upon by Moser and Tardos in 2010) gives a simple randomized construction with an equally elegant proof.

Voting can abstractly model any decision-making scenario and as such it has been extensively studied over the decades. Recently, the related literature has focused on quantifying the impact of utilizing only limited information in the voting process on the societal welfare for the outcome, by bounding the distortion of voting rules. Even though there has been significant progress towards this goal, all previous works have so far neglected the fact that in many scenarios (like presidential elections) voting is actually a distributed procedure. In this paper, we consider a setting in which the voters are partitioned into disjoint districts and vote locally therein to elect local winning alternatives using a voting rule; the final outcome is then chosen from the set of these alternatives. We prove tight bounds on the distortion of well-known voting rules for such distributed elections both from a worst-case perspective as well as from a best-case one. Our results indicate that the partition of voters into districts leads to considerably higher distortion, a phenomenon which we also experimentally showcase using real-world data.

Normalized Matching Property (NMP) is a simple and natural generalization of the famous Hall's marriage condition for bipartite graphs, to the setting when the sizes of the two vertex classes are distinct. It is a well-studied notion in the context of graded posets and several well-known ones are known to have it (for instance the boolean lattice or the poset of subspaces of a finite dimensional vector space over \(\mathbb{F}_q\)).

However, in this talk, we will consider NMP with a 'random twist': if for every possible edge in a bipartite graph, we toss a coin in order to decide if we keep it or not, how biased must the coin be to expect to have NMP in the graph with high probability? We shall arrive at a sharp threshold for this event. Next, what can we say about explicit graphs that are known to behave 'random-like'? One of the earliest notions of a pseudorandom graph was given by Thomason in the 80s. We shall prove an 'almost' vertex decomposition theorem: every Thomason pseudorandom bipartite graph admits - except for a negligible portion of its vertex set - a partition into trees that have NMP and which arise organically through the Euclidean GCD algorithm.

As machine learning tools become more and more widely used for making impactful decisions in the world, there has been a growing drive to quantify and understand fairness and to impose constraints that will help protect against discrimination by ML algorithms. However there have been many challenges in defining consistent and achievable notions of fairness, where "achievable" sometimes goes beyond just the complexity of a problem and into pure impossibility results.

We will look at a simple but damning such example in the problem of deciding whether or not to give parole based on the likelihood that the defendant will commit another offense. This is a decision with huge ramifications for defendants and which has historically had pernicious racist elements, so it would seem natural to give the task to algorithms which can have fairness guarantees imposed. However [Chouldechova'16] shows that for an algorithm subject to a basic fairness constraint between two groups with different recidivism rates, a simple application of Bayes Rule shows that the algorithm will highly discriminate against the group with higher recidivism in a different way.

This is a 25-minute practice talk about my paper "Beating Treewidth for Average-Case Subgraph Isomorphism", which I will present at IPEC in two weeks. The content will overlap with a previous talk by me that many of you have seen. See https://arxiv.org/pdf/1902.06380.pdf for the abstract.

A proof system \(\mathcal{P}\) is said to be \(f\)-automatizable if there exists an algorithm that, given any unsatisfiable formula \(\tau\), outputs a \(\mathcal{P}\)-refutation of \(\tau\) in time \(f(n,S)\), where \(S\) is the size of the shortest \(\mathcal{P}\)-refutation of \(\tau\). Automatizability was only understood for very powerful proof systems until a landmark paper of Alekhnovich and Razborov conditionally ruled out polynomial automatizability for Resolution, one of the most important and well-studied proof systems. In this work we present a simplified version of their proof, obtaining stronger automatizability lower bounds under the exponential time hypothesis assumption.

In this talk I will give an introduction to the use of the Karchmer-Wigderson game in giving lower bounds for circuits using communication complexity. In particular, I will describe the equivalences between deterministic communication and formula size (Karchmer and Wigderson 1988) and between polynomial local search and circuit size (Razborov 1995).

Given a classical noisy channel one can associate to it a graph. Studying this graph can tell us interesting things about the channel, such as the zero error capacity of the channel. Quantum graphs arose out of work done to generalize this association to the exciting world of quantum channels.

In this talk we will look at the original motivation for quantum graphs and receive a crash course on quantum channels. We then will talk about various attempts that have been made to generalize well known graph parameters, like the chromatic number, to this setting.

The discrepancy problem in set systems has been studied since the early 1980's by Beck and Fiala. Originally focused on set systems arising through geometric constructions, general set systems are now often studied. In recent years, there has been an emphasis on understanding the discrepancy of set systems which are constructed using randomness.

In this talk we shall review the famous Beck-Fiala degree conjecture, and the best known positive result relating the discrepancy of a general set system to its maximum degree. We shall then focus on a recent probabilistic bound on the discrepancy of a random set system, published by Ezra and Lovett in 2015. This paper involves a nontrivial application of the Lovász local lemma, yielding an upper bound on discrepancy which matches the Beck-Fiala conjecture up to a logarithmic factor.

We will show how the recently developed container method (independently by Saxton and Thomason and Morris, Balogh and Samotij) can be used to solve problems in extremal combinatorics.

Liquid democracy, which combines features of direct and representative democracy has been proposed as a modern practice for collective decision making. Its advocates support that by allowing voters to delegate their vote to more informed voters can result in better decisions. In an attempt to evaluate the validity of such claims, we study liquid democracy as a means to discover an underlying ground truth. We revisit a recent model by Kahng et al. [2018] and conclude with three negative results, criticizing an important assumption of their modeling, as well as liquid democracy more generally. In particular, we first identify cases where natural local mechanisms are much worse than either direct voting or the other extreme of full delegation to a common dictator. We then show that delegating to less informed voters may considerably increase the chance of discovering the ground truth. Finally, we show that deciding delegations that maximize the probability to find the ground truth is a computationally hard problem.

The works of Barrington (1989) and Ben-Or & Cleve (1992) showed surprising ways of carrying out computation in very limited space. In particular, the insight of Ben-Or & Cleve's result for simulating log-depth arithmetic circuits using only three registers and a very limited instruction set was that one can carry out arithmetic using registers regardless of their current values by making sure to mathematically cancel out the contribution of their original values. This idea stayed mostly dormant until 2014, when the idea was revived and greatly extended by Buhrman et al. in a line of research they called "catalytic computing". By extending the power and memory of Ben-Or & Cleve, they built a natural extension of space-bounded Turing machines to answer the following question: what can we accomplish when our available space is huge but already filled in with other files, which we want to return undisturbed at the end of the computation?

We will cover the key results of Ben-Or & Cleve and Buhrman et al. with a focus on the key arithmetic techniques used in their proofs. The techniques use nothing but elementary arithmetic and yet have very few proven limitations as of now, and with recent work (e.g. Cook (2019)) using elements of Buhrman et al. to obtain surprising and novel upper bounds. We hope to inspire attendees to think of other results that can be built up from the results presented, and to reemphasize how simple and clean ideas can lead to surprising--almost unbelievable--results.

Proof complexity began as a program to prove \(\mathsf{NP} \neq \mathsf{coNP}\). Although this goal still appears to be far out of reach, the study of proof complexity has had an exciting and often unexpected impact on a wide variety of diverse fields, from automated theorem proving and sat solving, to convex optimization and circuit complexity. Many of the most exciting connections have come from algebraic proof systems, proof systems that operate over algebraic objects.

This talk will survey most well-known algebraic proof systems, the known techniques for obtaining lower bounds for these systems, as well as some interesting connections between these systems and other fields.

I summarize Ryan Williams's proof that not every language computable in nondeterministic exponential time can be computed by a polynomial-size \(\mathsf{ACC}\) circuit family.

Symmetric polynomials (also known as symmetric functions) are a classic topic in algebraic combinatorics and have been recently become more important in theoretical computer science, particularly in arithmetic complexity and quantum computing. I will overview some notions related to symmetric functions, including the RSK algorithm, and the chromatic symmetric function of a graph.

We start by recalling the PCP theorem and its three variants: proof verification, gap amplification (hardness of approximation), and games. We will see how we can generalize each of these to the quantum setting. Then we see the techniques developed in the paper "Low-degree testing of quantum states and a quantum entangled games PCP for \(\mathsf{QMA}\)" that resolves the games variant of the Quantum PCP Conjecture. I will review any background information we need on quantum info and PCP.

I will give an overview of the main methods (gradient methods, Interior Point methods, newton's methods) in convex optimization in the context of \(\ell_p\)-norm minimization. I would also present a new simple algorithm that converges much faster than any of these known methods.

The canonical problem that gives an exponential separation between deterministic and randomized communication complexity in the classical two-party communication model is 'Equality'. In this work we show that even allowing access to an 'Equality' oracle, deterministic protocols remain exponentially weaker than randomized ones. More precisely, we exhibit a total function on \(n\) bits with randomized one-sided communication complexity \(O(\log n)\), but such that every deterministic protocol with access to `Equality' oracle needs \(\Omega(n)\) cost to compute it.

Additionally we exhibit a natural and strict infinite hierarchy within \(\mathsf{BPP}\), starting with the class \(\mathsf{PEQ}\) at its bottom.

My TSS talk will be a crash course in classical theory of machine learning. We will define 'probably approximately correct' (PAC) learning and give the elegant characterization of PAC learnability in terms of 'VC dimension' (Fundamental Theorem of PAC Learning). Closely related topics we will explore include uniform convergence, empirical risk minimization, the No Free Lunch Theorem, and Sauer's lemma.

Complete subgraphs, not contained in any other, or cliques, define an intuitive notion of maximal connectedness within portions of a graph. Finding all such maximal cliques is an NP-hard problem, with myriad applications. Current state-of-the-art algorithms for solving it remain based upon Bron–Kerbosch’s branch and bound algorithm from 1973. We will go over this algorithm, including improved selections of pivots to improve bounding the search space. We will also discuss connections to graph degeneracy and how it can be used to construct improved algorithms. Work in 2013 by Eppstein, Löffler, and Strash demonstrated a practical algorithm, capable of solving maximal clique for large real graphs. They provide a kernalization, resulting in a fixed-parameter tractable (\(\mathsf{FPT}\)) algorithm, running in time \(O(dn3^{d/3})\), for a graph with \(n\) vertices and degeneracy \(d\). We will also review a new explanation by Walteros and Buchanan for the easiness of maximal clique for commonly encountered graphs, due to a connection between graph degeneracy and its clique number. Finally, time permitting, we will also go over recent work extending the Bron–Kerbosch algorithm to temporal graphs, which are of increasing relevance in large datasets, across a number of fields.

This work presents an optimal 0.5-competitive algorithm for the problem of maximum weighted online perfect bipartite matching with i.i.d. arrivals. In this problem, we are given a known set of workers, a distribution over job types, and non-negative utility weights for each pair of worker and job types. At each time step, a job is drawn i.i.d. from the distribution over job types. Upon arrival, the job must be irrevocably assigned to a worker and cannot be dropped. The goal is to maximize the expected sum of utilities after all jobs are assigned.

Property testing studies highly-efficient algorithms for approximately deciding whether an object has some property. For example, deciding whether a function is monotone. The aim is to determine whether the object (typically represented as a Boolean function \(f\)) has a property using as few queries (evaluations of \(f\) on some input \(x\)) as possible. Property testing algorithms have potential applications in areas such as machine learning and big data.

I will detail a method for obtaining lower bounds in property testing by a reduction to communication complexity which was used by Blais, Brody and Matulef to resolve several longstanding open problems in the area.

A non-blocking chromatic tree is a type of balanced binary search tree where multiple processes can concurrently perform search and update operations. We prove that a certain implementation has amortized cost \(O(\dot{c} + \log n)\) for each operation, where \(\dot{c}\) is the maximum number of concurrent operations at any point during the execution and \(n\) is the maximum number of keys in the tree during the operation. This amortized analysis presents new challenges compared to existing analyses of other non-blocking data structures.

Suppose we have a random graph that has a bipartition (that is not known to us). The bipartition is such that there is an edge within a partition with probability p and an edge across with probability \(q\). Now our goal is to recover the partition. The difficulty of recovery depends on the gap between \(p\) and \(q\). Combinatorial and SDP approaches have not been successful in recovering the partition when p-q is around \(\Omega(\sqrt{\log(n)/n})\). However, there is a spectral algorithm that achieves exact recovery with high probability. In this TSS I would talk about the spectral algorithm.

How computationally difficult is it to play games? If the win condition for the game can be specified in polynomial time, it is well-known that polynomial-length games of perfect information can be \(\mathsf{PSPACE}\)-complete. This class of games does not include games such as Poker, where players have private information. This class of games has more computational power, being \(\mathsf{EXP}\)-complete. I'll present the proof of this statement, which is similar to the proof that \(\mathsf{IP} = \mathsf{PSPACE}\).

We study the problem of secure two-party computation in the presence of a trusted setup. If there is an unconditionally UC-secure protocol for \(f\) that makes use of calls to an ideal \(g\), then we say that \(g\) reduces to \(g\) (and write \(f \sqsubseteq g\)). Some g are complete in the sense that all functions reduce to \(g\). However, almost nothing is known about the power of an incomplete \(g\) in this setting. We shed light on this gap by showing a characterization of \(f \sqsubseteq g\) for incomplete \(g\).

Very roughly speaking, we show that \(f\) reduces to \(g\) if and only if it does so by the simplest possible protocol: one that makes a single call to ideal \(g\) and uses no further communication. Furthermore, such simple protocols can be characterized by a natural combinatorial condition on \(f\) and \(g\).

Looking more closely, our characterization applies only to a very wide class of \(f\), and only for protocols that are deterministic or logarithmic-round. However, we give concrete examples showing that both of these limitations are inherent to the characterization itself. Functions not covered by our characterization exhibit qualitatively different properties. Likewise, randomized, superlogarithmic-round protocols are qualitatively more powerful than deterministic or logarithmic-round ones.

Extremal combinatorics studies how large a set of objects can be while satisfying a constraint. One technique is to associate the objects with vectors and prove that the vectors corresponding to a legal set of objects are linearly independent; then the dimension of the vector space is an upper bound on the answer. I'll present a couple short examples of (variants of) this technique, including applications to circuit complexity.

This will be an overview of discrepancy theory. We will follow Lovasz et. al's treatment of the material as presented in their 1986 paper. After going through definitions and some geometric intuition we will present two important, but hopefully intuitive, results: bounding linear discrepancy by hereditary discrepancy, and bounding the discrepancy in the Beck-Fiala instance.

The Minimum Circuit Size Problem (MCSP) takes the truth table of a Boolean function \(f\) as input, along with a parameter \(k\), and asks whether there exists a circuit of size \(k\) computing \(f\). Despite the simplicity of MCSP, it remains one of the most poorly understood NP problems, with much disagreement about whether or not it's NP-complete. We give a brief survey on MCSP, including a large body of results showing why proving reductions to MCSP has traditionally been so difficult.

It is often the case that practical performance of algorithms differs markedly from their characterization as "hard" (i.e. \(\mathsf{NP}\)) or not (\(\mathsf{P}\)). Often numerous \(\mathsf{SAT}\) instances, for example, turn out to not only be tractable, but practical to run at scale. Conversely, some polynomial-time algorithms of practical use turn out to take years on some inputs of interest. It is, in part, for these reasons that so much effort has been devoted of late toward a less coarse approach to complexity. Within \(\mathsf{NP}\), these motivations and others gave rise to the now well-known notions of fixed-parameter tractability (\(\mathsf{FPT}\)), and more recently their interesting (but still vague) connections with the \(\mathsf{APX}\) hierarchy. Within \(\mathsf{P}\), these motivations have spurred the development of fine-grained complexity, and more recently their intriguing and concrete connections with average-case complexity.

This talk will focus upon fine-grained complexity, and particular connections to average-case hardness. We will provide an overview of average case hardness, largely derived from Impagliazzo's 1995 exposition. We will then focus upon recent work, connecting key algorithms in genome bioinformatics (edit distance and LCS) to Orthogonal Vectors and \(\mathsf{SETH}\), exploring the substantial reductions in complexity that occur with correlated input instances (Goldwasser & Holden, 2016). Finally, we will discuss its broader implications for average-case hardness and future directions, touching upon its connections with the recent rigorous results in this area (presented at STOC2017).

Marcus Hutter has derived an algorithm which, for any given problem, is asymptotically as fast as the fastest algorithm which provably solves that problem. The algorithm works by interleaving i) a search for proofs that a program solves a problem and ii) the execution of programs proven to work, in such a way that the total execution time is within a factor of 5 of the time taken by the fastest program (plus a nasty constant). I will present this algorithm and the proof of its correctness.

The Subgraph Isomorphism Problem asks whether \(H\) has a subgraph isomorphic to \(G\). Alon, Yuster, and Zwick (1994) showed how to reduce this to the so-called Colored Subgraph Isomorphism problem. Li, Razborov and Rossman (2014) proved that the AC\(^0\) complexity of this problem is at least \(n^{\kappa_{col}(G)}\), where \(\kappa_{col}(G) = \Omega(treewidth(G) / \log(treewidth(G)))\) is a parameter in their paper. I'll explain all that in greater detail and present a counterexample to the conjecture that \(\kappa_{col}(G) = \Omega(tw(G))\).

The popular matching problem involves a bipartite graph (Applicants and Posts). The applicants have a preference list over the posts. Our aim is to find a matching \(M\) of applicants and posts which satisfies the following: For every other matching \(M'\), the number of applicants that prefer \(M'\) over \(M\) is at most the number of applicants that prefer \(M\) over \(M'\). Such a matching \(M\) is called a popular matching. The popular matching problem is, given an instance, find a popular matching if exists. The first paper on this problem came in 2005 and that gave an algorithm to find such a matching when the preference lists of the applicants are complete as well as when it has ties. I will be talking about these algorithms in the talk.

Many computer programming applications requires cutting a graph into two large pieces (then recursing on each piece during the execution of an algorithm, for example). The cut ratio \(\phi\) is one way to evaluate the balanced properties of a cut \(S\). If our graph is \(G = (V, E)\) and the function \(e(U)\) counts the number of edges in a subgraph \(U\), then the cut ratio is defined as $$\phi(S) = e(S)/min(|S|, |V-S|)$$ We will see Cheeger's inequality: $$\phi(G)^2/(2d_{\max}) \leq \lambda_2 \leq 2\phi(G)$$ where \(d_{\max}\) is the maximum degree and \(\lambda_2\) is the second smallest eigenvalue.

Valiant gives an \(O(n^{5.3})\) monotone formula computing majority using a randomized construction. This remains the best known result, and is conjectured to be asymptotically optimal, even though the best lower bound is \(\Omega(n^2)\). We will first look at a simpler construction due to Goldreich that incorporates most of the key ideas in Valiant's construction. If we have time, we will then turn our attention to Valiant's construction.

In a shocking result, Barrington (1989) proved that any function computable by a Boolean formula of polynomial size can be computed by a width five branching program of polynomial size, and with a fairly simple construction. This shows, for example, that the majority function on \(n\) bits can be computed without actually "having to count" the number of 1's. Just as surprising and even more elegant was the follow-up result of Ben-Or and Cleve (1992), which showed that over any ring \(R\), any function computable by an arithmetic formula over \(R\) of polynomial size can be computed by a straight-line program with three registers storing elements of \(R\). We present the latter result and discuss its implications, including a simpler proof of Barrington's theorem and the catalytic computing model of Buhrman et al (2014).

An interactive proof system is a protocol between an unbounded (though untrustworthy) prover and a weak randomized verifier --- a well known result due to Shamir proves that the class of languages decidable by an interactive protocol with a polynomial number of rounds is exactly \(\mathsf{PSPACE}\). In this seminar we will discuss an extension of this result, showing that if you have *two* unbounded provers, then we can compute any language in non-deterministic exponential time (\(\mathsf{NEXP}\)) --- a result which ultimately inspired the PCP theorem.

Diploid organisms, like humans, contain two copies of each allele―genomic positions which together encode for all biological functions. Most variation is composed of single base differences that occur with reasonable frequency within a population. Groups of these proximal differences from a single chromosome are referred to as haplotypes, while conflated pairs of chromosomes are genotypes, which is what most experiments are able to measure. The goal is to infer haplotypes from the measured genotypes.

There are \(2k − 1\) possible haplotype pairs that can explain a genotype with \(k\) heterozygous sites. Therefore the problem requires additional constraints to decide how to select resolving pairs. One objective that has been of substantial focus, is minimizing the number of haplotypes used to resolve all genotypes across the population. Under this objective, the goal is to find any one instance of haplotypes that resolve the genotypes, using a minimal number of distinct haplotypes.

This formulation of the problem is referred to as Haplotype Inference by Pure Parsimony (HIPP). This problem is \(\mathsf{APX}\)-hard, and therefore \(\mathsf{NP}\)-hard. A diverse set of combinatoric approaches have been developed for this problem, including a branch-and-bound algorithm, integer linear programming formulations, and SAT encodings. There is also a \(\mathsf{#P}\)-hard extension of this problem, which involves inferring the complete set of haplotypes (CHIPP). In this talk I will describe the HIPP and CHIPP problems, their degree of applicability to the underlying biology, and the main approaches used to solve them. Time permitting, I will also explore some interesting connections between approximability and fixed parameter tractability.

Statistical validity typically requires that data be collected independently of the choice as to which property of the data is to be measured. By contrast, the study of adaptive data analysis aims to allow interaction with the data beforehand in such a way that subsequent measurement performed on the data remains representative of the distribution from which the data has been drawn. In an application far removed from its original motivations, differential privacy has been studied as a means to meeting these goals. In particular, it has been shown that, through an interface meeting sufficient differential privacy requirements, a data analyst may be allowed to interact with their data adaptively, so that generalization guarantees may still be provided for conclusions drawn from the data.

This paper approaches the previous paradigm with particular attention to the case where the quantity to be approximated is a statistical query, namely the expected value of some real-valued function on random draws from the distribution in question.

A non-blocking data structure is one that can be updated concurrently by multiple processes without using locks. Even if a process crashes in the middle of its update, other processes must continue to complete operations. In this talk, we look at the implementation of a non-blocking binary search tree by Ellen et al, 2014. If time permits, we will discuss its proof of correctness and amortized step complexity.

In the design of concurrent algorithms, the reduction of unnecessary and costly synchronization is a primary goal in order to improve efficiency. We will look at two types of synchronization patterns and formalize the conditions under which they cannot be avoided, as well as give examples to illustrate the use of these synchronization patterns in the contexts of both mutual exclusion and linearizable objects.

Many machine learning tasks involve private data, such as medical or financial records. Stochastic gradient descent (SGD) is a widely used optimization algorithm in machine learning, particularly in deep learning, due to its scalability. In this talk, we will derive a differentially private version of SGD and prove its privacy guarantee and utility guarantee.

A special case of a combinatorial theorem of De Bruijn and Erdos asserts that every non-collinear set of n points in the plane determines at least \(n\) distinct lines. Chen and Chvatal conjectured that this assertion generalizes to metric spaces with appropriately defined lines. In this talk, we present a work of Beaudou et al. where they prove this generalization in all metric spaces induced by connected chordal graphs.

Professor Tarjan spoke to us about a concurrent version of the union-find data structure. I present a proof that in the non concurrent case, a sequence of \(m\) operations starting with \(n\) singleton sets takes \(O((m+n)\alpha(n))\) time, where \(\alpha\) is the inverse of Ackermann's function.

We study the problem of secure two-party computation in the presence of a trusted setup. If there is an unconditionally UC-secure protocol for \(f\) that makes use of calls to an ideal \(g\), then we say that \(g\) reduces to \(g\) (and write \(f \sqsubseteq g\)). Some g are complete in the sense that all functions reduce to \(g\). However, almost nothing is known about the power of an incomplete \(g\) in this setting. We shed light on this gap by showing a characterization of \(f \sqsubseteq g\) for incomplete \(g\).

Very roughly speaking, we show that \(f\) reduces to \(g\) if and only if it does so by the simplest possible protocol: one that makes a single call to ideal \(g\) and uses no further communication. Furthermore, such simple protocols can be characterized by a natural combinatorial condition on \(f\) and \(g\).

Looking more closely, our characterization applies only to a very wide class of \(f\), and only for protocols that are deterministic or logarithmic-round. However, we give concrete examples showing that both of these limitations are inherent to the characterization itself. Functions not covered by our characterization exhibit qualitatively different properties. Likewise, randomized, superlogarithmic-round protocols are qualitatively more powerful than deterministic or logarithmic-round ones.

The minimum enclosing circle problem (MEC) seeks to find the smallest disk enclosing a given set of points in the plane. Through years of concerted effort --- and a least one wrong turn --- the problem has been solved optimally. This presentation will be a historical retrospective on the MEC problem and will highlight major steps towards this accomplishment. In particular, we will describe Megiddo's linear time algorithm, an algorithm which applies the prune and search technique that he developed at around the same time. This technique is a useful tool for solving a variety of optimization problems. If time permits, we will also mention Welzl's linear time randomized algorithm which is the standard approach used to solve MEC today.

If a finite set of independent events occur each with probability less than 1, then there is a positive probability that none of these events occur. The Lovasz Local Lemma is a relaxation of this basic fact to allow for events which are "mostly independent". A groundbreaking paper by Moser and Tardos gave a constructive proof of the Lovasz Local Lemma which runs in expected polynomial time under certain conditions. In this talk, I will give the proof and the (surprisingly simple) constructive algorithm for the Lovasz Local Lemma.

In this talk, we discuss the Satisfiability Coding Lemma (introduced by Paturi, Pudlak and Zane), which roughly says that "isolated" random satisfying assignments for a \(k\)-CNF \(F\) have low entropy. Time permitting, we will discuss two applications of the Coding Lemma:

(1) Exponential lower bounds for depth-3 boolean circuits computing parity.

(2) A fast (\(O(2^{(1-1/k)n})\)) algorithm for \(k\)-\(\mathsf{SAT}\) for each \(k\).

The semantics of definite logic programs (comprised of Horn clauses) is their unique minimum model, which is the intersection of all their Herbrand models. This doesn't hold if we allow for negated atoms in clause bodies, where programs with the same set of classical models may have different computational meanings. I will present a purely model-theoretic characterization of the semantics of logic programs using an infinite-valued logic and show that every program has a unique minimum model.

Restricting ourselves to sublinear time creates an interesting challenge. While a small number of problems can be solved optimally in this way, it usually necessitates an approximate solution. In this talk, we discus a surprising result showing we can obtain sublinear time approximation algorithms from local algorithms. Local algorithms are distributed algorithms which operate in a constant number of communication rounds, which restricts a node to communicating only with its local "neighbourhood". As an example, we apply this reduction to a local algorithm for Vertex Cover.

If a finite set of independent events occur each with probability less than 1, then there is a positive probability that none of these events occur. The Lovasz Local Lemma is a relaxation of this basic fact to allow for events which are "mostly independent". A groundbreaking paper by Moser and Tardos gave a constructive proof of the Lovasz Local Lemma which runs in expected polynomial time under certain conditions. In this talk, I will give the proof and the (surprisingly simple) constructive algorithm for the Lovasz Local Lemma.

In order to prove that a boolean function requires large formula size, one may try to come up with a measure \(M\) for all boolean functions \(f\) such that \(M(f)\) serves as a lower bound on the size of any formula computing \(f\). Such a measure becomes useful if it can be non-trivially bounded from below for some explicit function. In the context of monotone formulas even Submodular complexity measures manage to yield super polynomial lower bounds. Razborov's result observes that in the non-monotone case such a measure can never be super-linear. Time permitting, I'll present a constructive extension of this result due to Aaron Potechin, that provides amortized branching program upper bounds.

I will present the proof of the following classical theorem from cryptography. If f is a one-way function, then it is infeasible to predict the xor of a random subset of bits of \(x\), given \(f(x)\) and the subset. This theorem helps us to, among other things, construct pseudo-random number generators from one-way functions. The theorem is due to Goldreich and Levin (1989), while the proof that I will present is due to Charlie Rackoff.

Topology is the study of properties which are preserved under continuous transformations of spaces. The most studied topics in this area are Algebraic, Differential and Geometric topology, and they all share fundamental concepts which are studied under the umbrella of General topology, also known as Point-Set topology. In this talk, we are going to define what open and closed sets are, derive a cute result from those simple definitions, and then proceed to discuss continuity, connectedness and compactness. Along the way, we will visit some known theorems from calculus and talk about what it means to glue geometric figures together.

In distributed computing, a memory model specifies how shared memory appears to each process. Generally the sequential consistency memory model is assumed. However, in practice, more relaxed memory models are used, which only enforce a subset of the ordering constraints that are enforced by sequential consistency. To guarantee that each process executes its program in a sequentially consistent manner, expensive synchronization operations such as memory barriers must be used. We introduce the ordering constraints enforced by both the sequential consistency model and the total store ordering (TSO) model, the role of synchronization operations in TSO, and an algorithm for a work-stealing queue under TSO that is optimized to reduce the number of synchronization operations required for correctness.

There are currently few analysis techniques available to compare implementations of concurrent data structures apart from experimental results. Unlike the analysis of sequential data structures, the fact that the analysis of concurrent data structures depends on steps made by multiple processes makes analysis much more difficult. We introduce the complexity measure of contention, and show how we can use amortized analysis to show the worst-case amortized step complexity of non-blocking algorithms. No prior knowledge of the asynchronous shared memory model will be assumed.

Submodular functions are a class of set functions which exhibit the diminishing return property. These functions have several applications in machine learning, game theory, and economy. Other than these applications, and of course more importantly for us, there is a deep theory behind their optimization methods.

We will introduce these functions and cover some of the optimization methods with a more focus on their maximization. Finally, we will discuss some open problems in this field.

In this talk, we explore a streamlined way of obtaining tight upper bounds (thumbs up for treewidth) and lower bounds (thumbs down for \(\mathsf{ETH}\)) for planar problems. We'll focus on 3-Colouring, but the techniques work for Independent Set, Vertex Cover, Feedback Vertex Set etc.

Of all models of computation in complexity theory, quantum computing is one of the strangest and least similar to the rest of the field. Nevertheless computer scientists have defined many complexity classes and written many algorithms in the quantum setting. We introduce the basic details of quantum computing, namely the qubit and basic quantum gates, and time permitting we show a basic quantum algorithm that performs a task provably impossible in the classical setting.

In this talk I will ask and partially answer the following question: can we create randomness? Or rather, given a small amount of randomness, can we give an algorithm which will efficiently produce a much longer string which *looks* random according to certain statistical tests? Naturally this is impossible in general, but for certain simple classes of tests we will give straightforward algebraic constructions which fool them. We will also show that a certain type of strong pseudorandom generator would show \(\mathsf{P} = \mathsf{BPP}\), give explicit constructions for many existence proofs and give us ways to deterministically construct objects which have the properties of random ones! (But would also imply pretty strong circuit lower bounds :( )

Let f be a monotone boolean function on n variables. Taking a disjunction of the minterms of f shows that f can be represented by a depth-2 monotone formula of size \(2^{O(n)}\), and counting arguments show that this is tight: almost all monotone boolean functions require size \(2^{\Omega(n)}\). Despite this, the best known lower bounds for any explicit monotone boolean function is on the order of \(2^{\Omega(n/\log n)}\) for monotone formulas and \(2^{n^{\epsilon}}\) for other monotone complexity measures within monotone \(\mathsf{P}\), such as switching network size and span program size.

We discuss recent work that proves the first strongly exponential lower bounds (on the order of \(2^{cn}\) for constant \(c > 0\)) for a monotone variant of the SAT problem in all monotone circuit models mentioned above and more. Our lower bounds are tight (up to the constant \(c\)) for any monotone boolean function, and thus represent the first explicit example of any monotone boolean function matching the size lower bounds obtained by easy counting arguments.

A point circuit is a circuit which has a point hardwired in it and outputs 1 if the input is same as the point and 0 else. One of the few known positive results in the area of circuit obfuscation, where the goal is to make a circuit "unintelligible" while maintaining its functionality, is a candidate obfuscator for the family of points circuits based on a strong one-way permutation assumption [Wee 05]. The assumption stipulates that there exists an efficiently computable permutation such that every poly-size adversary can invert the permutation on at most a polynomial number of points. In this talk, I will present the construction and prove that it satisfies a strong form of obfuscation security called the Virtual Black Box security for the class of point circuits. I will also discuss whether such a strong assumption is necessary for obfuscating point circuits.

Cutting Planes was originally introduced to relate integer linear programming. It is a heuristic which iteratively applies rules to shrink the size of the input polytope until it arrives at the integer hull. Later, Cook et al. showed that Cutting Planes can be interpreted as a proof system for refuting unsatisfiable systems of linear inequalities. I will give a short survey of this proof system and cover a fascinating result by Pudlak which allows lower bounds for certain circuit classes to be transferred to certain proof systems.

Perhaps the most famous circuit class is \(\mathsf{AC}^0\), the class of constant-depth circuits with unbounded fan-in \(\land\) and \(\lor\) gates (along with negations). In this lecture we discuss the classes which, in contrast to \(\mathsf{AC}^0\), all have logarithmic depth.

It is known that log-depth circuits with unbounded fan-in \(\land\) and fan-in 2 \(\lor\) gates--also known as \(\mathsf{SAC}^1\)--contains \(\mathsf{NL}\), but between this class and the more well-known \(\mathsf{TC}^1\), there are a host of circuit classes, defined with regards to gate types and fan-in restrictions. We will introduce these classes and prove some surprising relations between them, as per Allender et al, 2014.

A graph H is a minor of a graph G if H can be obtained from a subgraph of G by contracting edges.

The Graph Minor Theorem (aka the Robertson-Seymour Theorem) states that in any infinite collection of finite graphs, there is one graph that is the minor of the other. In other words: Finite graphs are well quasi ordered under the graph minor relation.

In this talk, we'll prove the Graph Minor Theorem for trees: If \(T_1, T_2,\ldots\) is an infinite sequence of finite trees, there exists \(i\) and \(j\) such that \(i < j\), and \(T_i\) is homeomorphic to a subtree of \(T_j\).

Consider the following cryptographic scenario: there are a set of n individuals, and some collection of subsets of these individuals A. The goal is to share pieces of information with each of the individuals such that

(1) Any collection of individuals appearing in A can re-combine their shares to recover some secret k.

(2) There is no way for any collection of individuals not appearing in A to recover the secret.

In such a scenario we use a so-called secret sharing scheme, which is an information-theoretically secure method of solving this problem. In this seminar we discuss secret sharing schemes and a natural restriction --- linear secret sharing schemes --- and show that the amount of information required to be shared in a linear secret sharing scheme is tightly characterized by monotone span program size.

Interactive oracle proofs (IOPs) are a natural generalisation of both interactive proofs (IPs) and probabilistically checkable proofs (PCPs). In this talk I will discuss some simple complexity-theoretic properties of IOPs, and give a recent result which shows the power of this new model relative to both IPs and PCPs. I will then show that we can use algebraic techniques to construct perfect zero knowledge IOPs (actually IPCPs) for \(\mathsf{#P}\) via sumcheck.