# Theory Lunch

Once a week, the Berkeley theory community gets together, socializes, has lunch, and then listens to an informal board presentation on open questions, new results, old results worth not forgetting, or whatever is fit to entertain a crowd of theoreticians. At the theory lunch, we do not believe in using slides, waiting until the end to ask questions, or stopping the speaker when he or she runs out of time.

Unless otherwise specified, the event occurs Wednesdays 12:00-13:00 in the Wozniak Lounge (on the 4th floor of Soda Hall). If you want to join the mailing list, click here.

### Fall 2018

• Nov 28: Mohammad Hajiabadi on Trapdoor Functions from the Computational Diffie-Hellman Assumption

Trapdoor functions (TDFs) are a fundamental primitive in cryptography. Yet, the current set of assumptions known to imply TDFs is surprisingly limited, when compared to public-key encryption. We present a new general approach for constructing TDFs. Specifically, we give a generic construction of TDFs from any Hash Encryption (Döttling and Garg [CRYPTO '17]) satisfying a property which we call recyclability. By showing how to build such hash-encryption schemes based on CDH, we obtain the first construction of TDFs with security proved under the CDH assumption. While TDFs from the Decisional Diffie-Hellman (DDH) assumption were previously known, the possibility of basing them on CDH had remained open since the introduction of the Diffie-Hellman assumption in the 70's.

Joint work with Sanjam Garg.

• Nov 21: No Lunch (Thanksgiving)
• Nov 14: Turing Laureate Lunch - Andrew Yao
• Nov 07: Turing Laureate Lunch - William Kahan
• Oct 31: Turing Laureate Lunch - Michael Stonebraker
• Oct 24: Turing Laureate Lunch - Richard Karp
• Oct 17: Turing Laureate Lunch - Manuel Blum
• Oct 10: Turing Laureate Lunch - David Patterson
• Oct 03: Turing Laureate Lunch - Shafi Goldwasser and Silvio Micali
• Sep 26: Urmila Mahadev on Classical Homomorphic Encryption for Quantum Circuits

I'll discuss the question of blind quantum computation on the cloud: can a classical client delegate a desired quantum computation to a remote quantum server while hiding all data from the server? This question has been studied since 2005 in various settings, and I will begin by giving a brief history of previous work. I will then describe a recent result which shows that certain classical homomorphic encryption schemes suffice for this task.

• Sep 19: Aloni Cohen on Towards Modeling Singling Out

Data privacy laws---like HIPAA, FERPA, Title 13 in the US, and the GDPR in the EU---govern the use of sensitive personal information. They aim to delineate normative boundaries of appropriate use and impose steep penalties upon rule breakers. Conceptually, these laws are based on notions including personally-identifiable information, linkage, distinguishability, anonymization, and inference. Practically, adherence to these laws is often achieved using a variety of ad hoc privacy enhancing techniques, including $k$-anonymity, bucketing, rounding, pseudonymization, and swapping. It is becoming increasingly clear that these techniques are often inadequate for providing the privacy protection envisioned by these laws. New techniques for data privacy are being developed in industry, government, and the academy. But a significant conceptual gap still exists between legal and technical thinking around data privacy. This has resulted in uncertainty as to the which technical offerings are appropriate. We aim to address this uncertainty by translating between the legal and the technical.

We suggest a formalization for the GDPR's notion of singling out. More specifically, we examine what it means for a data anonymization mechanism to ensure security against singling out in a data release. Ultimately, our goal is to be able to reason about whether certain classes of techniques (e.g., k-anonymity, differential privacy, pseudonymization) effectively prevent singling out attacks and to understand the strengths and weaknesses of the GDPR's protection against singling out more generally. As motivation for this work, I will describe our successful attack as part of the world's first bug bounty challenge for anonymized data re-identification.

Based on joint work with Kobbi Nissim.

• Sep 12: Nick Spooner on Multi-prover interactive proofs: Classical, quantum, and no-signaling

The study of multiplayer games underlies many fundamental questions in both complexity theory and quantum mechanics. In this talk I will give an overview of how multi-prover interactive proofs provide a complexity-theoretic view of the power of quantum entanglement and no-signaling strategies. This reveals a rich and often surprising complexity landscape. In particular I will discuss results due to Ito and Vidick (2012), and Kalai, Raz and Rothblum (2013), which elucidate the power of entangled and no-signaling strategies, respectively.

• Sep 05: Avi Wigderson on Group actions beget polytopes

I'll give a variety of examples of subsets of Euclidean space which arise in a wide variety of mathematical contexts. Common to all, but surprising in many cases, is that they are convex polytopes. Moreover, they all can be seen as arising from group actions. This viewpoint, and general results of geometric invariant theory yield their convex and linear structures in a unified way, and motivates naming them moment polytopes.

I will state a recent work which provides an efficient weak separation oracle for large classes of moment polytopes. This is particularly interesting as most are only implicitly described, and have exponentially many facets!

I will assume no special background, but as this talk is short, I will have to be sketchy.

### Spring 2018

• May 02: Vijay Vazirani on Distributive Lattices, Stable Matchings, and Robust Solutions

Our results are: -Introduce the problem of finding stable matchings that are robust to errors in the input. -An efficient algorithm for the following class of errors: Permute arbitrarily the preference list of any one boy or any one girl. This algorithm critically uses the next result. -A generalization of the classic theorem of Birkhoff (1937) on finite distributive lattices.

Based on two recent joint papers with Tung Mai. https://arxiv.org/pdf/1804.00553.pdf https://arxiv.org/pdf/1804.05537.pdf

• Apr 25: Fotis Iliopoulos on A New Perspective on Stochastic Local Search and the Lovasz Local Lemma

We present a new perspective on the analysis of stochastic local search algorithms, via linear algebra, and use it to establish a new criterion for their convergence. Our criterion captures and unifies the analysis of all currently known LLL-inspired local search algorithms, including all current applications of the entropy compression method. It can be seen as a generalization of the Lovasz Local Lemma that quantifies the interaction strength of bad events, so that weak interactions form correspondingly small obstacles to algorithmic convergence. As a demonstration of its power, we use our criterion to analyze a complex local search algorithm for the classical problem of coloring graphs with sparse neighborhoods. We prove that any improvement over our algorithm would require a major (and unexpected) breakthrough in random graph theory, suggesting that our criterion reaches the edge of tractability for this problem. Finally, we consider questions such as the number of possible distinct final states and the probability that certain portions of the state space are visited by a local search algorithm. Such information is currently available for the Moser-Tardos algorithm and for algorithms satisfying a combinatorial notion of commutativity introduced of Kolmogorov. Our framework provides a very natural and more general notion of commutativity (essentially matrix commutativity) which allows the recovery of all such results with much simpler proofs.

Joint work with Dimitris Achlioptas and Alistair Sinclair.

• Apr 18: Ilya Razenshteyn on Nearest Neighbors for General Distances

The Approximate Nearest Neighbor Search (ANN) problem is defined as follows. Given n points in \mathbb{R}^d, we would like to compute and store a small amount of auxiliary information and use it to answer queries of the following kind very quickly: given a query point, return one of the n points that is approximately closest to the query. The ANN problem can be defined with respect to any norm, and we would like to understand how the norm affects the complexity of the problem. We are interested in algorithms that have polynomial dependence on the dimension d.

Traditionally, the ANN problem has been studied for the \ell_1 and \ell_2 norms, with a very few exceptions. I will outline a new framework based on nonlinear spectral gaps for the ANN problem over general norms, and discuss its implications. The main ingredient is a new randomized partitioning procedure for a set of points lying in a normed space. This procedure, in turn, builds on the recent geometric result of Naor: any graph embeddable in a d-dimensional normed space such that:

• All edges have length at most one,
• Most pairs of vertices are \gg \log d apart must have a sparse cut.

Based on work joint with Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, and Erik Waingarten.

• Apr 11: Aaron Schild on Spectral Subspace Sparsification

We introduce a new approach to spectral sparsification that approximates the quadratic form of the pseudoinverse of a graph Laplacian restricted to a subspace with dimension d. We show that sparsifiers with at most O(d(\log d)/\epsilon^2) edges exist. Our setting generalizes that of Schur complement sparsifiers. Our approach produces sparsifiers by sampling a uniformly random spanning tree of the input graph and using that tree to guide an edge elimination procedure that contracts, deletes, and reweights edges. In the context of Schur complement sparsifiers, our approach has two benefits over prior work. First, it produces a sparsifier in m^{1+o(1)} time rather than \tilde{O}(m + n\epsilon^{-2}) time, which is faster for small enough values of \epsilon. We directly exploit this to compute \epsilon-approximate effective resistances for a set P of vertex pairs in m^{1+o(1)} + \tilde{O}(|P|\epsilon^{-2}) time, which improves on a \tilde{O}(m + (n + |P|)\epsilon^{-2}) time algorithm from prior work (Durfee-Kyng-Peebles-Rao-Sachdeva '17). Secondly, it yields sparsifiers that are reweighted minors of the input graph. As a result, we give a near-optimal answer to an \ell_2-version of the Steiner point removal problem.

A key ingredient of our algorithm is a subroutine of independent interest: a near-linear time algorithm that, given a set of vertices S, builds a data structure from which we can query a \delta-multiplicative approximation to the decrease in the effective resistance between two vertices after identifying all vertices in S to a single vertex with inverse polynomial additional additive error in O((\log n)/\delta^2) time.

Joint work with Huan Li

• Apr 04: Henry Yuen on How complex can entangled games be?

An important goal in quantum complexity theory is to understand the power of interactive proofs involving entangled provers. In the early 90s, Babai, Fortnow and Lund showed that MIP, the set of problems decidable by (classical) multiprover interactive proofs, is exactly NEXP. Currently, we are far from an analogous characterization of the class MIP, analogue of MIP with entangled provers. All that is known is that MIP is at least as powerful as NEXP, but no complexity upper bound is known — it may even contain undecidable languages!

I’ll discuss some new evidence that MIP* might be much, much harder than MIP: for any time-constructible function T(n), the class of problems solvable in nondeterministic time T(n) have interactive proofs with entangled provers where the completeness/soundness gap is 1/ log T(n).

As a corollary of our results, we obtain an alternate proof of William Slofstra’s breakthrough result that the problem of determining whether a quantum multiprover interactive protocol accepts with probability 1 is undecidable.

Joint work with Joseph Fitzsimons, Zhengfeng Ji and Thomas Vidick.

• Mar 28: No Lunch (Spring Break)
• Mar 21: Dima Kogan on The Discrete-logarithm Problem with Preprocessing

We study discrete-log algorithms that use preprocessing. In this model, an adversary may use a very large amount of precomputation to produce an "advice" string about a specific group (e.g., NIST P-256). In a subsequent online phase, the adversary's task is to use the preprocessed advice to quickly compute discrete logarithms in the group. Motivated by surprising recent preprocessing attacks on the discrete-log problem, we study the power and limits of such algorithms.

In particular, we focus on generic algorithms that operate in every cyclic group. We show a lower bound on the success probability of any generic discrete-log algorithm with preprocessing. Our lower bound, which is tight up to logarithmic factors, uses a synthesis of incompressibility techniques and classic methods for generic-group lower bounds. We apply our techniques to prove related lower bounds for the CDH, DDH, and multiple-discrete-log problems.

Time permitting, we will also briefly discuss a new generic preprocessing attacks for certain decisional-type problems in groups.

Joint work with Henry Corrigan-Gibbs

• Mar 14: No Lunch (Visit Days)
• Mar 07: Sam Hopkins on High-dimensional clustering, mixture models, and sum of squares proofs

I will describe a new algorithm for some high-dimensional unsupervised learning problems, including clustering samples from mixtures of well-separated Gaussians. This is the first polynomial-time algorithm to tolerate between-cluster separation less than what is tolerated by greedy (single-linkage) clustering, a long-standing benchmark set by Dasgupta and Schulman in 2000. The design of the algorithm is based on a "proofs to algorithms" methodology: we first design a very simple proof of cluster identifiability in the well-separated mixture model, show that this proof is captured in the SoS proof system, and then use it as a dual certificate to analyze a sum-of-squares SDP.

Based on joint work with Jerry Li, to appear in STOC 2018. (See also independent work by Kothari, Steinhardt, and Steurer, also to appear STOC 2018)

• Feb 28: Manuel Sabin on Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity

We show that popular hardness conjectures about problems from the field of fine-grained complexity theory imply structural results for resource-based complexity classes. Namely, we show that if either k-Orthogonal Vectors requires n^{k - o(1)} time or k-CLIQUE requires n^{\omega k/3 - o(1)} time (for \omega the matrix multiplication constant) to count on randomized machines for all but finitely many input lengths, then the following hold: BPP can be decided in polynomial time using only n^{\alpha} random bits on average over any efficient input distribution, for any constant \alpha > 0 BPP can be decided in polynomial time with no randomness on average over the uniform distribution DTIME [t(n)] \nsubseteq BPP, for time-constructible t(n)=n^{\omega(1)} These derandomizations improve over previous ones achieved from worst-case uniform assumptions by succeeding on all but finitely many input lengths, as is wanted in asymptotics. Previously, derandomizations from worst-case uniform assumptions were only know to succeed on infinitely many input lengths. It is specifically the structure and moderate hardness of the k-Orthogonal Vectors and k-CLIQUE problems that makes removing this restriction possible.

Via this uniform derandomization, we connect the problem-centric and resource-centric views of complexity theory by showing that exact hardness assumptions made about specific problems like k-CLIQUE imply structural results like EXP \neqBPP. Viewed pessimistically, this result poses a barrier to proving some of the main assumptions of fine-grained complexity, lest we also attain major breakthroughs in classical complexity theory. Alternately, we can hope to make progress on problems like EXP vs BPP by working on very concrete conjectures about specific problems.

• Feb 21: Thodoris Lykouris on Small-loss bounds for online learning with partial information

We consider the problem of adversarial (non-stochastic) online learning with partial information feedback, where at each round, a decision maker selects an action from a finite set of alternatives. We develop a black-box approach for such problems where the learner observes as feedback only losses of a subset of the actions that includes the selected action. When losses of actions are non-negative, under the graph-based feedback model introduced by Mannor and Shamir, we offer algorithms that attain the so called "small-loss" o(\alpha L^{\star}) regret bounds with high probability, where \alpha is the independence number of the graph, and L^{\star} is the loss of the best action. Prior to our work, there was no data-dependent guarantee for general feedback graphs even for pseudo-regret (without dependence on the number of actions, i.e. utilizing the increased information feedback). Taking advantage of the black-box nature of our technique, we extend our results to many other applications such as semi-bandits (including routing in networks), contextual bandits (even with an infinite comparator class), as well as learning with slowly changing (shifting) comparators.

In the special case of classical bandit and semi-bandit problems, we provide optimal small-loss, high-probability guarantees of \tilde{O}(\sqrt{dL^{\star}}) for actual regret, where d is the number of actions, answering open questions of Neu. Previous bounds for bandits and semi-bandits were known only for pseudo-regret and only in expectation. We also offer an optimal \tilde{O}(\sqrt{\kappa L^{\star}}) regret guarantee for fixed feedback graphs with clique-partition number at most \kappa.

Joint work with Karthik Sridharan and Eva Tardos.

• Feb 14: Ido Nachum on Learners that Use Little Information

We will talk about learning algorithms that are restricted to using a small amount of information from their input sample. We introduce a category of learning algorithms we term d-bit information learners, which are algorithms whose output conveys at most d bits of information on their input. A central theme in this work is that such algorithms generalize. If time permits, we will talk about lower and upper bounds regarding the information complexity of learning.

• Feb 07: Emanuele Natale on State-Efficient Plurality Consensus in Population Protocols

We consider the classical Population Protocol model: given a generic directed strongly-connected graph, a finite-state automaton a_u, called agent, resides on each node u; at each discrete-time step, an edge (u,v) of the graph is selected, a_u reads the state of a_v and update its state accordingly.

The only, classical assumption about how edges are chosen is that the scheduler satisfies the following fairness condition: if a configuration c appears infinitely often in the execution of the protocol, then it will also appear infinitely often any configuration that may be reached from c under a suitable sequence of edge-activation choices.

We study the Exact Plurality Consensus Problem: each agent is initially assigned a value, and the goal of the agents is to eventually have a correct guess on which value is initially the most frequent one in the system.

An open problem is what is the optimal space complexity for the Exact Plurality Consensus Problem, i.e. the number of states each agent should have in order to solve it. In fact, the best algorithm so far for the general multi-valued case had an exponential number of states.

In this work, we provide the first exact plurality consensus protocol with \tilde{O}(k^2) states. We further prove that k^2 states are necessary.

• Jan 31: Vijay Bhattiprolu on Approximability of matrix p-to-q norms

We'll discuss some Algorithmic and hardness results of the p-to-q matrix norm problem for the different regimes of p and q. In this talk we'll focus more on the algorithmic side, where we'll discuss a generalization of Krivine's algorithm for the grothendieck problem to the case of p >= 2 >= q that allows us to improve on known approximation algorithms for this regime.

Based on two recent joint works with Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee and Madhur Tulsiani.

• Jan 24: Theory Retreat Presentation

### Fall 2017

• Dec 06: Akshayaram Srinivasan on Two-round Multiparty Secure Computation under Minimal Assumptions

Secure Multiparty Computation (MPC) allows a set of mutually distrusting parties to compute a joint function of their private input such that nothing else apart from the output of the function is leaked. In this work, we give a round-optimal construction of MPC under minimal assumptions.

Based on joint work with Sanjam Garg.

• Nov 29: Aviad Rubinstein on Distributed PCP Theorems for Hardness of Approximation in P

We present a new model of probabilistically checkable proof (PCP), which we call "Distributed PCP": A satisfying assignment (x in {0,1}^n) to a CNF formula is shared between two parties (Alice knows x1, ... x{n/2}, and Bob knows x_{n/2+1},...,x_n). Their goal is to jointly write a PCP for x, while exchanging little or no information.

Using our new framework, we obtain, for the first time, PCP-like reductions from the Strong Exponential Time Hypothesis (SETH) to approximation problems in P.

Mostly based on joint work with Amir Abboud and Ryan Williams.

• Nov 22: No Lunch (Thanksgiving week)
• Nov 15: Pasin Manurangsi on Parameterized Inapproximability of Dominating Set

In the Dominating Set problem, we are given a graph G and an integer k, and the goal is to find a dominating set of size k in G. The parameterized regime focuses on the setting where k is small. In this case, the trivial algorithm solves the problem in O(n^{k + 1}) time and it can be sped up to O(n^k) for sufficiently large k. This is also known to be tight: any O(n^{k - \varepsilon})-time algorithm will refute the Strong Exponential Time Hypothesis (SETH). But what about approximation algorithms? E.g. can we find a dominating set of size 2k (given that G has a dominating set of size k) in time O(n^{k - \varepsilon})?

We give a negative answer to this question by showing that, assuming SETH, no O(n^{k - \varepsilon})-time algorithm can approximate the problem to within (\log n)^{1/\text{poly}(k)} factor. Our result is obtained by establishing a connection between communication complexity and parameterized hardness of approximation, generalizing ideas from a recent breakthrough work of Abboud, Rubinstein and Williams (FOCS 2017). The connection is quite flexible and it also allows us to obtained lower bounds under other assumptions (the k-Sum Conjecture, ETH and W[1]-hardness). In this talk, I will outline this simple connection and, if time permits, discuss some related open questions. No prior knowledge on the topic is required.

Based on joint work with Karthik C.S. and Bundit Laekhanukit

• Nov 08: Ilias Diakonikolas on Computational Lower Bounds for Statistical Estimation Problems

A number of techniques have been developed in information theory to establish sample complexity lower bounds for inference tasks. But how do we prove lower bounds on the computational complexity of statistical problems?

In this talk, I will describe a technique that yields unconditional computational lower bounds for Statistical Query (SQ) algorithms — a powerful but restricted family of algorithms — for various high-dimensional statistical tasks. The prototypical application of our technique will be for the problem of learning mixtures of separated Gaussians. We show a super-polynomial gap between the sample complexity and the computational complexity of any Statistical Query algorithm for this problem.

The talk will be based on this paper: https://arxiv.org/abs/1611.03473

Joint work with Daniel Kane (UCSD) and Alistair Stewart (USC).

• Nov 01: Jingcheng Liu on The Ising Partition Function: Zeros and Deterministic Approximation

We study the problem of approximating the partition function of the ferromagnetic Ising model in graphs and hypergraphs. Our first result is a deterministic approximation scheme (an FPTAS) for the partition function in bounded degree graphs that is valid over the entire range of parameters β (the interaction) and λ (the external field), except for the case |λ|=1 (the zero-field'' case). A randomized algorithm (FPRAS) for all β,λ has long been known. Unlike most other deterministic approximation algorithms for problems in statistical physics and counting, our algorithm does not rely on thedecay of correlations'' property. Rather, we exploit and extend machinery developed recently by Barvinok, and Patel and Regts, based on the location of the complex zeros of the partition function, which can be seen as an algorithmic realization of the classical Lee-Yang approach to phase transitions. Time permitting I'll show a sketch of how to prove Lee-Yang type theorems. No familiarity with the subject is assumed.

Based on joint work with Alistair Sinclair and Piyush Srivastava.

• Oct 25: Fan Wei on Local max-cut in smoothed polynomial time

In 1988, Johnson, Papadimitriou and Yannakakis wrote that "Practically all the empirical evidence would lead us to conclude that finding locally optimal solutions is much easier than solving NP-hard problems". Since then the empirical evidence has continued to amass but formal proofs of this phenomenon have remained elusive. A canonical (and indeed complete) example is the local max-cut problem for which no polynomial time method is known. In a breakthrough paper, Etscheid and Röglin proved that the smoothed complexity of local max-cut is quasi-polynomial. In this paper we prove smoothed polynomial complexity for local max-cut, thus confirming that finding locally optimal solutions for max-cut is much easier than solving it. In this short talk, I will give a gentle introduction to this problem and some proof sketch.

Joint work with Omer Angel, Sebastien Bubeck, and Yuval Peres.

• Oct 18: Igor Shinkar on Testing Linearity against No-Signaling Strategies

No-signaling strategies are collections of distributions with certain non-local correlations. They have been studied in Physics as a strict generalization of quantum strategies to understand the power and limitations of Nature's apparent non-locality. Recently, they have received attention in Theoretical Computer Science due to their connections to Complexity and Cryptography.

We initiate the study of Property Testing against no-signaling strategies, focusing on the classical problem of linearity testing. We prove that any no-signaling strategy that passes the linearity test with high probability must be close to a quasi-distribution over linear functions. Quasi-distributions generalize the notion of probability distributions over global objects (such as functions) by allowing negative probabilities, while at the same time requiring that local views follow standard distributions (with non-negative probabilities). Quasi-distributions arise naturally in the study of Quantum Mechanics as a tool to describe various non-local phenomena in Nature.

Our analysis of the linearity test relies on Fourier analytic techniques applied to quasi-distributions. Along the way, we also establish a general equivalence between no-signaling strategies and quasi-distributions, which we believe will provide a useful perspective on the study of no-signaling strategies beyond Property Testing.

Joint work with Alessandro Chiesa and Peter Manohar.

• Oct 11: Thatchaphol Saranurak on Expander decomposition

I will present an almost-linear-time algorithm for decomposing graphs into expanders. Formally, given an n-node m-edge graph G = (V, E), we partition V into {V_1, \dots, V_k} for some k, such that 1) the induced subgraph of each part G[V_i] has high expansion, and 2) the number of edges crossing each part is small. This tool is useful in various contexts (e.g. near-linear time algorithm in undirected graphs and directed graphs, dynamic graph algorithms, and also approximation algorithms).

The algorithm is a simple black box reduction to the balanced sparsest cut problem and takes O(m^{1 + o(1)}) time. To the best of my knowledge, previous algorithms either 1) take \Omega(mn) time, or 2) only guarantee that each part V_i contains some subgraph with high expansion or is contained in some subgraph with high expansion. (For ours, exactly G[V_i] has high expansion.)

