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.

Spring 2017

  • 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: Akshayram 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 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

Fall 2009

Spring 2009

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 2006

Fall 2005

Spring 2005

Fall 2004

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 2003

Spring 2003

Fall 2002

Spring 2002

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