Skip to main content
We gratefully acknowledge support from the Simons Foundation, member institutions, and all contributors. Donate
arXiv logo
Cornell University Logo

Data Structures and Algorithms

Authors and titles for recent submissions

See today's new changes

Total of 57 entries : 1-50 51-57
Showing up to 50 entries per page: fewer | more | all

Mon, 1 Dec 2025 (showing 18 of 18 entries )

[1] arXiv:2511.23363 [pdf, html, other]
Title: Homomorphism Testing with Resilience to Online Manipulations
Esty Kelman, Uri Meir, Debanuj Nayak, Sofya Raskhodnikova
Subjects: Data Structures and Algorithms (cs.DS)
[2] arXiv:2511.23211 [pdf, html, other]
Title: Improved and Parameterized Algorithms for Online Multi-level Aggregation: A Memory-based Approach
Alexander Turoczy, Young-San Lin
Comments: 29 pages
Subjects: Data Structures and Algorithms (cs.DS)
[3] arXiv:2511.23012 [pdf, html, other]
Title: Solution Discovery for Vertex Cover, Independent Set, Dominating Set, and Feedback Vertex Set
Rin Saito, Anouk Sommer, Tatsuhiro Suga, Takahiro Suzuki, Yuma Tamura
Subjects: Data Structures and Algorithms (cs.DS)
[4] arXiv:2511.22914 [pdf, html, other]
Title: Towards an algebraic approach to the reconfiguration CSP
Kei Kimura
Comments: To appear in Proceedings of SOFSEM-26
Subjects: Data Structures and Algorithms (cs.DS)
[5] arXiv:2511.22912 [pdf, html, other]
Title: Spanning Trees with a Small Vertex Cover: the Complexity on Specific Graph Classes
Toranosuke Kokai, Akira Suzuki, Takahiro Suzuki, Yuma Tamura, Xiao Zhou
Subjects: Data Structures and Algorithms (cs.DS)
[6] arXiv:2511.22803 [pdf, html, other]
Title: Sublinear Edge Fault Tolerant Spanners for Hypergraphs
Jialin He, Nicholas Popescu, Chunjiang Zhu
Subjects: Data Structures and Algorithms (cs.DS)
[7] arXiv:2511.22604 [pdf, html, other]
Title: Improved exploration of temporal graphs
Paul Bastide, Carla Groenland, Lukas Michel, Clément Rambaud
Comments: 8 pages, 2 figures
Subjects: Data Structures and Algorithms (cs.DS); Combinatorics (math.CO)
[8] arXiv:2511.22289 [pdf, html, other]
Title: Efficient Trace Frequency Queries in Sparse Graphs
Christine Awofeso, Pål Grønås Drange, Patrick Greaves, Oded Lachish, Felix Reidl
Subjects: Data Structures and Algorithms (cs.DS)
[9] arXiv:2511.22212 [pdf, html, other]
Title: Balancing Two-Dimensional Straight-Line Programs
Itai Boneh, Estéban Gabory, Paweł Gawrychowski, Adam Górkiewicz
Subjects: Data Structures and Algorithms (cs.DS)
[10] arXiv:2511.22084 [pdf, html, other]
Title: How fast are algorithms reducing the demands on memory? A survey of progress in space complexity
Hayden Rome, Jayson Lynch, Jeffery Li, Chirag Falor, Neil Thompson
Subjects: Data Structures and Algorithms (cs.DS)
[11] arXiv:2511.22070 [pdf, html, other]
Title: MagnifierSketch: Quantile Estimation Centered at One Point
Jiarui Guo, Qiushi Lyu, Yuhan Wu, Haoyu Li, Zhaoqian Yao, Yuqi Dong, Xiaolin Wang, Bin Cui, Tong Yang
Subjects: Data Structures and Algorithms (cs.DS)
[12] arXiv:2511.21919 [pdf, html, other]
Title: Identifying all snarls and superbubbles in linear-time, via a unified SPQR-tree framework
Francisco Sena, Aleksandr Politov, Corentin Moumard, Manuel Cáceres, Sebastian Schmidt, Juha Harviainen, Alexandru I. Tomescu
Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM); Quantitative Methods (q-bio.QM)
[13] arXiv:2511.21876 [pdf, html, other]
Title: Differential privacy from axioms
Guy Blanc, William Pires, Toniann Pitassi
Subjects: Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG)
[14] arXiv:2511.21868 [pdf, html, other]
Title: A Combinatorial Characterization of Constant Mixing Time
Lap Chi Lau, Raymond Liu
Subjects: Data Structures and Algorithms (cs.DS); Combinatorics (math.CO)
[15] arXiv:2511.23388 (cross-list from cs.LG) [pdf, html, other]
Title: Learning-Augmented Online Bipartite Matching in the Random Arrival Order Model
Kunanon Burathep, Thomas Erlebach, William K. Moses Jr
Comments: 17 pages, 1 figure, 1 table. An extended abstract of this paper appears in the proceedings of the 51st International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2026)
Subjects: Machine Learning (cs.LG); Data Structures and Algorithms (cs.DS)
[16] arXiv:2511.23160 (cross-list from quant-ph) [pdf, other]
Title: Efficient Identification of Permutation Symmetries in Many-Body Hamiltonians via Graph Theory
Saumya Shah, Patrick Rebentrost
Comments: 18 pages, 5 tables
Subjects: Quantum Physics (quant-ph); Data Structures and Algorithms (cs.DS)
[17] arXiv:2511.22562 (cross-list from math.CO) [pdf, html, other]
Title: Making an oriented graph acyclic using inversions of bounded or prescribed size
Jørgen Bang-Jensen, Frédéric Havet, Florian Hörsch, Clément Rambaud, Amadeus Reinald, Caroline Silva
Comments: 38 pages, 1 figure
Subjects: Combinatorics (math.CO); Data Structures and Algorithms (cs.DS)
[18] arXiv:2511.21867 (cross-list from quant-ph) [pdf, html, other]
Title: Accuracy and resource advantages of quantum eigenvalue estimation with non-Hermitian transcorrelated electronic Hamiltonians
Alexey Uvarov, Artur F. Izmaylov
Comments: 11 pages
Subjects: Quantum Physics (quant-ph); Data Structures and Algorithms (cs.DS); Chemical Physics (physics.chem-ph)

