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 63 entries : 1-50 51-63
Showing up to 50 entries per page: fewer | more | all

Fri, 22 Nov 2024 (showing 12 of 12 entries )

[1] arXiv:2411.14387 [pdf, other]
Title: Hardness Amplification for Dynamic Binary Search Trees
Shunhua Jiang, Victor Lecomte, Omri Weinstein, Sorrachai Yingchareonthawornchai
Subjects: Data Structures and Algorithms (cs.DS)
[2] arXiv:2411.14344 [pdf, html, other]
Title: Overcomplete Tensor Decomposition via Koszul-Young Flattenings
Pravesh K. Kothari, Ankur Moitra, Alexander S. Wein
Comments: 42 pages
Subjects: Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG)
[3] arXiv:2411.14305 [pdf, html, other]
Title: Outlier-robust Mean Estimation near the Breakdown Point via Sum-of-Squares
Hongjie Chen, Deepak Narayanan Sridharan, David Steurer
Comments: Accepted at SODA 2025, 47 pages
Subjects: Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG); Machine Learning (stat.ML)
[4] arXiv:2411.14006 [pdf, html, other]
Title: Experimental comparison of graph-based approximate nearest neighbor search algorithms on edge devices
Ali Ganbarov, Jicheng Yuan, Anh Le-Tuan, Manfred Hauswirth, Danh Le-Phuoc
Subjects: Data Structures and Algorithms (cs.DS); Hardware Architecture (cs.AR); Computer Vision and Pattern Recognition (cs.CV); Distributed, Parallel, and Cluster Computing (cs.DC); Performance (cs.PF)
[5] arXiv:2411.13817 [pdf, html, other]
Title: Dynamic Structural Clustering Unleashed: Flexible Similarities, Versatile Updates and for All Parameters
Zhuowei Zhao, Junhao Gan, Boyu Ruan, Zhifeng Bao, Jianzhong Qi, Sibo Wang
Subjects: Data Structures and Algorithms (cs.DS)
[6] arXiv:2411.13728 [pdf, html, other]
Title: Distributed Distance Sensitivity Oracles
Vignesh Manoharan, Vijaya Ramachandran
Subjects: Data Structures and Algorithms (cs.DS)
[7] arXiv:2411.13708 [pdf, html, other]
Title: Comments on "$\mathcal{O}(m\cdot n)$ algorithms for the recognition and isomorphism problems on circular-arc graphs"
Tomasz Krawczyk
Comments: Comment on doi:https://doi.org/10.1137/S0097539793260726
Subjects: Data Structures and Algorithms (cs.DS); Combinatorics (math.CO)
[8] arXiv:2411.14431 (cross-list from cs.CC) [pdf, html, other]
Title: On Optimal Testing of Linearity
Vipul Arora, Esty Kelman, Uri Meir
Comments: To appear at SOSA 2025
Subjects: Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS)
[9] arXiv:2411.14349 (cross-list from cs.LG) [pdf, html, other]
Title: Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginals
Anxin Guo, Aravindan Vijayaraghavan
Subjects: Machine Learning (cs.LG); Data Structures and Algorithms (cs.DS)
[10] arXiv:2411.14336 (cross-list from math.PR) [pdf, html, other]
Title: Finding the root in random nearest neighbor trees
Anna Brandenberger, Cassandra Marcussen, Elchanan Mossel, Madhu Sudan
Comments: 22 pages, 7 figures
Subjects: Probability (math.PR); Data Structures and Algorithms (cs.DS); Social and Information Networks (cs.SI)
[11] arXiv:2411.13682 (cross-list from cs.LG) [pdf, html, other]
Title: Differentially Private Learning Beyond the Classical Dimensionality Regime
Cynthia Dwork, Pranay Tankala, Linjun Zhang
Subjects: Machine Learning (cs.LG); Cryptography and Security (cs.CR); Data Structures and Algorithms (cs.DS)
[12] arXiv:2411.13601 (cross-list from stat.CO) [pdf, other]
Title: Error Analysis of Sum-Product Algorithms under Stochastic Rounding
Pablo de Oliveira Castro (LI-PaRAD, UVSQ), El-Mehdi El Arar (IRISA, UR), Eric Petit, Devan Sohier (LI-PaRAD, UVSQ)
Subjects: Computation (stat.CO); Data Structures and Algorithms (cs.DS)

Thu, 21 Nov 2024 (showing 7 of 7 entries )

