I am a professor at the Chinese University of Hong Kong, which I joined in 2008. Previously I was a postdoc at ITCS at Tsinghua University, DIMACS at Rutgers University, and the Institute for Advanced Study in Princeton. I got my B.Sc. and M.Eng. degrees from the Massachussetts Institute of Technology and my Ph.D. at 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
- Probability (U): F22, F20, S20, S19, S14, S13
- Statistics (U): S22, S21
- Cryptography (G): F20, S18, F12, S11
- Computational complexity (G): F19, S16, S10, F07, S07
- Discrete mathematics (U): F18, F17, F16, F15, F14
- Data privacy (G): S15
- Codes, Boolean functions, and expanders (G): F13, S12
- Formal languages and automata theory (U): F11, F10, F09, F08
Graduate students
- Yanbo Chen, current Ph.D. student
- King On Yung, 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 Harvard University
- Chiwang Chow, M. Phil. 2013, now at Amazon
- Fan Li, M. Phil. 2013
Postdoctoral advisees
- Krishnamoorthy Dinesh, 2019 – 2021
- Gautam Prakriya, 2019 – 2022
My current research is concerned with the complexity-theoretic foundations of cryptography, parallel implementations of cryptographic primitives, randomness and pseudo-randomness in computation and communication, 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 EUROCRYPT 2023, CCC 2023, and ASIACRYPT 2022. I am an associate editor of the ACM Transactions on Computation Theory.
I was previously involved in 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, Miguel Cueto Noval, Charlotte Hoffmann, and Alon Rosen. Public-key encryption from Continuous Learning with Errors. To appear at TCC 2022.
- Masayuki Abe, Miguel Ambrona, Andrej Bogdanov, Miyako Okhubo, and Alon Rosen: Acyclicity programming for sigma-protocols. To appear 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, 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.
Research grants
- Cryptographic reductions and quantum adversaries (CUHK14207721), funded by HK Research Grants Council General Research Fund, Jan 2022 – Dec 2024. Principal investigator.
- Pseudorandomness and property testing for real computation (CUHK14209920), funded by HK Research Grants Council General Research Fund, Jan 2021 – Dec 2023. Principal investigator.
- Extractors, proofs of sequentiality, and randomness on blockchains (CUHK14209419), funded by HK Research Grants Council General Research Fund, Jan 2020 – Dec 2022. Principal investigator.
- General Omniscient Arbitrarily Varying Channels (CUHK14301519), funded by Hong Kong Research Grants Council, 2019 – 2022. Co-investigator (principal investigator Prof. Sidharth Jaggi).
- Approximate degree of low-complexity functions (CUHK14207618), funded by HK Research Grant Council General Research Fund, Jan 2019 – Dec 2021. Principal investigator.
- Random local functions and pseudorandom functions (CUHK14209417), funded by HK Research Grant Council General Research Fund, Jan 2018 – Dec 2020. Principal investigator.
- Hardness versus randomness for noisy linear equations (CUHK 14238716), funded by HK Research Grant Council General Research Fund, Jan 2017 – Dec 2018. Principal investigator.
- Pseudorandom functions, secret sharing, encryption, and authentication: Complexity and constructions (CUHK14208215), funded by Hong Kong Research Grants Council, Jan 2016 – Dec 2018. Principal investigator.
- Complexity-theoretic foundations of homomorphic encryption (CUHK410113), funded by Hong Kong Research Grants Council, Jan 2014 – Dec 2016. Principal investigator.
- Pseudorandom bits: New tools against old adversaries (CUHK410112), funded by Hong Kong Research Grants Council, Jan 2013 – Dec 2015. Principal investigator.
- Random, semi-random, stable, pseudorandom instances: Hardness for heuristics (CUHK410111), funded by Hong Kong Research Grants Council, Jan 2012 – Dec 2014. Principal investigator.
- New constructions of pseudorandom generators (CUHK410309), funded by Hong Kong Research Grants Council, Jan 2010 – Dec 2012. Principal investigator.
- Fast and Sound Cryptography, funded by the European Research Council, 2012 – 2017. Project member (principal investigator Prof. Alon Rosen).
- A study of some key problems in the theory of secure computation, funded by the National Basic Research Program of China (973 program), 2007 – 2012. Key member (principal investigator Prof. Andrew Chi-Chih Yao).