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 47 entries : 1-25 26-47
Showing up to 25 entries per page: fewer | more | all

Fri, 21 Jun 2024 (showing 14 of 14 entries )

[1] arXiv:2406.14506 [pdf, html, other]
Title: Online Matching and Contention Resolution for Edge Arrivals with Vanishing Probabilities
Will Ma, Calum MacRury, Pranav Nuti
Journal-ref: In EC 2024
Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM); Combinatorics (math.CO)
[2] arXiv:2406.14384 [pdf, html, other]
Title: Low-Step Multi-Commodity Flow Emulators
Bernhard Haeupler, D Ellis Hershkowitz, Jason Li, Antti Roeyskoe, Thatchaphol Saranurak
Comments: Appears at STOC 2024
Subjects: Data Structures and Algorithms (cs.DS)
[3] arXiv:2406.14278 [pdf, html, other]
Title: Efficient Deterministic Algorithms for Maximizing Symmetric Submodular Functions
Zongqi Wan, Jialin Zhang, Xiaoming Sun, Zhijie Zhang
Subjects: Data Structures and Algorithms (cs.DS)
[4] arXiv:2406.14111 [pdf, html, other]
Title: Expander Hierarchies for Normalized Cuts on Graphs
Kathrin Hanauer, Monika Henzinger, Robin Münk, Harald Räcke, Maximilian Vötsch
Comments: Accepted to KDD'24, August 25-29, 2024, Barcelona, Spain
Subjects: Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG)
[5] arXiv:2406.13983 [pdf, html, other]
Title: Barter Exchange with Shared Item Valuations
Juan Luque, Sharmila Duppala, John Dickerson, Aravind Srinivasan
Comments: A previous version of this work appeared in the proceedings of WWW '24
Subjects: Data Structures and Algorithms (cs.DS)
[6] arXiv:2406.13573 [pdf, html, other]
Title: Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemer\'edi Graphs
Sepehr Assadi, Sanjeev Khanna
Comments: 24 pages, 2 figures
Subjects: Data Structures and Algorithms (cs.DS)
[7] arXiv:2406.13557 [pdf, other]
Title: satsuma: Structure-based Symmetry Breaking in SAT
Markus Anders, Sofia Brenner, Gaurav Rattan
Comments: accepted to SAT 2024
Subjects: Data Structures and Algorithms (cs.DS)
[8] arXiv:2406.13231 [pdf, html, other]
Title: Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut
Yu Cheng, Max Li, Honghao Lin, Zi-Yi Tai, David P.Woodruff, Jason Zhang
Subjects: Data Structures and Algorithms (cs.DS)
[9] arXiv:2406.13000 [pdf, html, other]
Title: Randomized Greedy Online Edge Coloring Succeeds for Dense and Randomly-Ordered Graphs
Aditi Dudeja, Rashmika Goswami, Michael Saks
Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM); Combinatorics (math.CO)
[10] arXiv:2406.14420 (cross-list from cs.LG) [pdf, html, other]
Title: Communication-efficient Vertical Federated Learning via Compressed Error Feedback
Pedro Valdeira, João Xavier, Cláudia Soares, Yuejie Chi
Subjects: Machine Learning (cs.LG); Distributed, Parallel, and Cluster Computing (cs.DC); Data Structures and Algorithms (cs.DS); Optimization and Control (math.OC)
[11] arXiv:2406.14330 (cross-list from quant-ph) [pdf, html, other]
Title: Promise of Graph Sparsification and Decomposition for Noise Reduction in QAOA: Analysis for Trapped-Ion Compilations
Jai Moondra, Philip C. Lotshaw, Greg Mohler, Swati Gupta
Subjects: Quantum Physics (quant-ph); Data Structures and Algorithms (cs.DS); Optimization and Control (math.OC)
[12] arXiv:2406.13879 (cross-list from quant-ph) [pdf, html, other]
Title: A Catalyst Framework for the Quantum Linear System Problem via the Proximal Point Algorithm
Junhyung Lyle Kim, Nai-Hui Chia, Anastasios Kyrillidis
Subjects: Quantum Physics (quant-ph); Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG); Optimization and Control (math.OC)
[13] arXiv:2406.13668 (cross-list from cs.LG) [pdf, html, other]
Title: Improved bounds for calibration via stronger sign preservation games
Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson, Noah Golowich, Robert Kleinberg, Princewill Okoroafor
Subjects: Machine Learning (cs.LG); Data Structures and Algorithms (cs.DS); Machine Learning (stat.ML)
[14] arXiv:2406.13412 (cross-list from quant-ph) [pdf, html, other]
Title: Tensor Decompositions and Adiabatic Quantum Computing for Discovering Practical Matrix Multiplication Algorithms
Valter Uotila
Comments: 12 pages, 6 figures
Subjects: Quantum Physics (quant-ph); Data Structures and Algorithms (cs.DS)

