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

Data Structures and Algorithms

Authors and titles for recent submissions

[ total of 58 entries: 1-38 | 39-58 ]
[ showing 38 entries per page: fewer | more | all ]

Tue, 28 May 2024

[1]  arXiv:2405.16713 [pdf, other]
Title: Finding Maximum Common Contractions Between Phylogenetic Networks
Authors: Bertrand Marchand, Nadia Tahiri, Olivier Tremblay-Savard, Manuel Lafond
Comments: full version (with complete set of proofs) of WABI 2024 submission
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)
[2]  arXiv:2405.16663 [pdf, ps, other]
Title: Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust
Authors: Hongjie Chen, Jingqiu Ding, Yiding Hua, David Steurer
Subjects: Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG); Machine Learning (stat.ML)
[3]  arXiv:2405.16408 [pdf, other]
Title: Reconfiguration and Enumeration of Optimal Cyclic Ladder Lotteries
Authors: Yuta Nozaki, Kunihiro Wasa, Katsuhisa Yamanaka
Subjects: Data Structures and Algorithms (cs.DS); Combinatorics (math.CO)
[4]  arXiv:2405.16103 [pdf, ps, other]
Title: Boolean Matrix Multiplication for Highly Clustered Data on the Congested Clique
Authors: Andrzej Lingas
Comments: To appear in Euro-Par 2024 proceedings, 14 pages
Subjects: Data Structures and Algorithms (cs.DS); Distributed, Parallel, and Cluster Computing (cs.DC)
[5]  arXiv:2405.15983 [pdf, ps, other]
Title: Hierarchical Clustering via Local Search
Authors: Hossein Jowhari
Comments: 14 pages
Subjects: Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG)
[6]  arXiv:2405.15963 [pdf, other]
Title: Learning Minimum Linear Arrangement of Cliques and Lines
Authors: Julien Dallot, Maciej Pacut, Marcin Bienkowski, Darya Melnyk, Stefan Schmid
Comments: ICDCS 2024
Journal-ref: ICDCS 2024
Subjects: Data Structures and Algorithms (cs.DS)
[7]  arXiv:2405.15811 [pdf, other]
Title: Maximizing Weighted Dominance in the Plane
Authors: Waseem Akram, Sanjeev Saxena
Subjects: Data Structures and Algorithms (cs.DS); Computational Geometry (cs.CG)
[8]  arXiv:2405.17001 (cross-list from cs.CC) [pdf, ps, other]
Title: Delta-modular ILP Problems of Bounded Co-dimension, Discrepancy, and Convolution
Authors: D. Gribanov, D. Malyshev, P. M. Pardalos
Subjects: Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS); Commutative Algebra (math.AC); Optimization and Control (math.OC)
[9]  arXiv:2405.15913 (cross-list from cs.LG) [pdf, other]
Title: Scaling up the Banded Matrix Factorization Mechanism for Differentially Private ML
Authors: Ryan McKenna
Subjects: Machine Learning (cs.LG); Cryptography and Security (cs.CR); Data Structures and Algorithms (cs.DS)

Mon, 27 May 2024

