We gratefully acknowledge support from
the Simons Foundation and member institutions.

Data Structures and Algorithms

Authors and titles for recent submissions

[ total of 40 entries: 1-40 ]
[ showing up to 49 entries per page: fewer | more ]

Fri, 17 May 2024

[1]  arXiv:2405.10253 [pdf, other]
Title: Adaptive Quotient Filters
Authors: Richard Wen, Hunter McCoy, David Tench, Guido Tagliavini, Michael A. Bender, Alex Conway, Martin Farach-Colton, Rob Johnson, Prashant Pandey
Subjects: Data Structures and Algorithms (cs.DS)
[2]  arXiv:2405.10238 [pdf, other]
Title: Rounding Large Independent Sets on Expanders
Authors: Mitali Bafna, Jun-Ting Hsieh, Pravesh K. Kothari
Comments: 57 pages, 3 figures
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)
[3]  arXiv:2405.10167 [pdf, ps, other]
Title: Near Uniform Triangle Sampling Over Adjacency List Graph Streams
Authors: Arijit Bishnu, Arijit Ghosh, Gopinath Mishra, Sayantan Sen
Comments: 26 pages
Subjects: Data Structures and Algorithms (cs.DS)
[4]  arXiv:2405.09975 [pdf, other]
Title: Distributed Delta-Coloring under Bandwidth Limitations
Authors: Yannic Maus, Magnús M. Halldórsson
Subjects: Data Structures and Algorithms (cs.DS); Distributed, Parallel, and Cluster Computing (cs.DC)
[5]  arXiv:2405.09920 [pdf, ps, other]
Title: Dynamic online matching with budget refills
Authors: Maria Cherifa (ENSAE Paris), Clément Calauzènes, Vianney Perchet (ENSAE Paris)
Subjects: Data Structures and Algorithms (cs.DS)
[6]  arXiv:2405.09859 [pdf, other]
Title: Risk-Sensitive Online Algorithms
Authors: Nicolas Christianson, Bo Sun, Steven Low, Adam Wierman
Comments: Accepted for presentation at the Conference on Learning Theory (COLT) 2024
Subjects: Data Structures and Algorithms (cs.DS)
[7]  arXiv:2405.09784 (cross-list from cs.LG) [pdf, other]
Title: Online bipartite matching with imperfect advice
Authors: Davin Choo, Themis Gouleakis, Chun Kai Ling, Arnab Bhattacharyya
Comments: Accepted into ICML 2024
Subjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Data Structures and Algorithms (cs.DS); Machine Learning (stat.ML)

Thu, 16 May 2024

[8]  arXiv:2405.09338 [pdf, ps, other]
Title: Interval Selection in Sliding Windows
Authors: Cezar-Mihail Alexandru, Christian Konrad
Comments: 22 pages, 6 figures
Subjects: Data Structures and Algorithms (cs.DS)
[9]  arXiv:2405.09141 [pdf, other]
Title: Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity
Authors: Tijn de Vos, Aleksander B. G. Christiansen
Subjects: Data Structures and Algorithms (cs.DS)
[10]  arXiv:2405.09011 [pdf, ps, other]
Title: Symmetric-Difference (Degeneracy) and Signed Tree Models
Authors: Édouard Bonnet, Julien Duron, John Sylvester, Viktor Zamaraev
Comments: 21 pages, 7 figures
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Combinatorics (math.CO)
[11]  arXiv:2405.08938 [pdf, ps, other]
Title: Pointwise Lipschitz Continuous Graph Algorithms via Proximal Gradient Analysis
Authors: Quanquan C. Liu, Grigoris Velegkas, Yuichi Yoshida, Felix Zhou
Subjects: Data Structures and Algorithms (cs.DS)
[12]  arXiv:2405.08931 [pdf, ps, other]
Title: A QPTAS for Facility Location on Unit Disk graphs
Authors: Zachary Friggstad, Mohsen Rezapour, Mohammad R. Salavatipour, Hao Sun
Subjects: Data Structures and Algorithms (cs.DS)
[13]  arXiv:2405.08927 [pdf, ps, other]
Title: Expanderizing Higher Order Random Walks
Authors: Vedat Levi Alev, Shravas Rao
Subjects: Data Structures and Algorithms (cs.DS)
[14]  arXiv:2405.09525 (cross-list from quant-ph) [pdf, ps, other]
Title: Improved classical shadows from local symmetries in the Schur basis
Authors: Daniel Grier, Sihan Liu, Gaurav Mahajan
Subjects: Quantum Physics (quant-ph); Data Structures and Algorithms (cs.DS); Information Theory (cs.IT); Machine Learning (cs.LG)
[15]  arXiv:2405.09393 (cross-list from cs.DM) [pdf, other]
Title: Counting overlapping pairs of strings
Authors: Eric Rivals, Pengfei Wang
Comments: - HAL: lirmm-04576588v1 - this https URL - 16 pages, 1 figure, 2 tables, appendix A, B, C - Mots cl\'es: corr\'elation, chevauchement, bordure, combinatoire, limites, esp\'erance, population, algorithmique, treillis - Keywords: correlation, overlap, border, counting, bounds, expectation, Asymptotics, limits, population, stringology, lattice
Subjects: Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS)
[16]  arXiv:2405.09157 (cross-list from math.OC) [pdf, other]
Title: A Primal-Dual Framework for Symmetric Cone Programming
Authors: Jiaqi Zheng, Antonios Varvitsiotis, Tiow-Seng Tan, Wayne Lin
Subjects: Optimization and Control (math.OC); Computational Geometry (cs.CG); Distributed, Parallel, and Cluster Computing (cs.DC); Data Structures and Algorithms (cs.DS)

