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 the Massachussetts Institute of Technology and my Ph.D. at UC Berkeley.
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.
I run the theory lunches at CUHK and ITCSC activities like the annual Winter School for computer science undergraduates in Asia and the somewhat irregular seminar (with Chandra Nair). If you are interested in giving a talk or participating, please send me an email.
Looking to do graduate work in theory of computing? Talk to my graduate students Siyao, Chin, Chiwang, and Fan to find out what life in the trenches is really like. If you are still interested do apply to CUHK CSE.
Here are some undergraduate (U) and graduate (G) computer science courses I have taught at CUHK, Tsinghua, and Rutgers and some I plan to teach in the future. Feel free to browse the lecture notes and other materials below. I have removed links to some old solution sets (don't want to make it too easy for the students) so do get in touch if you need help.
In 2012 I received an award for excellence in teaching from my department.
Courses
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 currently serving on the program committee of TAMC 2013. I have previously been a PC member for RANDOM 2012, FAW-AAIM 2012, CATS 2010, STOC 2009, China Theory Week 2008, and some smaller workshops.
Publications
Cryptography
- Andrej Bogdanov and Chin Ho Lee: Limits of provable security for homomorphic encryption. ECCC TR12-156, 2012.
- Andrej Bogdanov and Chin Ho Lee: On the depth complexity of homomorphic encryption schemes. ECCC TR12-157, 2012.
- 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 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, 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, Akinori Kawachi, and Hidetoki Tanaka: Hard Functions for Low-degree Polynomials over Prime Fields. To appear in Transactions on Computation Theory, 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. 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 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 works
- 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
- Pseudorandom bits: New tools against old adversaries, funded by Hong Kong Research Grants Council, Jan 2013 – Dec 2015. Principal investigator.
- Random, semi-random, stable, pseudorandom instances: Hardness for heuristics, funded by Hong Kong Research Grants Council, Jan 2012 – Dec 2014. Principal investigator.
- New constructions of pseudorandom generators, 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.
- 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.
I live in Hong Kong, where I work as an assistant professor at the Computer Science and Engineering department at the Chinese University of Hong Kong. I come from Skopje, Macedonia (马其顿) in the former Yugoslavia. It is a small country in the Balkans. I have also lived in places like Oran, Cambridge, Berkeley, Princeton, New York, and Beijing.
I try to maintain Project Americano where I have little reviews about some nice places to have coffee. I am always on the lookout for new suggestions!
