3 papers
cs.DS2026
Bounding the Fragmentation of B-Trees Subject to Batched Insertions
Michael A. Bender, Aaron Bernstein, Nairen Cao +5
The issue of internal fragmentation in data structures is a fundamental challenge in database design. A seminal result of Yao in this field shows that evenly splitting the leaves o…
cs.DS2025
Min-Max Correlation Clustering via Neighborhood Similarity
Nairen Cao, Steven Roche, Hsin-Hao Su
We present an efficient algorithm for the min-max correlation clustering problem. The input is a complete graph where edges are labeled as either positive or negative ,…
cs.DC2024
Parallel, Distributed, and Quantum Exact Single-Source Shortest Paths with Negative Edge Weights
Vikrant Ashvinkumar, Aaron Bernstein, Nairen Cao +5
This paper presents parallel, distributed and quantum algorithms for single-source shortest paths when edges can have negative weights (negative-weight SSSP). We show a framework t…