Michael Goodrich

About

Michael Goodrich is a Distinguished Professor at the University of California, Irvine, where he has been a faculty member in the Department of Computer Science since 2001. He currently serves as the Technical Director for the ICS Center for Algorithms and Theory of Computation. Prior to his tenure at UC Irvine, he was a professor in the Department of Computer Science at Johns Hopkins University from 1987 to 2001. His research is focused on the design of high performance algorithms and data structures with applications to information assurance and security, the Internet, machine learning, and geometric computing. He has pioneered and led research on efficient solutions to fundamental problems such as sorting, convex hull construction, nearest-neighbor searching, linear programming, privacy-preserving data access, network traceback, and data authentication. His work has been supported by the U.S. National Science Foundation and the U.S. Department of Defense, including agencies such as the NSA, ARO, ONR, and DARPA. With over 300 publications and several widely-adopted books, his recent contributions include work on efficient and secure distributed data structures, information privacy, social networks, and cloud security. He has served as a scientific consultant to organizations including AT&T, Walt Disney Animation Studios, and the NSF, and has experience as an expert witness in patent and intellectual property litigation involving algorithms, cryptography, and computer…

Research topics

• Computer Science
• Combinatorics
• Mathematics
• Algorithm
• Discrete mathematics
• Arithmetic
• Computer network
• Parallel computing
• Operating system

Selected publications

• Simplified Chernoff bounds with powers-of-two probabilities

  Information Processing Letters · 2023 · 3 citations

  Senior authorCorresponding

  In this paper, we derive simplified Chernoff bounds with powers-of-two probabilities, and we show their uses in analyzing probabilistic algorithms.

  PublisherDOI

• Atomic Power in Forks: A Super-Logarithmic Lower Bound for Implementing Butterfly Networks in the Nonatomic Binary Fork-Join Model

  Society for Industrial and Applied Mathematics eBooks · 2021 · 3 citations

  1st authorCorresponding

  We prove an Ω (log n log log n) lower bound for the span of implementing the n input, log n-depth FFT circuit (also known as butterfly network) in the nonatomic binary fork-join model. In this model, memory-access synchronizations occur only through fork operations, which spawn two child threads, and join operations, which resume a parent thread when its child threads terminate. Our bound is asymptotically tight for the nonatomic binary fork-join model, which has been of interest of late, due to…

  DOI

• A lower bound for the Quickhull convex hull algorithm that disproves the Quickhull precision conjecture

  Information Processing Letters · 2025-01-14 · 1 citations

  articleOpen access1st authorCorresponding

  The Quickhull algorithm is a simple algorithm for constructing the convex hull of a set of n points. Quickhull is usually described for points in the plane, in which case it is defined as a divide-and-conquer algorithm, where one has a pair of points ( p , r ) such that p and r are on the convex hull, and one then finds the point, q , farthest from the line p r ‾ , which must also be on the convex hull, and then uses the triangle ( p , q , r ) to divide the remaining points and recursively solve…

  PublisherDOI

• Zip-zip Trees: Making Zip Trees More Balanced, Biased, Compact, or Persistent

  Algorithmica · 2026-04-16

  preprintOpen access

  Abstract We define simple variants of zip trees, called zip-zip trees , which provide several advantages over zip trees, including overcoming a bias that favors smaller keys over larger ones. We analyze zip-zip trees theoretically and empirically, showing, e.g., that the expected depth of a node in an n -node zip-zip tree is at most $$1.3863\log n-1+o(1)$$ , which matches the expected depth of treaps and binary search trees built by uniformly random insertions. Unlike these other data structures…

  PublisherDOI

• How to Sort in a Refrigerator: Simple Entropy-Sensitive Strictly In-Place Sorting Algorithms

  ArXiv.org · 2026-03-05

  articleOpen access

  While modern general-purpose computing systems have ample amounts of memory, it is still the case that embedded computer systems, such as in a refrigerator, are memory limited; hence, such embedded systems motivate the need for strictly in-place algorithms, which use only O(1) additional memory besides that used for the input. In this paper, we provide the first comparison-based sorting algorithms that are strictly in-place and have a running time that is optimal in terms of the run-based entrop…

  PublisherOA PDF

Recent grants

• TWC: Medium: Collaborative: Privacy-Preserving Distributed Storage and Computation

  NSF · $391k · 2012–2018

• ITR: Algorithms for the Technology of Trust

  NSF · $300k · 2003–2008

• TC:Large:Collaborative Research: Towards Trustworthy Interactions in the Cloud

  NSF · $500k · 2010–2015

Frequent coauthors

• David Eppstein

  134 shared

• Roberto Tamassia

  Providence College

  121 shared

• Stephen Kobourov

  University of Arizona

  38 shared

• Michael Mitzenmacher

  Harvard University Press

  35 shared

• Mikhail J. Atallah

  32 shared

• Christian A. Duncan

  29 shared

• Gill Barequet

  Technion – Israel Institute of Technology

  29 shared

• Olga Ohrimenko

  21 shared

Education

• Ph.D., Computer Science

  University of California, Irvine

  1986

• M.S., Computer Science

  University of California, Irvine

  1982

• B.S., Mathematics

  University of California, Santa Barbara

  1979

Awards & honors

• IEEE Computer Society Technical Achievement Award
• Brown Univ. Award for Technological Innovation
• Pond Award for Excellence in Undergraduate Teaching
• Fellow of the American Association for the Advancement of Sc…
• Fellow of the IEEE

Similar researchers at University of California, Irvine

• Pierre Baldih-121
• Gene Tsudikh-82
• Padhraic Smythh-78