Employment
The Chinese Unviersity of Hong Kong, 2008 –. Assistant professor
ITCS, Tsinghua University, 2007 – 2008. Postdoctoral researcher in Computer Science
DIMACS, Rutgers University, 2006 – 2007. Postdoctoral researcher in Computer Science
Institute for Advanced Study, Princeton, 2005 – 2006. Postdoctoral researcher in the School of Mathematics
Education
University of California, Berkeley. Ph. D. in Computer Science, 2005
Massachusetts Insitute of Technology, B. Sc. and M. Eng. in Computer Science and Engineering, 2001
Massachusetts Institute of Technology, B. Sc. in Mathematics, 2000
Teaching
CSC 5170: Theory of computational complexity, Spring 2010
CSC 3130: Formal languages and automata theory, Fall 2009
CSC 3130: Formal languages and automata theory, Fall 2008
80240233: Computational Complexity, ITCS, Tsinghua University, Fall 2007
CS 538: Complexity of Computation, Rutgers, the State University of New Jersey, Spring 2007
Publications
- Andrej Bogdanov, Kunal Talwar, and Andrew Wan: Hard instances for satisfiability and quasi-one-way functions. To appear in Proceedings of the First Symposium on Innovations in Computer Science (ICS), 2010.
- Andrej Bogdanov and Youming Qiao: On the security of Goldreich's one-way function. In Proceedings of the 13th International Workshop on Randomization and Computation (RANDOM), 2009.
- 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 Emanuele Viola: Pseudorandom bits for polynomials. In Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS), 2007.
- Andrej Bogdanov and Muli Safra: Hardness amplification for errorless heuristics. In Proceedings of the 38th 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. In SIAM Journal on Computing, vol. 36, no. 4, 2006. (Preliminary version in Proceedings of the 34th 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: Gap amplification fails below 1/2. Note on ECCC TR05-46, 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 33rd 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.
Awards
William A. Martin Memorial Thesis Award for Best M. Eng. Thesis in Computer Science, Massachusetts Institute of Technology, Honorable Mention, 2002
Events and Committees
CATS 2010 ☮ STOC 2009 ☮ MSRA Theory Workshop 2008 ☮ China Theory Week 2008
Links
The Institute for Theoretical Computer Science and Communications at the Chinese University of Hong Kong
Project Americano has some coffeeshop reviews from around the world I try to maintain
An attempt to explain where I come from