[10]  arXiv:2405.15492 [pdf, other]
Title: Finding Induced Subgraphs from Graphs with Small Mim-Width
Authors: Yota Otachi, Akira Suzuki, Yuma Tamura
Comments: To appear in the proceedings of the 19th Scandinavian Symposium on Algorithm Theory (SWAT 2024)
Subjects: Data Structures and Algorithms (cs.DS)
[11]  arXiv:2405.15449 [pdf, ps, other]
Title: Faster $(Δ+ 1)$-Edge Coloring: Breaking the $m \sqrt{n}$ Time Barrier
Authors: Sayan Bhattacharya, Din Carmon, Martín Costa, Shay Solomon, Tianyi Zhang
Comments: Started to circulate in April 2024
Subjects: Data Structures and Algorithms (cs.DS)
[12]  arXiv:2405.15372 [pdf, other]
Title: When far is better: The Chamberlin-Courant approach to obnoxious committee selection
Authors: Sushmita Gupta, Tanmay Inamdar, Pallavi Jain, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh
Subjects: Data Structures and Algorithms (cs.DS); Computer Science and Game Theory (cs.GT)
[13]  arXiv:2405.15371 [pdf, other]
Title: Engineering Optimal Parallel Task Scheduling
Authors: Matthew Akram, Nikolai Maas, Peter Sanders, Dominik Schreiber
Subjects: Data Structures and Algorithms (cs.DS)
[14]  arXiv:2405.15088 [pdf, other]
Title: Adaptive Dynamic Bitvectors
Authors: Gonzalo Navarro
Subjects: Data Structures and Algorithms (cs.DS)
[15]  arXiv:2405.15084 [pdf, other]
Title: Efficient Certificates of Anti-Concentration Beyond Gaussians
Authors: Ainesh Bakshi, Pravesh Kothari, Goutham Rajendran, Madhur Tulsiani, Aravindan Vijayaraghavan
Subjects: Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG); Machine Learning (stat.ML)
[16]  arXiv:2405.14995 [pdf, other]
Title: Lower Bound on the Greedy Approximation Ratio for Adaptive Submodular Cover
Authors: Blake Harris, Viswanath Nagarajan
Comments: 7 pages, 1 figure. arXiv admin note: substantial text overlap with arXiv:2208.08351
Subjects: Data Structures and Algorithms (cs.DS); Artificial Intelligence (cs.AI); Machine Learning (cs.LG)
[17]  arXiv:2405.15543 (cross-list from math.CO) [pdf, ps, other]
Title: A tame vs. feral dichotomy for graph classes excluding an induced minor or induced topological minor
Authors: Martin Milanič, Nevena Pivač
Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS)
[18]  arXiv:2405.15368 (cross-list from cs.CC) [pdf, other]
Title: Complexity of Robust Orbit Problems for Torus Actions and the abc-conjecture
Authors: Peter Bürgisser, Mahmut Levent Doğan, Visu Makam, Michael Walter, Avi Wigderson
Subjects: Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS); Algebraic Geometry (math.AG); Representation Theory (math.RT)
[19]  arXiv:2405.15193 (cross-list from cs.DB) [pdf, other]
Title: CuckooGraph: A Scalable and Space-Time Efficient Data Structure for Large-Scale Dynamic Graphs
Authors: Zhuochen Fan, Yalun Cai, Zirui Liu, Jiarui Guo, Xin Fan, Tong Yang, Bin Cui
Subjects: Databases (cs.DB); Data Structures and Algorithms (cs.DS)

Fri, 24 May 2024

