Siyao Guo 

Assistant Professor, Computer Science

Room S741,  NYU Shanghai

siyao.guo (a) nyu.edu

About Me [CV]

I am an assistant professor in Computer Science at NYU Shanghai.

Before that, I was a postdoc at New York University, UC Berkeley, and Northeastern University.  

I did my Ph.D. at the Chinese University of Hong Kong, under the supervision of Andrej Bogdanov. 

My research interests are theoretical computer science, in particular cryptography, computational complexity, and pseudorandomness. 

Publications  [DBLP] [Google Scholar]

28.  Akshima, Tyler Besselman, Siyao Guo, Zhiye Xie and Yuping Ye:

       Tight Time-Space Tradeoffs for the Decisional Diffie-Hellman Problem.

        In STOC 2024.


27.   Akshima, Xiaoqi Duan,  Siyao Guo, Qipeng Liu: 

         On Time-Space Lower Bounds for Finding Collisions in Sponge Hash Functions.

          In TCC 2023. Pdf.



26.  Alexander Golovnev, Siyao Guo, Spencer Peters and Noah Stephens-Davidowitz: 

         The (Im)possibility of Simple Search-to-Decision Reductions for Approximate Optimization. 

         In APPROX 2023. Pdf.


25.  Alexander Golovnev, Siyao Guo, Spencer Peters and Noah Stephens-Davidowitz: 

         Revisiting Time-Space Tradeoffs for Function Inversion. 

         In CRYPTO 2023. Pdf.


24.  Akshima, Siyao Guo and Qipeng Liu:  

         Time-Space Lower Bounds for Finding Collisions in Merkle-Damgard Hash Functions.

          In CRYPTO 2022 and Journal of Cryptology 2024. Pdf.  


23.  Siyao Guo, Qian Li, Qipeng Liu and Jiapeng Zhang:  

         Unifying Presampling via Concentration Bounds. 

          In TCC 2021. Pdf.


22.  Yevgeniy Dodis, Siyao Guo, Noah Stephens-Davidowitz and Zhiye Xie:  

          No Time to Hash: Provable Super-Efficient Entropy Accumulation.  

          In CRYPTO 2021. Pdf.


21.  Yevgeniy Dodis, Siyao Guo, Noah Stephens-Davidowitz and Zhiye Xie:  

          On Linear Extractors for Independent Sources. 

           In ITC 2021. Pdf.


20.  Nick Gravin, Siyao Guo, Tsz Chiu Kwok and Pinyan Lu:  

          Concentration Bounds for Almost K-wise Independence with Applications to Non-Uniform Security.  

          In SODA 2021. Pdf.


19.  Kai-Min Chung, Siyao Guo, Qipeng Liu and Luowen Qian:  

         Tight Quantum Time-Space Tradeoffs for Function Inversion. 

          In FOCS 2020. Pdf.


18.  Divesh Aggarwal, Siyao Guo, Maciej Obremski, Joao Ribeiro and Noah Stephens-Davidowitz:  

         Extractor Lower Bounds, Revisited.  

         In RANDOM 2020.  Pdf.


17.  Alexander Golovnev, Siyao Guo, Thibaut Horel, Sunoo Park and Vinod Vaikuntanathan: 

         Data Structures Meet Cryptography:  3 SUM with Preprocessing.  

         In STOC 2020.  Pdf.


16.  Siyao Guo, Pritish Kamath, Alon Rosen, Katerina Sotiraki:  

         Limits on the Efficiency of (Ring) LWE based Non-Interactive Key Exchange.   

         In PKC 2020 (and Invited to Journal of Cryptology).  Pdf.


15.  Marshall Ball, Siyao Guo and Daniel Wichs:  

          Non-Malleable Codes for Decision Trees.  

          In CRYPTO 2019.  Pdf. 


14.  Marshall Ball, Dana Dachman-Soled, Siyao Guo, Tal Malkin, Li-Yang Tan:  

         Non-Malleable Codes for Small-Depth Circuits. 

         In FOCS 2018. Pdf.


13.  Salman Beigi, Andrej Bogdanov, Omid Etesami, Siyao Guo: 

         Optimal Deterministic Extractors for Generalized Santha-Vazirani Sources. 

         In RANDOM 2018. Pdf.


12.  Sandro Coretti, Yevgeniy Dodis, Siyao Guo:  

         Non-Uniform Bounds in the Random-Permutation, Ideal-Cipher, and Generic-Group Models.  

         In CRYPTO 2018. Pdf.


11.  Sandro Coretti, Yevgeniy Dodis, Siyao Guo, John Steinberger: 

         Random Oracles and Non-Uniformity.  

         In EUROCRYPT 2018. Pdf. 


10.  Yevgeniy Dodis, Siyao Guo and Jonathan Katz: 

         Random Oracles with Auxiliary Input, Revisited.  

         In EUROCRYPT 2017. Pdf. Slides.     

    

9.   Clement Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar, Karl Wimmer:  

        Testing k-monotonicity: The rise and fall of Boolean functions.  

         In ITCS 2017 (and Journal of  ToC).  Pdf.  Poster. 


8.   Andrej Bogdanov, Siyao Guo and Ilan Komargodski:  

        Threshold Secret Sharing Requires a Linear Size Alphabet.  

        In TCC 2016B (and Journal of ToC). Pdf.  Slides.


7.   Andrej Bogdanov, Siyao Guo, Daniel Masny, Silas Richelson and Alon Rosen:  

        On the Hardness of Learning with Rounding Over Small Modulus.  

        In TCC 2016A.  Pdf. 


6.   Siyao Guo, Pavel Hubacek,  Alon Rosen and Margarita Vald: 

        Rational Sumchecks.  

        In TCC 2016A. Pdf.


5.   Siyao Guo and Ilan Komargodski:  

        Negation-limited Formulas.  

        In RANDOM 2015 (and Journal of TCS).  Pdf.   Slides.


4.   Siyao Guo, Tal Malkin,  Igor C. Oliveira and Alon Rosen:  

        The Power of Negations in Cryptography.  

         In TCC 2015.  Pdf.  Slides.


3.   Siyao Guo,  Pavel Hubacek,  Alon Rosen and Margarita Vald:  

        Rational Arguments:  Single Round Delegation with Sublinear Verification.  

        In ITCS 2014. Pdf. 


2.   Adi Akavia,  Andrej Bogdanov,  Siyao Guo,  Akshay Kamath and Alon Rosen:  

       Candidate Weak Pseudorandom Functions in AC0 o MOD2.  

       In ITCS 2014. Pdf.  Slides.


1.   Andrej Bogdanov and Siyao Guo:  

      Sparse Extractor Families for All the Entropy.  

      In ITCS 2013. Pdf.  Slides