CayleyR: Solving the TopSpin puzzle via cycle intersection

• URL: http://arxiv.org/abs/2607.13219v1
• Date: Tue, 14 Jul 2026 19:28:41 GMT
• Title: CayleyR: Solving the TopSpin puzzle via cycle intersection
• Abstract summary: We present cayleyR, an R package for solving permutation puzzles by detecting cycle intersections in Cayley graphs.<n>We describe the mathematical framework, the algorithm, and its implementation, which combines a C++ hash-indexed state store with optional Vulkan GPU acceleration.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present cayleyR, an R package for solving permutation puzzles by detecting cycle intersections in Cayley graphs. The core algorithm performs an iterative bidirectional search: from both the initial and target permutation states, random operation sequences generate cycles in the Cayley graph of the symmetric group Sn; their intersection yields a connecting path. When no direct intersection is found, a distance-guided bridge selection narrows the gap, and the process repeats. The package targets the TopSpin(n,k) puzzle, whose state space is a Cayley graph of Sn generated by a cyclic shift and a prefix reversal. We describe the mathematical framework, the algorithm, and its implementation, which combines a C++ hash-indexed state store with optional Vulkan GPU acceleration. The software is publicly available on CRAN.

Related papers

• Scalable Graph Coreset Selection via Greedy Sampling [48.91894218306487]
  We propose a simple and effective column-selective graph sampling algorithm based on a minimum inner product greedy selection rule.<n>We analyze the algorithm under the block model and show that, when the degree distribution is balanced across nodes, the algorithm achieves proportional sampling to cluster size.
  arXiv  Detail & Related papers  (2026-07-30T02:45:31Z)
• SWING: Unlocking Implicit Graph Representations for Graph Random Features [57.956136773668476]
  We propose SWING: Space Walks for Implicit Network Graphs, a new class of algorithms for computations involving Graph Random Features on graphs.<n>We provide detailed analysis of SWING and complement it with thorough experiments on different classes of i-graphs.
  arXiv  Detail & Related papers  (2026-02-13T08:12:38Z)
• Diffusion Models for Cayley Graphs [0.0]
  We show how to formulate problems in the framework of diffusion models.<n>We propose a reversed score'' ansatz which substantially improves over previous comparable algorithms.
  arXiv  Detail & Related papers  (2025-03-07T16:33:16Z)
• CayleyPy RL: Pathfinding and Reinforcement Learning on Cayley Graphs [0.0]
  This paper is the second in a series of studies on developing efficient artificial intelligence-based approaches to pathfinding on large graphs.<n>We present a novel combination of a reinforcement learning approach with a more direct diffusion distance approach from the first paper.<n>We provide strong support for the OEIS-A186783 conjecture that the diameter is equal to n(n-1)/2 by machine learning and mathematical methods.
  arXiv  Detail & Related papers  (2025-02-25T21:53:41Z)
• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry. The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time. Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
  arXiv  Detail & Related papers  (2024-05-02T10:29:06Z)
• Qandle: Accelerating State Vector Simulation Using Gate-Matrix Caching and Circuit Splitting [3.3002472385435655]
  We address the computational complexity associated with state-vector simulation for quantum circuits. Quantum gate matrix caching reduces the overhead of repeated applications of the Kronecker product. Circuit splitting divides the circuit into sub-circuits with fewer gates by constructing a dependency graph.
  arXiv  Detail & Related papers  (2024-04-14T10:52:01Z)
• General Graph Random Features [42.75616308187867]
  We propose a novel random walk-based algorithm for unbiased estimation of arbitrary functions of a weighted adjacency matrix. Our algorithm enjoys subquadratic time complexity with respect to the number of nodes, overcoming the notoriously prohibitive cubic scaling of exact graph kernel evaluation.
  arXiv  Detail & Related papers  (2023-10-07T15:47:31Z)
• Quick Adaptive Ternary Segmentation: An Efficient Decoding Procedure For Hidden Markov Models [41.99844472131922]
  Decoding the original signal from the noisy observations is one of the main goals in nearly all HMM based data analyses.<n>We present QATS, a divide-and-conquer algorithm with computational polylogarithmic complexity in the length of the sequence, and cubic in the size of the state space.<n>An implementation of QATS is in the R-package QATS on GitHub.
  arXiv  Detail & Related papers  (2023-05-29T19:37:48Z)
• Kernelized multi-graph matching [0.0]
  We introduce a novel kernelized multigraph matching technique that handles both the attributes of the pair and the edges of the graphs. We propose several projectors leading to improved stability of the results.
  arXiv  Detail & Related papers  (2022-10-11T07:22:47Z)
• Multimarked Spatial Search by Continuous-Time Quantum Walk [0.0]
  We describe a framework for determining the computational complexity of spatial search by continuous-time quantum walk on arbitrary graphs. The quantum walk is driven by a Hamiltonian derived from the adjacency matrix of the graph modified by the presence of the marked vertices.
  arXiv  Detail & Related papers  (2022-03-27T20:22:17Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  We address the non- optimisation problem of finding a matrix on the Stiefel manifold that maximises a quadratic objective function. We propose a simple yet effective sparsity-promoting algorithm for finding the dominant eigenspace matrix.
  arXiv  Detail & Related papers  (2021-09-30T19:17:35Z)
• Determinantal Beam Search [75.84501052642361]
  Beam search is a go-to strategy for decoding neural sequence models. In use-cases that call for multiple solutions, a diverse or representative set is often desired. By posing iterations in beam search as a series of subdeterminant problems, we can turn the algorithm into a diverse subset selection process.
  arXiv  Detail & Related papers  (2021-06-14T13:01:46Z)
• Biclustering and Boolean Matrix Factorization in Data Streams [12.005731086591139]
  We study the clustering of bipartite graphs and Boolean matrix factorization in data streams. We provide an algorithm that, after one pass over the stream, recovers the set of clusters on the right side of the graph using sublinear space. We evaluate an implementation of the algorithm on synthetic data and on real-world data.
  arXiv  Detail & Related papers  (2020-12-05T23:02:43Z)
• Learning the Positions in CountSketch [51.15935547615698]
  We consider sketching algorithms which first compress data by multiplication with a random sketch matrix, and then apply the sketch to quickly solve an optimization problem. In this work we propose the first learning algorithm that also optimize the locations of the non-zero entries. We show this algorithm gives better accuracy for low rank approximation than previous work, and apply it to other problems such as $k$-means clustering for the first time.
  arXiv  Detail & Related papers  (2020-07-20T05:06:29Z)
• Space-Time Correspondence as a Contrastive Random Walk [47.40711876423659]
  We cast correspondence as prediction of links in a space-time graph constructed from video. We learn a representation in which pairwise similarity defines transition probability of a random walk. We demonstrate that a technique we call edge dropout, as well as self-supervised adaptation at test-time, further improve transfer for object-centric correspondence.
  arXiv  Detail & Related papers  (2020-06-25T17:56:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.