[20]  arXiv:2405.14835 [pdf, other]
Title: Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
Authors: Sepehr Assadi, Prantar Ghosh, Bruno Loff, Parth Mittal, Sagnik Mukhopadhyay
Comments: Accepted at CCC 2024
Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)
[21]  arXiv:2405.14254 [pdf, other]
Title: Path-Reporting Distance Oracles with Linear Size
Authors: Ofer Neiman, Idan Shabat
Comments: 27 pages, 2 figures
Subjects: Data Structures and Algorithms (cs.DS)
[22]  arXiv:2405.13613 [pdf, other]
Title: Enumerating Graphlets with Amortized Time Complexity Independent of Graph Size
Authors: Alessio Conte, Roberto Grossi, Yasuaki Kobayashi, Kazuhiro Kurita, Davide Rucci, Takeaki Uno, Kunihiro Wasa
Subjects: Data Structures and Algorithms (cs.DS)
[23]  arXiv:2405.13450 [pdf, ps, other]
Title: Cascading-Tree Algorithm for the 0-1 Knapsack Problem (In Memory of Heiner M{ü}ller-Merbach, a Former President of IFORS)
Authors: Mahdi Moeini (ENSIIE), Daniel Schermer (TU Kaiserslautern), Oliver Wendt (TU Kaiserslautern)
Subjects: Data Structures and Algorithms (cs.DS); Optimization and Control (math.OC)
[24]  arXiv:2405.13371 [pdf, other]
Title: Faster Vizing and Near-Vizing Edge Coloring Algorithms
Authors: Sepehr Assadi
Subjects: Data Structures and Algorithms (cs.DS)
[25]  arXiv:2405.13343 [pdf, other]
Title: Average sensitivity of the Knapsack Problem
Authors: Soh Kumabe, Yuichi Yoshida
Comments: 23 pages, ESA 2022
Subjects: Data Structures and Algorithms (cs.DS)
[26]  arXiv:2405.14765 (cross-list from quant-ph) [pdf, other]
Title: A Quantum Speed-Up for Approximating the Top Eigenvectors of a Matrix
Authors: Yanlin Chen, András Gilyén, Ronald de Wolf
Comments: 50 pages
Subjects: Quantum Physics (quant-ph); Data Structures and Algorithms (cs.DS)
[27]  arXiv:2405.14194 (cross-list from cs.SI) [pdf, other]
Title: Graphlets correct for the topological information missed by random walks
Authors: Sam F. L. Windels, Noel Malod-Dognin, Natasa Przulj
Subjects: Social and Information Networks (cs.SI); Artificial Intelligence (cs.AI); Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG)
[28]  arXiv:2405.14183 (cross-list from cs.LG) [pdf, other]
Title: Deterministic Policies for Constrained Reinforcement Learning in Polynomial-Time
Authors: Jeremy McMahan
Subjects: Machine Learning (cs.LG); Data Structures and Algorithms (cs.DS)
[29]  arXiv:2405.14066 (cross-list from cs.LG) [pdf, ps, other]
Title: Online Classification with Predictions
Authors: Vinod Raman, Ambuj Tewari
Comments: 24 pages
Subjects: Machine Learning (cs.LG); Data Structures and Algorithms (cs.DS); Machine Learning (stat.ML)
[30]  arXiv:2405.13994 (cross-list from cs.LG) [pdf, other]
Title: Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint
Authors: Murad Tukan, Loay Mualem, Moran Feldman
Subjects: Machine Learning (cs.LG); Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS)
[31]  arXiv:2405.13877 (cross-list from cs.CG) [pdf, ps, other]
Title: On connections between k-coloring and Euclidean k-means
Authors: Enver Aman, Karthik C. S., Sharath Punna
Subjects: Computational Geometry (cs.CG); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS)
[32]  arXiv:2405.13875 (cross-list from cs.CC) [pdf, other]
Title: On the Inapproximability of Finding Minimum Monitoring Edge-Geodetic Sets
Authors: Davide Bilò, Giordano Colli, Luca Forlizzi, Stefano Leucci
Subjects: Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS)
[33]  arXiv:2405.13797 (cross-list from math.CO) [pdf, other]
Title: Sparse Induced Subgraphs of Large Treewidth
Authors: Édouard Bonnet
Comments: 16 pages, 3 figures
Subjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS)
[34]  arXiv:2405.13420 (cross-list from math.NT) [pdf, ps, other]
Title: Recovering short generators via negative moments of Dirichlet $L$-functions
Authors: Iu-Iong Ng, Yuichiro Toma
Comments: 16 pages
Subjects: Number Theory (math.NT); Data Structures and Algorithms (cs.DS)
[35]  arXiv:2405.13351 (cross-list from quant-ph) [pdf, other]
Title: Quantum (Inspired) $D^2$-sampling with Applications
Authors: Ragesh Jaiswal, Poojan Shah
Comments: arXiv admin note: substantial text overlap with arXiv:2308.08167
Subjects: Quantum Physics (quant-ph); Data Structures and Algorithms (cs.DS)
[36]  arXiv:2405.13273 (cross-list from quant-ph) [pdf, other]
Title: Dequantizability from inputs
Authors: Tae-Won Kim, Byung-Soo Choi
Subjects: Quantum Physics (quant-ph); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS)

Wed, 22 May 2024 (showing first 2 of 12 entries)

[37]  arXiv:2405.12876 [pdf, other]
Title: Approximating TSP Variants Using a Bridge Lemma
Authors: Martin Böhm, Zachary Friggstad, Tobias Mömke, Joachim Spoerhase
Subjects: Data Structures and Algorithms (cs.DS)
[38]  arXiv:2405.12765 [pdf, other]
Title: Faster Linear-Size And-Or Path and Adder Circuits
Authors: Ulrich Brenner, Anna Silvanus
Subjects: Data Structures and Algorithms (cs.DS)
[ total of 58 entries: 1-38 | 39-58 ]
[ showing 38 entries per page: fewer | more | all ]

Disable MathJax (What is MathJax?)

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