Publications

(In theoretical computer science, the list of authors is generally sorted in alphabetical order.)

• Is nasty noise actually harder than malicious noise?

  Guy Blanc, Yizhi Huang, Tal Malkin, Rocco Servedio.

  To appear in 37th Annual ACM-SIAM Symposium on Discrete Algorithms. (SODA 2026)

  Best Paper Award, SODA 2026.

  [ arXiv ]
  
  

• Halfspaces are hard to test with relative error.

  Xi Chen, Anindya De, Yizhi Huang, Shivam Nadimpalli, Rocco Servedio, Tianqi Yang.

  To appear in 37th Annual ACM-SIAM Symposium on Discrete Algorithms. (SODA 2026)

  [ arXiv ]
  
  

• Fine-Grained Complexity in a World without Cryptography.

  Josh Alman, Yizhi Huang, Kevin Yeo.

  44th Annual International Conference on the Theory and Applications of Cryptographic Techniques. (EUROCRYPT 2025)

  [ ePrint ] [ Proceedings ]
  
  

• Relative-error monotonicity testing.

  Xi Chen, Anindya De, Yizhi Huang, Yuhao Li, Shivam Nadimpalli, Rocco Servedio, Tianqi Yang.

  36th Annual ACM-SIAM Symposium on Discrete Algorithms. (SODA 2025)

  [ arXiv ] [ Proceedings ]
  
  

• NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach.

  Yizhi Huang, Rahul Ilango, Hanlin Ren.

  55th Annual ACM Symposium on Theory of Computing. (STOC 2023)

  SIAM Journal on Computing, 54(4), pp. 819–886, 2025.

  [ ECCC ] [ ePrint ] [ Journal ] [ Proceedings ]
  
  

• Range Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs Algorithms.

  Yeyuan Chen, Yizhi Huang, Jiatu Li, Hanlin Ren.

  55th Annual ACM Symposium on Theory of Computing. (STOC 2023)

  [ ECCC ] [ Proceedings ]
  
  

• Parallel Discrete Sampling via Continuous Walks.

  Nima Anari, Yizhi Huang, Tianyu Liu, Thuy-Duong Vuong, Brian Xu, Katherine Yu.

  55th Annual ACM Symposium on Theory of Computing. (STOC 2023)

  [ Proceedings ]