Hi! Hopefully you found the right Paul! I am currently a PhD student at Stanford University. I did my undergrad and Master's at the University of British Columbia (in Math/Physics and Computer Science respectively). This website exists mainly for me to exercise my web design skills (or lack thereof). If you have any questions about this page, send me a message!
For work related matters, my CV can be found here.
Feel free to email me at paul.liu@stanford.edu.
The majority of network datasets consists of unweighted graphs. However, many networks have a natural notion of weight on the edges of the graph. For example, traffic flows in transportation networks or relationship strength in social networks. In this work, we offer efficient algorithms for computing heavy cliques in an arbitrary weighted network. We focus on large-scale networks arising from real-world applications, and show that our method performs orders of magnitudes faster than existing baseline approaches.
In submission.
Subgraph isomorphism is a classic and well studied problem in computer science. However, modern graph datasets now contain richer structure, and incorporating temporal information in particular has become a key part of network analysis. In this work we develop fast sampling algorithms for temporal motif counting (subgraph isomorphism where the subgraph must have edges appearing in a specific order). Our results show that we can achieve one to two orders of magnitude speedup over existing algorithms with minimal and controllable loss in accuracy on a number of datasets.
Published in ACM International Conference on Web Search and Data Mining (WSDM 2019).
Submodular optimization has received significant attention in both practice and theory, as a wide array of problems in machine learning, auction theory, and combinatorial optimization have submodular structure. In this paper, we present two algorithms for cardinality constrained submodular optimization that greatly simplifies prior works in both analysis and implementation.
Published in Symposium on Simplicity in Algorithms (SOSA 2019).
In this work we develop efficient approximation algorithms for various graph problems in the MRC model. The problems we tackle include weighted vertex cover and matching, maximal clique, maximal independent set, edge colouring, and vertex colouring.
Published in the 2018 Symposium on Parallelism in Algorithms and Architectures. The slides for the talk can be found here.
Within the computational geometry (CG) community, the shifting strategy is a popular algorithmic paradigm for approximation algorithms. In this work we revisit the shifting strategy in the streaming model. Using the streaming-shifting strategy, we give low-memory approximation algorithms for classical CG problems such as unit disc cover. When combined with the shifting coreset technique of Fonseca et al., we are able to approximate streaming variants of geometric dominating set, independent set, etc.
Published in the 2018 Canadian Conference on Computational Geometry.
We characterize length optimal collision-avoiding motions for a pair of disc robots on an obstacle free plane. The motions are composed of at most six (straight or circular-arc) segments, and their total length can be expressed as a simple integral with a closed form solution depending only on the initial and final positions of the robots.
Published in the 2016 Canadian Conference on Computational Geometry. Long form with extended results can be found here.
This work is an improved result of my earlier result: A fast 25/6-approximation for the minimum unit disk cover problem.
Short paper published in the 2015 Canadian Conference on Computational Geometry. Long form with extended results published in Computational Geometry: Theory and Application.
A software package for the solution and preconditioning of symmetric indefinite and skew-symmetric linear systems. This software package is quite easy to use and includes a Matlab interface. Matrices with millions of columns and hundreds of millions of non-zeros have been tested. See more information here.
This paper arose from my sym-ildl project. Published in ACM Transactions on Mathematical Software.
Given a point set P in 2D, what is the minimum number of unit radius discs that covers all of the points? This is called the Unit Disk Cover (UDC) problem and has a wide variety of applications in facility location, motion planning, and image processing. Unfortunately, UDC is also NP-Hard.
In this work we present simple and practical 25/6 - approximation algorithms for UDC with runtime O(n log n) and space O(n). This algorithm additionally extends to discs in any Lp norm.
A simulator for the pendumlum wave machine (youtube video). This beautiful phenomenon is the result of some pretty interesting physics, all of which is explained here. I've also made a calculator to calculate the lengths required for your own pendulum wave machine.
The code was used in the music video for the song Wave by the Crystal Fighters. The video used the calculator and simulator above to set up the machines, as well as some extra calculations that I ran on air resistance of the swingers. The real hard work goes to the guys who built the machine and filmed the video though!
A small but powerful C++ package designed for solving and preconditioning skew-symmetric and symmetric indefinite matrices. This software package is quite easy to use and includes a Matlab interface. Matrices with millions of columns and hundreds of millions of non-zeros have been tested. More details can be found here.
A class project for CS 348C: Physically Based Animation. Highly turbulent flows require extremely fine grids to simulate accurately, and is prohibitive for graphics applications. With the Wavelet Turbulence method, procedurally generated turbulence can be added to coarse grid simulations. In this project I attempt to refine the ideas of the Wavelet Turbulence to support anisotropic and time-varying noise. See the full paper here.
A class project done CPSC 517: Sparse Matrix Computation. In this project I review several algorithms that scales the infinity norm of each row and column in a given matrix to 1. Algorithms are provided for symmetric and unsymmetric matrices, as well as cases for which only the matrix-vector products can be obtained. See the full paper here.
For those that bookmark too many things but never remember to revisit any of them. A small chrome extension to keep in touch with old bookmarks. Find out more here.
A class project for CPSC 536N: Randomized Algorithms. In this project I review Indyk's classic result on high dimensional nearest neighbour queries, and try to apply similar techinques to the Unit Disc Cover (UDC) problem in high dimensional spaces. The paper contains a novel approximation algorithm for a relaxed version of the UDC problem when the dimension is large. See the full paper here.
A fun project done for the 2012 international university physics contest. The figure above is a model of a ping-pong ball spinning at 100 rad/s without drag. See the full paper here.
CS 490 is a Student Directed Seminar, and is a 3 credit course organized by senior students at UBC. Students are free to teach whatever they want (subject to a review by the UBC CS department of course), similar to MIT's independent activities period, but with the time commitment of a regular course. CS 490 is typically taught as an Introduction to Programming Contests course by members of the UBC ACM Team. It was lots of fun teaching the course! See here for the course webpage.
While I was struggling to do research in computer graphics, I was fortunate enough to be a teaching assistant for CS 348C. CS 348C is a grad-level course on physically based computer graphics animation. The course required students to produce video results of their work, and every assignment we had a showcase of the best student results. Aside from normal TA duties, I had a lot of fun compositing the submissions into larger music videos (see course webpage!). See here for the course webpage.
Science One is an inter-disciplinary course at UBC encompassing all first-year science courses (equivalent of at least six full-credit courses). The students are taught a mega-course encompassing first year Math, Physics, Biology, and Chemistry. Helped design assignments and taught review sessions for the Math portion of the program. See here for the course webpage.