Tianqi Yang

Myself

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

Publications

2023

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

    Joint work with Lijie Chen and Ryan Williams

2022

  • 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

2021

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