Thu, 27 Nov 2025 (showing 7 of 7 entries )

[19] arXiv:2511.21418 [pdf, html, other]
Title: Sublinear Time Low-Rank Approximation of Hankel Matrices
Michael Kapralov, Cameron Musco, Kshiteej Sheth
Comments: To appear in SODA 2026
Subjects: Data Structures and Algorithms (cs.DS); Numerical Analysis (math.NA)
[20] arXiv:2511.20882 [pdf, html, other]
Title: Quadratic-Time Algorithm for the Maximum-Weight $(k, \ell)$-Sparse Subgraph Problem
Bence Deák, Péter Madarasi
Subjects: Data Structures and Algorithms (cs.DS); Computational Geometry (cs.CG); Discrete Mathematics (cs.DM); Combinatorics (math.CO)
[21] arXiv:2511.20771 [pdf, html, other]
Title: Exploiting Low Scanwidth to Resolve Soft Polytomies
Sebastian Bruchhold, Mathias Weller
Comments: 22 pages. An extended abstract was accepted at SOFSEM 2026
Subjects: Data Structures and Algorithms (cs.DS)
[22] arXiv:2511.21637 (cross-list from cs.GT) [pdf, html, other]
Title: Arctic Auctions, Linear Fisher Markets, and Rational Convex Programs
Vijay V. Vazirani
Comments: 24 pages
Subjects: Computer Science and Game Theory (cs.GT); Data Structures and Algorithms (cs.DS); Theoretical Economics (econ.TH)
[23] arXiv:2511.21099 (cross-list from cs.GT) [pdf, html, other]
Title: Cycle Cancellation for Submodular Fractional Allocations and Applications
Chandra Chekuri, Pooja Kulkarni, Ruta Mehta, Jan Vondrak
Comments: 20 pages
Subjects: Computer Science and Game Theory (cs.GT); Data Structures and Algorithms (cs.DS)
[24] arXiv:2511.21015 (cross-list from cs.CC) [pdf, html, other]
Title: The communication complexity of distributed estimation
Parikshit Gopalan, Raghu Meka, Prasad Raghavendra, Mihir Singhal, Avi Wigderson
Subjects: Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS)
[25] arXiv:2511.20954 (cross-list from cs.CG) [pdf, html, other]
Title: $δ$-core subsampling, strong collapses and TDA
Elias Gabriel Minian
Comments: 14 pages, 8 figures, 5 tables
Subjects: Computational Geometry (cs.CG); Data Structures and Algorithms (cs.DS); Algebraic Topology (math.AT)

