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 **

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.

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.

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.

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.

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.

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.

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$).

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.

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

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.

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

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 theoryread-request@lists.cs.columbia.edu 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
` xichen-at-cs.columbia.edu
`