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: W24, W23, F18, F17, F16, F15, F14
- 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
- Tsun Ming Cheung, M. Phil. 2021, now at McGill University
- 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
- 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 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. 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.
Publications
Cryptography
- 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, 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.
- 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 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
- Scott Aaronson, Andris Ambainis, Andrej Bogdanov, Krishnamoorthy Dinesh, Tsung Ming Cheung: On quantum versus classical query complexity. ECCC TR21-115, 2021.
- 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.