Andrej Bogdanov

SITE 5-068  |  abogdano (a)

I am a professor at the University of Ottawa. I moved here from the Chinese University of Hong Kong in 2023. Previously I was a postdoc at ITCS (now IIIS, Tsinghua), DIMACS (Rutgers), and IAS. I obtained my B.S. and M.Eng. degrees from the MIT and my Ph.D. from UC Berkeley. I spent some time as a Visiting Professor at the Tokyo Institute of Technology in 2013 and at the Simons Institute for the Theory of Computing in 2017 and 2021.

My research is in computational complexity and the foundations of cryptography. I like to work on pseudorandomness, one-way functions, property testing, and pretty much anything with discrete probability in it.


Graduate students

Postdoctoral advisees

My research is on the foundations of cryptography, average-case complexity of algorithms and proofs, constructions of public-key encryption, (pseudo)randomness, and sublinear-time algorithms.

My master's thesis was in formal verification. It was awarded an honorable mention for best M.Eng. thesis in Computer Science at MIT in 2001.

I am serving on the program committee of RANDOM 2024 and ASIACRYPT 2024. I am an associate editor of the ACM Transactions on Computation Theory.

I was previously involved in SODA 2024, CCC 2023, EUROCRYPT 2023, ASIACRYPT 2022, RANDOM 2022, TCC 2021, CRYPTO 2021, TCC 2020, ICALP 2020, ISAAC 2019, CCC 2019, EUROCRYPT 2019, TCC 2018, FOCS 2017, China Theory Week 2016, TCC 2016A and B, FSTTCS 2015, CCC 2015, ProvSec 2014, TAMC 2013, RANDOM 2012, FAW-AAIM 2012, CATS 2010, STOC 2009 and China Theory Week 2008.





Sublinear-time algorithms