3 papers
cs.DS2026
Improved Low-Overhead Communication-Efficient String Reconciliation and Edit Distance
Michael T. Goodrich, Gonzalo Navarro, Claire A. To
Suppose two parties, Alice and Bob, hold long character strings, and , respectively, and they are interested in determining how similar and are. {Moreover, they want…
cs.DS2026
Simple Low-Overhead Communication-Efficient String Reconciliation and Edit Distance
Michael T. Goodrich, Gonzalo Navarro, Claire A. To
Suppose two parties, Alice and Bob, hold long character strings, and , respectively, and they are interested in determining how similar and are. {Moreover, they want…
cs.CG2025
Entropy-Bounded Computational Geometry Made Easier and Sensitive to Sortedness
David Eppstein, Michael T. Goodrich, Abraham M. Illickan +1
We study entropy-bounded computational geometry, that is, geometric algorithms whose running times depend on a given measure of the input entropy. Specifically, we introduce a meas…