Contact

Address:
Room 5.08, Informatics Forum, 10 Crichton Street,
Edinburgh, EH8 9AB, Scotland, UK
Email: pw384 # hotmail # com
CV: [Here] (Last update: 14/04/2024 dd/mm/yyyy)
[Google Scholar] | [ORCID] | [dblp]

About Me

I am currently a Postdoctoral Research Associate (PDRA) at the School of Informatics, University of Edinburgh. I obtained a PhD degree at the same university under the supervision of Heng Guo. Prior to that, I got a Bachelor of Science (summa cum laude) at Peking University and was a member of PKU’s Turing Class. Previous experience could be found in the CV provided above.

Misc

• My Erdős-Bacon-Sabbath number is infinity - I am not revealing the Erdős number here (it’s a constant). One of my life goals is to bound this number by a constant.
• If you add “misc” after the slash of this page’s URL then you could find some personal stuff like hobbies.

---

Research

My research interest lies in several topics in theoretical computer science. To be more precise, I enjoy problems with inspiring combinatorial structures and/or surprising computational hardness. That includes (randomised) algorithms and complexity of approximate counting, and extremal/probabilistic combinatorics.

The focus of my recent research is different aspects of approximate counting problems beyond (in)tractability, such as random structures, derandomisation, fine-grained perspective, parameterised counting, applications to other fields, and so on.

For a full list of research articles, please view this page.

Two selected papers:

Inapproximability of counting hypergraph colourings
with Andreas Galanis and Heng Guo
ACM Trans. Comput. Theory, 14(3-4):10, pp. 1-33, 2022

• This is my debut paper in the study of approximate algorithms, and a showcase of my mathematical analysis skills.
• We show that approximately counting hypergraph colourings remains hard even within the Lovász local lemma (LLL) regime, under which the searching problem is tractable due to Moser-Tardos Algorithm. The hardness bound we obtain is square-root of that for the searching problem. Therefore, we confirm the “sampling-is-computationally-harder” phenomenon for this prototypical problem where LLL was originally developed.

A simple polynomial-time approximation algorithm for the total variation distance between two product distributions
with Weiming Feng, Heng Guo and Mark Jerrum
TheoretiCS, Volume 2 (2023), Article 8, 1-7 (preliminary version in SOSA 2023)

• This is a showcase of simplicity that, albeit within 5 pages, exploits and manipulates the fundamental aspect of coupling, a tool that is used frequently in probability theory.
• We give {Insert title here}, despite the exact computation is known to be #P-hard and does not admit any polynomial-time algorithm unless FP=#P.

---

Useful Links

Tools: Useful inequalities || mathcha
Job hunting: TCS Jobs || Math Jobs || DMANET
OA books / notes: UW CSE599 || MIT 18.225 || Levin-Peres || Arora-Barak || Friedli-Velenik
Good TCS websites: Complexity Zoo || Property Testing Review || FPT Wiki
Miscellaneous: Encyclopaedia Metallum