IEEE FOCS 2010
TechTalks from event: IEEE FOCS 2010
51st Annual IEEE Symposium on Foundations of Computer Science

Subexponential Algorithms for Unique Games and Related problemsWe give subexponential time approximation algorithms for the unique games and the small set expansion problems. Specifically, for some absolute constant c, we give:
1 An exp(kn^epsilon)time algorithm that, given as input a kalphabet unique game on n variables that has an assignment satisfying 1epsilon^c fraction of its constraints, outputs an assignment satisfying 1epsilon fraction of the constraints.
2. An exp(n^epsilon/delta)time algorithm that, given as input an nvertex regular graph that has a set S of delta n vertices with edge expansion at most epsilon^c outputs a set S' of at most delta n vertices with edge expansion at most epsilon.
We also obtain a subexponential algorithm with improved approximation for the MultiCut problem, as well as subexponential algorithms with improved approximations to MaxCut, SparsestCut and VertexCover on some interesting subclasses of instances.
Khot's Unique Games Conjecture (UGC) states that it is NPhard to achieve approximation guarantees such as ours for unique games. While our results stop short of refusing the UGC, they do suggest that Unique Games is significantly easier than NPhard problems such as 3SAT, 3LIN, Label Cover and more, that are believed not to have a subexponential algorithm achieving a nontrivial approximation ratio.
The main component in our algorithms is a new result on graph decomposition that may have other applications. Namely we show that for every delta>0 and a regular nvertex graph G, by changing at most delta fraction of G's edges, one can break G into disjoint parts so that the induced graph on each part has at most n^epsilon eigenvalues larger than 1eta (where epsilon,eta depend polynomially on delta). Our results are based on combining this decomposition with previous algorithms for unique games on graphs with few large eigenvalues (Kolla and Tulsiani 2007, Kolla 2010).

Nevanlinna Prize Talk. Laplacian GemsI will explain some of the most interesting applications of solving linear equations in Laplacian matrices as well as some of the most interesting ideas that have been used in algorithms that solve these equations. The main applications will come from machine learning and optimization. The algorithmic ideas I discuss will include local clustering, sparsification, lowstretch spanning trees, and an underappreciated technique of Lovasz and Simonovits for bounding the convergence rate of Markov chains.

Dependent Randomized Rounding via Exchange Properties of Combinatorial StructuresWe consider the problem of randomly rounding a fractional solution $x$ in a polytope $P subset RR^n$ to a vertex $X$ of $P$, so that $E[X] = x$. Our goal is to achieve {em concentration properties} for linear and submodular functions of the rounded solution. Such dependent rounding techniques, with concentration bounds for linear functions, have been developed in the past for two polytopes: the assignment polytope (that is, bipartite matchings and $b$matchings) cite{S01,GKPS06,KMPS09}, and more recently for the spanning tree polytope cite{AGMGS10}. These schemes have led to a number of new algorithmic results.
In this paper we describe a new {em swap rounding} technique which can be applied in a variety of settings including {em matroids}, {em matroid intersection} and {em nonbipartite graph $b$matchings}, while providing Chernofftype concentration bounds for linear and submodular functions of the rounded solution. In addition to existing techniques based on negative correlation, we use martingale methods to obtain an exponential tail estimate for monotone submodular functions, and also for linear functions in settings where negative correlation does not hold. The rounding scheme explicitly exploits {em exchange properties} of the underlying combinatorial structures, and highlights these properties as the basis for concentration bounds.
The framework of matroids and matroid intersection provides a unifying scheme for several known applications cite{GKPS06,KMPS09,CCPV09,KST09,AGMGS10} as well as new ones, and its flexibility allows a richer set of constraints to be incorporated easily. We illustrate this on the maxmin allocation problem with submodular valuations, submodular maximization subject to a matroid and multiple linear constraints, the crossing spanning tree problem, and resource allocation / broadcast scheduling problems with various demand/capacity constraints.

