For Spring 2015 the usual time for the meetings will be Friday at 12:00 - 13:30 in the open meeting area, CSB 477. Abstracts for talks are given below the talk schedule.

** Theory Seminar on Google Calendar **

Tyson Williams

University of Wisconsin Madison

**Abstract:**
Coherent configurations (CCs) are generalizations of association schemes
What does Siegel's theorem on finiteness of integer solutions have to do
with complexity theory? In this talk we discuss a new complexity dichotomy
theorem for counting problems. Such a dichotomy is a classification of a
class of problems into exactly two kinds: those that are polynomial time
computable, and those that are #P-hard, and thus intractable. An example
problem in this dichotomy is the problem of counting the number of valid
edge colorings of a graph. We show that an effective version of Siegel's
theorem and some Galois theory are key ingredients in the proof of this
dichotomy.

This is Joint work with Jin-Yi Cai and Heng Guo.

Ilya Razenshteyn

MIT

**Abstract:**
Coherent configurations (CCs) are generalizations of association schemes
Imagine the following communication task. Alice and Bob each
have a point from a metric space. They want to transmit a few
bits and decide whether their points are close to each other or
are far apart. Of particular interest are sketching protocols: Alice
and Bob both compute short summaries of their inputs and then
a referee, given these summaries, makes the decision; sketches
are very useful for the nearest neighbor search, streaming,
randomized linear algebra etc. Indyk (FOCS 2000) showed that
for the l_p spaces with 0 < p <= 2 the above problem allows a
very efficient sketching protocol. Consequently, any metric that
can be mapped into the l_p space with all the distances being
approximately preserved has a good protocol as well.

I will show that for normed spaces (a very important class of metric spaces) embedding into l_p is the only possible technique for solving the communication problem. Slightly more formally, we show that any normed space that admits a good communication (in particular, sketching) protocol for distinguishing close and far pairs of points embeds well into l_p with p being close to 1. The proof uses tools from communication complexity and functional analysis.

As a corollary, we will show communication lower bounds for the planar Earth Mover's Distance (minimum-cost matching metric) and for the trace norm (the sum of the singular values of a matrix) by deriving them from the (known) non-embeddability theorems and (the contrapositive of) our result.

The talk is based on a joint paper with Alexandr Andoni and Robert Krauthgamer (arXiv:1411.2577).

Clement Canonne

Columbia University

**Abstract:**
In many situations, sample data is obtained from a noisy or imperfect
source. In order to address such corruptions, we introduce the concept
of a "sampling corrector". Such algorithms use structure that the
distribution is purported to have, in order to allow one to make
'on-the-fly' corrections to samples drawn from probability distributions.
These algorithms then act as filters between the noisy data and the
end user.

We show connections between sampling correctors, distribution learning algorithms, and distribution property testing algorithms. We show that these connections can be utilized to expand the applicability of known distribution learning and property testing algorithms. We then focus on the question of whether algorithms for sampling correctors can be more efficient in terms of sample complexity than learning algorithms for the analogous families of distributions. When correcting monotonicity, we show that this is indeed the case for distributions that are very close to monotone.

We consider the question of whether an additional source of independent random bits are required by sampling correctors to implement the correction process. We show that for correcting close-to-uniform distributions and close-to-monotone distributions, no additional source of random bits is required, as the samples from the input source itself can be used to produce this randomness.

Finally, we consider a restricted error model that aims at capturing "missing data" corruptions. In this model, we show that distributions that are close to monotone have sampling correctors that are significantly more efficient than achievable by the learning approach.

Joint work with Themis Gouleakis (CSAIL, MIT) and Ronitt Rubinfeld (CSAIL, MIT and Tel Aviv University).

Mrinal Kumar

Rutgers University

**Abstract:**

Starting with a beautiful result of Gupta et al in 2012, the last few years have seen exciting progress on the problem of proving lower bounds for interesting special classes of homogeneous depth four arithmetic circuits. These lower bounds are particularly interesting since they seem to come tantalizingly close to resolving the algebraic analog of the P vs NP conjecture.

I will talk about these developments and end with a discussion of a recent exponential lower bound for general homogeneous depth 4 arithmetic circuits. It is known that any asymptotic improvement in the exponent of this lower bound would imply super-polynomial lower bounds for general arithmetic circuits.

Based on joint work with Shubhangi Saraf.

Tsvi Kopelowitz

University of Michigan

**Abstract:**

The 3SUM hardness conjecture has proven to be a valuable and popular tool for proving conditional lower bounds on the complexities of dynamic data structures and graph problems. This line of work was initiated by Patrascu [STOC 2010] and has received a lot of recent attention. Most of these lower bounds are based on reductions from 3SUM to a special set intersection problem introduced by Patrascu, which we call Patrascu's Problem. However, the framework introduced by Patrascu that reduces 3SUM to Patrascu's Problem suffers from some limitations, which in turn produce polynomial gaps between the achievable lower bounds via this framework and the known upper bounds.