[13] arXiv:2411.13462 [pdf, html, other]
Title: Sampling and Integration of Logconcave Functions by Algorithmic Diffusion
Yunbum Kook, Santosh S. Vempala
Comments: 60 pages, 1 figure
Subjects: Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG); Statistics Theory (math.ST); Machine Learning (stat.ML)
[14] arXiv:2411.13374 [pdf, other]
Title: On the structure of normalized models of circular-arc graphs -- Hsu's approach revisited
Tomasz Krawczyk
Comments: 84 pages
Subjects: Data Structures and Algorithms (cs.DS)
[15] arXiv:2411.12976 [pdf, html, other]
Title: Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds
Samuel Hwang, Noah G. Singer, Santhoshini Velusamy
Comments: 17 pages, 7 figures
Subjects: Data Structures and Algorithms (cs.DS)
[16] arXiv:2411.13513 (cross-list from cs.GT) [pdf, html, other]
Title: Procurement Auctions via Approximately Optimal Submodular Optimization
Yuan Deng, Amin Karbasi, Vahab Mirrokni, Renato Paes Leme, Grigoris Velegkas, Song Zuo
Subjects: Computer Science and Game Theory (cs.GT); Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG)
[17] arXiv:2411.13171 (cross-list from cs.CG) [pdf, other]
Title: Parameterized Geometric Graph Modification with Disk Scaling
Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Saket Saurabh, Meirav Zehavi
Comments: To appear in ITCS 2025
Subjects: Computational Geometry (cs.CG); Data Structures and Algorithms (cs.DS)
[18] arXiv:2411.13141 (cross-list from cs.CC) [pdf, html, other]
Title: (Independent) Roman Domination Parameterized by Distance to Cluster
Pradeesha Ashok, Gautam K. Das, Arti Pandey, Kaustav Paul, Subhabrata Paul
Comments: arXiv admin note: text overlap with arXiv:2405.10556 by other authors
Subjects: Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS); Combinatorics (math.CO)
[19] arXiv:2411.13083 (cross-list from cs.LG) [pdf, html, other]
Title: Omnipredicting Single-Index Models with Multi-Index Models
Lunjia Hu, Kevin Tian, Chutong Yang
Subjects: Machine Learning (cs.LG); Data Structures and Algorithms (cs.DS); Optimization and Control (math.OC); Machine Learning (stat.ML)

Wed, 20 Nov 2024 (showing 14 of 14 entries )

