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 security. He holds numerous honors, including being an ACM Distinguished Scientist, a Fellow of the AAAS, IEEE, and ACM, a Fulbright Scholar, and a foreign member of the Royal Danish Academy of Sciences and Letters. His educational background includes a B.A. in Mathematics and Computer Science from Calvin University and a Ph.D. in Computer Science from Purdue University.

Research topics

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

Selected publications

• 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, however, zip-zip trees achieve their bounds using only $$O(\log \log n)$$ bits of metadata per node, w.h.p., as compared to the $$\Theta (\log n)$$ bits per node required by treaps. In addition, we describe a “just-in-time” zip-zip tree variant, which needs just an expected O (1) number of bits of metadata per node. Moreover, we can define zip-zip trees to be strongly history independent, whereas treaps are generally only weakly history independent. We also introduce biased zip-zip trees , which have an explicit bias based on key weights, so the expected depth of a key, k , with weight, $$w_k$$ , is $$O(\log (W/w_k))$$ , where W is the weight of all keys in the weighted zip-zip tree. Finally, we show that one can easily make zip-zip trees partially persistent with only O ( n ) space overhead w.h.p.

  PublisherDOI

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

  Open MIND · 2026-03-05

  preprint

  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 entropy, H(A), of an input array, A, of size n. In particular, we describe two remarkably simple paradigms for implementing stack-based natural mergesort algorithms to be strictly in-place in O(n(1 + H(A))) time.

  DOI

• 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 entropy, H(A), of an input array, A, of size n. In particular, we describe two remarkably simple paradigms for implementing stack-based natural mergesort algorithms to be strictly in-place in O(n(1 + H(A))) time.

  PublisherOA PDF

• Parallel Joinable B-Trees in the Fork-Join I/O Model

  ArXiv.org · 2025-01-01

  articleOpen access1st authorCorresponding

  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) using trees, the join-based framework is widely studied. This framework has received particular attention in the parallel setting, and has been shown to be effective in enabling simple and theoretically efficient set operations on trees. Despite the widespread adoption of parallel join-based trees, a major drawback of previous work on such data structures is the inefficiency of their input/output (I/O) access patterns. Some recent work (e.g., C-trees and PaC-trees) focused on more I/O-friendly implementations of these algorithms. Surprisingly, however, there have been no results on bounding the I/O-costs for these algorithms. It remains open whether these algorithms can provide tight, provable guarantees in I/O-costs on trees. This paper studies efficient parallel algorithms for set operations based on search tree algorithms using a join-based framework, with a special focus on achieving I/O efficiency in these algorithms. To better capture the I/O-efficiency in these algorithms in parallel, we introduce a new computational model, Fork-Join I/O Model, to measure the I/O costs in fork-join parallelism. This model measures the total block transfers (I/O work) and their critical path (I/O span). Under this model, we propose our new solution based on B-trees. Our parallel algorithm computes the union, intersection, and difference of two B-trees with $O(m \log_B(n/m))$ I/O work and $O(\log_B m \cdot \log_2 \log_B n + \log_B n)$ I/O span, where $n$ and $m \leq n$ are the sizes of the two trees, and $B$ is the block size.

  PublisherOA PDFDOI

• Zip-Tries: Simple Dynamic Data Structures for Strings

  Society for Industrial and Applied Mathematics eBooks · 2025-01-01

  book-chapter

  In this paper, we introduce zip-tries, which are simple, dynamic, memory-efficient data structures for strings. Zip-tries support search and update operations for k-length strings in 𝕆(κ + log n ) time in the standard RAM model or in 𝕆(κ/α + log n ) time in the word RAM model, where α is the length of the longest string that can fit in a memory word, and n is the number of strings in the trie. Importantly, we show how zip-tries can achieve this while only requiring bits of metadata per node w.h.p., which is an exponential improvement over previous results for long strings. Despite being considerably simpler and more memory efficient, we show how zip- tries perform competitively with state-of-the-art data structures on large datasets of long strings.

  PublisherDOI

• The Rectilinear Marco Polo Problem

  ArXiv.org · 2025-08-20

  preprintOpen access

  We study the rectilinear Marco Polo problem, which generalizes the Euclidean version of the Marco Polo problem for performing geometric localization to rectilinear search environments, such as in geometries motivated from urban settings, and to higher dimensions. In the rectilinear Marco Polo problem, there is at least one point of interest (POI) within distance $n$, in either the $L_1$ or $L_\infty$ metric, from the origin. Motivated from a search-and-rescue application, our goal is to move a search point, $Δ$, from the origin to a location within distance $1$ of a POI. We periodically issue probes from $Δ$ out a given distance (in either the $L_1$ or $L_\infty$ metric) and if a POI is within the specified distance of $Δ$, then we learn this (but no other location information). Optimization goals are to minimize the number of probes and the distance traveled by $Δ$. We describe a number of efficient search strategies for rectilinear Marco Polo problems and we analyze each one in terms of the size, $n$, of the search domain, as defined by the maximum distance to a POI.

  PublisherOA PDFDOI

• Circle Quasi-Cartograms: Dorling Cartograms with Edge Connections and Relaxed Overlap Conditions

  2025-11-03

  articleOpen accessSenior author

  Suppose that we are given a graph G = (V, E), such that vertices have geographic (x, y)-coordinates and positive weights representing statistical data. A Dorling cartogram is a way to visualize G where vertices are drawn as non-overlapping circles such that the circle for each vertex, υ ɛ V, is drawn with area proportional to υ's weight and placed close to the anchoring location for υ. However, the edges of G are not drawn in such visualizations and adjacency information can be lost. In this paper, we introduce circle quasi-cartograms, which are modifications of Dorling cartograms where attractive forces are also applied between nodes according to the edges of the input graph. Our goal is to preserve the geographic information of the graph while still accurately representing the statistical data via vertex weights. Applications include population visualization, where we aim to accurately represent the size of populations while also visualizing connections between the geographic regions. Our experiments indicate that these techniques improve on the “spread” of Dorling cartograms, allowing us to trade off visualizing spatial information at the cost of statistical information, which can be controlled by adjusting anchor and overlap forces.

  PublisherDOI

• Fast Geographic Routing in Fixed-Growth Graphs

  Lecture notes in computer science · 2025-01-01

  book-chapter
  PublisherDOI

• Zip-Tries: Simple Dynamic Data Structures for Strings

  Society for Industrial and Applied Mathematics eBooks · 2025-01-01

  book-chapterOpen access

  In this paper, we introduce zip-tries, which are simple, dynamic, memory-efficient data structures for strings. Zip-tries support search and update operations for k-length strings in 𝕆(κ + log n ) time in the standard RAM model or in 𝕆(κ/α + log n ) time in the word RAM model, where α is the length of the longest string that can fit in a memory word, and n is the number of strings in the trie. Importantly, we show how zip-tries can achieve this while only requiring bits of metadata per node w.h.p., which is an exponential improvement over previous results for long strings. Despite being considerably simpler and more memory efficient, we show how zip- tries perform competitively with state-of-the-art data structures on large datasets of long strings.

  PublisherOA PDFDOI

• Parallel Peeling of Invertible Bloom Lookup Tables in a Constant Number of Rounds

  Lecture notes in computer science · 2025-01-01

  book-chapter1st authorCorresponding
  PublisherDOI

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

• NSF-BSF: AF: Small: Geometric Realizations and Evolving Data

  NSF · $482k · 2018–2022

• Collaborative Research: Algorithms for Graphs on Surfaces

  NSF · $400k · 2008–2013

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