October 6: Toniann Pitassi (University of Toronto), Separating the analogs of NP, BPP and P in the NOF Multiparty Communication Model
Number-on-forehead communication protocols are a fascinating model of
computation where k collaborating players are trying to evaluate a function, f,
where the input to the function is partitioned into k pieces, where the
i-th piece, $x_i$, is placed on player $i$'s forehead. Thus each player sees
all but his/her own input. In order to compute $f$, the players communicate
by writing bits on a shared blackboard and the complexity of the protocol
is the number of bits that are communicated. This model is very important
has found applications in a surprising variety of areas, including circuit
complexity, pseudorandomness, and proof complexity.
In this model, a protocols is said to be efficient if it has complexity
polylogn. Correspondingly, $P^{cc}_k$, $BPP^{cc}_k$, and $NP^{cc}_k$
are the NOF communication complexity analogs of the standard complexity
classes. For example, $RP^{cc}_k$ is the class of functions having
efficient one-sided-error communication complexity, and one of the
most fundamental open problems is to separate these classes.
In this talk we will discuss two new results.
Our first result (joint with Paul Beame, Matei David and
Philipp Woelfel), gives a function that has an efficient
randomized protocol, but requires linear complexity in
the deterministic model, for up to $k=n^{\epsilon}$ players.
Thus we separate $BPP^{cc}_k$ from $P^{cc}_k$.
In our second theorem (joint with Matei David and Emanuele Viola),
we exhibit an explicit function that can be computed by a
nondeterministic NOF protocol communicating $O(logn)$ bits but requiring
nearly linear number of bits of communication for randomized NOF protocols
with $k=\delta \log n$ players for any fixed $\delta <1$.
Thus, we separate $NP^{cc}_k$ from $RP^{cc}_k$.
The first proof is unusual in that it is nonconstructive; for
the second proof, we simplify and extend ideas from several recent
breakthrough papers (Sherstov, Lee-Shraibman, and Chattopadhyay-Ada).
Finally we will discuss recent extensions of our second result
(Beame and Huynh-Ngoc), and applications of these results
in proof complexity.
October 13: Alexander Razborov (University of Chicago), A simple proof of Bazzi's theorem
Pseudo-random generators that are secure against constant depth polynomial size circuits have been
known since the seminal paper by Ajtai and Wigderson (1985). All available constructions of such
generators, however, appear to be somewhat special and ad hoc. In 1990, Linial and Nisan made a
bold and elegant conjecture stating that this property is in fact possessed by any generator in which
any selection of polylogarithmically many output bits is independent; examples of such generators
are abundant. This conjecture turned out surprisingly difficult, and it was only the last year that
Bazzi proved it for the case of DNF formulas. The main purpose of our talk is to present a
substantially simplified version of his proof.
October 23: Prahladh Harsha (University of Texas at Austin), The Communication Complexity
of Correlation
In this talk, we examine the communication required for generating
correlated random variables remotely. Consider a pair of joint random
variables (X,Y). Suppose Alice is given a sample x distributed
according to X, and she has to send a message to Bob who is then
required to generate a value with distribution exactly Y|_{X=x} (i.e,
the conditional distribution of Y given X=x). We consider the minimum
expected number of bits (which we call C(X:Y)) Alice needs to send Bob
to achieve this. We show that if Alice and Bob are allowed to share
random bits (independent of Alice's input x), then Alice need send no
more than approximately the mutual information number of bits. More
formally,
I[X:Y] <= C(X:Y) <= I[X:Y] + O(log I[X:Y]) + O(1)
where I[X:Y] = H[X] + H[Y] - H[X,Y] is the mutual information between
the random variables X and Y.
As an application of this characterization of mutual information, we
derive a direct sum theorem in communication complexity that
substantially improves the previous such result shown by Jain et al
2003.
Our proofs are based on a rejection sampling procedure that relates
the relative entropy between two distributions to the communication
complexity of generating one distribution from the other.
October 30: Gil Kalai (Hebrew University and Yale
University), Noise Sensitivity, Noise Stability, Percolation and some connections to TCS
Noise sensitivity was defined in a paper by Benjamini, Kalai, and Schramm (1999).
A closely related notion was considered by Tsirelson and Vershik. I will describe the notion of noise sensitivity of Boolean functions and some basic results and problems related to it. A fun way to explain it (especially after 2000) is in terms of the probability that small mistakes in counting the votes in an election will change the outcome. We will consider the following:
November 3: Nathan Srebro (TTI-C), On the Informational Cost of Tractability
As with many other machine learning problems, most formulations of
clustering correspond to non-convex, NP-hard, optimization problems.
Yet, when the data really is clustered, and enough data is available,
local search and other heuristics tend to be able to recover the
clustering. At an extreme regime, we can even prove the clustering is
tractably recoverable. On the other extreme, if the data is not well
clustered, or not enough data is available, the "optimal" clustering,
although hard to find, is meaningless. This leads to the common wisdom
that "clustering isn't hard: its either easy, or not interesting".
Is it in-fact the case that when a meaningful clustering is
statistically recoverable, it is also easy to find computationally? If
so, we certainly do not have a rigorous understanding of why this is
the case. Or, is there a regime in which the clustering is
statistically recoverable, but not tractably recoverable? E.g., might
we need more samples in order to ensure that our recovery methods
work, beyond what is statistically necessary if we had infinite
computational power? Can we quantify this increase in the required
sample size due to our computational limitations?
In this talk I will discuss the above issues, mostly in the context of
clustering data from a mixture of Gaussians, but also in some other
machine learning problems. I will also mention other ways in which
increasing the size of the data reduces, rather than increases, the
amount of required computation, contrary to the standard approach of
studying the complexity of computation as increasing with the size of
the data.
November 10: Ketan Mulmuley (University of Chicago),
On P vs NP and Geometric Complexity Theory
This series of two talks on November 10--one in logic seminar
and one in theory seminar--will complement a series of
three high level colloquium talks on GCT on November 5, 12 and 19 (2.30
p.m.).
Geometric complexity theory (GCT) is an approach to the P vs. NP problem
via
algebraic geometry, representation theory, and the theory of a new class
of quantum groups, called nonstandard quantum groups, that arise in
this approach. In particular, GCT says that the P vs. NP problem
in characteristic zero is intimately linked to the Riemann Hypothesis
over finite fields. These complementary talks would elaborate on the
basic notion of obstructions in GCT.
No background in algebraic geometry, representation theory or quantum
groups would be assumed.
References for GCT:
The basic plan of GCT is given in:
GCTflip: "On P vs. NP, Geometric Complexity Theory and the Flip I: high
level view".
It has been partially implemented in a series of papers:
GCT1 to GCT11.
GCT1 to 4: Joint with Milind Sohoni
GCT5: Joint with Hari Narayanan
GCTflip, its abstract (GCTabs), and GCT1-8 are available on
the speaker's personal home page. GCT8-11 are under preparation.
November 17: Gyorgy Turan (University of Illinois at Chicago),
Cube Partitions and Decision Trees
It is an often discovered result that every k-term DNF can
have at most 2^k - 1 prime implicants and this bound is sharp.
We complete this result by giving an explicit description of
all k-term DNF with the maximal number of prime implicants:
these are DNF that can be represented as a certain kind of
decision tree.
The proof uses a splitting lemma for partitions
of the hypercube into neighboring cubes. We then consider the
splittability of general cube partitions, measuring the
influence of variables for the cube partition. We also discuss
the connection between this topic and decompositions of
complete graphs into complete bipartite graphs. Time permitting, we
mention several related open problems.
This is joint work with Bob Sloan and Balazs Szorenyi.
November 20: Yuri Makarychev (Microsoft Research),
On the Advantage over Random for Maximum Acyclic Subgraph
We will describe a new approximation algorithm for the
Maximum Acyclic Subgraph Problem. Given an instance where the maximum acyclic
subgraph contains 1/2 + \delta fraction of all edges, our algorithm
finds an acyclic subgraph with 1/2 + \Omega(\delta/log n)
fraction of all edges. We will also describe our integrality gap
instance, which was recently used by Guruswami, Manokaran,
and Raghavendra to prove a UGC-inapproximability result for this problem.
This is joint work with Moses Charikar and Konstantin
Makarychev (appeared at FOCS'07).
November 25: Michael Mahoney (Stanford University),
Statistical Leverage and Improved Matrix Algorithms
Given an m x n matrix A and a rank parameter k, define the leverage of the i-th row of A to be the i-th diagonal element of the projection matrix onto the span of the top k left singular vectors of A. Historically, this statistical concept (and generalizations of it) has found extensive applications in, e.g, diagnostic regression analysis. Recently, this concept has been central in the development of improved algorithms for several fundamental matrix problems. Two examples of this will be described. The first problem is the least squares approximation problem, in which there are n constraints and d variables. Classical algorithms, dating back to Gauss and Legendre, use O(nd2) time. We describe a randomized algorithm that uses only roughly O(n d log d) time to compute a
relative-error, i.e., 1+/-epsilon, approximation. The second problem is the problem of selecting a ``good'' set of exactly k columns from an m x n matrix, and the algorithm of Gu and Eisenstat provides the best previously existing result. We describe a two-stage algorithm that improves on their result (assuming that k is small). Recent application of these ideas in modern statistical data analysis will be briefly described.
December 1: James Lee (University of Washington),
Eigenvalue bounds, spectral partitioning, and flow deformations
We present a new approach to upper bounds on the eigenvalues of the Laplacian on finite graphs. Such bounds are used to analyze the efficacy of popular spectral partitioning heuristics. Whereas previous methods, e.g. those of Spielman and Teng in the setting of graphs, and Hersch in the setting of surfaces, relied on conformal mappings into a model space, our approach is intrinsic.
We use a certain kind of multi-commodity flow at optimality to deform the geometry of the graph. As the flow spreads out, the graph becomes more uniform. We then embed this geometry into Euclidean space to recover a bound on the eigenvalues. Analyzing the structure of the optimal flow requires arguments from geometric combinatorics.
In particular, we are able to resolve a conjecture of Spielman and Teng that gives optimal eigenvalue bounds for graphs which exclude any fixed minor. Unlike previous spectral approaches, we can obtain separators without a bounded degree assumption; although the second eigenvector may perform poorly in this setting, we show that our test vector still gives a \sqrt{n}-sized separator, yielding an alternate proof of the Alon-Seymour-Thomas theorem on separators in non-planar graphs.
January 9: Scott Aaronson (MIT),
The Limits of Advice
Since the work of Karp and Lipton in the 1980s,
complexity theorists have grown to love the /poly operator, which adds
a polynomial-size "advice string" to any complexity class. But it's
interesting to consider much more general kinds of "advice objects"
than just strings. In this talk, I'll present a new framework for
understanding the limitations of advice objects. Results include the
following:
* Given as "advice" a black box that computes an arbitrary Boolean
function f drawn from a set of singly exponential size, we can
simulate that black box using an *untrusted* black box combined with a
polynomial-size advice string.
* The complexity class BQP/qpoly, or quantum polynomial-time with
polynomial-size quantum advice, is contained in QMA/poly. Indeed,
given any language L in BQP/qpoly, one can give a local Hamiltonian H
on poly(n) qubits such that any ground state of H is a valid
quantumadvice state for L.
* A polynomial-space quantum computer that can flip an "advice coin"
an unlimited number of times, can be simulated in PSPACE/poly. This
is so despite the surprising fact that a bounded-space quantum
computer can detect arbitrarily small changes in the bias of a coin.
Joint work with my student Andy Drucker.
January 12: Nicole Immorlica (Nortwestern University),
The Role of Compatibility in Technology Diffusion on Social Networks
In many settings, competing technologies -- for example, operating
systems, instant messenger systems, or document formats -- can be seen
adopting a limited amount of compatibility with one another; in other
words, the difficulty in using multiple technologies is balanced
somewhere between the two extremes of impossibility and effortless
interoperability. There are a range of reasons why this phenomenon
occurs, many of which -- based on legal, social, or business
considerations -- seem to defy concise mathematical models. Despite
this, we show that the advantages of limited compatibility can arise
in a very simple model of diffusion in social networks, thus offering
a basic explanation for this phenomenon in purely strategic terms. Our
approach builds on work on the diffusion of innovations in the
economics literature, which seeks to model how a new technology A
might spread through a social network of individuals who are currently
users of technology B. We consider several ways of capturing the
compatibility of A and B, focusing primarily on a model in which users
can choose to adopt A, adopt B, or -- at an extra cost -- adopt both A
and B. We characterize how the ability of A to spread depends on both
its quality relative to B, and also this additional cost of adopting
both, and find some surprising non-monotonicity properties in the
dependence on these parameters: in some cases, for one technology to
survive the introduction of another, the cost of adopting both
technologies must be balanced within a narrow, intermediate range. We
also extend the framework to the case of multiple technologies, where
we find that a simple model captures the phenomenon of two firms
adopting a limited "strategic alliance" to defend against a new, third
technology.
Joint work with J. Kleinberg, M. Mahdian, and T. Wexler.
January 26: Paolo Codenotti (University of Chicago),
Isomorphism of Hypergraphs of Low Rank in Moderately Exponential Time
We give an algorithm to decide isomorphism of k-hypergraphs in
time exp(O~(k2\sqrt{n})), where n is the number of vertices.
(The tilde refers to a polylogarithmic factor.) The case of
bounded k answers a 24-year-old question and removes an obstacle
to improving the exp(O~(\sqrt{n})) worst-case bound for Graph
Isomorphism testing. The best previously known bound, even for
k=3, was C^n (Luks 1999; Luks puts no restriction on k). Our
analysis combines combinatorial and group theoretic methods.
Joint work with Laszlo Babai.
February 6: Subhash Khot (New York University),
Inapproximability of NP-complete problems, Discrete Fourier
Analysis, and Geometry
This talk will give an overview of some recent results on inapproximability of NP-complete problems and connections
to discrete Fourier analysis and geometry.
February 16: Caroline Klivans (University of Chicago),
Combinatorial Laplacians
The graph Laplacian is a well-known and well-studied matrix
associated to a graph. The eigenvalues, for example, have been used
for embeddings, clustering and coloring.
The combinatorial Laplacian is a higher dimensional analogue for more
general cell complexes. The combinatorial Laplacian first appeared as
a discrete version of the usual Laplacian on differential forms for a
Riemannian manifold and was later utilized for efficient computations
of Betti numbers. These results gave rise to a number of questions
concerning the Laplacian spectra and its combinatorial significance.
I will give a brief survey of this operator and discuss recent work on
cellular matrix tree theorems which, analogous to the graphical case,
enumerate spanning trees of a complex using the combinatorial Laplacian.
February 23: Dhruv Mubayi (University of Illinois at Chicago),
Coloring Simple Hypergraphs
Improvements of the obvious lower bounds on the independence number
of (hyper)graphs have had impact on problems in discrete geometry,
coding theory, number theory and combinatorics. One of the most
famous examples is the result of Komlos-Pintz-Szemeredi (1982) on
the independence number of 3-uniform hypergraphs which made
important progress on the decades old Heilbronn problem.
We give a sharp upper bound on the chromatic number of simple
k-uniform hypergraphs that implies the above result as well as more
general theorems due to Ajtai-Komlos-Pintz-Spencer-Szemeredi, and
Duke-Lefmann-Rodl. Our proof technique is inspired by work of
Johansson on graph coloring and uses the semi-random or nibble
method. This is joint work with Alan Frieze.
March 2: Lance Fortnow (Nortwestern University),
Program Equilibria and Discounted Computation Time
Tennenholtz developed Program Equilibrium to model
play in a finite two-player game where each player can base
their strategy on the other player's strategies. Tennenholtz's
model allowed each player to produce a "loop-free'' computer
program that had access to the code for both players. He showed
a folk theorem where any mixed-strategy individually rational
play could be an equilibrium payoff in this model even in a
one-shot game. Kalai et al. gave a general folk theorem for
correlated play in a more generic commitment model.
We develop a new model of program equilibrium using general
computational models and discounting the payoffs based on the
computation time used. We give an even more general folk
theorem giving correlated-strategy payoffs down to the pure
minimax of each player. We also show equilibrium in other games
not covered by the earlier work.
March 6: Allan Borodin (University of Toronto),
Sequential Elimination Graphs and Simple Combinatorial Algorithms
The local ratio framework introduced by Bar Yehuda and Evan in 1981
provides a unified framework for many approximation algorithms.
Recently, the local ratio technique has been used to provide
efficient approximation algorithms for a number of packing
problems. Motivated by these recent algorithms,
Akcoglu, Aspnes, DasGupta and Kao suggested a new class of graphs
extending the class of chordal graphs. Namely,
"sequential k-independent graphs" generalize the concept
of a perfect elimination ordering by allowing the ``local neighborhood''
of each vertex in the ordering to have independence number k.
We study this class of graphs and show how various graph problems
can be efficiently approximated by conceptually simple combinatorial algorithms.
We also compare this new graph class to other known classes of graphs
For example, planar grpahs are sequentially 3-independent.
Sequential k-independent graphs are another example of the more general
concept of sequential elimimation
graphs.
The results in this talk are based on work by Yuli Ye.
March 30: Raghav Kulkami (University of Chicago),
Any monotone property of sparse graphs is evasive
We call an n-vertex graph "sparse" if its number of edges is O(n).
A graph property is said to be ''evasive'' if, in order to decide its membership,
one needs to query all {n \choose 2} possible edges in wosrt case.
Karp conjectures that any non-trivial monotone graph property
must be evasive. It is a longstanding open question.
We prove Karp's conjecture when
restricted to 'sparse' graphs, i.e.,
we show that any non-trivial monotone decreasing
property of n-vertex 'sparse' graphs is 'evasive' for all large enough n.
We use the topological approach proposed by Kahn, Saks and
Sturtevant [1984] as a black box. The extra component of our method is a
further connection to analytic number theory. In particular, we
construct new group actions which rely crucially on some deep
and interesting properties of the numbers. Under the Generalized
Reimann Hypothesis, we can further stregthen our result to
show that any monotone property of ''weakly sparse'' graphs is evasive,
where 'weakly sparse' means that the number of edges are bounded by
O(n^{5/4 - \epsilon}). We give an evidence that this can be further
improved to O(n^3/2) but these bounds are far from the desired
{n \choose 2} bound.
This is a joint work with Anandam Banerjee, Department of Mathematics, Northeastern University
and Vipul Naik, Department of Mathematics, University of Chicago.
April 6: Mark Braverman (Microsoft Research), Poly-logarithmic Independence Fools AC0 Circuits
We will describe the recent proof of the 1990 Linial-Nisan conjecture. The conjecture states that bounded-depth boolean circuits cannot distinguish poly-logarithmically independent distributions from the uniform one. The talk will be almost completely self-contained.
April 13: Hariharan Naranayan (University of Chicago),
Random Walks on Polytopes and an Affine Interior Point Algorithm for Linear Programming
Let K be a polytope in R^n defined by m linear inequalities. We give a new Markov Chain algorithm to draw a nearly uniform sample from K. The underlying Markov Chain is the first to have a mixing time
that is strongly polynomial when started from a ``central'' point x. If s is the supremum over all chords pq passing through x of |p-x|/|q-x| and \epsilon is
an upper bound on the desired total variation distance from the uniform, it is sufficient to take O(m n( n log (s m) + log 1/\epsilon)) steps of the random walk. We use this result to design an affine interior point algorithm that does a single random walk to approximately solve linear programs with high probability in polynomial time.
The fact that this algorithm has a run-time
that is provably polynomial is notable since the run-time of the analogous deterministic affine algorithm analyzed by Dikin has no known polynomial
guarantees. This is work with Ravi Kannan.
April 20: Stephen Smale (TTI-C),
Some perspectives on complexity theory
I will give my viewpoint on the power of the concept "polynomial time" in
science, as well as some limitations and pitfalls.
April 27: Zeev Dvir (IAS),
Recent progress on Kakeya sets, mergers and extractors
Kakeya sets (in vector spaces over finite fields) are sets
that contain a line in every direction. It was conjectured by Wolff
in 1999 that every Kakeya set has positive density (its size is a
constant fraction of the whole space). This conjecture is motivated by
several problems in mathematics and in computer science. In
particular, it has a tight connection with explicit constructions of
'extractors' and 'mergers' which are efficient procedures that
transform weak sources of randomness into strong ones and have many
applications.
In this talk I will show the recent proof of Wolff's conjecture [D.
08], the application of the proof technique to the construction of
mergers and extractors [D. Wigderson 08] and a new work [D. Kopparty
Sudan Saraf 09] that extends the methods in earlier papers to derive
near optimal bounds on Kakeya sets and mergers.
May 4: Ronen Basri (Weizmann Institute and TTI-C),
Visibility Constraints on Features of 3D Objects
To recognize three-dimensional objects it is important to model how
their appearances can change due to changes in viewpoint. A key aspect
of this involves understanding which object features can be
simultaneously visible under different viewpoints. We address this
problem in an image based framework, in which we use a limited number
of images of an object taken from unknown viewpoints to determine
which subsets of features might be simultaneously visible in other
views. This leads to the problem of determining whether a set of
images, each containing a set of features, is consistent with a single
3D object. We assume that each feature is visible from a disk of
viewpoints on the viewing sphere. In this case we show the problem is
NP-hard in general, but can be solved efficiently when all views come
from a circle on the viewing sphere. We also give iterative algorithms
that can handle noisy data and converge to locally optimal solutions
in the general case. Our techniques can also be used to recover
viewpoint information from the set of features that are visible in
different images. We show that these algorithms perform well both on
synthetic data and images from the COIL dataset.
Joint work with Pedro Felzenswalb, Ross Girshick, David Jacobs, and
Caroline Klivans
May 11: David Xiao (Princeton University),
On the Black-box Complexity of PAC Learning
The PAC model (Valiant, CACM ’84) is one of the central
models studied in computational learning theory. There is evidence
that many specific classes of functions (e.g. intersections of half-
spaces, parity functions with noise, etc.) are hard to learn by
efficient algorithms, and cryptographic assumptions imply that
learning small circuits is hard. We say that PAC learning is hard if
no efficient algorithm can learn all functions computable by small
circuits.
In this talk, we show that the black-box complexity of PAC learning
lies strictly between NP and ZK. More precisely, if P = NP then PAC
learning is easy and if ZK !=BPP then PAC learning is hard, but black-
box techniques (with some additional restrictions) do not suffice to
prove equivalence in either case.
With regard to NP, we rule out non-adaptive reductions using a PAC
learning oracle to solve an NP-complete problem by showing this would
imply that coNP in contained in AM, which is considered implausible.
With regard to ZK, we rule out relativizing proofs that ZK !=BPP based
on hardness of learning. Using the characterization of ZK of Ong and
Vadhan (EUROCRYPT ’07), we also show that any black-box construction
of a (computational) ZK protocol for a language L based on hardness of
learning implies that L actually has a statistical zero knowledge
proof (i.e. L is in SZK), and hence such a black-box construction is
unlikely to exist for NP-complete languages.
Parts of this talk are based on joint work with Benny Applebaum and
Boaz Barak.
May 18: Igor Pak (University of Minnesota),
Combinatorics and complexity of partition bijections
The study of partition identities has a long history going back to
Euler, with applications ranging from Analysis to Number Theory, from
Enumerative Combinatorics to Probability. Partition bijections is a
combinatorial approach which often gives the shortest and the most
elegant proofs of these identities. These bijections are then often
used to generalize the identities, find "hidden symmetries", etc. In
the talk I will present a modern approach to partition bijections
based on the complexity ideas and geometry of random partitions. We
show that certain "natural" bijections do not exist, even for some
classical partition identities.
May 26: Eli Ben-Sasson (Technion),
Affine Dispersers from Subspace Polynomials
An affine disperser over a field F for sources of dimension d is a function f: F^n -> F that is nonconstant (i.e., takes more than one value) on inputs coming from a d-dimensional affine subspace of F^n.
Affine dispersers have been considered in the context of deterministic extraction of randomness from structured sources of imperfect randomness, and in particular, generalize the notion of dispersers for bit-fixing sources. Previously, explicit constructions of affine dispersers were known for every d=\Omega(n), due to [Barak, Kindler, Shaltiel, Sudakov and Wigderson] and [Bourgain]. (The latter in fact gives stronger objects called affine extractors).
In this work we give the first explicit affine dispersers for sublinear dimension. Specifically, our dispersers work even when d> n^{4/5}.
The main novelty in our construction lies in the method of proof, which relies on elementary properties of subspace polynomials. In contrast, the previous works mentioned above relied on sum-product theorems for finite fields.
Time permitting we shall discuss recent work which shows that some of our constructions are in fact affine extractors, i.e., the output of f is almost uniformly distributed on F.
Joint work with Swastik Kopparty.
September 15: Jin-Yi Cai (University of Wisconsin),
A Dichotomy Theorem for Graph Homomorphisms with Complex Values
Graph homomorphism (Lov\'{a}sz 1967) has been studied intensively by many researchers over the decades. In the physics community it is called Partition Function.
The problem can be stated as follows:
Given an $m \times m$ symmetric matrix $A$ over the complex field,
compute the function $Z_A(\cdot)$,
where for an arbitrary input graph $G$,
\[ Z_A(G) =
\sum_{\xi:V(G)\rightarrow [m]} \prod_{(u,v)\in E(G)} A_{\xi(u),\xi(v)}.\]
The problem encompasses many combinatorial counting problems
such as counting vertex covers, graph colorings etc.
We prove a complexity dichotomy theorem, that the problem is
either computable in P or \#P-hard, depending in $A$.
The complex field affords much possibility for cancelations
and thus non-trivial polynomial time algorithms. Indeed Fourier
matrices and character sums play a major role. In the complex
domain, there are also natural connections to holographic
algorithms. Due to the complexity of the proof, we will only
be able to give a rough outline.
Joint work with Xi Chen of Princeton and Pinyan Lu of Tsinghua.
Paper available on http://arxiv.org/abs/0903.4728 (111 pages.)
October 5: Dieter van Melkebeek (University of Wisconsin),
Satisfiability Allows No Nontrivial Sparsification Unless The
Polynomial-Time Hierarchy Collapses
Consider the following two-player communication process to decide a language
L: The first player holds the entire input x but is polynomially
bounded; the second player is computationally unbounded but does not know
any part of x; their goal is to cooperatively decide whether x belongs to L
at small cost, where the cost measure is the number of bits of communication
from the first player to the second player.
For any integer d>=3 and positive real epsilon we show that if
satisfiability for n-variable d-CNF formulas has a protocol of
cost O(n^{d-\epsilon}) then coNP is in NP/poly, which implies that the
polynomial-time hierarchy collapses to the third level. The result
even holds for conondeterministic protocols, and is tight
as there exists a trivial deterministic protocol for epsilon = 0.
Under the hypothesis that coNP is not in NP/poly, our result implies
tight lower bounds for parameters of interest in several areas, including
sparsification, probabilistically checkable proofs, instance compression,
and kernelization in parameterized complexity.
Joint work with H. Dell.
October 20: Janos Simon (University of Chicago),
Sorting by Random Insertion
We analyze the number of comparisons made by the following randomized sorting algorithm:
While the array is not sorted, choose a pair of elements and compare them.
At each stage we choose uniformly at random among the pairs whose relationship was not determined by the previous stages.
We obtain matching asymptotic upper and lower bounds.
(Joint work with Mark Braverman.)
November 3: Anastasios Sidiropoulos (TTI-C),
Graph Genus and Random Partitions
We study the quantitative geometry of graphs with small genus. In
particular, we exhibit new, optimal random partitioning schemes for
such graphs. Using these geometric primitives, we give exponentially
improved dependence on genus for a number of problems like approximate
max-flow/min-cut theorems, approximations for uniform and non-uniform
Sparsest Cut, treewidth approximation, Laplacian eigenvalue bounds,
Lipschitz extension theorems, and various embeddings into normed
spaces.
We list here a sample of these improvements. All the following
statements refer to graphs of genus g.
- We show that such graphs admit an O(log g)-approximate
multi-commodity max-flow/min-cut theorem for the case of uniform
demands. This bound is optimal, and improves over the previous bound
of O(g) [KPR93,FT03]. For non-uniform demands, we give a bound of
O(sqrt(log g)(log n)), improving over the previous bound of O(sqrt(g
log n)) [KLMN04].
- We give an O(log g)-approximation for treewidth, improving over the
previous bound of O(g) [FHL05].
- If a graph G has genus g and maximum degree D, the k-th Laplacian
eigenvalue of G is (log g)2 * O(k g D/n), improving over the previous
bound of g2 * O(k g D/n) [KLPT]. There is a lower bound of
Omega(kgD/n), making this result almost tight.
- We show that if (X,d) is the shortest-path metric on a graph of
genus g and S is a subset of X, then every L-Lipschitz map f : S -> Z
into a Banach space Z admits an O(L log g)-Lipschitz extension f' : X
-> Z. This improves over the previous bound of O(Lg) [LN05], and
compares to a lower bound of Omega(L sqrt(log g)). In a related way,
we show that there is an O(log g)-approximation for the 0-extension
problem on such graphs, improving over the previous O(g) bound.
- We show that if planar graphs embed into L_1 with O(1) distortion,
then graphs of genus g embed into L_1 with O(log g) distortion,
improving over the previous conditional bound of O(g2) [BLS09]. This
is conditionally
tight, as there is an Omega(log g) lower bound. We also show that
every n-vertex shortest-path metric on a graph of genus g embeds into
L_2 with distortion O(sqrt((log g)(log n))), improving over the
previous bound of O(sqrt(g log n)).
Joint work with James R. Lee.
November 10: Paul Beame (University of Washington),
Hardness Amplification in Proof Complexity
We present a generic method for converting any family of
unsatisfiable CNF formulas that require large resolution rank into CNF
formulas whose refutation requires large rank for proof systems that
manipulate polynomials or polynomial threshold functions of degree at
most k (known as Th(k) proofs). Such systems include: Lovasz-Schrijver
and Cutting Planes proof systems as well as their high degree
analogues (LS(k), LS+(k)), and CP(k) and Sherali-Adams and Lasserre
proofs.
These bounds are derived by analyzing two general families of proof
systems that we introduce that include Th(k) proofs as a special case
and require only that each proof line (or inference) be checkable (in
a certain weak sense) by an efficient k-party randomized communication
protocol.
For k=O(loglog n), we prove that from any unsatisfiable CNF formula F
requiring resolution rank r, we can obtain a related CNF formula
G=Lift_k(F) requiring refutation rank r/ log^O(1) n in the k-party
versions of these proof systems. Since resolution rank is at least
resolution width (for which many strong lower bounds are known), this
yields strong rank lower bounds in all of the above proof systems for
large classes of natural CNF formulas.
We also prove that there are strict rank hierarchies of these proof
systems with respect to k and derive exponential lower bounds on the
size of tree-like Th(k) refutations for large classes of lifted CNF
formulas. The rank hierarchies we prove extend to nearly exponential
separations in tree-like proof size.
Joint work with Trinh Huynh and Toniann Pitassi.
November 23: Joseph Landsberg (Texas A&M University),
Mathematical Aspects of the Geometric Complexity Theory
Approach to P Versus NP
K. Mulmuley and M. Sohoni have proposed an approach to P v.
NP via geometry and representation theory. I will report on joint work
with P. Buergisser, L. Manivel and J. Weyman of our study of their
work and possible future decisions.
December 1: Amir Yehudayoff (IAS),
Algebraic complexity with less relations
In his seminal paper, Valiant defined algebraic analogs for the complexity classes P and NP, which are called today VP and VNP, and showed that the permanent is complete for VNP. In this talk we study a more restricted algebraic world, a world in which the variables do not commute and associate. We show that, although restricted, this world exhibits some interesting properties: the permanent is complete even in the non-associative non-commutative version of VNP. We are also able to prove lower bounds for circuits in such a restricted world, and thus able to separate VP from VNP in a non-associative world.
Joint work with P. Hrubes and A. Wigderson.