Abstracts
Minimum Circuit Size, Graph Isomorphism and Related Problems
Eric Allender
The Minimum Circuit Size Problem (MCSP) and a related problem dealing with time-bounded Kolmogorov complexity (MKTP) occupy an important place in the complexity-theoretic landscape of NP, not known to be NP-hard, but hard for the class SZK (Statistical Zero Knowledge) under BPP-reductions. Our understanding of the complexity of these problems has been hampered by a paucity of techniques to reduce computational problems to MCSP and MKTP. Two years ago, a NYCAC talk presented a new technique, enabling a proof that the Graph Automorphism problem (GA) is ZPP-reducible to MKTP. Now the technique has been developed further, showing that Graph Isomorphism (GI) ZPP-reduces to MKTP, and also showing that a larger subclass of SZK is in ZPP^MKTP (including many problems that, unlike GA and GI, are not known to have quasipolynomial-time algorithms). This talk will explain what progress has been made, and why you should care.
slides
The Size and the Approximability of Minimum Temporally Connected Subgraphs
Dimitris Fotakis
TBA
slides
Multi-Clique-Width, a Powerful New Width Parameter
Martin Fürer
Multi-clique-width is a width parameter for graphs. It is obtained by a
simple modification in the definition of clique-width. It has the
advantage of providing a natural extension of tree-width. Unlike
clique-width, it does not explode exponentially compared to tree-width.
Efficient algorithms based on multi-clique-width are still possible for
interesting tasks like computing the size of a maximum independent set
(or even the independent set polynomial) or computing the chromatic
number. For these tasks, the running time as a function of the
multi-clique-width is the same as the running time of the fastest known
algorithm as a function of the clique-width. This results in an
exponential speed-up for some graphs, if the corresponding graph
generating expressions are given. The reason is that the
multi-clique-width is never bigger, but is exponentially smaller than
the clique-width for many graphs.
Tree-width and clique-width will be introduced.
slides
On the Quantitative Hardness of CVP
Alexander Golovnev
For odd integers p ≥ 1 (and p = ∞), we show that the Closest Vector Problem in the Lp norm (CVP_p) over rank n lattices cannot be solved in 2^{(1-ε)n} time for any constant ε > 0 unless the Strong Exponential Time Hypothesis (SETH) fails. We then extend this result to "almost all" values of p ≥ 1, not including the even integers. This comes tantalizingly close to settling the quantitative time complexity of the important special case of CVP_2 (i.e., CVP in the Euclidean norm), for which a 2^{n+o(n)} -time algorithm is known. In particular, our result applies for any p = p(n) != 2 that approaches 2 as n → ∞.
We also show a similar SETH-hardness result for SVP_∞; hardness of approximating CVP_p to within some constant factor under the so-called Gap-ETH assumption; and other quantitative hardness results for CVP_p and CVPP_p for any 1 ≤ p < ∞ under different assumptions.
The talk is based on joint work with Huck Bennett and Noah Stephens-Davidowitz.
slides
Recursion-Theoretic Ranking and Compression
Lane Hemaspaandra
For which sets A does there exist a mapping, computed by a total or partial recursive function, such that the mapping, when its domain is restricted to A, is a 1-to-1, onto mapping to Sigma^*? And for which sets A does there exist such a mapping that respects the lexicographical ordering within A? Both cases are types of perfect, minimal hash functions. The complexity-theoretic versions of these notions are known as compression functions and ranking functions. The present paper defines and studies the recursion-theoretic versions of compression and ranking functions, and in particular studies the question of which sets have, or lack, such functions. Thus, this is a case where, in contrast to the usual direction of notion transferal, notions from complexity theory are inspiring notions, and an investigation, in computability theory.
We show that the rankable and compressible sets broadly populate the 1-truth-table degrees, and we prove that every nonempty coRE cylinder is recursively compressible.
This is joint work with Dan Rubery.
slides
A computer scientist thinks about the brain
Christos Papadimitriou
Understanding how the mind (cognition, behavior, language, intelligence) emerges from the Brain (neurons, synapses, genes, molecules) is arguably the most challenging question facing science today. As the answer is likely to be -- to some extent -- computational, computer scientists should think about this problem. I will discuss recent work (with S. Vempala, W. Maass, and others) showing that, in a simplified model of neurons and plasticity, densely connected assemblies of neurons can be formed that code real world items or concepts, and that two such assemblies can change to increase their intersection in response to an observed association of the two concepts, hence explaining recent experimental results. Interestingly, our proposed mechanism can be seen as a simple and surprisingly effective heuristic for solving the densest K-subgraph problem in a random graph. I will also speculate about possible extensions of this work to the problem of understanding how language, and in particular syntax, happens in the Brain.
slides
The Complexity of Simple and Optimal Deterministic Mechanisms for an
Additive Buyer
Mihalis Yannakakis
We show that the Revenue-Optimal Deterministic Mechanism Design problem for
a
single additive buyer is #P-hard. This holds even when the distributions
have support size 2 for each item and, more importantly, even when the
optimal solution is guaranteed to be of a very simple kind:
the seller picks a price for each individual item and a (discounted) price
for the grand bundle of all the items;
the buyer can purchase either the grand bundle at its given price or any
subset of items
at their total individual prices.
The following problems are also #P-hard as corollaries of the proof:
- determining if individual item pricing is optimal for a given instance,
- determining if grand bundle pricing is optimal, and
- computing the optimal (deterministic) revenue.
On the positive side, we show that when the distributions are i.i.d. with
support size 2,
the optimal revenue obtainable by any mechanism, even a randomized one, can
be achieved by
a simple solution of the above kind (individual item pricing with a
discounted price for the grand bundle)
and furthermore, it can be computed in polynomial time.
The problem can be solved in polynomial time also when the number of items
is constant.
Joint work with Xi Chen, George Matikas, and Dimitris Paparas
slides
Ten Steps of EM Suffice for Mixtures of Two Gaussians
Manolis Zambetakis
The Expectation-Maximization (EM) algorithm is a widely used method for maximum likelihood estimation in models with latent variables. For estimating mixtures of Gaussians, its iteration can be viewed as a soft version of the k-means clustering algorithm. Despite its wide use and applications, there are essentially no known convergence guarantees for this method. We provide global convergence guarantees for mixtures of two Gaussians with known covariance matrices. We show that the population version of EM, where the algorithm is given access to infinitely many samples from the mixture, converges geometrically to the correct mean vectors, and provide simple, closed-form expressions for the convergence rate. As a simple illustration, we show that, in one dimension, ten steps of the EM algorithm initialized at infinity result in less than 1% error estimation of the means. In the finite sample regime, we show that, under a random initialization, O(d/\epsilon^2) samples suffice to compute the unknown vectors to within \epsillon in Mahalanobis distance, where d is the dimension. In particular, the error rate of the EM based estimator is O(\sqrt{d/n}), here n is the number of samples, which is optimal up to logarithmic factors.