Patrick Lin

I am currently pursuing a PhD in Computer Science at the University of Illinois at Urbana-Champaign (UIUC), advised by Jeff Erickson.

My CV: pdf.

Want to chat? Find me on on Fridays 2–3p CT.

Recent Updates


During my time at UIUC, I have primarily taught for courses related to Algorithms and Theoretical CS, though I am broadly interested in teaching anything I am qualified to.


Discrete Structures
CS 173 at UIUC.
Intro to Algorithms & Models of Computation
CS 374 at UIUC.

Teaching Assistant

Discrete Structures
CS 173 at UIUC.
Intro to Algorithms & Models of Computation
CS 374 at UIUC.
CS 473 at UIUC.
Algorithms for Big Data
CS 498 ABD at UIUC.

*Rated excellent by my students. **Rated outstanding by my students. Rated outstanding by the UIUC CS department.


My recent research has involved structural and computational aspects of surface-embedded graphs. I've done some (unpublished) work on distributed network design during internships at Google. In the past, I also worked on some problems in combinatorial optimization with a view towards learning theory.

A Note on Toroidal Maxwell–Cremona Correspondences
Preprint, September 2020.
Download: arXiv, pdf.

We explore toroidal analogues of the Maxwell–Cremona correspondence. Erickson and Lin showed the following correspondence for geodesic torus graphs \(G\): a positive equilibrium stress for \(G\), an orthogonal embedding of its dual graph \(G^*\), and vertex weights such that \(G\) is the intrinsic weighted Delaunay graph of its vertices. We extend their results to equilibrium stresses that are not necessarily positive, which correspond to orthogonal drawings of \(G^*\) that are not necessarily embeddings. We also give a correspondence between equilibrium stresses and parallel drawings of the dual.

How to Morph Graphs on the Torus
Coauthors To appear in SODA 2021.
Download: SODA, arXiv, pdf. Presentation: SODA.

We present the first algorithm to morph graphs on the torus. Given two isotopic essentially 3-connected embeddings of the same graph on the Euclidean flat torus, where the edges in both drawings are geodesics, our algorithm computes a continuous deformation from one drawing to the other, such that all edges are geodesics at all times. Previously even the existence of such a morph was not known. Our algorithm runs in \(O(n^{1+\omega/2})\) time, where \(\omega\) is the matrix multiplication exponent, and the computed morph consists of \(O(n)\) parallel linear morphing steps. Existing techniques for morphing planar straight-line graphs do not immediately generalize to graphs on the torus; in particular, Cairns’ original 1944 proof and its more recent improvements rely on the fact that every planar graph contains a vertex of degree at most 5. Our proof relies on a subtle geometric analysis of 6-regular triangulations of the torus. We also make heavy use of a natural extension of Tutte’s spring embedding theorem to torus graphs.

A Toroidal Maxwell–Cremona–Delaunay Correspondence
Coauthors Invited to special issue of JoCG. Preliminary version appeared in SoCG 2020.
Download: SoCG, arXiv, pdf. Presentation: VSAMRT.

We consider three classes of geodesic embeddings of graphs on Euclidean flat tori:

  • A torus graph \(G\) is equilibrium if it is possible to place positive weights on the edges, such that the weighted edge vectors incident to each vertex of \(G\) sum to zero.
  • A torus graph \(G\) is reciprocal if there is a geodesic embedding of the dual graph \(G^*\) on the same flat torus, where each edge of \(G\) is orthogonal to the corresponding dual edge in \(G^*\).
  • A torus graph \(G\) is coherent if it is possible to assign weights to the vertices, so that \(G\) is the (intrinsic) weighted Delaunay graph of its vertices.

The classical Maxwell–Cremona correspondence and the well-known correspondence between convex hulls and weighted Delaunay triangulations imply that the analogous concepts for plane graphs (with convex outer faces) are equivalent. Indeed, all three conditions are equivalent to \(G\) being the projection of the 1-skeleton of the lower convex hull of points in \(\mathbb{R}^3\). However, this three-way equivalence does not extend directly to geodesic graphs on flat tori. On any flat torus, reciprocal and coherent graphs are equivalent, and every reciprocal graph is equilibrium, but not every equilibrium graph is reciprocal. We establish a weaker correspondence: Every equilibrium graph on any flat torus is affinely equivalent to a reciprocal/coherent graph on some flat torus.