Joint work with Danupon Nanongkai and Christian Wulff-Nilsen.

• Oct 04: Aaron Schild on Localization of electrical flows

We show that in any graph, the average length of a flow path in an electrical flow between the endpoints of a random edge is O(\log^2 n). This is a consequence of a more general result which shows that the spectral norm of the entrywise absolute value of the transfer impedance matrix of a graph is O(\log^2 n). This result implies a simple oblivious routing scheme based on electrical flows in the case of transitive graphs.

Joint work with Satish Rao and Nikhil Srivastava.

• Sep 27: Igor Pak on Complexity of short generating functions

Short generating functions (GF) are power series defined as sums of terms ct^k/(1-t^a)(1-t^b).... One can think of each term as a GF of a generalized arithmetic progression. The size of a short GF A(t) is defined as the total bit length of the parameters a,b,c,k,... We study the problem whether a given GF has a short GF presentation of polynomial size.

This turn out to be a hard problem both mathematically and computationally. We resolve it modulo some complexity assumptions. Notably, we show that the truncated theta function \sum_{k<N} t^{k^2} does NOT have a short GF presentation of polynomial size unless #P is in FP/poly.

In the talk, I will spend much of the time giving a survey and motivating the problem. I will explain the connections to Presburger arithmetic, integer programming, number theory and discrete geometry.

