AUSO sink-finding problem
For each , let be the infimum, over randomized algorithms that use vertex-query access to an acyclic unique-sink orientation of the binary hypercube and output its unique sink, of the maximum over all such orientations of the expected number of vertex queries. Determine the asymptotic growth of ; equivalently, determine the optimal randomized query complexity for finding the sink of an -dimensional binary-hypercube AUSO.
References
- An improved randomized algorithm for finding sinks of Acyclic Unique Sink Orientations of the binary hypercube — arXiv — Thomas Dueholm Hansen, Uri Zwick
Source: arXiv
Progress summary
A new unrefereed paper claims the first improvement in over twenty years to the randomized method for finding sinks in these orientations, but the best possible efficiency remains unknown.
The problem asks for the optimal randomized query complexity of finding the unique sink in an acyclic unique-sink orientation of a binary hypercube. Such an algorithm would have consequences for linear programming, Markov decision processes, and stochastic games; no proposer or date is identified in the retrieved sources.
Known results
- A 2014 study improved the lower bound for a related policy-iteration formulation from to , while showing this does not determine sink-finding complexity.
October 2026 randomized upper-bound improvement
Thomas Dueholm Hansen and Uri Zwick report the first improvement in more than two decades to the best known randomized query bound for binary-hypercube AUSOs. The preprint improves an upper bound but does not prove optimality; its mathematical claims remain unverified.
Current status (as of October 2026): a claimed unverified improvement to the randomized upper bound is available, while the optimal complexity and a polynomial-query algorithm remain open.
Solutions 0
No solutions have been posted yet.