Wed, 26 Nov 2025 (showing 10 of 10 entries )

[26] arXiv:2511.20385 [pdf, html, other]
Title: Counting large patterns in degenerate graphs
Christine Awofeso, Patrick Greaves, Oded Lachish, Felix Reidl
Subjects: Data Structures and Algorithms (cs.DS)
[27] arXiv:2511.20376 [pdf, html, other]
Title: Robust Algorithms for Finding Cliques in Random Intersection Graphs via Sum-of-Squares
Andreas Göbel, Janosch Ruff, Leon Schiller
Subjects: Data Structures and Algorithms (cs.DS)
[28] arXiv:2511.20338 [pdf, html, other]
Title: Maintaining Bipartite Colourings on Temporal Graphs on a Budget
Duncan Adamson, George B. Mertzios, Paul G. Spirakis
Subjects: Data Structures and Algorithms (cs.DS)
[29] arXiv:2511.20111 [pdf, html, other]
Title: Greedy Algorithms for Shortcut Sets and Hopsets
Ben Bals, Joakim Blikstad, Greg Bodwin, Daniel Dadush, Sebastian Forster, Yasamin Nazari
Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM)
[30] arXiv:2511.19690 [pdf, html, other]
Title: The Buffer Minimization Problem for Scheduling Flow Jobs with Conflicts
Niklas Haas, Sören Schmitt, Rob van Stee
Comments: 17 pages, 1 figure, to appear in SOFSEM 2026
Subjects: Data Structures and Algorithms (cs.DS)
[31] arXiv:2511.20397 (cross-list from cs.LG) [pdf, html, other]
Title: Model-Based Learning of Whittle indices
Joël Charles-Rebuffé, Nicolas Gast, Bruno Gaujal
Comments: 31 pages, 8 figures, submitted to TOMPECS
Subjects: Machine Learning (cs.LG); Data Structures and Algorithms (cs.DS); Numerical Analysis (math.NA)
[32] arXiv:2511.20317 (cross-list from cs.SC) [pdf, html, other]
Title: Fast Matrix Multiplication via Ternary Meta Flip Graphs
A. I. Perminov
Subjects: Symbolic Computation (cs.SC); Data Structures and Algorithms (cs.DS)
[33] arXiv:2511.19998 (cross-list from cs.LG) [pdf, html, other]
Title: REWA: A General Theory of Witness-Based Similarity
Nikit Phadke
Subjects: Machine Learning (cs.LG); Data Structures and Algorithms (cs.DS); Information Retrieval (cs.IR)
[34] arXiv:2511.19880 (cross-list from cs.DC) [pdf, html, other]
Title: Improved Linear-Time Construction of Minimal Dominating Set via Mobile Agents
Prabhat Kumar Chand, Anisur Rahaman Molla
Subjects: Distributed, Parallel, and Cluster Computing (cs.DC); Data Structures and Algorithms (cs.DS); Multiagent Systems (cs.MA); Robotics (cs.RO)
[35] arXiv:2511.19439 (cross-list from math.RA) [pdf, html, other]
Title: Polynomial Algorithms for Simultaneous Unitary Similarity and Equivalence
Harikrishna VJ, Vittal Rao, Ramakrishnan K.R
Comments: 14 pages, 2 figures
Subjects: Rings and Algebras (math.RA); Data Structures and Algorithms (cs.DS); Quantum Physics (quant-ph)

Tue, 25 Nov 2025 (showing first 15 of 16 entries )

