## 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.

• 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

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
NYU

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
NYU

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