Zeyu Guo

Department of Computer Science University of Haifa zguotcs@gmail.com

I am a postdoctoral researcher at the Department of Computer Science of University of Haifa, working with Professor Noga Ron-Zewi. Previously, I was a postdoc at IIT Kanpur working with Professor Nitin Saxena. I completed my Ph.D. in computer science at Caltech in 2017, under Professor Chris Umans.

My research interests include pseudorandomness, coding theory, algebraic complexity theory, and applications of algebraic methods in theoretical computer science.

I am on the job market this year. See my CV, research statement and teaching statement.

Research

Ph.D. thesis

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

Papers

  • Zeyu Guo. Variety Evasive Subspace Families. Manuscript.
  • Zeyu Guo and Noga Ron-Zewi. Efficient List-Decoding with Constant Alphabet and List Sizes. To appear in STOC 2021. Also available on ECCC and arXiv.
  • Zeyu Guo, Ray Li, Chong Shangguan, Itzhak Tamo, and Mary Wootters. Improved List-Decodability of Reed–Solomon Codes via Tree Packings. Manuscript. Also available on ECCC and arXiv.
  • Zeyu Guo. Factoring Polynomials over Finite Fields with Linear Galois Groups: An Additive Combinatorics Approach. Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 42:1-42:14, 2020. Also available on arXiv.
  • Zeyu Guo and Rohit Gurjar. Improved explicit hitting-sets for ROABPs. Proceedings of the 24th International Workshop on Randomization and Computation (RANDOM), pages 4:1-4:16, 2020.
  • Zeyu Guo. Deterministic Polynomial Factoring over Finite Fields with Restricted Galois Groups. Manuscript.
  • Zeyu Guo, Mrinal Kumar, Ramprasad Saptharishi, and Noam Solomon. Derandomization from Algebraic Hardness. 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.
  • Zeyu Guo. Deterministic Polynomial Factoring over Finite Fields: A Uniform Approach via P-Schemes. Journal of Symbolic Computation. Manuscript version.
  • Zeyu Guo, Nitin Saxena, and Amit Sinhababu. Algebraic Dependencies and PSPACE Algorithms in Approximative Complexity. 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.
  • Zeyu Guo, Anand Kumar Narayanan, and Chris Umans. Algebraic Problems Equivalent to Beating Exponent 3/2 for Polynomial Factorization over Finite Fields. Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 47:1–47:14, 2016.
  • Zeyu Guo and He Sun. Gossip vs. Markov Chains, and Randomness-Efficient Rumor Spreading. Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 411-430, 2015. Full version on arXiv.
  • Zeyu Guo. Randomness-Efficient Curve Samplers. Proceedings of the 17th International Workshop on Randomization and Computation (RANDOM), page 575-590, 2013. Also available on ECCC.
  • Francis Y. L. Chin, Zeyu Guo, and He Sun. Minimum Manhattan Network is NP-Complete. 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.

    • Talks

    2020.12, Research Center for Mathematics and Interdisciplinary Sciences, Shandong University, Qingdao, China.

    2020.11, Technion Theory Lunch, Technion, Haifa, Israel.

    2020.08, The 45th International Symposium on Mathematical Foundations of Computer Science, virtual conference.

    2020.08, The 24th International Workshop on Randomization and Computation, virtual conference.

    2019.03, Workshop on Algebraic Complexity Theory, Bengaluru, India.

    2019.03, Indian Institute of Technology Bombay, Mumbai, India.

    2019.01, MPI-INF and MPI-MiS joint workshop on Theoretical Computer Science and Algebraic Geometry, Saarbrücken, Germany.

    2016.08, The 41st International Symposium on Mathematical Foundations of Computer Science, Krakow, Poland

    2015.07, The 12th International Conference on Finite Fields and Their Applications, Saratoga Springs, USA

    2015.01, The 26th ACM-SIAM Symposium on Discrete Algorithms, San Diego, USA

    2013.08, China Theory Week, Aarhus University, Denmark

    2012.08, Max Planck Institute for Informatics, Saarbrücken, Germany

    2009.06, The 25th Annual Symposium on Computational Geometry, Aarhus University, Denmark

    Teaching

    Teaching Assistant

    2014 Spring, CS 38: Introduction to Algorithms, Caltech

    2013 Spring, CS 151: Complexity Theory, Caltech

    2012 Winter, CS 138: Computer Algorithms, Caltech

    Contact Information

    zguotcs@gmail.com
    Department of Computer Science, University of Haifa, Haifa 3498838, Israel