Fractional cascading   •  With Leo Guibas   (ICALP 1985, Algorithmica 1986) Imagine a computer network that connect cities together, with at each node, tucked into a corner, the city's phone book. As you surf around, you look up a given name in every phone book that comes your way. Can you beat binary search? (No hashing, no superlinear storage.) The answer is yes. The trick is to preprocess the phone books by letting fractional samples cascade across the network. Success depends on the favorable outcome of a battle of exponentials pitting the swelling data volume caused by the cascading against the exponential decay from the sampling. The technique has found many uses, including packet routing and firewall rule evaluation. Fractional cascading in action is a beautiful sight to behold, with unpredictable avalanches reminiscent of Bak's sandpiles. Self-organized criticality beckons. Can phone books be replaced by higher-dimensional structures? No. Fractional cascading is magic in 1D!

The fast Johnson-Lindenstrauss transform and approximate nearest neighbors   •  With Nir Ailon   (STOC 2006, SICOMP 2009) The FJLT is a simple method for low-distortion embeddings by random projections using sparse matrices. The preconditioning idea behind it has found several real-world application (eg, Facebook AI Similarity Search). The idea behind the FJLT is to use Heisenberg's inequality to fill up sparse vectors via a randomized Fourier transform. Randomization is necessary because not all vectors can be densified. Fortunately, the dense vectors outnumber the sparse ones, so randomizing the FFT moves sparsity away from the playing field. Nothing terribly deep there but a rare use of the uncertainty principle in theoretical computer science.

Self-improving algorithms   •  With N. Ailon, K.L. Clarkson, D. Liu, W. Mulzer, C. Seshadhri   (SODA 2006, SICOMP 2011) We explore the intuitive idea that algorithms should learn from their users and adapt themselves to their needs. We provide a proof of concept by giving optimal algorithms for sorting and Delaunay triangulations, where optimality is defined with reference to arbitrary, unknown distributions on the inputs. Two decades on, the idea of self-improvement is all the rage in AI.

Lower bounds for linear degeneracy testing   •  With Nir Ailon   (STOC 2004, JACM 2005) Given n numbers, do any r of them add up to 0 or, more generally, form a zero of a given r-variate linear polynomial? From 3-SUM to bin packing to testing general position, this problem is ubiquitous. It is NP-complete but polynomial for constant r. We revisit a remarkable argument of Jeff Erickson and geometrize it to derive an exponential (in r) lower bound on decision-tree depth when the queries involve fewer than 2r variables. Amazingly, that threshold is tight! The proof is surprisingly mathy (polyhedral geometry, Reed-Solomon codes, tensor product, etc) but such is the nature of lower-bound work.

The convergence of bird flocking   •   (SoCG 2010, JACM 2014) Bird flocking was my introduction to the field of natural algorithms. In the Vicsek-Cucker-Smale model, birds average their velocities with those within a fixed distance. I showed that the birds' headings eventually stabilize. The proof was over 100 pages. In subsequent collaboration with Kritkorn Karntikoon, we used the s-energy to give a simpler proof and show that, as long as the number of flocks remains bounded, convergence is polynomial in the number of birds.

On the periodicity of random walks in dynamic networks   •   (IEEE Trans. Network Science, 2020) Dynamic networks guide the information flow in most natural algorithms. We investigate random walks in graphs whose edges change over time as a function of the current probability distribution of the walk. We show that such systems can be chaotic and even exhibit robust hyper-torpid mixing. This bears on a key biological question: How do large timescale ratios emerge in living matter? If each graph is strongly connected, the dynamics is asymptotically periodic almost surely.

Noisy Hegselmann-Krause systems: phase transition and the 2R-conjecture   •  With C. Wang, Q. Li, Weinan E   (J Stat Phys, 2017) Imagine a set of numbers randomly distributed between 0 and 1. At each step, every number moves to the average of its neighbors within a distance of R. The numbers track the opinions of agents who communicate locally and evolve by averaging. This forms what is known as a Hegselmann-Krause system. The famous 2R-conjecture says that the opinions will eventually cluster into points roughly 2R apart. This work proves the conjecture in the noisy thermodynamic limit: To our surprise, the separation is not quite 2R but ~2.29R.

Iterated learning in dynamic social networks   •  With C. Wang   (JMLR, 2019) Traditional models of chained Bayesian learning predict that information degrades across generations until agents revert to their innate prior beliefs. We show how this information decay can be overcome by either connecting the agents within time-varying social networks or (barely) increasing the length of the training sessions over time. This reveals how dynamic social structures and varied interaction lengths naturally preserve novel linguistic traits and enable networks of agents to achieve true, long-term consensus around target truths.