[36] arXiv:2511.19398 [pdf, html, other]
Title: PTF Testing Lower Bounds for Non-Gaussian Component Analysis
Ilias Diakonikolas, Daniel M. Kane, Sihan Liu, Thanasis Pittas
Subjects: Data Structures and Algorithms (cs.DS); Information Theory (cs.IT); Machine Learning (cs.LG); Statistics Theory (math.ST); Machine Learning (stat.ML)
[37] arXiv:2511.19153 [pdf, html, other]
Title: Fast and Flexible Flow Decompositions in General Graphs via Dominators
Francisco Sena, Alexandru I. Tomescu
Subjects: Data Structures and Algorithms (cs.DS); Optimization and Control (math.OC); Genomics (q-bio.GN)
[38] arXiv:2511.19085 [pdf, html, other]
Title: New Algorithms and Hardness Results for Connected Clustering
Jan Eube, Heiko Röglin
Subjects: Data Structures and Algorithms (cs.DS)
[39] arXiv:2511.19027 [pdf, html, other]
Title: A sufficient condition for characterizing the one-sided testable properties of families of graphs in the Random Neighbour Oracle Model
Christine Awofeso, Patrick Greaves, Oded Lachish, Amit Levi, Felix Reidl
Subjects: Data Structures and Algorithms (cs.DS)
[40] arXiv:2511.18666 [pdf, other]
Title: Overlap Analysis of the Shortest Path Problem: Local Search, Landscapes, and Franz--Parisi Potential
Frederic Koehler, Joonhyung Shin
Comments: Abstract shortened for arxiv
Subjects: Data Structures and Algorithms (cs.DS); Combinatorics (math.CO); Probability (math.PR)
[41] arXiv:2511.18554 [pdf, html, other]
Title: Online Smoothed Demand Management
Adam Lechowicz, Nicolas Christianson, Mohammad Hajiesmaili, Adam Wierman, Prashant Shenoy
Comments: 69 pages, 12 figures
Subjects: Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG); Systems and Control (eess.SY)
[42] arXiv:2511.18546 [pdf, html, other]
Title: Weighted Chairman Assignment and Flow-Time Scheduling
Siyue Liu, Victor Reis
Subjects: Data Structures and Algorithms (cs.DS)
[43] arXiv:2511.18460 [pdf, html, other]
Title: Steiner Forest: A Simplified Better-Than-2 Approximation
Anupam Gupta, Vera Traub
Subjects: Data Structures and Algorithms (cs.DS)
[44] arXiv:2511.18263 [pdf, html, other]
Title: Approximating maximum properly colored forests via degree bounded independent sets
Yuhang Bai, Kristóf Bérczi, Johanna K. Siemelink
Subjects: Data Structures and Algorithms (cs.DS)
[45] arXiv:2511.18253 [pdf, other]
Title: From Hop Reduction to Sparsification for Negative Length Shortest Paths
Kent Quanrud, Navid Tajkhorshid
Comments: Updates the running times in the previous version based on independent work by LLRZ25
Subjects: Data Structures and Algorithms (cs.DS)
[46] arXiv:2511.17707 [pdf, html, other]
Title: Reconstructing Sets of Strings from Their k-way Projections: Algorithms & Complexity
Elise Tate, Joshua A. Grochow
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)
[47] arXiv:2511.19225 (cross-list from cs.GT) [pdf, other]
Title: Bipartiteness in Progressive Second-Price Multi-Auction Networks with Perfect Substitute
Jordana Blazek, Frederick C. Harris Jr
Subjects: Computer Science and Game Theory (cs.GT); Data Structures and Algorithms (cs.DS); Theoretical Economics (econ.TH)
[48] arXiv:2511.19068 (cross-list from q-bio.GN) [pdf, other]
Title: The TAG array of a multiple sequence alignment
Jannik Olbrich, Enno Ohlebusch
Subjects: Genomics (q-bio.GN); Data Structures and Algorithms (cs.DS)
[49] arXiv:2511.19018 (cross-list from cs.DM) [pdf, html, other]
Title: Using random spanning trees in survivable networks design
Blazej Wrobel, Dominik Bojko
Subjects: Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS)
[50] arXiv:2511.18252 (cross-list from math.PR) [pdf, html, other]
Title: The Mixed Birth-death/death-Birth Moran Process
David A. Brewster, Yichen Huang, Michael Mitzenmacher, Martin A. Nowak
Comments: To appear at ITCS 2026
Subjects: Probability (math.PR); Data Structures and Algorithms (cs.DS)
Total of 57 entries : 1-50 51-57
Showing up to 50 entries per page: fewer | more | all