5 papers · 1 filter
Exact Learning of Weighted Graphs Using Composite Queries
Michael T. Goodrich, Songyu Liu, Ioannis Panageas
In this paper, we study the exact learning problem for weighted graphs, where we are given the vertex set, , of a weighted graph, , but we are not given . The prob…
Parallel Joinable B-Trees in the Fork-Join I/O Model
Michael Goodrich, Yan Gu, Ryuto Kitagawa +1
Balanced search trees are widely used in computer science to efficiently maintain dynamic ordered data. To support efficient set operations (e.g., union, intersection, difference)…
Optimal Parallel Algorithms for Convex Hulls in 2D and 3D under Noisy Primitive Operations
Michael T. Goodrich, Vinesh Sridhar
In the noisy primitives model, each primitive comparison performed by an algorithm, e.g., testing whether one value is greater than another, returns the incorrect answer with rando…
Quantum Combine and Conquer and Its Applications to Sublinear Quantum Convex Hull and Maxima Set Construction
Shion Fukuzawa, Michael T. Goodrich, Sandy Irani
We introduce a quantum algorithm design paradigm called combine and conquer, which is a quantum version of the "marriage-before-conquest" technique of Kirkpatrick and Seidel. In a…
Computational Geometry with Probabilistically Noisy Primitive Operations
David Eppstein, Michael T. Goodrich, Vinesh Sridhar
Much prior work has been done on designing computational geometry algorithms that handle input degeneracies, data imprecision, and arithmetic round-off errors. We take a new approa…