Data Structures and Algorithms

Authors and titles for cs.DS in Mar 2024

[1]  arXiv:2403.00129 [pdf, ps, other]

Title: Average-Case Local Computation Algorithms

Authors: Amartya Shankha Biswas, Ruidi Cao, Edward Pyne, Ronitt Rubinfeld

Comments: 27 pages

Subjects: Data Structures and Algorithms (cs.DS)

[2]  arXiv:2403.00246 [pdf, ps, other]

Title: Analysis of Phylogeny Tracking Algorithms for Serial and Multiprocess Applications

Authors: Matthew Andres Moreno, Santiago Rodriguez Papa, Emily Dolson

Subjects: Data Structures and Algorithms (cs.DS); Populations and Evolution (q-bio.PE)

[3]  arXiv:2403.00266 [pdf, other]

Title: Algorithms for Efficient, Compact Online Data Stream Curation

Authors: Matthew Andres Moreno, Santiago Rodriguez Papa, Emily Dolson

Subjects: Data Structures and Algorithms (cs.DS)

[4]  arXiv:2403.00306 [pdf, other]

Title: qPMS Sigma -- An Efficient and Exact Parallel Algorithm for the Planted $(l, d)$ Motif Search Problem

Authors: Saurav Dhar, Amlan Saha, Dhiman Goswami, Md. Abul Kashem Mia

Subjects: Data Structures and Algorithms (cs.DS)

[5]  arXiv:2403.00465 [pdf, other]

Title: Polyamorous Scheduling

Authors: Leszek Gąsieniec, Benjamin Smith, Sebastian Wild

Comments: v2: stronger and simplified hardness-of-approximation results, corrected constant in layering approximation algorithm

Subjects: Data Structures and Algorithms (cs.DS); Social and Information Networks (cs.SI); Optimization and Control (math.OC)

[6]  arXiv:2403.00536 [pdf, other]

Title: Approximating the Geometric Knapsack Problem in Near-Linear Time and Dynamically

Authors: Moritz Buchem, Paul Deuker, Andreas Wiese

Subjects: Data Structures and Algorithms (cs.DS)

[7]  arXiv:2403.00643 [pdf, ps, other]

Title: Undercomplete Decomposition of Symmetric Tensors in Linear Time, and Smoothed Analysis of the Condition Number

Authors: Pascal Koiran, Subhayan Saha

Comments: 55 pages

Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC); Numerical Analysis (math.NA)

[8]  arXiv:2403.01085 [src]

Title: A Strongly Subcubic Combinatorial Algorithm for Triangle Detection with Applications

Authors: Adrian Dumitrescu

Comments: The triangle detection algorithm may fail. The analysis of Case 2.1 (in Subsection 2.1) is invalid. Thanks to Zach Hunter for pointing this out

Subjects: Data Structures and Algorithms (cs.DS); Combinatorics (math.CO)

[9]  arXiv:2403.01568 [pdf, other]

Title: Approximations and Hardness of Packing Partially Ordered Items

Authors: Ilan Doron-Arad, Guy Kortsarz, Joseph Naor, Baruch Schieber, Hadas Shachnai

Subjects: Data Structures and Algorithms (cs.DS)

[10]  arXiv:2403.01797 [pdf, other]

Title: Unleashing Graph Partitioning for Large-Scale Nearest Neighbor Search

Authors: Lars Gottesbüren, Laxman Dhulipala, Rajesh Jayaram, Jakub Lacki

Subjects: Data Structures and Algorithms (cs.DS); Information Retrieval (cs.IR)

[11]  arXiv:2403.01839 [pdf, ps, other]

Title: Fully Polynomial-time Algorithms Parameterized by Vertex Integrity Using Fast Matrix Multiplication

Authors: Matthias Bentert, Klaus Heeger, Tomohiro Koana

Subjects: Data Structures and Algorithms (cs.DS)

