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.

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.