Contact
Address:
Faculty of Informatics and Data Science,
University of Regensburg, 93053 Regensburg, Germany
Email: pw384 # hotmail # com
CV: [Here] (Last update: 04/10/2024 dd/mm/yyyy)
[Google Scholar] | [ORCID] | [dblp]
About Me
I am currently a postdoctoral researcher at the Faculty of Informatics and Data Science, University of Regensburg, working in the Algorithms and Complexity Theory group (Lehrstuhl) led by Radu Curticapean. Prior to this, I was 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. Even earlier, 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