Home

Short Bio

I am an Associate Professor in the Theory Group of the Department of Computer Science and Technology at Nanjing University. I am broadly interested in theoretical computer science.

Before that, I completed undergrad at SJTU and PhD at UC Berkeley, and I was a postdoc at Caltech. My PhD thesis focuses on the interplay between phase transitions in statistical physics, locations of zeros of graph polynomials, and algorithmic questions such as the tractable boundaries of approximate counting, sampling and inference; an online copy is available here.

Papers

DBLP, Scholar.

Optimal Bounds on Private Graph Approximation
with Jalaj Upadhyay and Zongrui Zou.
SODA 2024.
Uniqueness and Rapid Mixing in the Bipartite Hardcore Model
with Xiaoyu Chen and Yitong Yin.
FOCS 2023.
Zeros of ferromagnetic 2-spin systems [arxiv] [slides]
with Heng Guo and Pinyan Lu.
SODA 2020.
Correlation decay and partition function zeros: Algorithms and phase transitions [Extended abstract][arxiv] [slides]
with Alistair Sinclair and Piyush Srivastava.
FOCS 2019. Invited to SICOMP special issue for FOCS 2019.
Private Selection from Private Candidates [arxiv] [slides] [poster]
with Kunal Talwar.
STOC 2019.
Fisher zeros and correlation decay in the Ising model [Extended abstract] [arxiv] [slides] [poster]
with Alistair Sinclair and Piyush Srivastava.
J. Math. Phys. (2019). Extended abstract appeared in ITCS 2019.
The Ising Partition Function: Zeros and Deterministic Approximation [Extended abstract] [arxiv] [slides]
with Alistair Sinclair and Piyush Srivastava.
J. Stat. Phys. (2019). Extended abstract appeared in FOCS 2017.
Uniform Sampling through the Lovász Local Lemma [arxiv]
with Heng Guo and Mark Jerrum.
J. ACM (2019). Preliminary version appeared in STOC 2017.
Decentralized Anonymous Micropayments [ePrint]
with Alessandro Chiesa, Matthew Green, Peihan Miao, Ian Miers, and Pratyush Mishra.
EUROCRYPT 2017.
FPTAS for #BIS with Degree Bounds on One Side [arxiv] [slides]
with Pinyan Lu.
STOC 2015.
FPTAS for Counting Monotone CNF [arxiv] [slides]
with Pinyan Lu.
SODA 2015.
The Complexity of Ferromagnetic Two-spin Systems with External Fields [arxiv]
with Pinyan Lu and Chihao Zhang.
RANDOM 2014.
FPTAS for Counting Weighted Edge Covers
with Pinyan Lu and Chihao Zhang.
ESA 2014.
A Simple FPTAS for Counting Edge Covers [arxiv] [slides]
with Chengyu Lin and Pinyan Lu.
SODA 2014.

Teaching @ NJU

TBA.

Teaching @ UC Berkeley

CS 70. Discrete Mathematics and Probability Theory. Fall 2018.
CS174. Combinatorics and Discrete Probability. Spring 2018.
CS170. Efficient Algorithms and Intractable Problems. Fall 2017.

Teaching @ SJTU

Principle and Practice of Computer Algorithms (PPCA). Summer 2012 Summer 2013
Set Theory & Mathematical Logic. Fall 2012 Spring 2014
Project Workshop for Operating System (Nachos). Fall 2013

Activities

In the spring of 2019, I attended the Geometry of Polynomials (Simons program) and Data Privacy: Foundations and Applications (Simons program).
In the summer of 2018, I was an intern at the Google Brain team, and was fortunate to work with Dr. Kunal Talwar.
In the summer of 2017, I was invited to present at the Dagstuhl Seminar on Computational Counting.
In the spring of 2016, I attended the Counting Complexity and Phase Transitions (Simons program).
In the summer of 2015, I was invited to present at the China theory week.
In the summer and fall of 2013, I was an intern at the theory group of Microsoft Research (Asia), and was fortunate to work with Prof. Pinyan Lu.

Dissertation

Approximate counting, phase transitions and geometry of polynomials. August 2019, UC Berkeley.

Contact

Email: liu (at) nju (dot) edu (dot) cn
Github: @Liuexp
Skype: Liuexp.
Office: CS 516 (by appointment only)