Siqi Liu

sliu18 AT berkeley DOT edu

I am a joint postdoctral researcher at the Center for Discrete Mathematics and Theoretical Computer Science and the Institute for Advanced Study. I got my PhD in Computer Science at UC Berkeley in 2023, advised by Alessandro Chiesa. I received my BA in Computer Science from UC Berkeley in 2018.

I am interested in theoretical computer science in general. Most recently, I have been thinking about constructions of high-dimensional expanders, their connections to manifolds, and their applications to coding theory.

Papers

New Codes on High Dimensional Expanders. [arXiv]

Irit Dinur, Siqi Liu, and Rachel Yun Zhang.

Local and Global Expansion in Random Geometric Graphs. [arXiv]

Siqi Liu, Sidhanth Mohanty, Tselil Schramm, and Elizabeth Yang.
STOC 2023 (55th Annual ACM Symposium on Theory of Computing)

Linear-time Probabilistic Proofs over Every Field. [eprint]

Alessandro Chiesa, Jonathan Bootle, Ziyi Guan, and Siqi Liu.

Testing Thresholds for High-Dimensional Sparse Random Geometric Graphs [arXiv]

Siqi Liu, Sidhanth Mohanty, Tselil Schramm, and Elizabeth Yang.
STOC 2022 (54th Annual ACM Symposium on Theory of Computing)

Hypercontractivity on High Dimensional Expanders [arXiv]

Tom Gur, Noam Lifshitz, and Siqi Liu.
STOC 2022 (54th Annual ACM Symposium on Theory of Computing)

Zero-Knowledge Succinct Arguments with a Linear-Time Prover [eprint]

Alessandro Chiesa, Jonathan Bootle, and Siqi Liu.
Eurocrypt 2022 (41st Annual International Conference on the Theory and Applications of Cryptographic Techniques)

On Statistical Inference when Fixed Points of Belief Propagation are Unstable [arXiv]

Siqi Liu, Sidhanth Mohanty, and Prasad Raghavendra.
FOCS 2021 (63rd IEEE Symposium on Foundations of Computer Science)

High-Dimensional Expanders from Expanders [arXiv]

Siqi Liu, Sidhanth Mohanty, and Elizabeth Yang.
ITCS 2020 (11th Innovations in Theoretical Computer Science conference)

On the Impossibility of Probabilistic Proofs in Relativized Worlds [eprint]

Alessandro Chiesa and Siqi Liu.
ITCS 2020 (11th Innovations in Theoretical Computer Science conference)

Risk Robust Mechanism Design for a Prospect Theoretic Buyer [pdf]

Siqi Liu, J. Benjamin Miller, and Christos Alexandros Psomas.
SAGT 2019 (12th International Symposium on Algorithmic Game Theory)

On the Competition Complexity of Dynamic Mechanism Design [arXiv]

Siqi Liu and Christos Alexandros Psomas.
SODA 2018 (29th ACM-SIAM Symposium on Discrete Algorithms)

Teaching Experience

Spring 2024: 671 Expanders and High-dimensional Expanders. [course page]

Instructor

Spring 2023: CS170 Efficient Algorithms and Intractable Problems.

Content Teaching Assistant

Fall 2022: CS172 Computability and Complexity.

Teaching Assistant

Spring 2017: CS170 Efficient Algorithms and Intractable Problems.

Teaching Assistant

Summer 2016: CS70 Discrete Math and Probability Theory.

Head Teaching Assistant