Wed, 15 May 2024

[17]  arXiv:2405.08787 [pdf, ps, other]
Title: Explicit Orthogonal Arrays and Universal Hashing with Arbitrary Parameters
Authors: Nicholas Harvey, Arvin Sahami
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC); Combinatorics (math.CO); Statistics Theory (math.ST)
[18]  arXiv:2405.08595 [pdf, other]
Title: Online busy time scheduling with flexible jobs
Authors: Susanne Albers, G. Wessel van der Heijden
Subjects: Data Structures and Algorithms (cs.DS)
[19]  arXiv:2405.08564 [pdf, other]
Title: Anytime Sorting Algorithms (Extended Version)
Authors: Emma Caizergues (LAMSADE, LINCS), François Durand (LINCS), Fabien Mathieu (LINCS)
Comments: 33rd International Joint Conference on Artificial Intelligence (IJCAI 2024), Aug 2024, Jeju City, Jeju Island, South Korea
Subjects: Data Structures and Algorithms (cs.DS)
[20]  arXiv:2405.08421 (cross-list from cond-mat.dis-nn) [pdf, other]
Title: Faster algorithms for the alignment of sparse correlated Erdös-Rényi random graphs
Authors: Andrea Muratori, Guilhem Semerjian
Comments: 31 pages
Subjects: Disordered Systems and Neural Networks (cond-mat.dis-nn); Data Structures and Algorithms (cs.DS); Probability (math.PR); Statistics Theory (math.ST)

Tue, 14 May 2024