[12]  arXiv:2403.01872 [pdf, ps, other]

Title: The Canadian Traveller Problem on outerplanar graphs

Authors: Laurent Beaudou, Pierre Bergé, Vsevolod Chernyshev, Antoine Dailly, Yan Gerard, Aurélie Lagoutte, Vincent Limouzy, Lucas Pastor

Subjects: Data Structures and Algorithms (cs.DS)

[13]  arXiv:2403.01902 [pdf, other]

Title: Random Generation of Git Graphs

Authors: Julien Courtiel (GREYC), Martin Pépin (GREYC)

Subjects: Data Structures and Algorithms (cs.DS); Combinatorics (math.CO)

[14]  arXiv:2403.02008 [pdf, other]

Title: How to Find Long Maximal Exact Matches and Ignore Short Ones

Authors: Travis Gagie

Subjects: Data Structures and Algorithms (cs.DS)

[15]  arXiv:2403.02140 [pdf, other]

Title: Matching Algorithms in the Sparse Stochastic Block Model

Authors: Anna Brandenberger, Byron Chin, Nathan S. Sheffield, Divya Shyamal

Comments: 28 pages

Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM)

[16]  arXiv:2403.02212 [pdf, ps, other]

Title: Constraint Satisfaction Problems with Advice

Authors: Suprovat Ghoshal, Konstantin Makarychev, Yury Makarychev

Subjects: Data Structures and Algorithms (cs.DS)

[17]  arXiv:2403.02300 [pdf, other]

Title: Statistical Query Lower Bounds for Learning Truncated Gaussians

Authors: Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, Nikos Zarifis

Subjects: Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG); Statistics Theory (math.ST); Machine Learning (stat.ML)

[18]  arXiv:2403.02582 [pdf, ps, other]

Title: On Approximate Fully-Dynamic Matching and Online Matrix-Vector Multiplication

Authors: Yang P. Liu

Comments: 30 pages

Subjects: Data Structures and Algorithms (cs.DS)

[19]  arXiv:2403.02636 [pdf, other]

Title: Algorithms for Galois Words: Detection, Factorization, and Rotation

Authors: Diptarama Hendrian, Dominik Köppl, Ryo Yoshinaka, Ayumi Shinohara

Comments: 16 pages,3 figures,accepted to CPM 2024

Subjects: Data Structures and Algorithms (cs.DS)

[20]  arXiv:2403.02665 [pdf, other]

Title: DGAP: Efficient Dynamic Graph Analysis on Persistent Memory

Authors: Abdullah Al Raqibul Islam, Dong Dai

Subjects: Data Structures and Algorithms (cs.DS); Distributed, Parallel, and Cluster Computing (cs.DC); Performance (cs.PF)

[21]  arXiv:2403.02997 [pdf, other]

Title: Cover Edge-Based Novel Triangle Counting

Authors: David A. Bader, Fuhuan Li, Zhihui Du, Palina Pauliuchenka, Oliver Alvarado Rodriguez, Anant Gupta, Sai Sri Vastav Minnal, Valmik Nahata, Anya Ganeshan, Ahmet Gundogdu, Jason Lew

Subjects: Data Structures and Algorithms (cs.DS)

[22]  arXiv:2403.03046 [pdf, ps, other]

Title: The Exchange Problem

Authors: Mohit Garg, Suneel Sarswat

Comments: 17 pages

Subjects: Data Structures and Algorithms (cs.DS); Computer Science and Game Theory (cs.GT)

[23]  arXiv:2403.03337 [pdf, ps, other]

Title: Fine-Grained Privacy Guarantees for Coverage Problems

Authors: Laxman Dhulipala, George Z. Li

Comments: 14 pages; abstract shortened to fit requirements

Subjects: Data Structures and Algorithms (cs.DS); Cryptography and Security (cs.CR)

[24]  arXiv:2403.03501 [pdf, other]

