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.

Research

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.

How to Morph Graphs on the Torus
Coauthors Submitted to SODA 2021.
Download: arXiv, pdf.
Abstract

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.
Abstract

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.
Abstract

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.
Abstract

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.

Teaching

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.
  • Instructor of Record: Su2020
  • Teaching Assistant: Fa2019*
Intro to Algorithms & Models of Computation
CS 374 at UIUC.
Algorithms
CS 473 at UIUC.
Algorithms for Big Data
CS 498 ABD at UIUC.

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

Expository Materials

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.
Topology
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.

Music

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.