Title: Explicit Signings for the Kadison-Singer Problem in Graphs.
Abstract: The solution to the long-standing Kadison-Singer problem by Marcus, Spielman, and Srivastava demonstrates the existence of unweighted spectral sparsifiers for graphs. However, the solution based on the expected characteristic polynomial only establishes existence, leaving the computation of sparse approximations as an important open problem. In this study, we present algorithms (along with explicit signings) tailored for specific classes of graphs. Of particular interest is the variety of tools from harmonic analysis, discrepancy theory, and random regular graphs that appear while analyzing this problem.
Title: Dynamic Approximate Multiplicatively-Weighted Nearest Neighbor
Abstract: In the nearest-neighbor problem, given a set P of points (in the plane, in 3-space, or higher dimension), we want to preprocess P so that, given another point q, its nearest neighbor (closest point) in P can be found efficiently. The approximate version of the problem does not insist that we return the point that's closest to q: returning a point that is a little further away is acceptable.
We describe a dynamic data structure for approximate nearest neighbor (ANN) queries with respect to multiplicatively weighted distances with additive offsets. Queries take polylogarithmic time, while the cost of updates is amortized polylogarithmic. The data structure requires near-linear space and construction time.
The approach works not only for the Euclidean norm, but for other norms in R^d, for any fixed d.
We employ our ANN data structure to construct a faster dynamic structure for approximate SINR queries, ensuring polylogarithmic query and polylogarithmic amortized update for the case of non-uniform power transmitters, thus closing a gap in previous state of the art.
Title: Hardness of Approximation of Diameter Clustering
Abstract: In the k-Diameter Clustering problem, we are given as input a set of points in a metric space, and the goal is to partition the pointset to k parts so as to minimize the maximum diameter across the parts. In the 1980s, a 2 factor polynomial time approximation algorithm was proposed for this problem (in all metrics). On the other hand, it was shown that approximating the k-Diameter problem to a factor better than 2 in the L-1 and L-infinity metrics, and to a factor better than 1.97 in the Euclidean metric is NP-hard. However, all the known hardness results were for the case when k (the number of clusters) was linear in the input size. In this talk, I will present some exciting new results on the (in)-approximability of the k-Diameter problem when k is a constant (for example k=3).
Title: Soft Foundations for Robot Path Planning: Theory and Practice
Abstract: Path Planning (a.k.a. motion planning) is a fundamental problem in robotics. Current "exact" algorithms cannot be implemented exactly and thus lack guarantees. Since 2012, we had propounded a novel "soft" approach to provide rigorous algorithms that are implementable. In a series of papers, we demonstrated the power of these ideas, by producing path planners for planar robots with 2, 3 and 4 degrees of freedom (DOF), and spatial 5-DOF robots. Under construction is a spatial 6-DOF planner (a "milestone" case). Our implementations outperform or match the state-of-art sampling-based planners.
There are 3 key elements in our approach: (1) The concept of "Resolution-exact Planners". We thus avoid the "Zero Problem" that plagues all exact computation. (2) The concept of "soft predicates", with accompanying "feature-based technique" to construct such predicates. (3) An algorithmic framework called "Soft Subdivision Search" (SSS) to incorporate these ideas. Our SSS planners have these features:
In this talk, we outline the theory underlying these results. For each robot class, we also introduce techniques necessary to achieve the above features.
Partly supported by an NSF Grant with Prof.Y.-J.Chiang, NYU Tandon.
Title: Hidden Permutations to the Rescue: Multi-Pass Semi-Streaming Lower Bounds for Approximate Matchings
Abstract: A semi-streaming graph algorithm processes its input graph by making one or a few passes over its edges and using a space proportional to the number of vertices, hence, (potentially) quadratically smaller than the input size. Semi-streaming algorithms have been at the forefront of theoretical research on processing massive graphs in recent years. In this talk, we will consider the maximum (bipartite) matching problem in the semi-streaming model, and present a tradeoff between the approximation ratio and number of passes.
Title: Learning on very, very large graphs
Abstract: Many learning problems involving graphs will involve repeated multiplications or solves with the graph Laplacian. However, for very large graphs, even holding all the nodes in one server can be prohibitive. Therefore, there is a growing need for graph operations that are *local*, e.g. where an operation performed on one node only affects a limited neighborhood of nodes. An important example of such an operation is the Forward Push method, developed for large web applications, in which the matrix/vector multiplication has bounded complexity, in terms of nodes touched. We explore accelerated versions of the Forward Push method, and extend its complexity analysis to the important node labeling problem for very large graphs.
Title: Traversing combinatorial polytopes via optimization
Abstract: We present a new framework that exploits combinatorial optimization for efficiently generating a large variety of combinatorial objects based on graphs, matroids, posets, and polytopes.
Our method relies on a simple and versatile algorithm for computing a Hamilton path on the skeleton of any 0/1-polytope conv(X), where X ⊆{0,1}^n. The algorithm uses as a black box any algorithm that solves the classical linear optimization problem, and the resulting delay, i.e., the running time per visited vertex on the Hamilton path, is only a polylogarithmic factor larger than the running time of the optimization algorithm. When X encodes a particular class of combinatorial objects, then traversing the skeleton of the polytope conv(X) along a Hamilton path corresponds to listing the combinatorial objects by local change operations, i.e., we obtain Gray code listings.
As a concrete example application of our framework, we obtain an O(T⋅log n) delay algorithm for the vertex enumeration problem on 0/1 polytopes, where T is the time needed to solve a linear program and n is the dimension of the polytope. This improves upon the 25-year-old O(T⋅n) delay algorithm due to Bussieck and Lübbecke.