4 papers
cs.DS2026
Do We Really Need to Read the Input? An Optimality Proof for Stone Game III
Andrew Au
Stone Game III admits a standard backward dynamic program using time and auxiliary space. The upper bound is immediate, but its optimality raises a deceptively simple…
cs.DS2026
A Tight Lower Bound for Cycle Detection in Grid Graphs
Andrew Au
We prove that any algorithm for detecting cycles in an grid graph, where cells are colored and adjacency is defined by matching colors, must read all cells in the…
cs.DS2026
Two Linear Passes Are Necessary for Sum-Exclude-Self Under Sublinear Space
Andrew Au
We prove that any algorithm computing the sum-exclude-self of an unsigned -bit integer array of length under sublinear space must perform two linear passes over the input. M…
cs.DS2026
Exact (n + 2) Comparison Complexity for the N-Repeated Element Problem
Andrew Au
This paper establishes the exact comparison complexity of finding an element repeated times in a -element array containing distinct values, under the equality-compari…