This is joint work with Danny Nguyen.

• Sep 20: Raghu Meka on Learning discrete markov random fields with nearly optimal runtime and sample complexity

We give a simple, multiplicative-weight update algorithm for learning undirected graphical models or Markov random fields (MRFs). The approach is new, and for the well-studied case of Ising models or Boltzmann machines, we obtain an algorithm that uses a nearly optimal number of samples and has quadratic running time (up to logarithmic factors), subsuming and improving on all prior work.

Our main application is an algorithm for learning the structure of t-wise MRFs with nearly-optimal sample complexity (up to polynomial losses in necessary terms that depend on the weights) and running time that is n^{O(t)}. All prior work runs in time n^{Ω(d)} for graphs of degree d and does not generate a hypothesis close in statistical distance even for t=3. We observe that our runtime has the correct dependence on n and t assuming the hardness of learning sparse parities with noise.

Our algorithm--the Sparsitron-- is easy to implement (has only one parameter) and holds in the online setting. It also gives the first solution to the problem of learning sparse Generalized Linear Models (GLMs).

This is based on joint work with Adam Klivans.

• Sep 13: Aleksander Madry on Matrix Scaling and Balancing via Second-order Optimization

Matrix scaling and balancing are two fundamental linear algebraic primitives that have been studied for decades in the scientific computing literature. In this presentation, I will describe a new continuous optimization based framework that enables us to solve both these problems in a unified and principled manner.

This framework relies on a certain second-order optimization primitive - called box-constrained Newton method, to efficiently minimize a broad class of so-called second-order robust functions. In the context of matrix scaling and balancing, one can then leverage and generalize the work on Laplacian system solving to obtain a very fast implementation of this primitive. This, in turn, leads to very efficient algorithms for the two problems of interest.

Based on joint work with Michael B. Cohen, Dimitris Tsipras, and Adrian Vladu.

• Sep 06: Nima Anari on Strongly Rayleigh Measures in Counting and Optimization

Strongly Rayleigh (SR) measures form a subset of discrete measures that exhibit one of the strongest forms of negative dependence. They contain several well-known distributions, such as collections of independent Bernoulli random variables, random spanning trees in graphs, finite determinantal point processes, and more.

In recent years, SR measures have found many algorithmic applications. I will briefly mention some of these results, drawing parallels to the algorithmic applications of continuous log-concave functions. These applications are roughly concerned with finding the mode of SR measures and their point-wise products, and integration/sampling from SR measures and their point-wise products.

Time-permitting I will show elements of the proofs and show how properties of SR measures are used to derive these results.

Based on joint works with Shayan Oveis Gharan, Alireza Rezaei, Amin Saberi, and Mohit Singh.

• Aug 30: Euiwoong Lee on An Algorithm for k-Vertex Separator and Applications to Vertex Deletion Problems

Given a graph G = (V, E) and an integer k, we study k-Vertex Separator, where the goal is to remove the minimum number of vertices such that each connected component in the resulting graph has at most k vertices. It has connections to several subareas of TCS (balanced graph partitioning, hypergraph vertex cover (HVC), and fixed parameter tractability (FPT)). Our main result is an O(log k)-approximation algorithm for k-Vertex Separator. Our result improves the best previous algorithms from graph partitioning and HVC.

This algorithm can be used as a subroutine to give approximation algorithms for vertex deletion problems. One example is k-Path Transversal, where the goal is to remove the minimum number of vertices such that there is no simple path of length k. With additional ideas developed in FPT algorithms and graph minor theory, we present an O(log k)-approximation algorithm for k-Path Transversal.

Based on joint work with Michal Wlodarczyk.

### Spring 2017

• May 10: Luca Trevisan on Some simple distributed network processes

We will describe network processes in which, at each step, each node communicates with its neighbors, or a random subset of neighbors, and it updates its state to be "more like" the state of the neighbors.

In a discrete setting, where there is a finite set of possible states, each node node updates to the state held by a plurality of sampled neighbors. Here we show that, in a complete communication network, there is a quick convergence to a consensus, regardless of the initial configuration and even in the presence of adversarial faults. If the set of possible states is ordered, and nodes update to the median of neighbors, convergence was known to be even faster, but less robust to adversarial tampering.

In a continuous setting, each node holds a bounded real number, and it updates to the average of sampled neighbors. Here we show that if the graph has a clustered structure, such as the one generated by the stochastic block model, the nodes can identify the cluster they belong to based on the evolution of the local state. This holds even in an asynchronous model in which only two nodes are active at a time, and the study of the latter setting leads to interesting questions about the concentration of the product of iid random matrices.

(Based on joint work with Luca Becchetti, Andrea Clementi, Pasin Manurangsi, Emanuele Natale, Francesco Pasquale, Riccardo Silvestri and Prasad Raghavendra.)

• May 03: Tom Gur on Distribution Testing Lower Bounds via Reductions from Communication Complexity

We present a new methodology for proving distribution testing lower bounds, establishing a connection between distribution testing and the simultaneous message passing (SMP) communication model. Extending the framework of Blais, Brody, and Matulef (CCC 2012), we show a simple way to reduce (private-coin) SMP problems to distribution testing problems. This method allows us to prove several new distribution testing lower bounds, as well as to provide simple proofs of known lower bounds.

Our main result is concerned with testing identity to a specific distribution p, given as a parameter. In a recent and influential work, Valiant and Valiant (FOCS 14) showed that the sample complexity of the aforementioned problem is closely related to the lp[2/3]-quasinorm of p. We obtain alternative bounds on the complexity of this problem in terms of an arguably more intuitive measure and using simpler proofs. More specifically, we prove that the sample complexity is essentially determined by a fundamental operator in the theory of interpolation of Banach spaces, known as Peetre's K-functional. We show that this quantity is closely related to the size of the effective support of p (loosely speaking, the number of supported elements that constitute the vast majority of the mass of p). This result, in turn, stems from an unexpected connection to functional analysis and refined concentration of measure inequalities, which arise naturally in our reduction.

Joint work with Eric Blais and Clément Canonne.

• Apr 26: Alexandra Kolla on Signings, expander graphs and perfect 2-matchings

The spectra of signed matrices have played a fundamental role in social sciences, graph theory, and control theory. In this talk, we investigate some computational problems of identifying symmetric signings of matrices with natural spectral properties. I will talk about a few results on matrix signings:

1. NP-completeness of certain signing problems and their implications towards constructing Ramanujan expanders via lifts.

2. A combinatorial characterization of matrices with invertible symmetric signings and an efficient algorithm using this characterization to verify whether a given matrix has an invertible symmetric signing, along with its implications to finding perfect 2-matchings. Time permitting, I will also discuss some other related signing problems.

• Apr 12: Huacheng Yu on Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds

This talk presents the first super-logarithmic lower bounds on the cell probe complexity of dynamic boolean (a.k.a. decision) data structure problems, a long-standing milestone in data structure lower bounds.

We introduce a new method for proving dynamic cell probe lower bounds and use it to prove a $\tilde{\Omega}(\log^{1.5} n)$ lower bound on the operational time of a wide range of boolean data structure problems, most notably, on the query time of dynamic range counting over $\mathbb{F}_2$. Proving an $\omega(\lg n)$ lower bound for this problem was explicitly posed as one of five important open problems in the late Mihai Patrascu's obituary [Tho13]. This result also implies the first $\omega(\lg n)$ lower bound for the classical 2D range counting problem, one of the most fundamental data structure problems in computational geometry and spatial databases.

Our technical centerpiece is a new way of "weakly" simulating dynamic data structures using efficient one-way communication protocols with small advantage over random guessing. This simulation involves a surprising excursion to low-degree (Chebychev) polynomials which may be of independent interest, and offers an entirely new algorithmic angle on the "cell sampling" method of Panigrahy et al. [PTW10].

Joint work with Kasper Green Larsen and Omri Weinstein.

• Apr 05: Arnab Bhattacharyya on On lower bounds for locally correctable codes

A locally correctable code (LCC) is an error correcting code that allows correction of an arbitrary coordinate of a corrupted codeword by querying only a few coordinates. Finding the optimal tradeoffs between the query complexity and length of LCCs has been a long-standing open problem. In this talk, I'll survey two recent results on lower bounds for the length of constant-query LCCs.

