Princeton

The graph realization problem has received a great deal of attention in recent years, due to its importance in applications such as wireless sensor networks and structural biology. We introduce the ASAP algorithm, for the graph realization problem in R^d, given a sparse and noisy set of distance measurements associated to the edges of a globally rigid graph. ASAP is a divide and conquer, non-incremental and non-iterative algorithm, which integrates local distance information into a global structure determination. Our approach starts with identifying, for every node, a subgraph of its 1-hop neighborhood graph, which can be accurately embedded in its own coordinate system. In the noise-free case, the computed coordinates of the sensors in each patch must agree with their global positioning up to some unknown rigid motion, that is, up to translation, rotation and possibly reflection. In other words, to every patch there corresponds an element of the Euclidean group Euc(3) of rigid transformations in R^3, and the goal is to estimate the group elements that will properly align all the patches in a globally consistent way. The reflections and rotations are estimated using a recently developed eigenvector synchronization algorithm, while the translations are estimated by solving an overdetermined linear system. Furthermore, the algorithm successfully incorporates information specific to the molecule problem in structural biology, in particular information on known substructures and their orientation. In addition, we also propose SP-ASAP, a faster version of ASAP, which uses a spectral partitioning algorithm as a preprocessing step for dividing the initial graph into smaller subgraphs. Our extensive numerical simulations show that ASAP and SP-ASAP are very robust to high levels of noise in the measured distances and to sparse connectivity in the measurement graph, and compare favorably to similar state-of-the art localization algorithms. Time permitting, we briefly discuss the analogy between the graph realization and the low-rank matrix completion problems, as well as an application of synchronization over Z_2 and its variations to bipartite multislice networks.

I describe a conjecture equating the two items appearing in the title.

I will review our current mathematical understanding of waves on black hole backgrounds, starting with the classical boundedness theorem of Kay and Wald on Schwarzschild space-time and ending with recent boundedness and decay theorems on a wider class of black hole space-times.

Recently there has been increasing interest in discrete analogues of classical operators in harmonic analysis. Often the difficulties one encounters in the discrete setting require completely new approaches; the most successful current approaches are motivated by ideas from classical analytic number theory. This talk will describe a menagerie of new results for discrete analogues of operators ranging from twisted singular Radon transforms to fractional integral operators both on R^n and on the Heisenberg group H^n. Although these are genuinely analytic results, key aspects of the methods come from number theory, and this talk will highlight the roles played by theta functions, Waring's problem, the Hypothesis K* of Hardy and Littlewood, and the circle method.