We address these issues by providing a tighter and more versatile framework for proving 3SUM lower bounds via a new reduction to Patrascu's Problem. Furthermore, our framework does not become weaker if 3SUM can be solved in truly subquadratic time, and provides some immediate higher conditional lower bounds for several problems, including for set intersection data-structures. For some problems, the new higher lower bounds meet known upper bounds, giving evidence to the optimality of such algorithms.

During the talk, we will discuss this new framework, and show some new (optimal) lower bounds conditioned on the 3SUM hardness conjecture. In particular, we will demonstrate how some old and new triangle listing algorithms are optimal for any graph density, and, time permitting, prove a conditional lower bound for incremental Maximum Cardinality Matching which introduces new techniques for obtaining amortized lower bounds.

Joint work with Shubhangi Saraf.

Igor Shinkar

NYU

**Abstract:**

An (n,k)-bit-fixing source is a distribution on n bit strings, that is fixed on n-k of the coordinates, and uniform on the remaining k bits. Explicit constructions of extractors for bit-fixing sources by Gabizon, Raz and Shaltiel (SICOMP 2006) and Rao (CCC 2009) extract (1-o(1))k bits for k = polylog(n), almost matching the probabilistic argument. Intriguingly, unlike other well-studied sources of randomness, a result of Kamp and Zuckerman (SICOMP 2006) shows that, for any k some small portion of the entropy in an (n,k)-bit-fixing source can be extracted. Although the extractor does not extract all the entropy, it does extract log(k)/2 bits.

In this work we prove that when the entropy k is small enough compared to n, this exponential entropy-loss is unavoidable, and it is impossible to extract more than log(k)/2 bits from (n,k)-bit-fixing sources. In some sense the remaining entropy is inaccessible, information theoretically.

In fact, our impossibility result holds for what we call zero-fixing sources. These are bit-fixing sources where the fixed bits are set to 0. We complement our negative result, by giving an explicit construction of an (n,k)-zero-fixing extractor, that outputs Omega(k) bits, even for k = polyloglog(n).

Furthermore, we give a construction of an (n,k)-bit-fixing extractor, for entropy k = (1+o(1))loglog(n), with running time n^polyloglog(n). We also give a new construction of an (n,k)-bit-fixing extractor, for entropy k = polylog(n) based on multi-source extractors.

Joint work with Gil Cohen

Nisheeth Vishnoi

EPFL

**Abstract:**

In the last few years, there has been a significant interest in the computational abilities of Physarum Polycephalum (a slime mold). This drew from a remarkable experiment which showed that this organism can compute shortest paths in a maze. Subsequently, the workings of Physarum were mathematically modeled as a dynamical system and algorithms inspired by this model were proposed to solve several graph problems. If these algorithms could be shown to work, it would raise the tantalizing possibility that nature, via evolution, has developed algorithms that could efficiently solve some of the most complex graph problems. An important step towards this was taken by Becchetti et al. who proved that one such algorithm for the shortest path problem on undirected graphs is efficient. In this talk I will show that Physarum-based algorithms can also efficiently solve flow problems on undirected and directed graphs.

This is joint work with Damian Straszak.

Li-Yang Tan

Simons Institute at UC Berkeley

**Abstract:**

We prove an average-case depth hierarchy theorem for Boolean circuits over the standard basis of AND, OR, and NOT gates. Our hierarchy theorem says that for every $d \geq 2$, there is an explicit $n$-variable function Boolean function $f$, computed by a linear-size depth-$d$ formula, which is such that any depth-$(d-1)$ circuit that agrees with $f$ on $(1/2 + o_n(1))$ fraction of all inputs must have size $\exp(n^{\Omega(1/d)}).$ This answers an open question posed by Håstad in his Ph.D. thesis.

Our average-case depth hierarchy theorem implies that the polynomial hierarchy is infinite relative to a random oracle with probability 1, confirming a conjecture of Håstad, Cai, and Babai. We also use our result to show that there is no "approximate converse" to the results of Linial, Mansour, Nisan and Boppana on the total influence of small-depth circuits, thus answering a question posed by O'Donnell, Kalai, and Hatami.

A key ingredient in our proof is a notion of random projections which generalize random restrictions.

Joint work with Ben Rossman and Rocco Servedio.

Ryan O'Donnell

CMU

**Abstract:**

A quantum experiment produces a particle that can be in one of d unknown orthogonal states v_1, ... v_d in C^d. In fact, it's a randomized experiment, so the particle's full state is a probability distribution p_1, ..., p_d over v_1, ..., v_d. (In other words, it's given by the density matrix rho = p_1| v_1 > < v_1| + ... + p_d |v_d > < v_d|.) The experimenter wishes to test whether the probability distribution (p_1, ..., p_d) (i.e., rho's spectrum) has some property. Examples include:

The experimenter can prepare n copies of the state and then measure them. The goal is to minimize n as a function of d.

We describe an approach to proving tight upper and lower bounds for these kinds of problems. The approach uses the asymptotic representation theory of the symmetric group; in particular Kerov's algebra of polynomial functions on Young diagrams.

This is joint work with John Wright (CMU).

Mahesh Viswanathan

University of Illinois Urbana-Champaign

**Abstract:**