Scenario Submodular Cover
Coauthors Appeared in WAOA 2016.
Download: WAOA, arXiv, pdf.

Many problems in Machine Learning can be modeled as submodular optimization problems. Recent work has focused on stochastic or adaptive versions of these problems. We consider the Scenario Submodular Cover problem, which is a counterpart to the Stochastic Submodular Cover problem studied by Golovin and Krause (2011). In Scenario Submodular Cover, the goal is to produce a cover with minimum expected cost, where the expectation is with respect to an empirical joint distribution, given as input by a weighted sample of realizations. In contrast, in Stochastic Submodular Cover, the variables of the input distribution are assumed to be independent, and the distribution of each variable is given as input. Building on algorithms developed by Cicalese et al. (2014) and Golovin and Krause (2011) for related problems, we give two approximation algorithms for Scenario Submodular Cover over discrete distributions. The first achieves an approximation factor of \(O(\log Qm)\), where \(m\) is the size of the sample and \(Q\) is the goal utility. The second, simpler algorithm achieves an approximation bound of \(O(\log QW)\), where \(Q\) is the goal utility and \(W\) is the sum of the integer weights. (Both bounds assume an integer-valued utility function.) Our results yield approximation bounds for other problems involving non-independent distributions that are explicitly specified by their support.

Discrete Stochastic Submodular Maximization
Coauthors: Appeared in CIAC 2015.
Download: CIAC, arXiv, pdf.

We consider the problem of stochastic monotone submodular function maximization, subject to constraints. We give results on adaptivity gaps, and on the gap between the optimal offline and online solutions. We present a procedure that transforms a decision tree (adaptive algorithm) into a non-adaptive chain. We prove that this chain achieves at least \(\tau\) times the utility of the decision tree, over a product distribution and binary state space, where \(\tau = \min_{i,j} \Pr[x_i = j]\). This proves an adaptivity gap of \(1/\tau\) (which is 2 in the case of a uniform distribution) for the problem of stochastic monotone submodular maximization subject to state-independent constraints. For a cardinality constraint, we prove that a simple adaptive greedy algorithm achieves an approximation factor of \((1−1/e^\tau)\) with respect to the optimal offline solution; previously, it has been proven that the algorithm achieves an approximation factor of \((1−1/e)\) with respect to the optimal adaptive online solution. Finally, we show that there exists a non-adaptive solution for the stochastic max coverage problem that is within a factor \((1−1/e)\) of the optimal adaptive solution and within a factor of \(\tau(1−1/e)\) of the optimal offline solution.

Expository Materials

I recently started writing a set of notes on Data Structures to supplement an improvised course I gave to W. Linda Xu. These notes are heavily incomplete and the presentation is not suitable for use by a more general audience (yet).

Basic Data Structures for an Advanced Audience
Download: draft pdf.

In the past I took notes live in LaTeX and then edited them afterwards. All notes are permanently in a draft state; some are more polished than others.

Combinatorial Optimization
as taught by Karthik Chandrasekaran in Fall 2015.
Download: draft pdf.
Intro to Cryptography
as taught by Oded Regev in Fall 2014.
Download: draft pdf.
Computational Complexity
as taught by Subhash Khot in Spring 2014.
Download: draft pdf.
as taught by Sylvain Cappell in Fall 2013, Spring 2014.
Download: draft pdf.

Miscellaneous Documents

Mostly joke papers found here.

Need more RAM? Just invent time travel!
Coauthors: Appeared in SIGBOVIK 2019. April Fool's Paper. Winner of “Most frighteningly like real research” award.
Download: SIGBOVIK.
SMACK: when research in algorithms goes around in circles
Coauthors: Appeared in SIGBOVIK 2016. April Fool's paper.
Download: SIGBOVIK.


I have performed in various choral groups for many years, usually as a tenor, occasionally as a baritone. I am currently on hiatus (since choir is cancelled for 2020) from the University of Illinois Oratorio Society and the Baroque Artists of Champaign-Urbana (BACH).

Some pictures with groups I've sung with: BACH, NYU Madrigal Singers.

Very old recordings:

Crazy Little Thing Called Love
Collaborators: Listen: YouTube.
Fix You
Collaborators: Listen: mp3.
Shoshone Love Song
Collaborators: Listen: YouTube.