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.