Columbia Theory Seminar, Fall 2015

For Fall 2015 the usual time for the meetings will be Friday at 11:30 - 13:00 in the CS conference room, CSB 453. Abstracts for talks are given below the talk schedule.

Theory Seminar on Google Calendar

  • Friday, September 11, 11:30, CSB 453: Tom Gur : Proofs of Proximity -- NP and IP analogues of Property Testing (Abstract)
  • Friday, September 25, 11:30, CSB 453: Tim Roughgarden : Complexity Theory and Algorithmic Game Theory: Some New Connections (Abstract)
  • Friday, October 2, 11:30, CSB 453: Clément Canonne : Testing Classes of Distributions: General Approaches to Particular Problems (Abstract)
  • Friday, October 9, 11:30, CSB 453: Ravishankar Krishnaswamy : Recent Results in Online Stochastic Optimization: Coping with Large Competitive Ratios (Abstract)
  • Friday, October 23, 11:30, CSB 453: Heng Guo : Spatial Mixing, Uniqueness, and Approximate Counting (Abstract)
  • Friday, October 30, 11:30, CSB 453: Laura Florescu : Spectral thresholds in the bipartite stochastic block model (Abstract)
  • Monday, November 2, 15:00, CSB 477 (note unusual time and place): Talya Eden: Approximately Counting Triangles in Sublinear Time (Abstract)
  • Friday, November 6, 11:30, CSB 453: Jinyu Xie: Tight Bounds for the Distribution-Free Testing (Abstract)
  • Wednesday, November 25, 14:30, CSB 477 (note unusual time and place): Greg Bodwin : The 4/3 Additive Spanner Exponent is Tight (Abstract)
  • Tuesday, December 1, 15:00, CSB 477 (note unusual time and place): Alexander Golovnev : Generalizations of the gate elimination method (Abstract)
  • Friday, December 11, 11:30, CSB 453: Seeun William Umboh : Online Network Design Algorithms via Hierarchical Decompositions (Abstract)

  • Talk Abstracts

    Friday, September 11:
    Proofs of Proximity -- NP and IP analogues of Property Testing
    Tom Gur
    Weizmann Institute of Science

    Abstract: Proofs of proximity are probabilistic proof systems wherein the verifier only performs a sublinear number of queries to its input, and soundness only means that, with high probability, the input is close to an accepting input. In their minimal form, called Merlin-Arthur proofs of proximity (MAP), the verifier receives, in addition to query access to the input, also free access to a short (sublinear) proof. A more general notion is that of an interactive proof of proximity (IPP), in which the verifier is allowed to interact with an all-powerful, yet untrusted, prover. MAP and IPP can be thought of as the NP and IP analogues of property testing, respectively.

    This talk will survey recent results and open problems regarding proofs of proximity. In particular, we will cover several constructions of proofs of proximity, lower bounds techniques, and exponential separations between the power of testers, MAPs, and IPPs.

    Friday, September 25:
    Complexity Theory and Algorithmic Game Theory: Some New Connections
    Tim Roughgarden
    Stanford University

    Abstract: We survey three recent applications of complexity theory to algorithmic game theory. First, we explain when and how communication and computational lower bounds for algorithms for an optimization problem translate to lower bounds on the price of anarchy (POA) in games derived from the problem. This is a new approach to POA lower bounds, based on reductions in lieu of explicit constructions. These lower bounds are particularly significant for problems of designing games that have only near-optimal equilibria, ranging from the design of simple combinatorial auctions to the existence of effective tolls for routing networks.

    Second, we study "the borders of Border's theorem," a fundamental result in auction design that gives an intuitive linear characterization of the feasible interim allocation rules of a Bayesian single-item environment. We explain a complexity-theoretic barrier that indicates, assuming standard complexity class separations, that Border's theorem cannot be extended significantly beyond the state-of-the-art.

    Finally, we explain "why prices need algorithms," in the sense that the guaranteed existence of pricing equilibria (like Walrasian equilibria) is inextricably connected to the computational complexity of related optimization problems: demand oracles, revenue-maximization, and welfare-maximization. This connection implies a host of impossibility results, and suggests a complexity-theoretic explanation for the lack of useful extensions of the Walrasian equilibrium concept.

    Includes joint work with Parikshit Gopalan, Noam Nisan, and Inbal Talgam-Cohen.

    Friday, October 2:
    Testing Classes of Distributions: General Approaches to Particular Problems
    Clément Canonne
    Columbia University

    Abstract: Inferring information about the probability distribution that underlies a data sample is an fundamental question in Statistics, and essentially every field of the natural sciences. However, it is only in the last decade or so, following the work of Batu, Fortnow, Rubinfeld, Smith, and White (2001), that this problem has been considered within the framework of property testing; quickly leading to a flurry of results.

    In this 3-part talk, I will focus on the following natural task: given a fixed class of distributions C (e.g., Binomial distributions), a parameter eps, and i.i.d. samples from an unknown probability distribution over {1,...,n}, how many samples are required to distinguish between (i) D in C vs. (ii) TV(D, D') > eps for D' in C?

    I will first cover two recent sets of results, both tackling this question with the same high-level objective: namely, to obtain /general/ algorithms and techniques that apply to a broad spectrum of classes C, while still yielding optimal or near-optimal sample complexities. Finally, if time allows I will describe new results which focus on the specific class of /histograms/, using both similar and new ideas to establish "tight-ish" bounds for this specific question.

    Based on joint work with Ilias Diakonikolas, Themis Gouleakis, and Ronitt Rubinfeld; as well as on independent work of Jayadev Acharya, Costis Daskalakis, and Gautam Kamath.

    Friday, October 9:
    Recent Results in Online Stochastic Optimization: Coping with Large Competitive Ratios
    Ravishankar Krishnaswamye
    Microsoft Research

    Abstract: Online algorithms have long been studied as a means to handle uncertainty in optimization. In these problems, the input is slowly revealed online and the algorithm must maintain a feasible solution with the part of the input which has been revealed, while at all times having performance comparable with the optimal offline solution for the partially arrived input. While it has led to numerous beautiful algorithmic techniques, there are many problems where this benchmark is too strong to derive meaningful positive results.

    As a result, recently, there has been much research on addressing these difficulties: two such methods are (a) introducing a stochastic element to the online arrivals (i.e. the arriving inputs are sampled from a distribution which the online algorithm may or may not know), and (b) changing the benchmark to competing against algorithms which also don't know the exact input and only know as much or as little as the online algorithm. In this talk, we will survey some recent results on both these methods, using the so-called prophet inequalities and stochastic knapsack as canonical examples.

    Friday, October 23:
    Spatial Mixing, Uniqueness, and Approximate Counting
    Heng Guo
    University of Wisconsin at Madison

    Abstract: One central problem in approximate counting is the complexity of partition functions of complex systems, such as the Ising model. Recently it has been shown that the complexity transition coincides with the phase transition of the uniqueness of Gibbs measures in infinite regular trees for antiferromagnetic 2-spin systems. In this talk we will explain these notions and how they relate to each other. In particular, spatial mixing properties play an important role. We will continue to talk about some recent development for ferromagnetic 2-spin models and monotone CNF formulas, where spatial mixing is not necessarily required for uniqueness or approximate counting.

    Friday, October 30:
    Spectral thresholds in the bipartite stochastic block model
    Laura Florescu

    Abstract: 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 planted random hypergraph partitioning and planted random k-SAT.

    When n_2 >> n_1, multiple thresholds emerge. Additionally, 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. Joint work with Will Perkins.

    Monday, November 2:
    Approximately Counting Triangles in Sublinear Time
    Talya Eden
    Tel Aviv University

    Abstract: We consider the problem of estimating the number of triangles in a graph. This problem has been extensively studied in both theory and practice, but all existing algorithms read the entire graph. In this work we design a {\em sublinear-time\/} algorithm for approximating the number of triangles in a graph, where the algorithm is given query access to the graph. The allowed queries are degree queries, vertex-pair queries and neighbor queries.

    We show that for any given approximation parameter $0<\epsilon<1$, the algorithm provides an estimate $\widehat{\tr}$ such that with high constant probability, $(1-\epsilon)\cdot \tr< \widehat{\tr}<(1+\epsilon)\cdot \tr$, where $t$ is the number of triangles in the graph $G$. The expected query complexity of the algorithm is $(\frac{n}{\tr^{1/3}} + \min \{m, \frac{m^{3/2}}{\tr} \}) \cdot poly(\log n, 1/\epsilon)$, where $n$ is the number of vertices in the graph and $m$ is the number of edges, and the expected running time is $(\frac{n}{\tr^{1/3}} + \frac{m^{3/2}}{\tr}) \cdot poly(\log n, 1/\epsilon)$. We also prove that $\Omega(\frac{n}{\tr^{1/3}} + \min \{m, \frac{m^{3/2}}{\tr}\})$ queries are necessary, thus establishing that the query complexity of this algorithm is optimal up to polylogarithmic factors in $n$ (and the dependence on $1/\epsilon$).

    Monday, November 6:
    Tight Bounds for the Distribution-Free Testing
    Jinyu Xie
    Columbia University

    Abstract: We improve both upper and lower bounds for the distribution-free testing of monotone conjunctions.

    Given oracle access to an unknown Boolean function f: {0,1}^n->{0,1} and sampling oracle access to an unknown distribution D over {0,1}^n, we present an O(n^{1/3}/epsilon^5)-query algorithm that tests whether f is a monotone conjunction versus epsilon-far from any monotone conjunction with respect to D. This improves the previous best upper bound of O(n^{1/2}/epsilon) by Dolev and Ron, when 1/epsilon is small compared to n.

    For some constant epsilon_0 > 0, we also prove a lower bound of \Omega(n^{1/3}) for the query complexity, improving the previous best lower bound of \Omega(n^{1/5}) by Glasner and Servedio.

    Our upper and lower bounds are tight, up to a polylogarithmic factor, when the distance parameter epsilon is a constant. Furthermore, the same upper and lower bounds can be extended to the distribution-free testing of general conjunctions, and the lower bound can be extended to that of decision lists and linear threshold functions.

    Joint work with Xi Chen.

    Wednesday, November 25:
    The 4/3 Additive Spanner Exponent is Tight
    Greg Bodwin
    Stanford University

    Abstract: 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 central 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

    Tuesday, December 1:
    Generalizations of the gate elimination method
    Alexander Golovnev

    Abstract: In this talk we consider Boolean circuits over the full binary basis. On one hand, it is known that almost all Boolean functions of $n$ variables require circuits of size $\Theta(2^n/n)$. On the other hand, the best known lower bound $3n-o(n)$ for an explicit Boolean function (that is, a function from NP) was given by Blum in 1984. This bound, as well as most of the previous bounds, is based on a simple method called gate elimination. The idea of the method is as follows: roughly, to prove a lower bound of $cn$ for a function from a certain class, one shows that in any circuit computing a function from the class one can find a substitution of a constant to an input variable that eliminates at least c gates from a circuit and keeps the function in the same class; the bound then follows by induction.

    In this talk, we discuss generalizations of gate elimination: we consider more evolved substitutions, circuit complexity measures, and generalized circuit models that simplify and improve the analysis.

    We show that affine disperser are not computable by circuits of size 3.01n. We also show that an explicit construction of dispersers for quadratic varieties (currently unknown) implies stronger lower bounds.

    Friday, December 11:
    Online Network Design Algorithms via Hierarchical Decompositions
    Seeun William Umboh
    University of Wisconsin-Madison

    Abstract: The technique of tree embedding is a powerful tool in network design that allows us to (approximately) reduce instances on arbitrary graphs to instances on trees. In this talk, I will present a new application of tree embeddings and show how it leads to improved competitive ratios for several online problems. Instead of using tree embeddings as part of an algorithm, we will use them to devise a framework for analyzing algorithms. Using our framework, we develop the first deterministic algorithms that achieve the optimal (up to constants) competitive ratios for the multi-commodity rent-or-buy, connected facility location, and Steiner network (with edge duplication) problems. Our algorithms are simple greedy algorithms that do not compute the embedding. We also obtain simpler analysis of previous algorithms for other problems.

    This work has appeared in SODA 2015.

    Contact xichen-at-cs-dot-columbia-dot-edu if you want to volunteer to give a talk (especially for students!). The talk can be about your or others' work. It can be anything from a polished presentation of a completed result, to an informal black-board presentation of an interesting topic where you are stuck on some open problem. It should be accessible to a general theory audience. I will be happy to help students choose papers to talk about.
    There is a mailing list for the reading group. General information about the mailing list (including how to subscribe yourself to it) is available here. If you want to unsubscribe or change your options, send email to with the word `help' in the subject or body (don't include the quotes), and you will get back a message with instructions.

    Comments on this page are welcome; please send them to

    Back to Theory of Computation at Columbia main page