I am an assistant 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 MIT and my Ph.D. at UC Berkeley.
My research is mostly 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. If you can't find me doing this chances are I am drinking coffee or somewhere else.
I run the theory lunches at CUHK and ITCSC activities like the annual Winter School and the somewhat irregular seminar (with Chandra Nair). If you are interested in giving a talk or participating, please send me an email.
Teaching
- Topics in the theory of computing (CSCI 5060): S12
- Formal languages and automata theory (CSCI 3130): F11, F10, F09, F08
- Cryptography (CSCI 5440): S11
- Computational complexity: S10 (CSCI 5170, CUHK), F07 (Tsinghua), S07 (Rutgers)
Publications
- Andrej Bogdanov and Youming Qiao: On the security of Goldreich's one-way function. In Computational Complexity, vol. 21, no. 1, 2012. (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. To appear 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. (Preliminary version in Proceedings of the Eighth Theory of Cryptography Conference (TCC), 2011.)
- 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, Akinori Kawachi, and Hidetoki Tanaka: Hard Functions for Low-degree Polynomials over Prime Fields. In Proceedings of the 36th International Symposium on Mathematical Foundations of Computer Science, 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. (Preliminary version in Proceedings of the 48th Annual Symposium on Foundations of Computer Science (FOCS), 2007.)
- 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. 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. (Preliminary version in Proceedings of the 44th Annual Symposium on Foundations of Computer Science (FOCS), 2003.)
- 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: Pseudorandom generators for low-degree polynomials. In Proceedings of the 37th Annual ACM Symposium on the Theory of Computing (STOC), 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.
- 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, Elitza Maneva, Samantha Riesenfeld: Power-aware base station positioning for sensor networks. In Proceedings of INFOCOM 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.
- 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.
Manuscripts
- Andrej Bogdanov and Fan Li: A better tester for bipartiteness? arXiv:1011.0531v1 [cs.DS], 2010.
- Andrej Bogdanov, Zeev Dvir, Elad Verbin, and Amir Yehudayoff: Pseudorandomness for width 2 branching programs. ECCC TR09-070, 2009.
- Andrej Bogdanov: Gap amplification fails below ½. Note on ECCC TR05-46, 2005.
Award
William A. Martin Memorial Thesis Award for Best M. Eng. Thesis in Computer Science, Massachusetts Institute of Technology, Honorable Mention, 2002
Events and Committees
RANDOM 2012 ☮ FAW-AAIM 2012 ☮ CATS 2010 ☮ STOC 2009 ☮ China Theory Week 2008