More Like this

1. The decomposition of the higher-order homology embedding constructed from the k-Laplacian

   Chen, Yu-Chia; Meila, Marina (December 2021, Advances in neural information processing systems)

   M. Ranzato; A. Beygelzimer; Y. Dauphin; P.S. Liang; J. Wortman Vaughan (Ed.)

   The null space of the k-th order Laplacian Lk, known as the {\em k-th homology vector space}, encodes the non-trivial 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 k-th 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 NP-hard 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
2. Algorithms for Contractibility of Compressed Curves on 3-Manifold Boundaries

   https://doi.org/10.1007/s00454-022-00411-x  

   Chambers, Erin Wolf; Lazarus, Francis; de Mesmay, Arnaud; Parsa, Salman (September 2023, Discrete & Computational Geometry)

   In this paper we prove that the problem of deciding contractibility of an arbitrary closed curve on the boundary of a 3-manifold 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 (non-compressed) curves, and, in very limited cases, for curves with self-intersections. Furthermore, our algorithm is fixed-parameter tractable in the size of the input 3-manifold. As part of our proof, we obtain new polynomial-time algorithms for compressed curves on surfaces, which we believe are of independent interest. We provide a polynomial-time 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 polynomial-time 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
3. Hodge decomposition of string topology

   https://doi.org/10.1017/fms.2021.26  

   Berest, Yuri; Ramadoss, Ajay C.; Zhang, Yining (January 2021, Forum of Mathematics, Sigma)

   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 finite-dimensional DG Lie algebras. Our theorem settles a conjecture of [7]. 

   more » « less
4. On the Two-sided Permutation Inversion Problem

   https://doi.org/10.62056/a0qj89n4e  

   Alagic, Gorjan; Bai, Chen; Poremba, Alexander; Shi, Kaiyan (April 2024, IACR Communications in Cryptology)

   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. 

   more » « less
5. Recursive State Machine Guided Graph Folding for Context-Free Language Reachability

   https://doi.org/10.1145/3591233  

   Lei, Yuxiang; Sui, Yulei; Tan, Shin_Hwei; Zhang, Qirun (June 2023, Proceedings of the ACM on Programming Languages)

   Context-free language reachability (CFL-reachability) is a fundamental framework for program analysis. A large variety of static analyses can be formulated as CFL-reachability problems, which determines whether specific source-sink pairs in an edge-labeled graph are connected by a reachable path, i.e., a path whose edge labels form a string accepted by the given CFL. Computing CFL-reachability is expensive. The fastest algorithm exhibits a slightly subcubic time complexity with respect to the input graph size. Improving the scalability of CFL-reachability is of practical interest, but reducing the time complexity is inherently difficult. In this paper, we focus on improving the scalability of CFL-reachability from a more practical perspective---reducing the input graph size. Our idea arises from the existence of trivial edges, i.e., edges that do not affect any reachable path in CFL-reachability. We observe that two nodes joined by trivial edges can be folded---by merging the two nodes with all the edges joining them removed---without affecting the CFL-reachability 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 CFL-reachability problem). In particular, given a CFL-reachability 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 value-flow analysis) show that GF significantly accelerates RSM/CFL-reachability by reducing the input graph size. On average, for value-flow 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