1) We show that any 2-query locally correctable code C: {0,1}^k -> [m]^n that can correct a constant fraction of corrupted symbols must have n > exp(k/(log m)) under the assumption of perfect completeness. Our result is tight upto constant factors in the exponent. The only previous lower bound that held for large m was Omega((k/log m)^2) due to [Katz & Trevisan '00]. Our result implies that LCC's with perfect completeness cannot yield 2-query private information retrieval schemes with sub-polynomial communication. Joint work with Sivakanth Gopi and Avishay Tal.

2) Affine-invariant codes are codes whose coordinates form a vector space over a finite field and which are invariant under affine transformations of the coordinate space. We give tight lower bounds on the length of affine-invariant LCC's with constant query complexity. If C is a subset of [m]^{K^n} where K is a finite field and m is a constant, describing an affine-invariant q-query LCC, then the number of codewords of C is at most exp(O(n^{q-1})). The dependence on n is tight since it's achieved by the Reed-Muller code of order q-1. A similar lower bound was obtained by [Ben-Sasson & Sudan '11] but only for linear codes. Joint work with Sivakanth Gopi.

• Mar 29: No Lunch (spring break)
• Mar 22: Andrej Bogdanov on Threshold Secret Sharing Requires a Linear-Size Alphabet

Shamir's scheme allows for a secret to be shared among n parties so that any t of them can reconstruct it, but no t - 1 of them can obtain any information about it. The scheme works for all choices of n and t, but even if the secret is a single bit the shares are about (log n)-bits long.

Extending previous work of Kilian and Nisan, we show that this is necessary: For all 1 < t < n, any "perfect" scheme for a one-bit secret must use shares of size at least max{ log(t + 1), log(n - t + 2) } ≥ log (n + 3)/2. The proof involves a detour into zero-sum games. (Based on joint work with Siyao Guo and Ilan Komargodski)

• Mar 15: No Lunch
• Mar 08: Alireza Rezaei on An MCMC Approach for Sampling Determinantal Point Processes and Strongly Rayleigh Measures

Strongly Rayleigh distributions are natural generalizations of product distributions and determinantal probability measures that satisfy the strongest form of negative dependence properties. We show that the "natural" Monte Carlo Markov Chain (MCMC) algorithm mixes rapidly in the support of a homogeneous strongly Rayleigh distribution. As a byproduct, our proof implies that Markov chains can be used to efficiently generate approximate samples of a k-determinantal point process.

Based on a joint work with Shayan Oveis Gharan and Nima Anari.

• Mar 01: Anindya De on Better bounds for trace reconstruction

Let x be a n bit string. A trace of x is obtained by deleting every bit with probability say 1/10. Suppose you have access to independent traces of x and want to recover x from these traces. How many traces do you need to reconstruct x? The best known upper bound is 2^{n^{1/3}} and the best known lower bound is n^{1/2}. So, plenty of open questions here! Note that while the best known upper bound is algorithmic, even improving the information theoretic upper bound is completely open.

• Feb 22: Ben Weitz on On the Bit Complexity of Sum-of-Squares Proofs

It has often been claimed that degree d Sum-of-Squares proofs can be found efficiently (via the Ellipsoid algorithm), if they exist. Recently, Ryan O'Donnell noted that this is not necessarily true, and gave an example of a polynomial system and a non-negative polynomial that admits degree two proofs of non-negativity, but these proofs necessarily involve numbers with an exponential number of bits, causing the Ellipsoid algorithm to run in exponential time. In this talk I will describe O'Donnell's counterexample, and present some additional results concerning the bit complexity of SoS proofs. I will give a stronger counterexample, negatively answering a question O'Donnell posed in his paper about whether Boolean constraints imply bounded proofs, and give a set of conditions that are sufficient to imply a bound on the coefficients in an SoS proof. Time permitting, I will demonstrate how this condition is applicable for many common use-cases of the SoS algorithm, such as Max-CSP, Balanced Separator, Max-Clique, and Max-Bisection. Based on joint work with Prasad Raghavendra.

• Feb 15: Avi Wigderson on Some basic problems and results from Invariant Theory (and its interactions with CS)

Invariant theory deals with properties of symmetries - actions of groups on sets of objects. It has been slower to join its sibling mathematical theories in the computer science party, but we now see it more and more in studies of computational complexity, pseudorandomness, and the analysis of algorithms.

I will discuss some basic questions and results of this field, and how they lead to fertile interaction with CS (in which symmetries occur perhaps more often than you think).

If you need more motivation - Invariant Theory is beautiful! Here is Hermann Weyl's poetic quote about its origins: "The theory of invariants came into existence in the middle of the nineteenth century somewhat like Minerva: a grown-up virgin, mailed in the shining armor of algebra, she sprang forth from Cayley's Jovian head."

No special background will be assumed.

• Feb 08: Yevgeniy Dodis on Fixing Cracks in the Concrete: Random Oracles with Auxiliary Input, Revisited

We revisit security proofs for various cryptographic primitives in the random oracle model with auxiliary input (ROM-AI): a (computationally unbounded) attacker A can compute arbitrary S bits of leakage z=z(O) about the random oracle O before attacking the system, and then use additional T oracle queries to O during the attack. This model was explicitly studied by Unruh in 2007 (CRYPTO 2007), but dates back to the seminal paper of Hellman in 1980 about time-space tradeoffs for inverting random functions, and has natural applications in settings where traditional random oracle proofs are not useful: (a) security against non-uniform attackers; (b) space-time tradeoffs; (c) security against preprocessing; (d) resilience to backdoors in hash functions.

We obtain a number of new results about ROM-AI, but our main message is that ROM-AI is the "new cool kid in town": it nicely connects theory and practice, has a lot of exciting open questions, leads to beautiful math, short definitions, elegant proofs, surprising algorithms, and is still in its infancy. In short, you should work on it!

• Feb 01: Marc Khoury on Restricted Constrained Delaunay Triangulations

We introduce the restricted constrained Delaunay triangulation (restricted CDT). The restricted CDT generalizes the restricted Delaunay triangulation, allowing us to define a triangulation of a surface that includes a set of constraining segments. We define the restricted CDT as the dual of a restricted Voronoi diagram defined on a surface that we have extended by topological surgery. We prove various combinatorial properties of restricted CDTs, including sampling conditions under which restricted CDTs exist and are homeomorphic to an underlying surface.

• Jan 25: Manuel Sabin on Average-Case Fine-Grained Hardness

We present functions that are hard to compute on average for algorithms running in some fixed polynomial time, assuming widely-conjectured \emph{worst-case} hardness of certain problems from the study of fine-grained complexity. Examples of unconditional versions of such functions are known from before (Goldmann et al., Inf. Process. Lett. 1994), but these have been canonical functions that have not found further use than as a proof of this concept, while our functions are closely related to well-studied problems and have considerable algebraic structure.

Based on the average-case hardness and structure of our functions, we outline the construction of a Proof of Work scheme and discuss possible approaches to constructing fine-grained One-Way Functions. We also show how our reductions make conjectures regarding the worst-case hardness of the problems we reduce from (and consequently the Strong Exponential Time Hypothesis) heuristically falsifiable in a sense similar to that of (Naor, CRYPTO 2003).

We prove our hardness results in each case by showing fine-grained reductions from solving one of three problems - namely, Orthogonal Vectors (OV), 3SUM, and All-Pairs Shortest Paths (APSP) - in the worst case to computing our function correctly on a uniformly random input. The conjectured hardness of OV and 3SUM then gives us a functions that takes $\Omega(n^{2-o(1)})$ time to compute on average, and that of APSP gives us a function that take $\Omega(n^{3-o(1)})$ time. Using the same techniques we also obtain a conditional average-case time hierarchy of functions.

• Jan 18: Eylon Yogev on Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds

The computational complexity of "Continues Local Search" type problems is captured by the complexity class CLS which is contained in the intersection of PLS and PPAD, two important subclasses of TFNP

In this talk, I will show hardness results for CLS, which is the smallest non-trivial class among the currently defined subclasses of TFNP. To this end, I will show hardness for a new total search problem which we call EOML, and show that it is contained in CLS. The hardness results are in terms of black-box (where only oracle access to the function is given) and white-box (where the function is represented succinctly by a circuit). In the black-box case, we show instances for which any (unbounded) randomized algorithm must make exponentially many queries in order to find a local optimum. In the white-box case, we show hardness for computationally bounded algorithms under cryptographic assumptions.

Joint work with Pavel Hubacek.

### Fall 2016

• Dec 14: Shiri Chechik on Fully dynamic all pairs shortest paths with worst case bounds

In the fully dynamic all-pairs shortest paths problem we are asked to maintain the shortest paths between all pairs in a graph under insertions and deletions of nodes. After each such update in the graph, the algorithm may spend some processing time and then has to output the new all pairs distances. There is a vast literature on dynamic shortest paths spanning over three decades and many papers cover different aspects of this problem.

In this talk, we introduce the problem and discuss the classic problem of dynamically maintaining shortest paths between all pairs of nodes of a directed weighted graph. We will consider the worst-case guarantees on the time needed to process a single update (in contrast to related results, the update time is not amortized over a sequence of updates).

Joint work with Ittai Abraham and Sebastian Krinninger.

• Dec 07: Pasin Manurangsi on Almost-polynomial Ratio ETH-hardness of Densest k-Subgraph

In the Densest k-Subgraph problem, given an undirected graph G and an integer k, the goal is to find a subgraph of G on k vertices that contains maximum number of edges. Even though the state-of-the-art algorithm for the problem achieves only O(n^1/4) approximation ratio (Bhaskara et al. 2010), the problem has resisted previous attempts at proving hardness of approximation with a matching ratio; in fact, the best approximation ratio ruled out under any worst case assumption is only any constant (Raghavendra and Steurer 2010).

In this talk, I will outline a simple sub-exponential time reduction and a proof which provides an almost polynomial (n^{1/polyloglog n}) ratio inapproximability of Densest k-Subgraph under the exponential time hypothesis.

• Nov 30: Amir Abboud on A Sequence of Hardness Results for Longest Common Subsequence

The LCS problem asks for the length of the Longest Common Subsequence of two strings of length n. A classic dynamic programming algorithm solves it in O(n^2) time, and it is perhaps the most basic problem on strings for which we don’t have near-linear time algorithms.

I will discuss several recent papers proving that this innocent looking problem is, in fact, very hard.

• Nov 23: No Lunch (Thanksgiving week)
• Nov 16: No Lunch
• Nov 09: Lin Yang on Streaming Symmetric Norms via Measure Concentration

We characterize the streaming space complexity of every symmetric norm l (a norm on R^n invariant under sign-flips and coordinate-permutations), by relating this space complexity to the measure-concentration characteristics of l. Specifically, we provide matching upper and lower bounds (up to polylog factors) on the space complexity of approximating the norm of the stream, where both bounds depend on the median and maximum of l(x) when x is drawn uniformly from the l_2 unit sphere. The same quantity governs many phenomena in high-dimensional spaces, such as large-deviation bounds and the critical dimension in Dvoretzky's Theorem. The family of symmetric norms contains several well-studied norms, such as all lp norms, and indeed we provide a new explanation for the disparity in space complexity between p ≤2 and p>2. In addition, we apply our general results to easily derive bounds for several norms were not studied before in the streaming model, including for example the top-k norm and the k-support norm, which was recently shown to be effective for machine learning tasks.

Joint work with: Jarosław Błasiok, Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer

The current version of the paper can be find at: http://arxiv.org/abs/1511.01111

• Nov 02: Daniel Masny on CCA-secure public key encryption from low-density subset sum

It is known that subset sum instances with low density are closely related to lattice problems such as the unique shortest vector problem (uSVP). Palacio, Lyubashevsky and Segev showed that subset sum could be seen as a variant of learning with errors (LWE) with deterministic noise. In this talk, we will use this observation to construct a chosen-ciphertext (CCA) secure public key encryption scheme. Even when an adversary has access to a decryption oracle, a break of the proposed scheme would imply solving low-density subset sum.

Joint work with Sebastian Faust and Daniele Venturi

• Oct 26: Alexandros Psomas on On Dynamic Fair Division

In the single-resource dynamic fair division model there is a homogeneous resource that is shared between agents dynamically arriving and departing over time. When N players are present, the only fair solution is obvious: everyone gets an N-th. The obvious caveat of this approach: too many disruptions. For a new agent to get her fair share, all other agents must give up a small piece.

When we fix the number of disruptions to the number of agents present the goal is to maximize fairness. I'll describe the optimal solution to this problem, and tell you all I know about how to divide multiple resources.

Joint work with Eric Friedman and Shai Vardi.

• Oct 19: Gil Cohen on Recent advances in randomness extractors and their applications

We survey recent developments in randomness extractors, in particular, non-malleable extractors and their applications to Ramsey graphs and privacy amplification. We present the two new pseudo-random objects that are at the center of recent progress - correlation breakers and independence-preserving mergers.

• Oct 12: Tselil Schramm on Strongly refuting random constraint satisfaction problems below the spectral threshold

Random instances of 3SAT are known to be unsatisfiable with high probability when there at least 5N clauses. However, given a random 3SAT instance on N variables, the task of refuting the instance, or of certifying that the instance has no satisfying assignments, is hypothesized to be computationally hard if there are O(N) clauses—in fact, the best known efficient algorithms for refutation require instances with at least N^(3/2) clauses, a factor of N^(1/2) beyond the unsatisfiability threshold at 5N.

In this talk, I will describe a new spectral algorithm that refutes 3SAT instances with fewer clauses, given more time. Our algorithm extends the best polynomial time algorithms at N^(3/2) clauses, interpolating between them and the exponential brute-force search at the unsatisfiability threshold at Theta(N) clauses.

This result also implies tight upper bounds on the value of sum-of-squares relaxations for random CSPs, as well as the value of sum-of-squares relaxations for random polynomial maximization over the unit sphere (injective tensor norm).

Based on joint work with Prasad Raghavendra and Satish Rao.

• Oct 05: Nir Ailon on How Speeding Up an Algorithm Leads to Uncertainty: Fourier Transform Computation

The Fourier transform is one of the most important linear operators in engineering. Computing it for a given input vector x in n-space can be done in time Theta(n log n) using Cooley and Tukey's FFT (Fast Fourier Transform). A lower bound better than trivial \Omega(n) has been evasive. In this talk I will show the surprising connection between speeding up FFT and uncertainty: If you could (theoretically) speed up FFT without changing the word size on the machine, then you would create uncertainty in the data in the form of numerical overflow or underflow. Alas, increasing the machine word size costs more time per multiplication/addition operation.

I will explain this principle and present two very recent related bounds together with a main conjecture and some related open problems. The talk requires standard linear algebra and very basic familiarity with Shannon entropy.

• Sep 28: Aviad Rubinstein on Dilemma Prisoners should upgrade their data plan

I'll try to convince you that finding an approximate Nash equilibrium is really hard.

Based on http://arxiv.org/abs/1606.04550 (to appear in FOCS 2016) http://arxiv.org/abs/1608.06580 (joint work w/ Yakov Babichenko)

• Sep 21: Kira Goldner on The FedEx Problem

Consider the following setting: a customer has a package and is willing to pay up to some value v to ship it, but needs it to be shipped by some deadline d. The customer is indifferent if the package is shipped early. Given the joint prior distribution from which (v, d) pairs are drawn, we characterize the auction that yields optimal revenue, contributing to the very limited understanding of optimal auctions beyond the single-parameter setting. Our work also demonstrates the importance of 'ironing' (and concavity) in revenue maximization, helping to illustrate why randomization is necessary to achieve optimal revenue. Finally, we strengthen the emerging understanding that duality is useful for both the design and analysis of optimal auctions in multi-parameter settings.

Joint work with Amos Fiat, Anna Karlin, and Elias Koutsoupias.

• Sep 14: Igor Shinkar on On Percolation and NP-Hardness

We study the computational hardness of problems whose inputs are obtained by applying random noise to worst-case instances. For an appropriate notion of noise we show that a number of classical NP-hard problems on graphs remain essentially as hard on the noisy instances as they are in the worst-case.

Focusing on the Graph Coloring problem, we establish the following result: Given any graph G, let H be a random subgraph of G obtained by deleting the edges of G independently with probability 0.5. Then, if $\chi(G)$ is large, then $\chi(H)$ is also large with high probability. This means that the chromatic number of any graph is robust'' to random edge deletions.

Joint work with Huck Bennett and Daniel Reichman.

• Sep 07: Andrea Lincoln on Deterministic Time-Space Tradeoffs for k-SUM

Given a set of numbers, the k-SUM problem asks for a subset of k numbers that sums to zero. When the numbers are integers, the time and space complexity of k-SUM is generally studied in the word-RAM model; when the numbers are reals, the complexity is studied in the real-RAM model, and space is measured by the number of reals held in memory at any point.

We present a time and space efficient deterministic self-reduction for the k-SUM problem which holds for both models, and has many interesting consequences. To illustrate:

3-SUM is in deterministic time O(n^2 lglg(n)/lg(n)) and space O(\sqrt{n lg(n)/lglg(n)}), extending the results of Gold and Sharir. 3-SUM is in deterministic time O(n^2) and space O(\sqrt n), derandomizing an algorithm of Wang.

A popular conjecture states that 3-SUM requires n^{2-o(1)} time on the word-RAM. We show that the 3-SUM Conjecture is in fact equivalent to the (seemingly weaker) conjecture that every O(n^{.51})-space algorithm for 3-SUM requires at least n^{2-o(1)} time on the word-RAM

Joint work with Virginia Vassilevska Williams, Josh Wang and Ryan Williams

### Spring 2016

• May 11: Dick Karp on Rearrangement in Restricted Space

We consider a problem of rearranging objects within a set of sites. Each object has an initial site, a goal site and a size. Each site has a capacity. A rearrangement algorithm executes a sequence of moves; each move takes an object from one site to another. The algorithm succeeds if it reaches a state where every object is located at its goal. At any stage, the load on a site is the sum of the sizes of the objects residing at that site. A move can only be made to a site whose load does not exceed its capacity. The demand for a site is the sum of the sizes of the objects having that site as their goal. We present a distributed algorithm that delivers each object to its goal while moving each object at most once, provided that the capacity of each site is greater than or equal to its demand. We also give an optimal distributed algorithm in the case where some sites have a demand exceeding their capacity, and a dynamic version in which objects enter the system over time. There are motivating examples in which the sites are warehouses, processors, freight cars, library shelves and tracks on a disk.

• May 04: Ran Gelles on Constant-rate coding for multiparty interactive communication is impossible

We study coding schemes for multiparty interactive communication over synchronous networks that suffer from stochastic noise, where each bit is independently flipped with probability $\epsilon$. We analyze the minimal overhead that must be added by the coding scheme in order to succeed in performing the computation despite the noise.

Our main result is a lower bound on the communication of any noise-resilient protocol over a star network with $n$-parties. Specifically, we show a task that can be solved by communicating $T$ bits over the noise-free network, but for which any protocol with success probability of $1-o(1)$ must communicate at least $\Omega(T \log n / \log \log n)$ bits when the channels are noisy. By a 1994 result of Rajagopalan and Schulman, the slowdown we prove is the highest one can obtain on any topology, up to a $\log \log n$ factor.

We complete our lower bound with a matching coding scheme that achieves the same overhead; thus, the capacity of star networks is $\Theta(\log \log n / \log n)$. Our bounds prove that, despite several previous coding schemes with rate $\Omega(1)$ for certain topologies, no coding scheme with constant rate $\Omega(1)$ exists for arbitrary $n$-party noisy networks.

Joint work with Mark Braverman, Klim Efremenko, and Bernhard Haeupler

• Apr 27: Theory Retreat Presentation
• Apr 20: Pratyay Mukherjee on Round Optimal Multi-party Computation using Fully-homomorphic Encryption

In multi-party computation (MPC) several parties P_1.....P_N holding private inputs x_1,......x_N want to compute any arbitrary public function y:= F(x_1,.......,x_N). The security requirement is that the party should not learn anything except y even any number of them behave arbitrarily malicious way. In MPC one of the main objective has been to minimize the number of interactions a.k.a. rounds.

Earlier work shows that it is impossible to construct an MPC protocol in 1 round. However, recent works constructed such protocol, albeit only from non-standard assumption like existence of Indistinguishability Obfuscation. In this work we construct the first MPC protocol from Learning with Errors assumption which reduces to worst-case lattice assumption.

Our main tool is Fully-homomorphic Encryption (FHE) which closely follows a basic template put forth by Asharov et al. (Eurocrypt '12) which construct a 3-round protocol. The structure is as follows:

Round-1 Parties interact to set up a common public key, PK of the FHE scheme. Round-2 Each party P_1 encrypts its input x_i under PK to generate ciphertext c_i and broadcasts. On receiving all c_i's each party homomorphically computes the ciphertext c := F(c_1.....c_N) which encrypts the output y = F(x_1,......x_N) Round-3 Finally parties jointly runs a one-round distributed decryption to get the output y

We essentially remove the first round by replacing the FHE scheme by a multi-key FHE scheme which we construct in this work following the ideas of Clear and McGoldrick (Crypto '15). Intuitively, such scheme guarantees that even when P_i encrypt its input x_i under public key pk_i generated independently, it is possible to homomorphically compute on the ciphertexts.

This is a joint work with Daniel Wichs (Northeastern Univ.)

Please find more details here http://eprint.iacr.org/2015/345.pdf

• Apr 13: Ariel Gabizon on Low-degree non-boolean dispersers for subspaces

Consider a vector space F^n, over a finite field F, and an integer k<n. We wish to construct an explicit polynomial f(X1,..,Xn) with the property that its restriction to any k-dimensional subspace V in F^n, is non-constant. This question was motivated by research in randomness extractors - combinatorial objects that can be useful for derandomizing algorithms (and other purposes). In a work with Matt DeVos, we constructed such f of degree n/k, provided the characteristic of F is larger than n/k. I will present this construction, and pose reducing the degree of f as an open problem.

• Apr 06: Holger Dell on Counting subgraphs modulo two

In this talk, we will discuss the subgraph problem: given graphs H and G, is H a (not necessarily induced) subgraph of G? We consider the problem with the restriction that H comes from a family F of graphs, while G can be arbitrary. It is open to fully classify those families F for which the problem is in P and for which families it is not in P (under reasonable complexity assumptions). As a first step towards solving this open problem, we investigate the related problem of computing the parity of the number of occurrences of H in G, and we will see some partial results in this talk. Interestingly, we cannot rely on the concept of NP-hardness for the hard cases since F could be a very sparse family of graphs, which leads to NP-incomplete problems; instead, we study the problem in the framework of parameterized complexity, where this issue disappears (work in progress with Curticapean and Husfeldt).

• Mar 30: Julian Shun on Sequential algorithms that are highly parallel

Over the past several decades there has been significant research on deriving new parallel algorithms for a variety of problems, with the goal of designing highly parallel (polylogarithmic depth), work-efficient (linear in the sequential running time) algorithms. For some problems, however, one might ask if perhaps a standard sequential algorithm is already highly parallel if we simply execute sub-computations opportunistically when they no longer depend on any other uncompleted sub-computations. We study this question and show that this is indeed the case for a variety of problems, including the standard greedy maximal independent set algorithm and the Knuth's textbook random permutation algorithm. Beyond the intellectual curiosity of whether sequential algorithms are inherently parallel, the approach has several important benefits for the design of parallel algorithms, including allowing for simple and fast implementations as well as deterministic parallelism.

Based on work published in SPAA '12 and SODA '15. Joint work with Guy Blelloch, Jeremy Fineman, Phillip Gibbons and Yan Gu.

• Mar 23: No Lunch (spring break)
• Mar 16: Amit Daniely on Complexity theoretic limitations on learning

We introduce a new method to reduce random CSP problems to learning problems. Under a natural generalization of Feige's assumption about random K-SAT and K-XOR, this method substantially reduces the gaps between known upper and lower bounds. Concretely, it follows that:

1. Learning DNFs is hard.
2. Learning an intersection of super logarithmic number of halfspaces is hard.
3. Learning Halfspaces in the presence of a tiny amount of noise is hard.
4. Several additional learning problems are hard. In particular, virtually all problems that were previously shown intractable (under various, mostly cryptographic, assumptions).

Based on joint work with Nati Linial and Shai Shelev-Shwartz

• Mar 09: No Lunch
• Mar 02: Rishi Gupta on A PAC Approach to Application-Specific Algorithm Selection

The best algorithm for a computational problem generally depends on the "relevant inputs," a concept that depends on the application domain and often defies formal articulation. While there is a large literature on empirical approaches to selecting the best algorithm for a given application domain, there has been surprisingly little theoretical analysis of the problem. We adapt concepts from statistical and online learning theory to reason about application-specific algorithm selection. Our models capture several state-of-the-art empirical and theoretical approaches to the problem, ranging from self-improving algorithms to empirical performance models, and our results identify conditions under which these approaches are guaranteed to perform well. We present one framework that models algorithm selection as a statistical learning problem, and our work here shows that dimension notions from statistical learning theory, historically used to measure the complexity of classes of binary- and real-valued functions, are relevant in a much broader algorithmic context. We also study the online version of the algorithm selection problem, and give possibility and impossibility results for the existence of no-regret learning algorithms.

Joint work with Tim Roughgarden.

• Feb 24: Benjamin Weitz on Symmetric SDP Lower Bounds for the Perfect Matching Problem

Yannakakis showed that the matching problem does not have a small symmetric linear program. Rothvo{\ss} recently proved that any, not necessarily symmetric, linear program also has exponential size. It is natural to ask whether the matching problem can be expressed compactly in a framework such as semidefinite programming (SDP) that is more powerful than linear programming but still allows efficient optimization. We answer this question negatively for symmetric SDPs: any symmetric SDP for the matching problem has exponential size. The two key technical ingredients underlying this result are showing that any small set of symmetric functions on the discrete space of matchings can be represented as low-degree polynomials, and giving an upper bound on the degree needed to derive polynomial identities that hold for every matching from a small set of axioms.

• Feb 17: Stephen Alstrup on Recent results (STOC/FOCS’15 and SODA’16) on labeling schemes and induced universal graphs

A graph G is said to be an induced-universal graph for a family F of graphs, if for every graph H of F there is an induced subgraph of G that is isomorphic to H. Directly related is adjacency labeling schemes.

An adjacency labeling scheme for a given family of graphs is a way of assigning labels to the vertices of each graph from the family such that given the labels of two vertices in the graph, and no other information, it is possible to determine whether or not the vertices are adjacent in the graph.

One recent results shows that there exists a graph G with O(n) nodes, such that any forest of n nodes is a node-induced subgraph of G. Equivalent using label of size log_2 n + O(1) bits one can decide adjacency for forest.

Other labeling schemes looks at e.g. distance labeling, and often will distance oracles build directly on labeling schemes. A recent result shows that label of size n/2 log_2 3 + O(log^2n) bits is sufficient to decide distance between nodes in undirected unweighted graphs.

• Feb 10: Laura Florescu on Spectral thresholds in the bipartite stochastic block model

We consider a bipartite stochastic block model on vertex sets $V_1$ and $V_2$ of size $n_1$ and $n_2$ respectively, with planted partitions in each, and ask at what densities can spectral algorithms recover the partition of the smaller vertex set. The model was used before to give a unified algorithm for random planted hypergraph partitioning and planted random $k$-SAT. We locate a sharp threshold for detection of the partition, in the sense of the results of Mossel, Neeman, Sly and Massouli\'e for the stochastic block model. This gives the best known bounds for efficient recovery densities in planted $k$-SAT and hypergraph partitioning as well as showing a barrier to further improvement via the reduction to the bipartite block model. We also show some thresholds at which various spectral algorithms work. Joint work with Will Perkins.

• Feb 03: Daniel Reichman on Smoothed analysis of connected graphs

The main paradigm of smoothed analysis on graphs suggests that for any large graph $G$ in a certain class of graphs, perturbing slightly the edge set of $G$ at random (usually adding few random edges to $G$) typically results in a graph having much “nicer” properties. In this work, we study smoothed analysis on trees or, equivalently, on connected graphs. Given an $n$-vertex connected graph $G$, form a random supergraph $G^$ of $G$ by turning every pair of vertices of $G$ into an edge with probability $\frac{\epsilon}{n}$, where $\epsilon$ is a small positive constant. This perturbation model has been studied previously in several contexts, including smoothed analysis, small world networks, and combinatorics. Connected graphs can be bad expanders, can have a very large diameter, and can possibly contain no long paths. In contrast, we show that if $G$ is an $n$-vertex connected graph, then typically $G^$ has edge expansion $\Omega(\frac{1}{\log n})$, diameter $O(\log n)$, and vertex expansion $\Omega(\frac{1}{\log n})$ and contains a path of length $\Omega(n)$, where for the last two properties we additionally assume that $G$ has bounded maximum degree. Moreover, we show that if $G$ has bounded degeneracy, then typically the mixing time of the lazy random walk on $G^*$ is $O(\log^2 n)$. All these results are asymptotically tight.

• Jan 27: Miklos Racz on Braess's paradox for the spectral gap in random graphs and delocalization of eigenvectors

If you add an edge to a random graph, do its conductance properties almost always get better? Perhaps surprisingly the answer is no, and I will discuss how this is connected to delocalization properties of eigenvectors. This is based on joint work with Ronen Eldan and Tselil Schramm.

• Jan 20: Alan Roytman on Packing small vectors

Online d-dimensional vector packing models many settings such as minimizing resources in data centers where jobs have multiple resource requirements (CPU, memory, etc.). However, no online d-dimensional vector packing algorithm can achieve a competitive ratio better than d. Fortunately, in many natural applications, vectors are relatively small, and thus the lower bound does not hold. For sufficiently small vectors, an O(log d)-competitive algorithm was known. We improve this to a constant competitive ratio, arbitrarily close to e (where e is the base of the natural logarithm), given that vectors are sufficiently small.

We give improved results for the two dimensional case. For arbitrarily small vectors, the First Fit algorithm for two dimensional vector packing is no better than 2-competitive. We present a natural family of First Fit variants, and for optimized parameters get a competitive ratio of approximately 1.48 for sufficiently small vectors.

We improve upon the 1.48 competitive ratio - not via a First Fit variant - and give a competitive ratio arbitrarily close to 4/3 for packing small, two dimensional vectors. We show that no algorithm can achieve better than a 4/3 competitive ratio for two dimensional vectors, even if one allows the algorithm to split vectors among arbitrarily many bins.

Joint work with Yossi Azar, Ilan Reuven Cohen, and Amos Fiat.

### Fall 2015

• Dec 09: Yin Tat Lee on Uniform Sampling for Matrix Approximation

In this talk, I give an iterative row sampling algorithm for matrix approximation that runs in input-sparsity time and preserves row structure and sparsity.

Random sampling has become a critical tool in solving massive matrix problems. For linear regression, a small, manageable set of data rows can be randomly selected to approximate a tall, skinny data matrix, improving processing time significantly. For theoretical performance guarantees, each row must be sampled with probability proportional to its statistical leverage score. Unfortunately, leverage scores are difficult to compute. A simple alternative is to sample rows uniformly at random. While this often works, uniform sampling will eliminate critical row information for many natural instances.

In this talk, I explain what information uniform sampling does preserve. Specifically, I show that uniform sampling yields a matrix that, in some sense, well approximates a large fraction of the original. While this weak form of approximation is not enough for solving linear regression directly, I show how to use this to build an iterative method.

• Dec 02: Di Wang on Accelerated First-order Method for Packing and Covering LPs

The linear coupling method was introduced recently by Allen-Zhu and Orecchia for solving convex optimization problems with first order methods, and it provides a conceptually simple way to integrate a gradient descent step and mirror descent step in each iteration. In the setting of standard smooth convex optimization, the method achieves the same convergence rate as that of the accelerated gradient descent method of Nesterov. The high-level approach of the linear coupling method is very flexible, and it has shown initial promise by providing improved algorithms for packing and covering linear programs. We will go over the general framework, and how how to achieve nearly linear time $\epsilon$-approximation of packing and covering LPs with convergence $1/\epsilon$.

• Nov 25: No Lunch (Thanksgiving week)
• Nov 18: Akshayaram Srinivasan on On the Exact Cryptographic Hardness of Finding a Nash Equilibrium

The exact hardness of computing a Nash equilibrium is a fundamental open question in algorithmic game theory. This problem is complete for the complexity class \ppad. It is well known that problems in PPAD cannot be \np-complete unless NP=coNP. Therefore, a natural direction is to reduce the hardness of PPAD to the hardness of problems used in cryptography.

Bitansky, Paneth, and Rosen [FOCS 2015] prove the hardness of PPAD assuming the existence of quasi-polynomially hard indistinguishability obfuscation and sub-exponentially hard one-way functions. This leaves open the possibility of basing PPAD hardness on simpler, polynomially hard, computational assumptions.

We make further progress in this direction and reduce PPAD hardness directly to polynomially hard assumptions. Our first result proves hardness of PPAD assuming the existence of polynomially hard indistinguishability obfuscation (IO) and one-way permutations. While this improves upon Bitansky et al.'s work, it does not give us a reduction to simpler, polynomially hard computational assumption because constructions of IO inherently seems to require assumptions with sub-exponential hardness. In contrast, {\em public key functional encryption} is a much simpler primitive and does not suffer from this drawback. Our second result shows that $\ppad$ hardness can be based on {\em polynomially hard} public key functional encryption and one-way permutations. Our results further demonstrate the power of polynomially hard public key functional encryption which is believed to be weaker than indistinguishability obfuscation.

Joint work with Sanjam Garg and Omkant Pandey.

• Nov 11: Greg Bodwin on The n^{4/3} Additive Spanner Bound is Tight

A +k additive spanner is a sparse subgraph that preserves all pairwise distances up to additive error +k. A classical result in this field states that all graphs have +6 spanners on n^{4/3} edges, but no sparser spanners are known for any constant k. Meanwhile, current lower bound allow for the possibility of constant error spanners on O(n^{1 + eps}) edges for all eps > 0. It is considered a major open problem to prove the existence/nonexistence of these nearly-linear sized additive spanners.

We resolve this question in the negative: there are graphs that provably have no spanners on n^{4/3 - eps} edges, unless the additive error is allowed to be polynomial in n. In this talk, we will describe a simple construction technique that produces one of these graphs. We will then discuss some extensions and implications of this new lower bound.

Joint work with Amir Abboud.

• Nov 04: Mark Zhandry on Anonymous Traitor Tracing: How to Embed Arbitrary Information in a Key

In a traitor tracing scheme, each user is given a different decryption key. A content distributor can encrypt digital content using a public encryption key and each user in the system can decrypt it using her decryption key. Even if a coalition of users combines their decryption keys and constructs some “pirate decoder” that is capable of decrypting the content, there is a public tracing algorithm that is guaranteed to recover the identity of at least one of the users in the coalition given black-box access to such decoder. All prior approaches to traitor tracing require an external mechanism to keep track of the users in the system and their identifying information in order to ensure accountability. In this talk, I will explain how to remove this restriction, resulting in an anonymous traitor tracing system, where honest users' identities remain hidden, and only dishonest users’ identities are made public. At the core of our construction is the solution to an interesting algorithmic problem, which I will show how to solve. Joint work with Ryo Nishimaki and Daniel Wichs.

• Oct 28: Nihar Shah on "Multiplicative" Incentive Mechanisms for Crowdsourcing

The growing need for labeled training data has made crowdsourcing an important part of machine learning. In this work, we design incentive-compatible payment mechanisms for such crowdsourcing setups. We show that surprisingly, under a mild and natural ""no-free-lunch"" requirement, our mechanisms are the one and only incentive-compatible class. Moreover, our mechanisms make the smallest possible payment to spammers among all possible incentive-compatible mechanisms. Interestingly, our mechanisms have a ""multiplicative"" structure where the final payment for a task is a product of the payments for each individual question. Our mechanisms have a simple description, and preliminary experiments involving 900 worker-task pairs on Amazon Mechanical Turk show a two-fold reduction in the error rates under our mechanism. Based on joint work with Denny Zhou and Yuval Peres from Microsoft Research.

• Oct 21: Yannai A. Gonczarowski on Cascading to Equilibrium: Hydraulic Computation of Equilibria in Resource Selection Games

Drawing intuition from a (physical) hydraulic system, we present a novel framework, constructively showing the existence of a strong Nash equilibrium in resource selection games (i.e., asymmetric singleton congestion games) with nonatomic players, the coincidence of strong equilibria and Nash equilibria in such games, and the uniqueness of the cost of each given resource across all Nash equilibria. Our proofs allow for explicit calculation of Nash equilibrium and for explicit and direct calculation of the resulting (unique) costs of resources, and do not hinge on any fixed-point theorem, on the Minimax theorem or any equivalent result, on linear programming, or on the existence of a potential (though our analysis does provide powerful insights into the potential, via a natural concrete physical interpretation). A generalization of resource selection games, called resource selection games with I.D.-dependent weighting, is defined, and the results are extended to this family, showing the existence of strong equilibria, and showing that while resource costs are no longer unique across Nash equilibria in games of this family, they are nonetheless unique across all strong Nash equilibria, drawing a novel fundamental connection between group deviation and I.D.-congestion. A natural application of the resulting machinery to a large class of constraint-satisfaction problems is also described. (Joint work with Moshe Tennenholtz.)

• Oct 14: Alessandro Chiesa on Interactive oracle proofs

I will present interactive oracle proofs, a proof system model that combines aspects of interactive proofs and probabilistically checkable proofs. I will talk about some initial constructions within this model, as well as cryptographic applications to obtaining succinct non-interactive proofs.

• Oct 07: Muli Safra on Open questions regarding boolean functions with potential applications

Following some theorems of Talagrand I will suggest a few extensions regarding parameters of boolean functions. We'll try to discuss potential applications.

• Sep 30: Gautam Kamath on Optimal Testing for Properties of Distributions

Given samples from an unknown distribution p, is it possible to distinguish whether p belongs to some class of distributions C versus p being far from every distribution in C? This fundamental question has received tremendous attention in statistics, focusing primarily on asymptotic analysis, and more recently in information theory and theoretical computer science, where the emphasis has been on small sample size and computational complexity. Nevertheless, even for basic properties of distributions such as monotonicity, log-concavity, unimodality, independence, and monotone-hazard rate, the optimal sample complexity is unknown. We provide a general approach via which we obtain sample-optimal and computationally efficient testers for all these distribution families. At the core of our approach is an algorithm which solves the following problem: Given samples from an unknown distribution p, and a known distribution q, are p and q close in ? 2 -distance, or far in total variation distance? The optimality of our testers is established by providing matching lower bounds with respect to both n and ?. Finally, a necessary building block for our testers and an important byproduct of our work are the first known computationally efficient proper learners for discrete log-concave and monotone hazard rate distributions.

Joint work with Jayadev Acharya and Costis Daskalakis. Paper to appear in NIPS 2015, preprint available at http://arxiv.org/abs/1507.05952.

• Sep 23: Nikhil Srivastava on Ramanujan Graphs from Finite Free Convolutions

We will show that a random d-regular graph is an optimal (i.e., Ramanujan) expander with nonzero probability. Notably, we will use tools inspired by asymptotic (i.e., large n limit) random matrix theory to prove statements about finite dimensional matrices. The mediating role will be played by the expected characteristic polynomials of the random matrices in question, exploiting in particular their real-rootedness and invariance properties.

Joint work with Adam Marcus (Princeton) and Dan Spielman (Yale).

• Sep 16: Tselil Schramm on Overcomplete tensor decomposition: speeding up sum-of-squares algorithms

Recently, there have been several works using the sum-of-squares hierarchy to solve classical problems in machine learning. However, these sum-of-squares algorithms are very slow, in some cases running in quasi-polynomial time. I will present a fast spectral algorithm for the overcomplete tensor decomposition problem, which uses ideas from the sum-of-squares rounding scheme to achieve similar performance in polynomial time. Based on joint work with Sam Hopkins, Jonathan Shi and David Steurer.

### Spring 2015

• Apr 29: Shay Solomon on Dynamic Approximate Matchings: A Density-Sensitive Approach
• Apr 22: Yaron Singer on Combinatorial Optimization under Noise
• Apr 15: Sam Wong on The cutting plane method and submodular minimization
• Apr 08: Surprise speaker
• Apr 01: Prasad Raghavendra on Multiplicative weight updates and lower bounds for LP/SDP size
• Mar 25: No Lunch (Spring Break)
• Mar 18: No Lunch (Visit Days)
• Mar 11: Ron Lavi on Competition among asymmetric sellers with fixed supply
• Mar 04: No Lunch
• Feb 25: Jingcheng Liu on Approximate counting via correlation decay

Imagine you want to know how many chocolates are there in a box, just roughly, how would you go about it? Perhaps a natural way is to do divide-and-conquer i.e. splitting the chocolates recursively. Now suppose we have one chocolate for each independent set of a graph, can we apply the same idea to count the number of independent sets? In this talk I'll try to give an overview of various frameworks and sources of approximate counting problems, and also a sketch of how one could formalize this recursive-splitting idea into a simple but general algorithm. The algorithm will be efficient whenever these "chocolates" (set of solutions) exhibit a property known as correlation decay. Based on joint works with Dr. Pinyan Lu.

• Feb 18: No Lunch
• Feb 11: Antonio Blanca on Giant components and mixing times

The random-cluster model (a.k.a. FK-model) on a finite graph G=(V,E) establishes a probability distribution over the subgraphs (V,A) of G which unifies the study of random graphs, spin systems and electrical networks. When G is the complete graph, the model exhibits a phase transition analogous to that in G(n,p) corresponding to the appearance of a "giant" component. By analyzing a particular Markov chain (known as the CM dynamics), we show how the smoothness of such transition has direct implications on the mixing time of the dynamics of the model.

• Feb 04: Aviad Rubinstein on Nash equilibrium and birthday repitition
• Jan 28: Jonah Brown-Cohen on Combinatorial optimization via polymorphisms

An elegant characterization of the complexity of constraint satisfaction problems has emerged in the form of the the algebraic dichotomy conjecture. Roughly speaking, the characterization asserts that a CSP A is tractable if and only if there exist certain non-trivial operations known as polymorphisms to combine solutions to A to create new ones. In an entirely separate line of work, the unique games conjecture yields a characterization of approximability of Max-CSPs. Surprisingly, this characterization for Max-CSPs can also be reformulated in the language of polymorphisms.

We study whether existence of non-trivial polymorphisms implies tractability beyond the realm of constraint satisfaction problems, namely in the value-oracle model which covers such examples as general submodular function minimization. Specifically, given a function f along with an appropriate operation that never increases the value of f, we design algorithms to minimize f.

### Fall 2014

• Dec 10: Sid Barman on An Approximate Version of Caratheodory's Theorem and Its Algorithmic Applications

In this talk I will present an approximate version of Caratheodory's theorem and its algorithmic applications. In particular, I will show that for every vector in the convex hull of a set of vectors X there exists a nearby (under p-norm distance, for p at least 2) vector that can be expressed as a convex combination of at most b vectors of X, where the bound b is independent of the dimension of the vectors.

Given the significance of Caratheodory's theorem, this approximate version is interesting in its own right. It also has notable algorithmic applications. Specifically, I will describe how this approximate version of Caratheodory's theorem leads to a new algorithm for computing approximate Nash equilibria in two-player games. This algorithm, in particular, provides a polynomial-time approximation scheme for Nash equilibrium in games where the sum of the payoff matrices is sparse. Moreover, for arbitrary two-player games the running time of the algorithm matches the best-known upper bound, which is obtained in (Lipton, Markakis, and Mehta 2003).

• Dec 03: No Lunch (Simons Workshop)
• Nov 26: No Lunch (Thanksgiving)
• Nov 19: George Piliouras on Games, Dynamics, and Average-case analysis
• Nov 12: Theory Retreat Presentation
• Nov 05: Jamie Morgenstern on Simple Mechanisms with Simple Stragies
• Oct 29: No Lunch (Simons Workshop)
• Oct 22: Tselil Schramm on A Better Approximation for Correlation Clustering
• Oct 15: Gary Miller on Generalized Laplacians
• Oct 08: Sanjam Garg on Indistinguishability Obfuscation: Definition and Amplification from NC^1 to General Circuits
• Oct 01: James Lee on Expansion Beyond The Spectral Gap: Curvature, Entropy, and Coupling
• Sep 24: No Lunch (Simons Workshop)
• Sep 17: Luca Trevisan on The Riemann Hypothesis for Graphs
• Sep 10: Christos Papadimitriou on Learning on the cheap

### Spring 2014

• Apr 30: Dimitris Achlioptas on The Local Lemma as a Random Walk
• Apr 23: Mario Szegedy on Impossibility Theorems and the Universal Algebraic Toolkit
• Apr 16: Theory Retreat Presentation
• Apr 09: Seung Woo Shin on DWave
• Apr 02: Justin Thaler on A Crash Course on Fast Interactive Proofs
• Mar 19: No Lunch (Spring Break)
• Mar 12: No Lunch (Visit Days)
• Mar 05: Jonathan Herman on Social Connectivity - Coalescence Process of Connected Components of a Random Acquaintances Graph Determined by Collisions of Random Walks
• Feb 26: No Lunch
• Feb 19: Shai Vardi on Local Computation
• Feb 12: Gregory Valiant on Instance-Optimal Testing
• Feb 05: Rishi Gupta on Model-Independent Algorithms for Social Networks

### Fall 2013

• Dec 03: Ning Tan on Symmetric LP and SDP relaxation
• Nov 27: No Lunch (Thanksgiving)
• Nov 20: Matt Weinberg on An algorithmic proof of Border's theorem
• Nov 13: Seung Woo Shin on The D-Wave Controversy
• Nov 06: Dominik Scheder on How to leak the darkest secrets in relative safety
• Oct 30: No Lunch (FOCS)
• Oct 23: Guoming Wang on A quantum algorithm for approximating the effective resistances of electrical networks
• Oct 16: Aviad Rubinstein on Reconstructing a Distribution Over Permutations
• Oct 09: Nihar Shah on Secret Sharing Across a Network with Low Communication Cost
• Oct 02: Anindya De on Limit theorems for Gaussian chaoses and applications

A fundamental fact about gaussians is that they are closed under linear combinations. What about more complicated combinations ? What are the conditions under which low-degree polynomials of gaussians are close to being gaussians ? In this talk, I will discuss some relevant limit theorems which partially answer this question and their applications.

Based on works with Ilias Diakonikolas and Rocco Servedio.

• Sep 25: Paul Christiano on Manipulation-proof reputation systems via online learning

Consider the problem faced by buyers and sellers on a completely decentralized online marketplace: a merchant may fail to deliver a high quality product, a buyer may harass a seller with the threat of a bad review, market participants may actually be coordinated shills aiming to manipulate the system, there are no available enforcement mechanisms to punish dishonest behavior, random noise may mask subtle malicious behavior by buyers or sellers, etc. We show how to convert online learning guarantees into manipulation-proof reputation systems which replicate the performance of the optimal "walled-garden" up to an additive loss per user of the system (i.e., they perform as well as if they had included only the optimal epsilon fraction of the merchants, with an additive loss that depends on 1 / epsilon). This guarantee holds even when the overwhelming majority of participants in the system coordinate in order to adversarially degrade its performance.

• Sep 18: Sev Gharibian on Approximation algorithms for quantum constraint satisfaction problems
• Sep 11: James Lee on Lifts of polytopes, approximation, and linear programming

In recent work with Chan, Raghavendra, and Steurer, we showed that any polynomial-sized linear program for max-cut has an integrality gap of 1/2, and any such LP for max-3sat has an integrality gap of 7/8. I will discuss the proof, open questions, and also resurgent claims that P=NP.

### Spring 2013

• May 08: Dick Karp and Alistair Sinclair on The Simons Institute

Dick and Alistair will give a (non-technical) update on what's going on at the Simons Institute, and how it will impact all of our lives next academic year. This is primarily aimed at our students and postdocs, but others are also welcome.

• May 01: Dick Karp on Algorithms for Finding Good Coins and Significant Disease Associations

We derive efficient algorithms for two sequential decision problems:

(1) We are given n coins and the ability to perform independent tosses of each coin. The heads probabilities of the coins are initially unknown. We are told that there exists one distinguished coin whose heads probability exceed the heads probabilities of all the other coins by at least a given value e. The problem is to minimize the expected number of coin tosses required to identify the distinguished coin.

(2) We are given n pairs of coins and the ability to to perform independent tosses of each coin. The heads probabilities of the coins are initially unknown. In the ith pair, one of the coins has heads probability p(i) + e**(i) and the other has heads probability p(i)- e(i). The problem is to minimize the number of coin tosses to determine argmax**_i e(i)^2/(p(i) (1- p(i)).

Problem 1 is a variant of the pure exploration version of the classical multi-armed bandit problem. The coins might correspond to treatments for a disease and the heads probability to the success probability of the treatment. The goal is to find the treatment with the highest success probability. In another setting, the coins correspond to algorithms for a task, and the heads probability is the probability that the algorithm performs correctly on an input drawn at random from a training set. The problem is to determine the algorithm with the highest probability of correct performance. A manuscript by Karthik Chandrasekharan and the speaker (2012) discusses a version in which the maximum heads probability is given in advance. Here we treat the case where the maximum heads probability is not given.

In Problem 2 each pair of coins corresponds to a genetic mutation that may be associated with a given disease. The heads probabilities p(i) + e(i) and p(i) - e(i) are the probabilities that the mutation occurs, respectively, in cases (individuals with the disease) and controls (members of the general population). We seek the mutation for which the hypothesis that e(i)>0 has the greatest significance according to the chi-square test.

• Apr 24: Anupam Gupta on Sparsest Cut for Bounded Treewidth Graphs
• Apr 17: Shayan Oveis-Gharan on New Approaches to the Traveling Salesman Problem
• Apr 10: Yaron Singer on Adaptive Seeding in Social Networks (and other Animals)
• Apr 03: James Lee on Information theory against an adversary (or for Umesh, Quantum hypothesis testing)
• Mar 20: No Lunch (Visit Days)
• Mar 13: Ilan Adler on A direct reduction of PPAD Lemke-verified linear complementarity problems to bimatrix games
• Mar 06: Nihar Shah on Codes for efficient and reliable distributed storage
• Feb 27: Christos Papadimitriou on Game Theoretic Modeling of the Web
• Feb 20: Paul Christiano on A Coordination Game in Networks
• Feb 13: Siu Man Chan on Pebble Games and Complexity
• Feb 06: Ravi Kannan on Non-negative Matrix Factorization
• Jan 30: Anindya De on The Sum-of-Squares Hierarchy and Max Cut

### Spring 2010

• May 12: Lofti Zadeh on Computing with imprecise probabilities
• May 05: Fritz Sommer on A review of mathematical problems in theoretical neuroscience
• Apr 28: Thomas Watson on Barriers to average-case complexity
• Apr 21: James Lee on A remarkable relationship between cover times of graphs and random projections
• Apr 14: Dick Karp on Online algorithms for implicit hitting set problems
• Apr 07: Christos Papadimitriou on Optimal auctions
• Mar 31: Thomas Vidick on A lower bound on a decision problem

We prove a communication complexity lower bound for the following problem: Alice gets a unit vector x, Bob a unit vector y, with the promise that either their inner product x.y > eps or x.y < -eps; their goal is to decide which. Our proof proceeds by round elimination and uses measure concentration techniques. (Joint work with Joshua Brody, Amit Chakrabarty, Oded Regev, and Ronald de Wolf.)

• Mar 15: Lorenzo Orecchia on Fast algorithms for balanced cut and local random walks [Location: 410 Hearst Mining Building]
• Mar 03: Free Lunch (report on theory retreat)
• Feb 24: Anindya De on Extractors via complexity amplification
• Feb 17: Ryan Williams on Improving exhaustive search implies superpolynomial lower bounds
• Feb 10: Dirk Sudhiolt on Ant Colony Optimization

Ant Colony Optimization (ACO) is a modern and very popular optimization paradigm inspired by the ability of ant colonies to find shortest paths between their nest and a food source. Despite its popularity, the theory of ACO is still in its infancy and a solid theoretical foundation is needed. I will present bounds on the running time of ACO systems for shortest path problems. This is joint work with Christian Horoba and it partly builds on previous results by Attiratanasunthron and Fakcharoenphol [Information Processing Letters, 105(3):88--92, 2008]. While the previous results were limited to single-destination shortest paths on directed acyclic graphs, our results hold for arbitrary directed graphs and the running time bounds have been improved. Our upper bound is asymptotically tight for large evaporation factors, holds with high probability, and transfers to the all-pairs shortest paths problem. There, a simple mechanism for exchanging information between ants with different destinations yields a significant improvement. A comparison with evolutionary and genetic approaches indicates that ACO is the best known metaheuristic for the all-pairs shortest paths problem.

• Feb 03: Christos Papadimitriou on Risk in games
• Jan 27: Sanjeev Arora on Computational complexity and information asymmetry in financial derivatives

### Spring 2008

• May 07: Kunal Talwar on Lower bounds for near neighbor search
• Apr 30: Jonathan Katz on Complete fairness in secure two-party computation
• Apr 23: Grant Schoenebeck on Integrality gaps in the Lasserre hierarchy
• Apr 16: Yaron Singer on The hardness of being truthful
• Apr 09: Jacob Abernethy on How to bet in a rigged casino using a random walk
• Apr 02: Venkat Guruswami on Compressed sensing, Euclidean sections, and the JL lemma
• Mar 26: No Lunch (spring break)
• Mar 19: Alexander Rakhlin on Algorithms for online bandit
• Mar 17: Greg Valiant on The complexity of Nash equilibria of action-graph games [Location: 410 Hearst Mining Building]
• Mar 12: Allan Sly on MCMC on exponential random graphs
• Mar 05: Luca Trevisan on Dense subsets of pseudorandom sets and arithmetic progressions in the primes
• Feb 27: Madhur Tulsiani on Unique games on expanders
• Feb 20: James Lee on Spectral bounds without conformal mappings
• Feb 13: Ravi Kannan on Random matrices and generative models
• Feb 06: Albert Atserias on Fractional edge covers and relational joins
• Jan 30: Andrej Bogdanov on Pseudorandom generators for low-degree polynomials [Location: 373 Soda Hall]
• Jan 23: Prahladh Harsha on Lower bounds for probabilistically checkable proofs of proximity [Location: 410 Hearst Mining Building]

### Spring 2007

• May 02: Nisheeth Vishnoi on Integrality gaps for sparsest cut
• Apr 25: Sergey Yekhanin on Locally decodable codes
• Apr 18: Luca Trevisan on Proving unsatisfiability of random k-SAT formulas
• Apr 11: Jayanth Kannan on New routing protocols
• Apr 04: Costis Daskalakis on Decoding error-correcting codes via linear programming
• Mar 28: No Lunch
• Mar 21: Jacob Abernethy on Experts algorithms, random sampling, and approximating the permanent
• Mar 14: No Lunch
• Mar 12: Lorenzo Orecchia on Expert algorithms [Location: 410 Hearst Mining Building]
• Mar 07: Grant Schoenebeck on Integrality gaps for Lovasz-Schrijver relaxations
• Feb 28: Konstantin and Yuri Makarychev on Near-optimal algorithms for maximum constraint satisfaction problems
• Feb 21: Elchanan Mossel on Asymptotics of games
• Feb 14: Umesh Vazirani on D-wave's "quantum computer"
• Feb 07: Albert Atserias on Distinguishing SAT from polynomial-size circuits
• Jan 31: Dick Karp on Noisy binary search
• Jan 24: Robert Špalek on How negative weights make adversaries stronger

### Fall 2006

• Nov 29: Kamalika Chaudhuri on A clustering problem
• Nov 22: No Lunch
• Nov 15: Sandu Popescu on Non-local correlations and communication complexity
• Nov 08: Alexandra Kolla on Honest-verifier zero knowledge
• Nov 01: Omid Etesami on Ad auctions and market equilibrium
• Oct 25: Ravi Kannan on Sampling in large matrices and tensors
• Oct 18: Iordanis Kerenidis on The one-way communication complexity of the Boolean Hidden Matching problem
• Oct 11: Nikhil Devanur on The bidirected cut relaxation of Minimum Steiner Tree
• Oct 04: Mani Narayanan on Tractable graph matching problem
• Sep 27: Costis Daskalakis on Reconstructing phylogenies from minimum information
• Sep 20: Henry Lin on Network decompositions and the power of choice in Polya urns
• Sep 13: Ben Reichardt on Fault tolerance in quantum computation
• Sep 06: Dick Karp on Sorting partial orders

### Spring 2004

• May 19: Cyntia Dwork on Privacy in public databases
• May 12: Hoeteck Wee on Obfuscation [Talk given by Luca Trevisan]
• May 07: Leonard Schulman on Clustering
• May 05: Frank McSherry on Spectral filtering and Gaussian mixtures
• Apr 28: Tim Roughgarden on Correlated equilibria
• Apr 21: Kamal Jain on Price-collecting Steiner forest [Location: 400 Cory Hall]
• Apr 14: Kamalika Chaudhuri on Degree-restricted MST
• Apr 07: Luca Trevisan on Inapproximability results proved using average-case assumptions
• Mar 31: Andrej Bogdanov on Pseudorandomness against degree-2 adversaries
• Mar 24: No Lunch (spring break)
• Mar 15: Iordanis Kerenidis on Communication complexity [Location: 380 Soda Hall]
• Mar 10: Ryan O'Donnell on Learning monotone functions
• Mar 03: Kobbi Nissim on Communication versus computation
• Feb 25: Nati Linial on Simplicial complexes [Location: 400 Cory Hall]
• Feb 18: Arnab Nilim on Optimal Markov decision problems [Location: 400 Cory Hall]
• Feb 11: Kris Hildrum on Peer-to-peer networks
• Feb 04: Scott Aaronson on The communication complexity of agreement
• Jan 28: No Lunch
• Jan 21: Baruch Awerbuch on Adaptive routing

### Fall 2001

• Nov 22: Free lunch (we will wish each other happy holidays)
• Dec 06: Iordanis Kerenidis on Collaborative filtering
• Nov 29: Satish Rao on Disjoint paths
• Nov 22: No Lunch (Thanksgiving week)
• Nov 15: Kenji Obata on Lower bound for property testing [Location: 373 Soda]
• Nov 08: Sivan Toledo on Linear algebraic algorithms
• Nov 01: David Wagner on Homomorphic signature schemes
• Oct 25: Christos Papadimitriou on Computational game theory
• Oct 18: Yuval Rabani on Directed multicuts
• Oct 11: Amir Shpilka on Lower bounds for matrix product
• Oct 04: Subhash Khot on A class of two-query PCPs
• Sep 27: Luca Trevisan on Sub-linear time MST approximation
• Sep 20: Beini Zhou on Black-box and non-black-box zero knowledge
• Sep 13: Sanjeev Arora on The nondeterministic hierarchy theorem
• Sep 11: Venkat Guruswami on Hypergraph coloring