[21]  arXiv:2405.07949 [pdf, other]
Title: Online Load and Graph Balancing for Random Order Inputs
Authors: Sungjin Im, Ravi Kumar, Shi Li, Aditya Petety, Manish Purohit
Subjects: Data Structures and Algorithms (cs.DS); Distributed, Parallel, and Cluster Computing (cs.DC)
[22]  arXiv:2405.07588 [pdf, other]
Title: Practical Computation of Graph VC-Dimension
Authors: David Coudert (COATI), Mónika Csikós (IRIF (UMR\_8243)), Guillaume Ducoffe (UniBuc, ICI), Laurent Viennot (DI-ENS, ARGO)
Journal-ref: Symposium on Experimental Algorithms (SEA) 2024, Jul 2024, Vienne, Austria
Subjects: Data Structures and Algorithms (cs.DS)
[23]  arXiv:2405.07353 [pdf, ps, other]
Title: Distributed Lovász Local Lemma under Bandwidth Limitations
Authors: Magnús M. Halldórsson, Yannic Maus, Saku Peltonen
Subjects: Data Structures and Algorithms (cs.DS); Distributed, Parallel, and Cluster Computing (cs.DC)
[24]  arXiv:2405.07122 [pdf, other]
Title: PCF Learned Sort: a Learning Augmented Sort Algorithm with $O(n \log\log n)$ Expected Complexity
Authors: Atsuki Sato, Yusuke Matsui
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)
[25]  arXiv:2405.06899 [pdf, other]
Title: Towards Metric DBSCAN: Exact, Approximate, and Streaming Algorithms
Authors: Guanlin Mo, Shihong Song, Hu Ding
Subjects: Data Structures and Algorithms (cs.DS)
[26]  arXiv:2405.06831 [pdf, other]
Title: Better Algorithms for Constructing Minimum Cost Markov Chains and AIFV Codes
Authors: Reza Hosseini Dolatabadi, Mordedcai J. Golin, Arian Zamani
Comments: Expanded version of paper appearing in ISIT 2024
Subjects: Data Structures and Algorithms (cs.DS)
[27]  arXiv:2405.06805 [pdf, ps, other]
Title: A (Weakly) Polynomial Algorithm for AIVF Coding
Authors: Reza Hosseini Dolatabadi, Mordecai J. Golin, Arian Zamani
Comments: Expanded version of paper appearing on ISIT 2024
Subjects: Data Structures and Algorithms (cs.DS)
[28]  arXiv:2405.06761 [pdf, other]
Title: Tree Proof-of-Position Algorithms
Authors: Aida Manzano Kharman, Pietro Ferraro, Homayoun Hamedmoghadam, Robert Shorten
Subjects: Data Structures and Algorithms (cs.DS)
[29]  arXiv:2405.07937 (cross-list from cs.LG) [pdf, other]
Title: Active Learning with Simple Questions
Authors: Vasilis Kontonis, Mingchen Ma, Christos Tzamos
Comments: To appear at COLT 2024
Subjects: Machine Learning (cs.LG); Data Structures and Algorithms (cs.DS)
[30]  arXiv:2405.07914 (cross-list from cs.LG) [pdf, ps, other]
Title: Distribution Learning Meets Graph Structure Sampling
Authors: Arnab Bhattacharyya, Sutanu Gayen, Philips George John, Sayantan Sen, N. V. Vinodchandran
Comments: 48 pages, 2 figures. Shortened abstract as per arXiv criteria
Subjects: Machine Learning (cs.LG); Data Structures and Algorithms (cs.DS); Machine Learning (stat.ML)
[31]  arXiv:2405.07792 (cross-list from cs.DB) [pdf, other]
Title: Optimal Matrix Sketching over Sliding Windows
Authors: Hanyan Yin, Dongxie Wen, Jiajun Li, Zhewei Wei, Xiao Zhang, Zengfeng Huang, Feifei Li
Subjects: Databases (cs.DB); Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG)
[32]  arXiv:2405.07725 (cross-list from cs.DC) [pdf, ps, other]
Title: Decentralized Distributed Graph Coloring: Cluster Graphs
Authors: Maxime Flin, Magnus M. Halldorsson, Alexandre Nolin
Subjects: Distributed, Parallel, and Cluster Computing (cs.DC); Data Structures and Algorithms (cs.DS)
[33]  arXiv:2405.07434 (cross-list from cs.DC) [pdf, other]
Title: Concurrent aggregate queries
Authors: Gal Sela, Erez Petrank
Subjects: Distributed, Parallel, and Cluster Computing (cs.DC); Data Structures and Algorithms (cs.DS)
[34]  arXiv:2405.07331 (cross-list from cs.LG) [pdf, other]
Title: Stochastic Bandits with ReLU Neural Networks
Authors: Kan Xu, Hamsa Bastani, Surbhi Goel, Osbert Bastani
Subjects: Machine Learning (cs.LG); Data Structures and Algorithms (cs.DS); Machine Learning (stat.ML)
[35]  arXiv:2405.07110 (cross-list from q-bio.PE) [pdf, other]
Title: A Vector Representation for Phylogenetic Trees
Authors: Cedric Chauve, Caroline Colijn, Louxin Zhang
Subjects: Populations and Evolution (q-bio.PE); Data Structures and Algorithms (cs.DS); Combinatorics (math.CO)

Mon, 13 May 2024

[36]  arXiv:2405.06244 [pdf, other]
Title: A $(\frac32+\frac1{\mathrm{e}})$-Approximation Algorithm for Ordered TSP
Authors: Susanne Armbruster, Matthias Mnich, Martin Nägele
Subjects: Data Structures and Algorithms (cs.DS)
[37]  arXiv:2405.06209 [pdf, ps, other]
Title: Fast and Slow Mixing of the Kawasaki Dynamics on Bounded-Degree Graphs
Authors: Aiya Kuchukova, Marcus Pappik, Will Perkins, Corrine Yap
Subjects: Data Structures and Algorithms (cs.DS); Combinatorics (math.CO); Probability (math.PR)
[38]  arXiv:2405.06208 [pdf, other]
Title: A Lock-free Binary Trie
Authors: Jeremy Ko
Subjects: Data Structures and Algorithms (cs.DS)
[39]  arXiv:2405.06616 (cross-list from math.PR) [pdf, ps, other]
Title: Fast Mixing in Sparse Random Ising Models
Authors: Kuikui Liu, Sidhanth Mohanty, Amit Rajaraman, David X. Wu
Comments: 66 pages, 4 figures
Subjects: Probability (math.PR); Data Structures and Algorithms (cs.DS); Combinatorics (math.CO)
[40]  arXiv:2405.06357 (cross-list from quant-ph) [pdf, ps, other]
Title: Beyond Bell sampling: stabilizer state learning and quantum pseudorandomness lower bounds on qudits
Authors: Jonathan Allcock, Joao F. Doriguello, Gábor Ivanyos, Miklos Santha
Comments: 35 pages
Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS)
[ total of 40 entries: 1-40 ]
[ showing up to 49 entries per page: fewer | more ]

Disable MathJax (What is MathJax?)

Links to: arXiv, form interface, find, cs, new, 2405, contact, help  (Access key information)