MinimumCost Network Design with (Dis)economies of ScaleGiven a network, a set of demands and a cost function $f(cdot)$, the mincost n etwork design problem is to route all demands with the objective of minimizing $ sum_e f(ell_e)$, where $ell_e$ is the total traffic load under the routing. We focus on cost functions of the form $f(x)= sigma + x^{alpha}$ for $x > 0$, with $f(0) = 0$. For $alpha le 1$, $f(cdot)$ is subadditive and exhibits beha vior consistent with economies of scale. This problem corresponds to the wells tudied BuyatBulk network design problem and admits polylogarithmic approximati on and hardness.
In this paper, we focus on the less studied scenario of $alpha > 1$ with a posi tive startup cost $sigma > 0$. Now, the cost function $f(cdot)$ is neither sub additive nor superadditive. This is motivated by minimizing networkwide energy consumption when supporting a set of traffic demands. It is commonly accepted that, for some computing and communication devices, doubling processing speed mo re than doubles the energy consumption. Hence, in Economics parlance, such a cos t function reflects emph{diseconomies of scale}.
We begin by discussing why existing routing techniques such as randomized roundi ng and treemetric embedding fail to generalize directly. We then present our m ain contribution, which is a polylogarithmic approximation algorithm. We obtain this result by first deriving a bicriteria approximation for a related capacitat ed mincost flow problem that we believe is interesting in its own right. Our ap proach for this problem builds upon the welllinked decomposition due to Chekuri KhannaShepherd~cite{ChekuriKS05}, the construction of expanders via matchings due to KhandekarRaoVazirani~cite{KhandekarRV06}, and edgedisjoint routing i n wellconnected graphs due to RaoZhou~cite{RaoZ06}. However, we also develop new techniques that allow us to keep a handle on the total cost, which was not a concern in the aforementioned literature.

One Tree Suffices: A Simultaneous O(1)Approximation for SingleSink BuyatBulkWe study the singlesink buyatbulk problem with an unknown cost function. We want to route flow from a set of demand nodes to a root node, where the cost of routing x total flow along an edge is proportional to f(x) for some concave, nondecreasing function f satisfying f(0)=0. We present a simple, fast, deterministic, combinatorial algorithm that takes a set of demands and constructs a single tree T such that for all f the cost f(T) is a 49.48approximation of the optimal cost for that f. This is within a factor of 2 of the best approximation ratio currently achievable when the tree can be optimized for a specific function. Trees achieving simultaneous O(1)approximations for all concave functions were previously not known to exist regardless of computation time.

Min stCut Oracle for Planar Graphs with NearLinear Preprocessing TimeFor an undirected $n$vertex planar graph $G$ with nonnegative edgeweights, we consider the following type of query: given two vertices $s$ and $t$ in $G$, what is the weight of a min $st$cut in $G$? We show how to answer such queries in constant time with $O(nlog^5n)$ preprocessing time and $O(nlog n)$ space. We use a GomoryHu tree to represent all the pairwise min cuts implicitly. Previously, no subquadratic time algorithm was known for this problem. Since allpairs min cut and the minimum cycle basis are dual problems in planar graphs, we also obtain an implicit representation of a minimum cycle basis in $O(nlog^5n)$ time and $O(nlog n)$ space and an explicit representation with additional $O(C)$ time and space where $C$ is the size of the basis.
These results require that shortest paths be unique. We deterministically remove this assumption with an additional $log^2 n$ factor in the running time.

Subcubic Equivalences Between Path, Matrix, and Triangle ProblemsThe main question in the online chain partitioning problem is to determine whether there exists an algorithm that partitions online posets of width at most $w$ into polynomial number of chains  see Trotter's chapter emph{Partially ordered sets} in the emph{Handbook of Combinatorics}. So far the best known online algorithm of Kierstead used at most $(5^w1)/4$ chains; on the other hand Szemer'{e}di proved that any online algorithm requires at least $inom{w+1}{2}$ chains. These results were obtained in the early eighties and since then no progress in the general case has been done.
We provide an online algorithm that partitions orders of width $w$ into at most $w^{16log{w}}$ chains. This yields the first subexponential upper bound for online chain partitioning problem.