Title: Double Exponential Lower Bound for Telephone Broadcast

Authors: Prafullkumar Tale

Subjects: Data Structures and Algorithms (cs.DS)

[25]  arXiv:2403.03504 [pdf, other]

Title: Graph Visualization for Blockchain Data

Authors: Marcell Dietl, Andre Gemünd, Daniel Oeltz, Felix M. Thiele, Christian Werner

Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM)

[26]  arXiv:2403.03696 [pdf, ps, other]

Title: Largest common subgraph of two forests

Authors: Dieter Rautenbach, Florian Werner

Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM); Combinatorics (math.CO)

[27]  arXiv:2403.03830 [pdf, other]

Title: Parameterized Algorithms for Balanced Cluster Edge Modification Problems

Authors: Jayakrishnan Madathil, Kitty Meeks

Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM)

[28]  arXiv:2403.03906 [pdf, other]

Title: On HTLC-Based Protocols for Multi-Party Cross-Chain Swaps

Authors: Emily Clark, Chloe Georgiou, Katelyn Poon, Marek Chrobak

Subjects: Data Structures and Algorithms (cs.DS)

[29]  arXiv:2403.03990 [pdf, other]

Title: A Sierpinski Triangle Data Structure for Efficient Array Value Update and Prefix Sum Calculation

Authors: Brent Harrison, Jason Necaise, Andrew Projansky, James D. Whitfield

Comments: 8 pages, 4 figures

Subjects: Data Structures and Algorithms (cs.DS)

[30]  arXiv:2403.04230 [pdf, ps, other]

Title: Equivalence Testing: The Power of Bounded Adaptivity

Authors: Diptarka Chakraborty, Sourav Chakraborty, Gunjan Kumar, Kuldeep S. Meel

Subjects: Data Structures and Algorithms (cs.DS)

[31]  arXiv:2403.04263 [pdf, ps, other]

Title: Switching Classes: Characterization and Computation

Authors: Dhanyamol Antony, Yixin Cao, Sagartanu Pal, R.B. Sandeep

Comments: 36 pages

Subjects: Data Structures and Algorithms (cs.DS); Combinatorics (math.CO)

[32]  arXiv:2403.04542 [pdf, ps, other]

Title: A Simple and Near-Optimal Algorithm for Directed Expander Decompositions

Authors: Aurelio L. Sulser, Maximilian Probst Gutenberg

Subjects: Data Structures and Algorithms (cs.DS)

[33]  arXiv:2403.04589 [pdf, ps, other]

Title: Algorithms and complexity for path covers of temporal DAGs: when is Dilworth dynamic?

Authors: Dibyayan Chakraborty, Antoine Dailly, Florent Foucaud, Ralf Klasing

Comments: 21 pages

Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM); Combinatorics (math.CO)

[34]  arXiv:2403.04598 [pdf, other]

Title: Optimizing Inventory Placement for a Downstream Online Matching Problem

Authors: Boris Epstein, Will Ma (Columbia University)

Subjects: Data Structures and Algorithms (cs.DS)

[35]  arXiv:2403.04630 [pdf, ps, other]

Title: Time-Aware Projections: Truly Node-Private Graph Statistics under Continual Observation

Authors: Palak Jain, Adam Smith, Connor Wagaman

Subjects: Data Structures and Algorithms (cs.DS); Cryptography and Security (cs.CR)

[36]  arXiv:2403.04726 [pdf, other]

Title: A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimation

Authors: Ankit Pensia

Subjects: Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG); Statistics Theory (math.ST); Machine Learning (stat.ML)

[37]  arXiv:2403.04874 [pdf, ps, other]

Title: Improved Lower Bound for Differentially Private Facility Location

Authors: Pasin Manurangsi

Subjects: Data Structures and Algorithms (cs.DS); Cryptography and Security (cs.CR)

[38]  arXiv:2403.04951 [pdf, other]