Cutting hyperplanes for divide-and-conquer   •   (FOCS 1991, DCG 1993) Cuttings are the most powerful divide-and-conquer tools in computational geometry. They're a product of the sampling revolution that shook the field in the late eighties. This paper presents the first optimal construction with respect to both time and size. It builds on earlier collaboration with Joel Friedman and seminal results by Jirka Matoušek. The algorithm starts out predictably, as we dig our way through a hierarchy of hyperplane arrangements. But then we hit a snag! The recursion's tiny errors get amplified at each level and sampling alone can't rescue us from the catastrophic buildup. What to do? True to form, geometry steps in to save the day.

An optimal algorithm for intersecting line segments in the plane   •  With Herbert Edelsbrunner   (FOCS 1988, JACM 1992) How do we compute optimally all pairwise intersections among a collection of line segments. The challenge is to avoid sorting the intersections, which rules out standard Bentley-Ottmann sweeplining. I had shown earlier how to do that, but at the price of a pesky additive overhead. Our way around the peskiness was to use a hierarchical sweep and exploit the rich combinatorics of line arrangements. The data structuring is all pre-VC dimension. In retrospect, Herbert and I were lucky to pull it off, given the limited divide-and-conquer technology of the day.

An optimal convex hull algorithm in any fixed dimension   •   (FOCS 1991, DCG 1993) Welcome to the glorious world of derandomization! In 1989, Clarkson and Shor published one of the most influential papers in computational geometry. Its highlight was an optimal probabilistic resolution of the convex hull problem in fixed dimension, a lovely algorithm crying out to be derandomized. Lovely might not be the first word that comes to mind when reading my paper, as you watch in horror a punishing barrage of sampling artillery fired at enemy positions. The VC-dimension armada charges ahead with all it's got: semicuttings, ε-approximations, dual shatter functions, k-sets, product spaces, sensitive sampling, higher-moment averaging, etc. Suddenly, in the fog of battle, doubts begin to creep in. Are we trying to cross the Pacific in a fancy gold-plated bathtub? Spoiler alert: In the end, it all worked out and the world was made safer for determinism. Hervé Brönnimann, Jirka Matoušek, and I later joined forces to simplify the algorithm: It's lighter fare but still a full course meal. For easier digestion, I recommend this version (Chapter 7).

Quasi-optimal range searching in spaces of finite VC-dimension   •  With Emo Welzl   (DCG 1989) We prove that any set of n points in the plane can be made into the vertices of a simple polygon that no line can cut in more than roughly √n places. This fundamental geometric fact should be taught in every high school in the land. The proof is elementary, yet surprising and a joy to teach in the classroom. It is easy to generalize to higher dimension and other settings, and the result provides a powerful new tool for range searching and discrepancy theory. Our result sharpens a previous bound by my coauthor, which featured one of the early uses of the multiplicative weights update method in computer science (all credit to Emo). The improvement comes from a packing argument interesting in its own right, which Haussler generalized a few years later to set systems of bounded VC-dimension. Roughly, the idea is to define a discrete metric for a hyperplane arrangement and argue that it behaves in much the same way as its Euclidean counterpart.

A spectral approach to lower bounds with applications to geometric searching   •   (FOCS 1994, SICOMP 1998) This work began with the observation that designing data structures for range searching is often an eigenvalue problem in disguise. To prove complexity bounds is then a matter of estimating the spectrum of certain linear maps, which is right in discrepancy theory's wheelhouse. To cement the connection, I devised an entropy-based approach to arithmetic circuits that went like this. Feed the circuit a random input from a well-chosen distribution and observe the computation with blurry eyes. If the dominant eigenvalue is high enough then the circuit will tend to amplify the signals, in turn causing the blurring to increase the entropy—something that wouldn't happen with clear vision (deterministically). Now argue that, in a bounded-coefficient model, no (blurry) gate can raise the entropy by too much, hence the need for many gates. Voilà. Using entropy has two benefits: (i) it has powerful algebraic identities; (ii) it gives us a stronger result by allowing the addition of up to a linear number of help gates into the circuit. Where lower bounds for range searching differ from upper bounds is in their heavy reliance on classical math: in this case, convex geometry, linear algebra, algebraic topology, Fourier analysis, graph theory, stochastic geometry, number theory, information theory, coding theory, tensors, and even wavelets [1, 2, 3, 4, 5, 6, 7, 8, 9].