Wed, 19 Jun 2024 (showing 7 of 7 entries )

[15] arXiv:2406.12799 [pdf, html, other]
Title: Sample-Based Matroid Prophet Inequalities
Hu Fu, Pinyan Lu, Zhihao Gavin Tang, Hongxun Wu, Jinzhao Wu, Qianfan Zhang
Comments: To appear at EC'24
Subjects: Data Structures and Algorithms (cs.DS)
[16] arXiv:2406.12727 [pdf, html, other]
Title: Massively Parallel Ruling Set Made Deterministic
Jeff Giliberti, Zahra Parsaeian
Comments: Full paper version (BA at PODC'24)
Subjects: Data Structures and Algorithms (cs.DS); Distributed, Parallel, and Cluster Computing (cs.DC)
[17] arXiv:2406.12383 [pdf, html, other]
Title: Biased Pareto Optimization for Subset Selection with Dynamic Cost Constraints
Dan-Xuan Liu, Chao Qian
Comments: This paper has appeared at PPSN'24
Subjects: Data Structures and Algorithms (cs.DS); Neural and Evolutionary Computing (cs.NE)
[18] arXiv:2406.12339 [pdf, html, other]
Title: Implementation Of Dynamic De Bruijn Graphs Via Learned Index
Riccardo Nigrelli
Subjects: Data Structures and Algorithms (cs.DS)
[19] arXiv:2406.12149 [pdf, html, other]
Title: Tight Streaming Lower Bounds for Deterministic Approximate Counting
Yichuan Wang
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)
[20] arXiv:2406.12717 (cross-list from cs.CC) [pdf, html, other]
Title: Parameterized Shortest Path Reconfiguration
Nicolas Bousquet, Kshitij Gajjar, Abhiruk Lahiri, Amer E. Mouawad
Subjects: Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS); Combinatorics (math.CO)
[21] arXiv:2406.12392 (cross-list from quant-ph) [pdf, html, other]
Title: Variational ground-state quantum adiabatic theorem
Bojan Žunkovič, Pietro Torta, Giovanni Pecci, Guglielmo Lami, Mario Collura
Comments: 5 + 6 pages, 10 figures
Subjects: Quantum Physics (quant-ph); Data Structures and Algorithms (cs.DS)

Tue, 18 Jun 2024 (showing first 4 of 13 entries )

[22] arXiv:2406.11649 [pdf, html, other]
Title: Making Old Things New: A Unified Algorithm for Differentially Private Clustering
Max Dupré la Tour, Monika Henzinger, David Saulpic
Comments: Oral presentation at ICML 2024
Subjects: Data Structures and Algorithms (cs.DS); Cryptography and Security (cs.CR); Machine Learning (cs.LG)
[23] arXiv:2406.11393 [pdf, html, other]
Title: Diagram Control and Model Order for Sugiyama Layouts
Sören Domrös, Reinhard von Hanxleden
Comments: 18 pages. A short version of this paper will be published at the DIAGRAMS conference 2024
Subjects: Data Structures and Algorithms (cs.DS); Programming Languages (cs.PL)
[24] arXiv:2406.11225 [pdf, html, other]
Title: Almost Linear Size Edit Distance Sketch
Michal Koucký, Michael Saks
Subjects: Data Structures and Algorithms (cs.DS)
[25] arXiv:2406.11075 [pdf, html, other]
Title: Perturbation-Resilient Sets for Dynamic Service Balancing
Jin Sima, Chao Pan, Olgica Milenkovic
Comments: arXiv admin note: text overlap with arXiv:2303.12996
Subjects: Data Structures and Algorithms (cs.DS); Information Theory (cs.IT); Combinatorics (math.CO)
Total of 47 entries : 1-25 26-47
Showing up to 25 entries per page: fewer | more | all