Title: NP-Completeness for the Space-Optimality of Double-Array Tries

Authors: Hideo Bannai, Keisuke Goto, Shunsuke Kanda, Dominik Köppl

Subjects: Data Structures and Algorithms (cs.DS)

[39]  arXiv:2403.04999 [pdf, ps, other]

Title: A basic lower bound for property testing

Authors: Eldar Fischer

Comments: 4 pages. Added a related work reference

Subjects: Data Structures and Algorithms (cs.DS)

[40]  arXiv:2403.05041 [pdf, other]

Title: Data-Dependent LSH for the Earth Mover's Distance

Authors: Rajesh Jayaram, Erik Waingarten, Tian Zhang

Subjects: Data Structures and Algorithms (cs.DS)

[41]  arXiv:2403.05074 [pdf, other]

Title: Single Family Algebra Operation on ZDDs Leads To Exponential Blow-Up

Authors: Kengo Nakamura, Masaaki Nishino, Shuhei Denzumi

Comments: 19 pages, 6 figures

Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)

[42]  arXiv:2403.05198 [pdf, other]

Title: Efficient Algorithms for Personalized PageRank Computation: A Survey

Authors: Mingji Yang, Hanzhi Wang, Zhewei Wei, Sibo Wang, Ji-Rong Wen

Comments: 20 pages, "accepted version" of an article accepted by IEEE Transactions on Knowledge and Data Engineering (TKDE) for publication

Subjects: Data Structures and Algorithms (cs.DS)

[43]  arXiv:2403.05775 [pdf, other]

Title: Scalable $k$-clique Densest Subgraph Search

Authors: Xiaowei Ye, Miao Qiao, Rong-Hua Li, Qi Zhang, Guoren Wang

Subjects: Data Structures and Algorithms (cs.DS)

[44]  arXiv:2403.05781 [pdf, other]

Title: Approximate Bipartite $b$-Matching using Multiplicative Auction

Authors: Bhargav Samineni, S M Ferdous, Mahantesh Halappanavar, Bala Krishnamoorthy

Comments: 14 pages; Accepted as a refereed paper in the 2024 INFORMS Optimization Society conference

Subjects: Data Structures and Algorithms (cs.DS)

[45]  arXiv:2403.05943 [pdf, ps, other]

Title: Hamiltonicity, Path Cover, and Independence Number: An FPT Perspective

Authors: Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, Kirill Simonov

Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM)

[46]  arXiv:2403.06290 [pdf, other]

Title: Revisiting Path Contraction and Cycle Contraction

Authors: R. Krithika, V. K. Kutty Malu, Prafullkumar Tale

Subjects: Data Structures and Algorithms (cs.DS)

[47]  arXiv:2403.06335 [pdf, ps, other]

Title: Improved FPT Approximation Scheme and Approximate Kernel for Biclique-Free Max k-Weight SAT: Greedy Strikes Back

Authors: Pasin Manurangsi

Comments: Added a discussion on related independent work of Inamdar et al. (ICALP 2024)

Subjects: Data Structures and Algorithms (cs.DS)

[48]  arXiv:2403.06547 [pdf, other]

Title: Fun Maximizing Search, (Non) Instance Optimality, and Video Games for Parrots

Authors: Jérémy Barbay

Subjects: Data Structures and Algorithms (cs.DS)

[49]  arXiv:2403.06580 [pdf, ps, other]

Title: Arborescences and Shortest Path Trees when Colors Matter

Authors: P. S. Ardra, Jasine Babu, Kritika Kashyap, R. Krithika, Sreejith K. Pallathumadam, Deepak Rajendraprasad

Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC); Discrete Mathematics (cs.DM)

[50]  arXiv:2403.06608 [pdf, ps, other]

Title: Balanced Substructures in Bicolored Graphs

Authors: P. S. Ardra, R. Krithika, Saket Saurabh, Roohani Sharma

Comments: Minor changes

Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC)