Tianqi Yang


I am a forth-year undergraduate at Institute for Interdisciplinary Information Sciences (known as Yao Class), Tsinghua University. I’m currently visiting Prof. Ryan Williams at MIT for this semester. My research interests are graph algorithms and computational complexity, including circuit lower bounds, pseudorandomness, and the relationship between complexity and cryptography.

Email: yangtq19 at mails dot tsinghua dot edu dot cn



  • Black-box Constructive Proofs are Unavoidable, To appear in ITCS 2023

    Joint work with Lijie Chen and Ryan Williams


  • Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs, CCC 2022 [ECCC]

    Joint work with Lijie Chen and Jiatu Li

  • The Exact Complexity of Pseudorandom Functions and Tight Barriers to Lower Bound Proofs, STOC 2022, Best Student Paper Award [ECCC] [IACR Eprint] [STOC version] [Slide at STOC]

    Joint work with Zhiyuan Fan and Jiatu Li

  • \(3.1n − o(n)\) Circuit Lower Bounds for Explicit Functions, STOC 2022 [ECCC] [STOC version] [Slide at STOC]

    Joint work with Jiatu Li


  • Tree Path Minimum Query Oracle via Boruvka Trees [arXiv]