Tianqi Yang¶
I am a first-year Ph.D. at Columbia University, co-advised by Prof. Josh Alman, Xi Chen, Tal Malkin, Toniann Pitassi, Rocco Servedio, and Henry Yuen. My research interests lie broadly in circuit complexity, pseudorandomness, cryptography, and proof complexity.
Email: [my first name] dot [my last name] at columbia dot edu
Publications¶
2023¶
- Black-box Constructive Proofs are Unavoidable, ITCS 2023 [ITCS version]
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] [CCC version]
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