This past week was the final exam week for our spring term, and in it we also held the doctoral defense of another Ph.D. student, Vinesh Sridhar (advised by Mike Goodrich). Vinesh organized his thesis in an unusually symmetric way, with two parts on computing with noisy primitives, two parts on in-place algorithms, two parts on sequential algorithms, and two parts on parallel algorithms, in four combinations (noisy sequential, noisy parallel, in-place sequential, in-place parallel).

I’ve previously written here about Vinesh’s work with Mike and me on computational geometry algorithms with noisy primitives, which we published in WADS 2025. In this work, following a random walk back and forth along a search path in a history DAG or other geometric data structure (and occasionally, choosing a false step and then backtracking) allows algorithms based on this idea to avoid the logarithmic time penalty of repeating each noisy query for enough repetitions to be sure that it is accurate. Being sure means “with high probability”: the failure probability should be inversely polynomial in the input size.

Vinesh and Mike published a parallel follow-up to this at CCCG 2025, “Optimal parallel algorithms for convex hulls in 2d and 3d under noisy primitive operations”. A difficulty here is that, for a divide-and-conquer algorithm, a failure probability that is inverse polynomial in the size of a small subproblem may not be inverse polynomial in the much larger input size. To work around this, Vinesh and Mike used the idea of “failure sweeping”, in which one divides the input into polynomially-many subproblems, lets some of them fail with a probability that is larger than the target failure probability (but still small enough that with high probability there are few failures). Then, one cleans up the failed subproblems in a second pass using a fast and more reliable parallel algorithm with a greater total work bound that is cancelled by the smaller number of subproblems.

The in-place part of Vinesh’s thesis focused on in-place sorting algorithms, where one is allowed only \(O(1)\) extra words of memory beyond the array being sorted. The classical choice for this is heapsort, which can be implemented to run in-place and takes time \(O(n\log n)\) to sort an \(n\)-item array. This is optimal in the worst case, but many other sorting algorithms go beyond worst case time complexity to run more quickly for inputs that are not completely unsorted. An important class of these are entropy-sensitive sorting algorithms. Their runtime on input sequences that can be partitioned into \(r\) sorted runs of size \(n_i\) is \(O(n(H+1))\), where the entropy \(H\) is defined by

\[\mathrm{H}=-\sum_{i=1}^r \frac{n_i}{n}\log_2 \frac{n_i}{n}.\]

This can be done by finding runs and then repeatedly merging the shortest two, but the merged runs may not be consecutive in the input sequence, making an in-place merge problematic. Instead, Timsort and several similar alternatives build a stack of runs in a left-right scan of the input, while doing so merging pairs of short runs near the top of the stack. This leaves a sequence of sorted runs on the stack whose sizes grow roughly according to a geometric sequence, which can be repeatedly popped and merged. The geometric growth of the stack means that the stack itself can be stored in \(O(\log n)\) space, but while small this is not small enough to be in-place. Vinesh finds two strategies for reducing the space in this family of algorithms. In the “walking” strategy, only the top \(O(1)\) stack elements are maintained; the next ones below that are rediscovered one at a time, as they become needed, by a sequential search within each run. In the “jumping” strategy, some elements within each run are placed out of order, in order to encode extra information to speed up the walking algorithm. Vinesh shows that most entropy-sensitive merging algorithms (but not Timsort itself) can be made in-place by walking, and that all known ones can be made in-place by jumping. He published this work (joint with Ofek Gila and Mike Goodrich) as “How to sort in a refrigerator: Simple entropy-sensitive strictly in-place sorting algorithms” in LATIN 2026.

The final part of the thesis comes from a paper with the colorful title “Raiders of the lost log: Synchronous parallel in-place models and algorithms” (with Goodrich in the 28th Workshop on Advances in Parallel and Distributed Computational Models, 2026, and selected as an “outstanding paper” for APDCM 2027). It’s not currently free online but Vinesh and Mike promise to make an arXiv version soon. This part involves PRAM model parallel machines where the only shared memory is the input and each parallel processor has only a bounded amount of private memory. The title comes from a technique inspired by the first scene of the first Indiana Jones movie, in which Jones (unsuccessfully) swaps a sandbag for a booby-trapped gold figurine. In their algorithmic technique, Vinesh and Mike have the parallel processors each swap their working memory for a piece of the input data that they control, freeing up enough shared memory to perform their algorithms. They apply this technique not only to in-place sorting, but also to convex hulls, parallel primitives such as prefix sums and tree contraction, and the generation of random permutations.

The defense was presented very smoothly and clearly, and Vinesh’s many results (including several papers not included in the thesis) made for an easy pass of his defense. Congratulations, Vinesh!

(Discuss on Mastodon)