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

A separator theorem in minorclosed classesIt is shown that for each $t$, there is a separator of size $O(t sqrt{n})$ in any $n$vertex graph $G$ with no $K_t$minor.
This settles a conjecture of Alon, Seymour and Thomas (J. Amer. Math. Soc., 1990 and STOC'90), and generalizes a result of Djidjev (1981), and Gilbert, Hutchinson and Tarjan (J. Algorithm, 1984), independently, who proved that every graph with $n$ vertices and genus $g$ has a separator of order $O(sqrt{gn})$, because $K_t$ has genus $Omega(t^2)$.
The bound $O(t sqrt{n})$ is best possible because every 3regular expander graph with $n$ vertices is a graph with no $K_t$minor for $t=cn^{1/2}$, and with no separator of size $dn$ for appropriately chosen positive constants $c,d$.
In addition, we give an $O(n^2)$ time algorithm to obtain such a separator, and then give a sketch how to obtain such a separator in $O(n^{1+epsilon})$ time for any $epsilon > 0$. Finally, we discuss several algorithm aspects of our separator theorem, including a possibility to obtain a separator of order $g(t)sqrt{n}$, for some function $g$ of $t$, in an $n$vertex graph $G$ with no $K_t$minor in $O(n)$ time.

Optimal stochastic planarizationIt has been shown by Indyk and Sidiropoulos [IS07] that any graph of genus g>0 can be stochastically embedded into a distribution over planar graphs with distortion 2^O(g). This bound was later improved to O(g^2) by Borradaile, Lee and Sidiropoulos [BLS09]. We give an embedding with distortion O(log g), which is asymptotically optimal.
Apart from the improved distortion, another advantage of our embedding is that it can be computed in polynomial time. In contrast, the algorithm of [BLS09] requires solving an NPhard problem.
Our result implies in particular a reduction for a large class of geometric optimization problems from instances on genusg graphs, to corresponding ones on planar graphs, with a O(log g) loss factor in the approximation guarantee.

Solving linear systems through nested dissectionThe generalized nested dissection method, developed by Lipton, Rose, and Tarjan, is a seminal method for solving a linear system $Ax=b$ where $A$ is a symmetric positive definite matrix. The method runs extremely fast whenever $A$ is a wellseparable matrix (such as matrices whose underlying support is planar or avoids a fixed minor). In this work we extend the nested dissection method to apply to {em any} nonsingular wellseparable matrix over {em any} field. The running times we obtain essentially match those of the nested dissection method.

Approaching optimality for solving SDD linear systemsWe present an algorithm that on input a graph $G$ with $n$ vertices and $m+n1$ edges and a value $k$, produces an {em incremental sparsifier} $hat{G}$ with $n1 + m/k$ edges, such that the condition number of $G$ with $hat{G}$ is bounded above by $ ilde{O}(klog^2 n)$, with probability $1p$. The algorithm runs in time
$$ ilde{O}((m log{n} + nlog^2{n})log(1/p)).$$
As a result, we obtain an algorithm that on input an $n imes n$ symmetric diagonally dominant matrix $A$ with $m+n1$ nonzero entries and a vector $b$, computes a vector $ar{x}$ satisfying $xA^{+}b_A<epsilon A^{+}b_A $, in time
$$ ilde{O}(mlog^2{n}log(1/epsilon)).$$
The solver is based on a recursive application of the incremental sparsifier that produces a hierarchy of graphs which is then used to construct a recursive preconditioned Chebyshev iteration.

Fast approximation algorithms for cutbased graph problemsWe present a general method of designing fast approximation algorithms for cutbased minimization problems in undirected graphs. In particular, we develop a technique that given any such problem that can be approximated quickly on trees, allows approximating it almost as quickly on general graphs while only losing a polylogarithmic factor in the approximation guarantee. We present a general method of designing fast approximation algorithms for undirected cutbased minimization problems. More precisely, we develop a technique that given any such cutbased problem that can be approximated quickly on trees, allows approximating it almost as quickly on general graphs while only losing a polylogarithmic factor in the approximation guarantee.
To illustrate the applicability of our paradigm, we focus our attention on the undirected sparsest cut problem with general demands, and the balanced separator problem. By a simple use of our framework, we obtain polylogarithmic approximation algorithms for these problems that run in time close to linear. This establishes, in particular, the first polylogarithmicapproximation algorithm for the generalized sparsest cut problem whose running time breaks the multicommodity flow barrier of $Omega(n^2)$ time, and the first algorithms achieving such approximation ratio for the balanced separator and the (uniform) sparsest cut problem while running in time $o(m+n^{3/2})$.
The main tool behind our result is an efficient procedure that decomposes general graphs into simpler ones while approximately preserving the cutflow structure. This decomposition is inspired by hierarchical tree decompositions that were developed in the context of oblivious routing schemes.

Metric Extension Operators, Vertex Sparsifiers and Lipschitz ExtendabilityWe study vertex cut and flow sparsifiers that were recently introduced by Moitra (2009), and Leighton and Moitra (2010). Our results improve and generalize the results by Moitra (2009), and Leighton and Moitra (2010). We give a new polynomialtime algorithm for constructing O(log k / log log k) cut and flow sparsifiers, matching the best existential upper bound on the quality of a sparsifier, and improving the previous algorithmic upper bound of O(log^2 k / log log k). We show that flow sparsifiers can be obtained from linear operators approximating minimum metric extensions. We introduce the notion of (linear) metric extension operators, prove that they exist, and give an exact polynomialtime algorithm for finding optimal operators.
We then establish a direct connection between flow and cut sparsifiers and Lipschitz extendability of maps in Banach spaces, a notion studied in functional analysis since 1950s. Using this connection, we prove a lower bound of Omega(sqrt{log k /log log k}) for flow sparsifiers and a superconstant lower bound for cut sparsifiers. We show that if a certain open question posed by Ball in 1992 has a positive answer, then there exist ilde O(sqrt{log k}) cut sparsifiers. On the other hand, any lower bound on cut sparsifiers better than ilde Omega(sqrt{log k}) would imply a negative answer to this question.

Vertex Sparsifiers and Abstract Rounding AlgorithmsThe notion of vertex sparsification (in particular cutsparsification) is introduced in (M, 2009), where it was shown that for any graph $G = (V, E)$ and a subset of $k$ terminals $K subset V$, there is a polynomial time algorithm to construct a graph $H = (K, E_H)$ emph{on just the terminal set} so that simultaneously for all cuts $(A, KA)$, the value of the minimum cut in $G$ separating $A$ from $K A$ is approximately the same as the value of the corresponding cut in $H$. Then approximation algorithms can be run directly on $H$ as a proxy for running on $G$, yielding approximation guarantees independent of the size of the graph. In this work, we consider how well cuts in the sparsifier $H$ can approximate the minimum cuts in $G$, and whether algorithms that use such reductions need to incur a multiplicative penalty in the approximation guarantee depending on the quality of the sparsifier.
We give the first superconstant lower bounds for how well a cutsparsifier $H$ can simultaneously approximate all minimum cuts in $G$. We prove a lower bound of $Omega(log^{1/4} k)$  this is polynomiallyrelated to the known upper bound of $O(log k/log log k)$. This is an exponential improvement on the $Omega(log log k)$ bound given in (LM, 2010) which in fact was for a stronger vertex sparsification guarantee, and did not apply to cut sparsifiers.
Despite this negative result, we show that for many natural problems, we do not need to incur a multiplicative penalty for our reduction. Roughly, we show that any rounding algorithm which also works for the $0$extension relaxation can be used to construct good vertexsparsifiers for which the optimization problem is easy. Using this, we obtain optimal $O(log k)$competitive Steiner oblivious routing schemes, which generalize the results in cite{R}. We also demonstrate that for a wide range of graph packing problems (which includes maximum concurrent flow, maximum multiflow and multicast routing, among others, as a special case), the integr

A nonlinear lower bound for planar epsilonnetsWe show that the minimum possible size of an $epsilon$net for point objects and line (or rectangle)ranges in the plane is (slightly) bigger than linear in $1/epsilon$. This settles a problem raised by Matousek, Seidel and Welzl in 1990.

The subexponential upper bound for online chain partitioninghe 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.

Improved Bounds for Geometric PermutationsWe show that the number of geometric permutations of an arbitrary collection of $n$ pairwise disjoint convex sets in $ eals^d$, for $dgeq 3$, is $O(n^{2d3}log n)$, improving Wenger's 20 years old bound of $O(n^{2d2})$.
 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