Probabilistic automata are finite state machines that roll dice in each step to decide the next state on reading an input symbol. Such machines were first introduced by Rabin in the 1960s as a computational model on finite words, and, more recently, the theory has been extended to consider infinite length inputs. This talk will survey results about such machines, contrasting it with the theory of regular languages, and discuss open problems and applications to model checking.

Results presented will include joint work with Rohit Chadha, Dileep Kini, and Prasad Sistla.

Igor C. Oliveira

Columbia University

**Abstract:**

The study of monotonicity and negation complexity for Boolean functions has been prevalent in complexity theory as well as in computational learning theory, but little attention has been given to it in the cryptographic context. Recently, Goldreich and Izsak (2012) have initiated a study of whether cryptographic primitives can be monotone, and showed that one-way functions can be monotone (assuming they exist), but a pseudorandom generator cannot.

In this paper, we start by filling in the picture and proving that many other basic cryptographic primitives cannot be monotone. We then initiate a quantitative study of the power of negations, asking how many negations are required. We provide several lower bounds, some of them tight, for various cryptographic primitives and building blocks including one-way permutations, pseudorandom functions, small-bias generators, hard-core predicates, error-correcting codes, and randomness extractors. Among our results, we highlight the following.

i) Unlike one-way functions, one-way permutations cannot be monotone. ii) We prove that pseudorandom functions require log n - O(1) negations (which is optimal up to the additive term). iii) Error-correcting codes with optimal distance parameters require log n - O(1) negations (again, optimal up to the additive term). iv) We prove a general result for monotone functions, showing a lower bound on the depth of any circuit with t negations on the bottom that computes a monotone function f in terms of the monotone circuit depth of f.

Joint work with: Siyao Guo, Tal Malkin and Alon Rosen

Jin-Yi Cai

University of Wisconsin - Madison

**Abstract:**
The Fisher-Kasteleyn-Temperley (FKT) algorithm can count the number of
perfect matchings over planar graphs in polynomial time. For four decades
this stood as *the* important counting problem that has a P-time algorithm
over planar graphs while the same problem over general graphs is intractable.
In 2001, Les Valiant introduced matchgates. And subsequently he introduced
holographic algorithms based on matchgates. They solve a number of counting
problems over planar graphs, which are #P-hard over general graphs.

Over the past decade, a substantial theory has been developed, which aims to classify a broad class of counting problems by the local constraint functions that define them. Out of this work, a strong theme has emerged, which supports the following sweeping statement: All such locally defined counting problems can be classified into *exactly* three categories: (1) those that are P-time solvable over general graphs; (2) those that are P-time solvable over planar graphs but #P-hard over general graphs; and (3) those that remain #P-hard over planar graphs. Moreover, category (2) consists *precisely* of those problems that can be captured by Valiant's holographic reduction to the FKT. In other words, Valiant's holographic reduction followed by the FKT appears to be a *universal* method. This sweeping statement is supported by a number of complexity dichotomy theorems of ever broader scope.

So the question is: Is Valiant + FKT universal?

In this talk, I will answer this question.

Joint work with: Zhiguo Fu, Heng Guo and Tyson Williams
** Friday, May 15:
**

Noah Stephens-Davidowitz

NYU

**Abstract:**
We give a $2^{n+o(n)}$-time algorithm for the shortest vector problem
on lattices. The previous best-known algorithm of Micciancio and Voulgaris
runs in time $2^{2n+o(n)}$. The algorithm is based on an elementary yet
powerful observation that by properly combining samples from a Gaussian
distribution over the lattice, we can produce samples from a \emph{narrower}
Gaussian distribution on the lattice. We use this to sample from an arbitrarily
narrow Gaussian distribution over the lattice, allowing us to find a shortest
vector.

Joint work with Divesh Aggarwal, Daniel Dadush, and Oded Regev

Aaron Bernstein

Columbia University

**Abstract:**
I will talk about our recent paper on fully dynamic approximate matching,
which will appear in ICALP ‘15. Given a dynamic graph G, the goal is to
maintain an approximately maximum matching as edges are being
inserted into and deleted from G. Looking at the state of the art, we see
that maintaining an approximate matching actually breaks down into 2 very
different problems: maintaining a 2-or-worse approximation, and maintaining
a better-than-2 approximation. The reason for this is that in the former case,
it is enough to maintain a *maximal* matching, which turns out to be much
easier. For the former case, the state of the art maintains a 2-approximation
and requires only O(log(n)) amortized time per edge change in G. For the
latter case, the state of the art maintains a (1+eps) approximation but
requires O(m^1/2) time per edge change; nothing faster than O(m^1/2)
was known for this problem, even if we allowed a 1.99 approximation.

We present an algorithm that goes beyond this barrier in *bipartite* graphs. In particular, our main result maintains a (3/2+eps)-approximation in update time O(m^1/4). This is the fastest algorithm to maintain a better-than-2 approximation, and is also the fastest deterministic algorithm for *any* constant approximation. We also show how to maintain a (1+eps)-approximation with update time O(log(n)) if the bipartite graph has constant arboricity. Previous results that focused on fast algorithms for the constant arboricity case only achieved a 2-approximation.

Joint work with Cliff Stein.

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
`