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.
Courses
- Discrete mathematics: W26, W25, W24, W23, F18, F17, F16, F15, F14
- Great algorithms: F25, F24
- Complexity: F23, F19, S16, S10, F07, S07
- Probability: F22, F20, S20, S19, S14, S13
- Statistics: S22, S21
- Cryptography: F20, S18, F12, S11
- Data privacy: S15
- Codes, Boolean functions, and expanders: F13, S12
- Formal languages and automata theory: F11, F10, F09, F08
Graduate students
- Yanbo Chen, current Ph.D. student
- Lorenzo Taschin, current Ph. D. student, M. Phil. 2024 (EPFL, co-advised with Alessandro Chiesa)
- Bennett Punyan Hon, current M. S. student (co-advised with Arthur Mehta)
- King On Yung, Ph. D. 2024 (co-advised with Farzan Farnia)
- Tsun Ming Cheung, M. Phil. 2021, now at Academia Sinica
- Chin Hei Ho, M. Phil. 2020, now at SW7 group
- Chris Williamson, M. Phil. 2016, Ph. D. 2019, now at SW7 group
- Peter Poon, M. Phil. 2016 (co-advised with Lap Chi Lau)
- Gary Sham, M. Phil. 2015
- Siyao Guo, Ph. D. 2014, now at NYU Shanghai
- Chin Ho Lee, M. Phil. 2013, now at North Carolina State
- Chiwang Chow, M. Phil. 2013, now at Amazon
- Fan Li, M. Phil. 2013
Postdoctoral advisees
- Krishnamoorthy Dinesh, 2019 – 2021, now at IIT Palakkad
- Gautam Prakriya, 2019 – 2022
My research is in cryptography, average-case complexity, (pseudo)randomness, and sublinear-time algorithms.
I am serving on the program committees of SAC 2026 (co-chair), IWSEC 2026, ITCS 2027, and EUROCRYPT 2027. I am an associate editor of the ACM Transactions on Computation Theory.
Publications
Cryptography and Machine Learning
- Andrej Bogdanov, Alon Rosen, and Neekon Vafa: Statistically undetectable backdoors in deep neural networks. 43rd International Conference of Machine Learning (ICML), 2026.
- Andrej Bogdanov, Alon Rosen, Neekon Vafa, and Vinod Vaikutanathan: Adaptive robustness of hypergrid Johnson-Lindenstrauss. 58th ACM Symposium on Theory of Computing (STOC), 2026.
- Marco Benedetti, Andrej Bogdanov, Enrico M. Malatesta, Marc Mézard, Gianmarco Perrupato, Alon Rosen, Nikolaj I. Schwartzbach, and Riccardo Zecchina: Collision resistance of single-layer neural nets. arXiv:2606.03807, 2026.
- Marco Benedetti, Andrej Bogdanov, Enrico M. Malatesta, Marc Mézard, Gianmarco Perrupato, Alon Rosen, Nikolaj I. Schwartzbach, and Riccardo Zecchina: Are neural networks collision resistant? Phys. Rev. X 16, 021051, 2026.
- Marco Benedetti, Andrej Bogdanov, Enrico M. Malatesta, Marc Mézard, Gianmarco Perrupato, Alon Rosen, Nikolaj I. Schwartzbach, and Riccardo Zecchina: Overlap gap and computational thresholds in the square wave perceptron. J. Stat. Mech. 123303, 2025.
Cryptography
- Andrej Bogdanov, Chris Jones, Alon Rosen, and Ilias Zadik: Low-degree security of the Planted Random Subgraph problem. In Proceedings of the 22nd Theory of Cryptography Conference (TCC), 2024.
- Masayuki Abe, Andrej Bogdanov, Miyako Okhubo, Alon Rosen, Zehua Shang, and Mehdi Tibouchi: CDS composition of multi-round protocols. In Proceedings of CRYPTO 2024.
- Andrej Bogdanov, Pravesh Kothari, and Alon Rosen. Public-key encryption, local pseudorandom generators, and the low-degree method. In Proceedings of the 21st Theory of Cryptography Conference (TCC), 2023.
- Andrej Bogdanov. Csirmaz's Duality Conjecture and Threshold Secret Sharing. In Proceedings of the Fourth Conference on Information-Theoretic Cryptography (ITC), 2023.
- Andrej Bogdanov, Miguel Cueto Noval, Charlotte Hoffmann, and Alon Rosen. Public-key encryption from Continuous Learning with Errors. In Proceedings of the Twentieth Theory of Cryptography Conference (TCC), 2022.
- Masayuki Abe, Miguel Ambrona, Andrej Bogdanov, Miyako Okhubo, and Alon Rosen: Acyclicity programming for sigma-protocols. In Proceedings of the Nineteenth Theory of Cryptography Conference (TCC), 2021.
- Masayuki Abe, Miguel Ambrona, Andrej Bogdanov, Miyako Okhubo, and Alon Rosen: Non-interactive composition of sigma-protocols via share-then-hash. In Proceedings of ASIACRYPT 2020.
- Andrej Bogdanov, Siyao Guo, and Ilan Komargodski: Threshold secret sharing requires a linear size alphabet. In Theory of Computing, vol. 16, article 2, 2020. (Preliminary version in Proceedings of the Fourteenth Theory of Cryptography Conference (TCC-B), 2016.)
- Andrej Bogdanov, Yuval Ishai, and Akshayaram Srinivasan: Unconditionally secure computation against low-complexity leakage. In Proceedings of CRYPTO 2019.
- Andrej Bogdanov and Alon Rosen: Pseudorandom functions: Three decades later. Chapter 3 in Tutorials on the foundations of cryptography: Dedicated to Oded Goldreich, Springer, 2017.
- Andrej Bogdanov, Siyao Guo, Daniel Masny, Silas Richelson, and Alon Rosen: On the hardness of Learning with Rounding over small modulus. In Proceedings of the Thirteenth Theory of Cryptography Conference (TCC-A), 2016.
- Andrej Bogdanov and Chin Ho Lee: Homomorphic evaluation requires depth. In Proceedings of the Thirteenth Theory of Cryptography Conference (TCC-A), 2016.
- Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath, Alon Rosen: Candidate weak pseudorandom functions in AC0 o MOD2. In Proceedings of the 5th Symposium on Innovations in Theoretical Computer Science (ITCS), 2014.
- Andrej Bogdanov and Chin Ho Lee: Limits of provable security for homomorphic encryption. In Proceedings of CRYPTO 2013.
- Andrej Bogdanov and Youming Qiao: On the security of Goldreich's one-way function. In Computational Complexity, vol. 21, no. 1, 2012. Invited paper. (Preliminary version in Proceedings of the 13th International Workshop on Randomization and Computation (RANDOM), 2009.)
- Benny Applebaum, Andrej Bogdanov, Alon Rosen: A dichotomy for local small-bias generators. In Journal of Cryptology vol. 29, issue 3, pages 577-596, 2016. (Preliminary version in Proceedings of the Ninth Theory of Cryptography Conference (TCC), 2012.)
- Andrej Bogdanov and Alon Rosen: Input locality and hardness amplification. In Journal of Cryptology, vol. 26, pages 144-171, 2013. Invited paper. (Preliminary version in Proceedings of the Eighth Theory of Cryptography Conference (TCC), 2011.)
Randomness
- Andrej Bogdanov, William Hoza, Gautam Prakriya, and Edward Pyne: Hitting sets for regular branching programs. In Proceedings of the 2022 Computational Complexity Conference (CCC).
- Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, and Akshayaram Srinivasan: Bounded indistinguishability for simple sources. In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS), 2022.
- Andrej Bogdanov, Nikhil Mande, Justin Thaler, and Christopher Williamson: Approximate degree, secret sharing, and concentration phenomena. In Proceedings of the 23rd International Workshop on Randomization and Computation (RANDOM), 2019. (Subsumes Approximate degree of AND via Fourier analysis, ECCC TR18-197, 2018.)
- Salman Beigi, Andrej Bogdanov, Omid Etesami, and Siyao Guo: Complete classification of generalized Santha-Vazirani sources. In Proceedings of the 22nd International Workshop on Randomization and Computation (RANDOM), 2018.
- Andrej Bogdanov and Christopher Williamson: Approximate bounded indistinguishability. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP), 2017.
- Andrej Bogdanov, Yuval Ishai, Emanuele Viola, and Christopher Williamson: Bounded indistinguishability and the complexity of recovering secrets. In Proceedings of CRYPTO 2016.
- Andrej Bogdanov, Zeev Dvir, Elad Verbin, and Amir Yehudayoff: Pseudorandomness for width two branching programs. In Theory of Computing vol. 9, article 7, 2013.
- Andrej Bogdanov and Siyao Guo: Sparse extractor families for all the entropy. In Proceedings of the 4th Symposium on Innovations in Theoretical Computer Science (ITCS), 2013.
- Andrej Bogdanov, Periklis Papakonstantinou, and Andrew Wan: Pseudorandomness for linear length branching programs and stack machines. In Proceedings of the 16th International Workshop on Randomization and Computation (RANDOM), 2012.
- Andrej Bogdanov, Periklis Papakonstantinou, and Andrew Wan: Pseudorandomness for read-once formulas. In Proceedings of the 52nd Annual Symposium on Foundations of Computer Science (FOCS), 2011.
- Nayantara Bhatnagar, Andrej Bogdanov, and Elchanan Mossel: The computational complexity of estimating convergence time. In Proceedings of the 15th International Workshop on Randomization and Computation (RANDOM), 2011.
- Andrej Bogdanov and Elchanan Mossel: On extracting common random bits from correlated sources. IEEE Transactions on Information Theory, vol. 57, no. 10, 2011.
- Andrej Bogdanov and Emanuele Viola: Pseudorandom bits for polynomials. Siam J. Comp., vol. 39, no. 6, 2010. Invited paper. (Preliminary version in Proceedings of the 48th Annual Symposium on Foundations of Computer Science (FOCS), 2007.)
- Andrej Bogdanov: Pseudorandom generators for low-degree polynomials. In Proceedings of the 37th Annual ACM Symposium on the Theory of Computing (STOC), 2005.
Complexity
- Andrej Bogdanov, Rohit Chatterjee, Yunqi Li, and Prashant Nalini Vasudevan: Decoding balanced linear codes with preprocessing. In Proceedings of the 17th Conference on Innovations in Theoretical Computer Science (ITCS), 2026. To appear.
- Andrej Bogdanov, Alon Rosen, and Kel Zin Tan: Sample-efficient search-to-decision reduction for kLIN. In Proceedings of 45th Annual Cryptology Conference (CRYPTO), 2025.
- Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, and Sruthi Sekar. Bounded simultaneous messages. In Proceedings of the 43rd conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2023.
- Andrej Bogdanov, Tsun Ming Cheung, Krishnamoorthy Dinesh, and John C. S. Lui. Classical simulation of one-query quantum distinguishers. In Proceedings of the 27th International Conference on Randomization in Computation (RANDOM), 2023.
- Andrej Bogdanov and Alon Rosen. Nondeterministic interactive refutations for nearest Boolean vector. In Proceedings of the 50th International Colloquium on Automata, Languages, and Programming (ICALP), 2023.
- Scott Aaronson, Andris Ambainis, Andrej Bogdanov, Krishnamoorthy Dinesh, Tsung Ming Cheung: On quantum versus classical query complexity. ECCC TR21-115, 2021.
- Andrej Bogdanov, Manuel Sabin, and Prashant Nalini Vasudevan: XOR codes and sparse random linear equations with noise. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 2019.
- Andrej Bogdanov: Small bias requires large formulas. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP), 2018.
- Andrej Bogdanov and Christina Brzuska: On basing size-verifiable one-way functions on NP-hardness. In Proceedings of the 12th Theory of Cryptography Conference (TCC), 2015.
- Andrej Bogdanov, Akinori Kawachi, and Hidetoki Tanaka: Hard Functions for Low-degree Polynomials over Prime Fields. In Transactions on Computation Theory 5(2):5, 2013. (Preliminary version in Proceedings of the 36th International Symposium on Mathematical Foundations of Computer Science, 2011.)
- Andrej Bogdanov, Kunal Talwar, and Andrew Wan: Hard instances for satisfiability and quasi-one-way functions. In Proceedings of the First Symposium on Innovations in Computer Science (ICS), 2010.
- Andrej Bogdanov, Elchanan Mossel and Salil Vadhan: The complexity of distinguishing Markov Random Fields. In Proceedings of the 12th International Workshop on Randomization and Computation (RANDOM), 2008.
- Andrej Bogdanov and Muli Safra: Hardness amplification for errorless heuristics. In Proceedings of the 48th Annual Symposium on Foundations of Computer Science (FOCS), 2007.
- Andrej Bogdanov and Luca Trevisan: Average-case complexity (and addendum). In Madhu Sudan, editor, Foundations and Trends in Theoretical Computer Science, volume 2, issue 1, Now Publishers, 2006.
- Andrej Bogdanov and Luca Trevisan: On worst-case to average-case reductions for NP problems. SIAM J. Comp., vol. 36, no. 4, 2006. Invited paper. (Preliminary version in Proceedings of the 44th Annual Symposium on Foundations of Computer Science (FOCS), 2003.)
- Andrej Bogdanov: Gap amplification fails below ½. Note on ECCC TR05-46, 2005.
- Andrej Bogdanov and Hoeteck Wee: More on non-commutative identity testing. In Proceedings of the 20th Annual Conference on Computational Complexity (CCC), 2005.
- Andrej Bogdanov and Hoeteck Wee: A stateful implementation of a random function supporting parity queries over hypercubes. In Proceedings of the 8th International Workshop on Randomization and Computation (RANDOM), 2004.
Sublinear-time algorithms
- Andrej Bogdanov and Lorenzo Taschin: Estimating the Euclidean distance to linearity. In Proceedings of the 16th Conference on Innovations in Theoretical Computer Science (ITCS), 2025.
- Azim Ospanov, Jingwei Zhang, Mohammad Jalali, Xuenan Cao, Andrej Bogdanov, and Farzan Farnia: Towards a scalable reference-free evaluation of generative models. In Proceedings of the 38th Annual Conference on Neural Information Processing Systems (NeurIPS), 2024.
- Andrej Bogdanov and Gautam Prakriya: Direct Sum and Partitionability Testing over General Groups. In Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP), 2021.
- Andrej Bogdanov and Baoxiang Wang: Learning and testing variable partitions. In Proceedings of the 11th Conference on Innovations in Theoretical Computer Science (ITCS), 2020.
- Andrej Bogdanov and Fan Li: A better tester for bipartiteness? arXiv:1011.0531v1 [cs.DS], 2010.
- Andrej Bogdanov and Luca Trevisan: Lower bounds for testing bipartiteness in dense graphs. In Proceedings of the 19th Annual Conference on Computational Complexity (CCC), 2004.
- Andrej Bogdanov, Kenji Obata, Luca Trevisan: A lower bound for testing 3-colorability in bounded degree graphs. In Proceedings of the 43rd Annual Symposium on Foundations of Computer Science (FOCS), 2002.
Other
- Xishi Wang, Amitalok Budulkey, Andrej Bogdanov, and Sidharth Jaggi: When are large codes possible for Arbitrarily Varying Channels? In Proceedings of the 2019 IEEE International Symposium on Information Theory (ISIT), 2019.
- Andrej Bogdanov, Elitza Maneva, Samantha Riesenfeld: Power-aware base station positioning for sensor networks. In Proceedings of INFOCOM 2004.
- Andrej Bogdanov, Stephen J. Garland, Nancy A. Lynch: Mechanical translation of I/O automaton specifications into first-order logic. In Proceedings of the 22nd IFIP WG 6.1 International Conference on Formal Techniques for Networked and Distributed Systems (FORTE), 2002.