Bio

I am a final year PhD student from Centre for Quantum Technologies, National University of Singapore. I am honoured to be advised by Prof. Divesh Aggarwal. My research interest lies in, broadly speaking, theoretical computer science, slightly biased towards complexity/hardness related stuff. I work mostly on hardness of Lattice problems (lower bounds and algorithms, etc) and a bit of complexity theory. 

Recently I have started exploring complexity problems related to Range Avoidance and more generally problems in the TFPH (Total Function Polynomial Hierarchy). 

Contact

Email: li.zeyong at u.nus.edu

Publications (the order of authorship is alphabetical) :

1. Improved Lower Bounds for 3-Query Matching Vector Codes.[eccc]
   Divesh Aggarwal, Pranjal Dutta, Zeyong Li, Maciej Obremski, Sidhant Saraogi.
   To appear in ITCS 2025.

2. Oblivious Classes Revisited: Lower Bounds and Hierarchies.[eccc]
   Karthik Gajulapalli, Zeyong Li, Ilya Volkovich.
   To appear in FSTTCS 2024.

3. Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simplified, Truly Uniform.[eccc,arxiv][Slide and Video at TCS+]
   Zeyong Li.
   In STOC 2024.

4. On the randomized complexity of range avoidance, with applications to cryptography and metacomplexity.[eccc]
   Eldon Chung, Alexander Golovnev, Zeyong Li, Maciej Obremski, Sidhant Saraogi, Noah Stephens-Davidowitz.
   In Submission.

5. The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs.[link]
   Yi-Jun Chang, Zeyong Li.
   In PODC 2023.

6. Lattice Problems Beyond Polynomial Time.[link]
   Divesh Aggarwal, Huck Bennett, Zvika Brakerski, Alexander Golovnev, Rajendra Kumar, Zeyong Li, Spencer Peters, Noah Stephens-Davidowitz, Vinod Vaikuntanathan.
   In STOC 2023.

7. An Improved Time-Approximation Factor tradeoff for (H)SVP.[link]
   Divesh Aggarwal, Zeyong Li, Noah Stephens-Davidowitz.
   In EUROCRYPT 2021.

8. Dimension preserving reductions between SVP and CVP in Different p-Norms.[link]
   Divesh Aggarwal, Yanlin Chen, Rajendra Kumar, Zeyong Li, Noah Stephens-Davidowitz.
   In SODA 2021.