 Award ID(s):
 1915165
 NSFPAR ID:
 10462016
 Date Published:
 Journal Name:
 SciPost Physics
 Volume:
 15
 Issue:
 2
 ISSN:
 25424653
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

M. Ranzato ; A. Beygelzimer ; Y. Dauphin ; P.S. Liang ; J. Wortman Vaughan (Ed.)The null space of the kth order Laplacian Lk, known as the {\em kth homology vector space}, encodes the nontrivial topology of a manifold or a network. Understanding the structure of the homology embedding can thus disclose geometric or topological information from the data. The study of the null space embedding of the graph Laplacian L0 has spurred new research and applications, such as spectral clustering algorithms with theoretical guarantees and estimators of the Stochastic Block Model. In this work, we investigate the geometry of the kth homology embedding and focus on cases reminiscent of spectral clustering. Namely, we analyze the {\em connected sum} of manifolds as a perturbation to the direct sum of their homology embeddings. We propose an algorithm to factorize the homology embedding into subspaces corresponding to a manifold's simplest topological components. The proposed framework is applied to the {\em shortest homologous loop detection} problem, a problem known to be NPhard in general. Our spectral loop detection algorithm scales better than existing methods and is effective on diverse data such as point clouds and images.more » « less

In this paper we prove that the problem of deciding contractibility of an arbitrary closed curve on the boundary of a 3manifold is in NP. We emphasize that the manifold and the curve are both inputs to the problem. Moreover, our algorithm also works if the curve is given as a compressed word. Previously, such an algorithm was known for simple (noncompressed) curves, and, in very limited cases, for curves with selfintersections. Furthermore, our algorithm is fixedparameter tractable in the size of the input 3manifold. As part of our proof, we obtain new polynomialtime algorithms for compressed curves on surfaces, which we believe are of independent interest. We provide a polynomialtime algorithm which, given an orientable surface and a compressed loop on the surface, computes a canonical form for the loop as a compressed word. In particular, contractibility of compressed curves on surfaces can be decided in polynomial time; prior published work considered only constant genus surfaces. More generally, we solve the following normal subgroup membership problem in polynomial time: given an arbitrary orientable surface, a compressed closed curve, and a collection of disjoint normal curves, there is a polynomialtime algorithm to decide if the curve lies in the normal subgroup generated by components of the normal curves in the fundamental group of the surface after attaching the curves to a basepoint.more » « less

null (Ed.)Abstract Let X be a simply connected closed oriented manifold of rationally elliptic homotopy type. We prove that the string topology bracket on the $S^1$ equivariant homology $ {\overline {\text {H}}}_\ast ^{S^1}({\mathcal {L}} X,{\mathbb {Q}}) $ of the free loop space of X preserves the Hodge decomposition of $ {\overline {\text {H}}}_\ast ^{S^1}({\mathcal {L}} X,{\mathbb {Q}}) $ , making it a bigraded Lie algebra. We deduce this result from a general theorem on derived Poisson structures on the universal enveloping algebras of homologically nilpotent finitedimensional DG Lie algebras. Our theorem settles a conjecture of [7].more » « less

In the permutation inversion problem, the task is to find the preimage of some challenge value, given oracle access to the permutation. This fundamental problem in query complexity appears in many contexts, particularly cryptography. In this work, we examine the setting in which the oracle allows for quantum queries to both the forward and the inverse direction of the permutation—except that the challenge value cannot be submitted to the latter. Within that setting, we consider three options for the inversion algorithm: whether it can get quantum advice about the permutation, whether the query algorithm can restrict the distribution with which the challenge input is sampled, and whether it must produce the entire preimage (search) or only the first bit (decision). We prove several theorems connecting the hardness of the resulting variations of the permutation inversion problem and establish lower bounds for them. Our results show that, perhaps surprisingly, the permutation inversion problem does not become significantly easier when the adversary is granted oracle access to the inverse—provided it cannot query the challenge itself.

Contextfree language reachability (CFLreachability) is a fundamental framework for program analysis. A large variety of static analyses can be formulated as CFLreachability problems, which determines whether specific sourcesink pairs in an edgelabeled graph are connected by a reachable path, i.e., a path whose edge labels form a string accepted by the given CFL. Computing CFLreachability is expensive. The fastest algorithm exhibits a slightly subcubic time complexity with respect to the input graph size. Improving the scalability of CFLreachability is of practical interest, but reducing the time complexity is inherently difficult. In this paper, we focus on improving the scalability of CFLreachability from a more practical perspectivereducing the input graph size. Our idea arises from the existence of trivial edges, i.e., edges that do not affect any reachable path in CFLreachability. We observe that two nodes joined by trivial edges can be foldedby merging the two nodes with all the edges joining them removedwithout affecting the CFLreachability result. By studying the characteristic of the recursive state machines (RSMs), an alternative form of CFLs, we propose an approach to identify foldable node pairs without the need to verify the underlying reachable paths (which is equivalent to solving the CFLreachability problem). In particular, given a CFLreachability problem instance with an input graph G and an RSM, based on the correspondence between paths in G and state transitions in RSM, we propose a graph folding principle, which can determine whether two adjacent nodes are foldable by examining only their incoming and outgoing edges. On top of the graph folding principle, we propose an efficient graph folding algorithm GF. The time complexity of GF is linear with respect to the number of nodes in the input graph. Our evaluations on two clients (alias analysis and valueflow analysis) show that GF significantly accelerates RSM/CFLreachability by reducing the input graph size. On average, for valueflow analysis, GF reduces 60.96% of nodes and 42.67% of edges of the input graphs, obtaining a speedup of 4.65× and a memory usage reduction of 57.35%. For alias analysis, GF reduces 38.93% of nodes and 35.61% of edges of the input graphs, obtaining a speedup of 3.21× and a memory usage reduction of 65.19%.more » « less