[20] arXiv:2411.12694 [pdf, html, other]
Title: Local Density and its Distributed Approximation
Aleksander Bjørn Christiansen, Ivor van der Hoog, Eva Rotenberg
Subjects: Data Structures and Algorithms (cs.DS); Distributed, Parallel, and Cluster Computing (cs.DC)
[21] arXiv:2411.12439 [pdf, html, other]
Title: Efficient terabyte-scale text compression via stable local consistency and parallel grammar processing
Diego Diaz-Dominguez
Subjects: Data Structures and Algorithms (cs.DS)
[22] arXiv:2411.12438 [pdf, other]
Title: Dimension Reduction via Sum-of-Squares and Improved Clustering Algorithms for Non-Spherical Mixtures
Prashanti Anderson, Mitali Bafna, Rares-Darius Buhai, Pravesh K. Kothari, David Steurer
Comments: 64 pages
Subjects: Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG); Machine Learning (stat.ML)
[23] arXiv:2411.12365 [pdf, other]
Title: Brief Announcement: Parallel Construction of Bumped Ribbon Retrieval
Matthias Becht, Hans-Peter Lehmann, Peter Sanders
Subjects: Data Structures and Algorithms (cs.DS)
[24] arXiv:2411.12241 [pdf, html, other]
Title: Extending the Burrows-Wheeler Transform for Cartesian Tree Matching and Constructing It
Eric M. Osterkamp, Dominik Köppl
Subjects: Data Structures and Algorithms (cs.DS)
[25] arXiv:2411.12160 [pdf, html, other]
Title: Space-Efficient Online Computation of String Net Occurrences
Takuya Mieno, Shunsuke Inenaga
Subjects: Data Structures and Algorithms (cs.DS)
[26] arXiv:2411.12099 [pdf, html, other]
Title: Sorted Consecutive Occurrence Queries in Substrings
Waseem Akram, Takuya Mieno
Subjects: Data Structures and Algorithms (cs.DS); Computational Geometry (cs.CG)
[27] arXiv:2411.12069 [pdf, html, other]
Title: Matroid Secretary via Labeling Schemes
Kristóf Bérczi, Vasilis Livanos, José Soto, Victor Verdugo
Comments: 35 pages, 3 figures
Subjects: Data Structures and Algorithms (cs.DS)
[28] arXiv:2411.12035 [pdf, html, other]
Title: Parsing Millions of DNS Records per Second
Jeroen Koekkoek, Daniel Lemire
Comments: software at this https URL
Subjects: Data Structures and Algorithms (cs.DS)
[29] arXiv:2411.12730 (cross-list from quant-ph) [pdf, other]
Title: Testing classical properties from quantum data
Matthias C. Caro, Preksha Naik, Joseph Slote
Comments: 38 + 14 pages, 2 tables, 2 figures
Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG)
[30] arXiv:2411.12700 (cross-list from cs.LG) [pdf, other]
Title: Learning multivariate Gaussians with imperfect advice
Arnab Bhattacharyya, Davin Choo, Philips George John, Themis Gouleakis
Subjects: Machine Learning (cs.LG); Data Structures and Algorithms (cs.DS); Information Theory (cs.IT); Machine Learning (stat.ML)
[31] arXiv:2411.12696 (cross-list from cs.GT) [pdf, html, other]
Title: Weighted Envy Freeness With Limited Subsidies
Noga Klein Elmalem, Rica Gonen, Erel Segal-Halevi
Comments: 45 pages, 1 table
Subjects: Computer Science and Game Theory (cs.GT); Data Structures and Algorithms (cs.DS)
[32] arXiv:2411.12582 (cross-list from math.CO) [pdf, html, other]
Title: Reconfiguration Using Generalized Token Jumping
Jan Matyáš Křišťan, Jakub Svoboda
Comments: To appear at WALCOM 2025
Subjects: Combinatorics (math.CO); Data Structures and Algorithms (cs.DS)
[33] arXiv:2411.12360 (cross-list from cs.CR) [pdf, html, other]
Title: An Affine Equivalence Algorithm for S-boxes based on Matrix Invariants
Xincheng Hu, Xiao Zeng, Zhaoqiang Liu, Guowu Yang
Subjects: Cryptography and Security (cs.CR); Data Structures and Algorithms (cs.DS)

Tue, 19 Nov 2024 (showing first 17 of 26 entries )

