Tianqi Yang

Myself

I am a third-year undergraduate at Institute for Interdisciplinary Information Sciences (known as Yao Class), Tsinghua University. 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

2022

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

    Joint work with Lijie Chen and Jiatu Li

  • The Exact Complexity of Pseudorandom Functions and Tight Barriers to Lower Bound Proofs, Accepted to 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, Accepted to STOC 2022 [ECCC] [STOC version] [Slide at STOC]

    Joint work with Jiatu Li

2021

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