Replacement Paths via Fast Matrix MultiplicationLet G = (V, E) be a directed edgeweighted graph and let P be a shortest path from s to t in G. The {em replacement paths} problem asks to compute, for every edge e on P, the shortest stot path that avoids e. Apart from approximation algorithms and algorithms for special graph classes, the naive solution to this problem  removing each edge e on P one at a time and computing the shortest stot path each time  is surprisingly the only known solution for directed weighted graphs, even when the weights are integrals. In particular, although the related {em shortest paths} problem has benefited from fast matrix multiplication, the replacement paths problem has not, and still required cubic time. For an nvertex graph with integral edgelengths in {M,...,M}, we give a randomized O(Mn^{1+2omega/3}) = O(Mn^{2.584}) time algorithm that uses fast matrix multiplication and is subcubic for appropriate values of M. In particular, it runs in O(n^{1+2omega/3}) time if the weights are small (positive or negative) integers. We also show how to construct a distance sensitivity oracle in the same time bounds. A query (u,v,e) to this oracle requires subquadratic time and returns the length of the shortest utov path that avoids the edge e. In fact, for any constant number of edge failures, we construct a data structure in subcubic time, that answer queries in subquadratic time. Our results also apply for avoiding vertices rather than edges.

AllPairs Shortest Paths in O(n2) Time With High ProbabilityWe present an allpairs shortest path algorithm whose running time on a complete directed graph on $n$ vertices whose edge weights are chosen independently and uniformly at random from $[0,1]$ is~$O(n^2)$, in expectation and with high probability. This resolves a long standing open problem. The algorithm is a variant of the dynamic allpairs shortest paths algorithm of Demetrescu and Italiano. The analysis relies on a proof that the number of emph{locally shortest paths} in such randomly weighted graphs is $O(n^2)$, again in expectation and with high probability. We also present a dynamic version of the algorithm that recomputes all shortest paths after a random edge update in $O(log^{2}n)$ expected time.

