Zeyu Guo

Research

Ph.D. thesis

P-schemes and Deterministic Polynomial Factoring over Finite Fields, 2017.

Papers

• Extractors for Images of Varieties
  Zeyu Guo, Ben Lee Volk, Akhil Jalan, and David Zuckerman
  Manuscript. Also available on ECCC and arXiv.
• Fast Multivariate Multipoint Evaluation Over All Finite Fields
  Vishwas Bhargava, Sumanta Ghosh, Zeyu Guo, Mrinal Kumar, and Chris Umans
  FOCS 2022. Also available on ECCC and arXiv.
• Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings
  Zeyu Guo, Ray Li, Chong Shangguan, Itzhak Tamo, and Mary Wootters
  Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 708–719, 2021.
• Variety Evasive Subspace Families
  Zeyu Guo
  An earlier version appears in Proceedings of the 36th Computational Complexity Conference (CCC), pages 20:1–20:33, 2021. Also available on ECCC and arXiv.
• Efficient List-Decoding with Constant Alphabet and List Sizes
  Zeyu Guo and Noga Ron-Zewi
  Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1502–1515, 2021. Also available on ECCC and arXiv. Journal version in IEEE Transactions on Information Theory 68(3): 1663–1682, 2022.
• Factoring Polynomials over Finite Fields with Linear Galois Groups: An Additive Combinatorics Approach
  Zeyu Guo
  Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 42:1–42:14, 2020. Also available on arXiv.
• Improved Explicit Hitting-Sets for ROABPs
  Zeyu Guo and Rohit Gurjar
  Proceedings of the 24th International Workshop on Randomization and Computation (RANDOM), pages 4:1–4:16, 2020.
• Deterministic Polynomial Factoring over Finite Fields with Restricted Galois Groups
  Zeyu Guo
  Manuscript.
• Derandomization from Algebraic Hardness
  Zeyu Guo, Mrinal Kumar, Ramprasad Saptharishi, and Noam Solomon
  SIAM Journal on Computing 51(2): 315–335, 2022. Also available on ECCC and arXiv. An earlier version appears in Proceedings of the 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 147–157, 2019.
• Deterministic Polynomial Factoring over Finite Fields: A Uniform Approach via P-Schemes
  Zeyu Guo
  Journal of Symbolic Computation 96: 22–67, 2020. Manuscript version.
• Algebraic Dependencies and PSPACE Algorithms in Approximative Complexity
  Zeyu Guo, Nitin Saxena, and Amit Sinhababu
  Proceedings of 33rd Computational Complexity Conference (CCC), pages 10:1–10:21, 2018. Journal version in Theory of Computing 16(15): 1–30, 2019. Also available on ECCC and arXiv.
• Algebraic Problems Equivalent to Beating Exponent 3/2 for Polynomial Factorization over Finite Fields
  Zeyu Guo, Anand Kumar Narayanan, and Chris Umans
  Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 47:1–47:14, 2016.
• Gossip vs. Markov Chains, and Randomness-Efficient Rumor Spreading
  Zeyu Guo and He Sun
  Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 411–430, 2015. Full version on arXiv.
• Randomness-Efficient Curve Samplers
  Zeyu Guo
  Proceedings of the 17th International Workshop on Randomization and Computation (RANDOM), page 575–590, 2013. Also available on ECCC.
• Minimum Manhattan Network is NP-Complete
  Francis Y. L. Chin, Zeyu Guo, and He Sun
  Proceedings of the 25th Annual Symposium on Computational Geometry (SCG), pages 393–402, 2009. Journal version in Discrete and Computational Geometry 45(4): 701–722, 2011.

Teaching

CSE 6321 – Computability and Complexity. Spring 2023.

Contact Information