8 papers
A Quantum Scaling Algorithm for Maximum-Weight Perfect Matching in General Graphs
Kourosh Mirsohi, Sandy Irani, Michael T. Goodrich
Quantum speed-ups have been obtained for many fundamental graph problems, including most variants of matching. A notable exception, however, is the maximum-weight perfect matching…
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…
Dynamic Accountable Storage: An Efficient Protocol for Real-time Cloud Storage Auditing
Michael T. Goodrich, Ryuto Kitagawa, Vinesh Sridhar
Ateniese, Goodrich, Lekakis, Papamanthou, Paraskevas, and Tamassia introduced the Accountable Storage protocol, which is a way for a client to outsource their data to a cloud stora…
Making Quickhull More Like Quicksort: A Simple Randomized Output-Sensitive Convex Hull Algorithm
Michael T. Goodrich, Ryuto Kitagawa
In this paper, we present Ray-shooting Quickhull, which is a simple, randomized, outputsensitive version of the Quickhull algorithm for constructing the convex hull of a set of n p…