Approximating Maximum Weight Matching in Nearlinear TimeGiven a weighted graph, the {em maximum weight matching} problem (MWM) is to find a set of vertexdisjoint edges with maximum weight. In the 1960s Edmonds showed that MWMs can be found in polynomial time. At present the fastest MWM algorithm, due to Gabow and Tarjan, runs in $ ilde{O}(msqrt{n})$ time, where $m$ and $n$ are the number of edges and vertices in the graph. Surprisingly, restricted versions of the problem, such as computing $(1epsilon)$approximate MWMs or finding maximum cardinality matchings, are not known to be much easier (on sparse graphs). The best algorithms for these problems also run in $ ilde{O}(msqrt{n})$ time.
In this paper we present the first nearlinear time algorithm for computing $(1epsilon)$approximate MWMs. Specifically, given an arbitrary realweighted graph and $epsilon>0$, our algorithm computes such a matching in $O(mepsilon^{2}log^3 n)$ time. The previous best approximate MWM algorithm with comparable running time could only guarantee a $(2/3epsilon)$approximate solution. In addition, we present a faster algorithm, running in $O(mlog nlogepsilon^{1})$ time, that computes a $(3/4epsilon)$approximate MWM.
 All Talks
 Geometric complexity theory (GCT)
 How to Grow Your Lower Bounds
 How To Think About Mechanism Design
 Constructive Algorithms for Discrepancy Minimization
 Bounded Independence Fools Degree2 Threshold Functions
 The Coin Problem, and Pseudorandomness for Branching Programs / Pseudorandom Generators for Regular Branching Programs
 Settling the Polynomial Learnability of Mixtures of Gaussians
 Polynomial Learning of Distribution Families
 Agnostically learning under permutation invariant distributions
 Learning Convex Concepts from Gaussian Distributions with PCA
 Determinant Sums for Undirected Hamiltonicity
 Fighting Perebor: New and Improved Algorithms for Formula and QBF Satisfiability
 The Monotone Complexity of kCLIQUE on Random Graphs
 The Complexity of Distributions
 Hardness of Finding Independent Sets in Almost 3Colorable Graphs
 Approximation Algorithms for the EdgeDisjoint Paths Problem via Raecke Decompositions
 Computational Transition at the Uniqueness Threshold
 Avner Magen Memorial Talk
 Clustering with Spectral Norm and the kmeans Algorithm
 Stability yields a PTAS for kMedian and kMeans Clustering
 The Geometry of Manipulation  a Quantitative Proof of the GibbardSatterthwaite Theorem
 Efficient volume sampling for row/column subset selection
 Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity
 New Constructive Aspects of the Lovasz Local Lemma
 The Geometry of Scheduling
 Sublinear Time Optimization for Machine Learning
 Estimating the longest increasing sequence in sublinear time
 Testing Properties of Sparse Images
 A Unified Framework for Testing LinearInvariant Properties
 Optimal Testing of ReedMuller Codes
 Subexponential Algorithms for Unique Games and Related problems
 Nevanlinna Prize Talk. Laplacian Gems
 Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures
 MinimumCost Network Design with (Dis)economies of Scale
 One Tree Suffices: A Simultaneous O(1)Approximation for SingleSink BuyatBulk
 Min stCut Oracle for Planar Graphs with NearLinear Preprocessing Time
 Subcubic Equivalences Between Path, Matrix, and Triangle Problems
 Replacement Paths via Fast Matrix Multiplication
 AllPairs Shortest Paths in O(n2) Time With High Probability
 Approximating Maximum Weight Matching in Nearlinear Time
 Pure and BayesNash Price of Anarchy for Generalized Second Price Auction
 Frugal and Truthful Auctions for Vertex Covers, Flows, and Cuts / Frugal Mechanism Design via Spectral Techniques
 Budget Feasible Mechanisms
 BlackBox Randomized Reductions in Algorithmic Mechanism Design
 Boosting and Differential Privacy
 A Multiplicative Weights Mechanism for Interactive PrivacyPreserving Data Analysis
 Impossibility of Differentially Private Universally Optimal Mechanisms
 The Limits of TwoParty Differential Privacy
 Deciding firstorder properties for sparse graphs
 Logspace Versions of the Theorems of Bodlaender and Courcelle
 A separator theorem in minorclosed classes
 Optimal stochastic planarization
 Solving linear systems through nested dissection
 Approaching optimality for solving SDD linear systems
 Fast approximation algorithms for cutbased graph problems
 Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability
 Vertex Sparsifiers and Abstract Rounding Algorithms
 A nonlinear lower bound for planar epsilonnets
 The subexponential upper bound for online chain partitioning
 Improved Bounds for Geometric Permutations
 On the Queue Number of Planar Graphs
 Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP
 A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Nonnegative Weights
 Overcoming the Hole In The Bucket: PublicKey Cryptography Resilient to Continual Memory Leakage
 Cryptography Against Continuous Memory Attacks
 On the Insecurity of Parallel Repetition for Leakage Resilience
 BlackBox, RoundEfficient Secure Computation via NonMalleability Assumption
 From Standard to Adaptive Hardness And Composable Security With No SetUp
 On the Computational Complexity of Coin Flipping
 Sequential Rationality in Cryptographic Protocols
 A Fourieranalytic approach to ReedMuller decoding
 Pseudorandom generators for CC0[p] and the Fourier spectrum of lowdegree polynomials over finite fields
 Matching Vector Codes / Local list decoding with a constant number of queries
 Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate
 A lower bound for dynamic approximate membership data structures
 Lower Bounds for Near Neighbor Search via Metric Expansion
 Distance Oracles Beyond the Thorup?Zwick Bound