[34] arXiv:2411.11781 [pdf, html, other]
Title: Towards Scalable and Practical Batch-Dynamic Connectivity
Quinten De Man, Laxman Dhulipala, Adam Karczmarz, Jakub Łącki, Julian Shun, Zhongqi Wang
Comments: This is a preliminary version of a paper that will appear at VLDB'25
Subjects: Data Structures and Algorithms (cs.DS); Databases (cs.DB); Distributed, Parallel, and Cluster Computing (cs.DC)
[35] arXiv:2411.11741 [pdf, html, other]
Title: A Bicriterion Concentration Inequality and Prophet Inequalities for $k$-Fold Matroid Unions
Noga Alon, Nick Gravin, Tristan Pollner, Aviad Rubinstein, Hongao Wang, S. Matthew Weinberg, Qianfan Zhang
Comments: To appear in ITCS 2025
Subjects: Data Structures and Algorithms (cs.DS); Probability (math.PR)
[36] arXiv:2411.11544 [pdf, html, other]
Title: The Complexity Landscape of Dynamic Distributed Subgraph Finding
Yi-Jun Chang, Lyuting Chen, Yanyu Chen, Gopinath Mishra, Mingyang Yang
Comments: 37 Pages
Subjects: Data Structures and Algorithms (cs.DS)
[37] arXiv:2411.11426 [pdf, html, other]
Title: SpiderDAN: Matching Augmentation in Demand-Aware Networks
Aleksander Figiel, Darya Melnyk, André Nichterlein, Arash Pourdamghani, Stefan Schmid
Comments: This paper has been accepted to SIAM Symposium on Algorithm Engineering and Experiments (ALENEX25)
Subjects: Data Structures and Algorithms (cs.DS); Networking and Internet Architecture (cs.NI)
[38] arXiv:2411.11277 [pdf, html, other]
Title: Massively Parallel Maximum Coverage Revisited
Thai Bui, Hoa T. Vu
Subjects: Data Structures and Algorithms (cs.DS); Distributed, Parallel, and Cluster Computing (cs.DC)
[39] arXiv:2411.11136 [pdf, html, other]
Title: Approximation algorithms for non-sequential star packing problems
Mengyuan Hu, An Zhang, Yong Chen, Mingyang Gong, Guohui Lin
Comments: Accepted for presentation in WALCOM 2025
Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM)
[40] arXiv:2411.11054 [pdf, html, other]
Title: Connectivity Certificate against Bounded-Degree Faults: Simpler, Better and Supporting Vertex Faults
Merav Parter, Elad Tzalik
Comments: To appear in SOSA 2025. 11 pages
Subjects: Data Structures and Algorithms (cs.DS)
[41] arXiv:2411.11051 [pdf, html, other]
Title: Amortized Analysis of Leftist Heaps
Berry Schoenmakers
Comments: 13 pages, 3 figures, full version (incl. Appendix B)
Journal-ref: Principles of Verification: Cycling the Probabilistic Landscape, Part I, LNCS 15260, Springer 2024, pp. 73-84
Subjects: Data Structures and Algorithms (cs.DS)
[42] arXiv:2411.11049 [pdf, html, other]
Title: Fault-Equivalent Lowest Common Ancestors
Asaf Petruschka
Subjects: Data Structures and Algorithms (cs.DS)
[43] arXiv:2411.10949 [pdf, html, other]
Title: Maximization of Approximately Submodular Functions
Thibaut Horel, Yaron Singer
Comments: 12 pages
Journal-ref: Advances in Neural Information Processing Systems 29, NeurIPS 2016, pp. 3045-3053
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)
[44] arXiv:2411.10707 [pdf, html, other]
Title: Differentiable Extensions with Rounding Guarantees for Combinatorial Optimization over Permutations
Robert R. Nerem, Zhishang Luo, Akbar Rafiey, Yusu Wang
Subjects: Data Structures and Algorithms (cs.DS); Optimization and Control (math.OC)
[45] arXiv:2411.10653 [pdf, html, other]
Title: Hardness Results on Characteristics for Elastic-Degenerated Strings
Dominik Köppl, Jannik Olbrich
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)
[46] arXiv:2411.11722 (cross-list from math.OC) [pdf, html, other]
Title: Solving convex QPs with structured sparsity under indicator conditions
Daniel Bienstock, Tongtong Chen
Subjects: Optimization and Control (math.OC); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS)
[47] arXiv:2411.11718 (cross-list from cs.DC) [pdf, html, other]
Title: Distributed Maximum Flow in Planar Graphs
Yaseen Abd-Elhaleem (1), Michal Dory (1), Merav Parter (2), Oren Weimann (1) ((1) University of Haifa, (2) Weizmann Institute of Science)
Comments: 54 pages, a short version about this work has appeared as a brief announcement in DISC 2024
Subjects: Distributed, Parallel, and Cluster Computing (cs.DC); Data Structures and Algorithms (cs.DS)
[48] arXiv:2411.11665 (cross-list from cs.DC) [pdf, html, other]
Title: Hash & Adjust: Competitive Demand-Aware Consistent Hashing
Arash Pourdamghani, Chen Avin, Robert Sama, Maryam Shiran, Stefan Schmid
Comments: This paper has been accepted to International Conference on Principles of Distributed Systems (OPODIS 2024)
Subjects: Distributed, Parallel, and Cluster Computing (cs.DC); Data Structures and Algorithms (cs.DS)
[49] arXiv:2411.11627 (cross-list from math.CO) [pdf, html, other]
Title: Explicit Two-Sided Vertex Expanders Beyond the Spectral Barrier
Jun-Ting Hsieh, Ting-Chun Lin, Sidhanth Mohanty, Ryan O'Donnell, Rachel Yun Zhang
Comments: 28 pages
Subjects: Combinatorics (math.CO); Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS)
[50] arXiv:2411.11516 (cross-list from cs.LG) [pdf, html, other]
Title: Efficient Sample-optimal Learning of Gaussian Tree Models via Sample-optimal Testing of Gaussian Mutual Information
Sutanu Gayen, Sanket Kale, Sayantan Sen
Comments: 47 pages, 16 figures, abstract shortened as per arXiv criteria
Subjects: Machine Learning (cs.LG); Data Structures and Algorithms (cs.DS); Machine Learning (stat.ML)
Total of 63 entries : 1-50 51-63
Showing up to 50 entries per page: fewer | more | all