Andrej Bogdanov
Contact Information
work address:
Institute for Theoretical Computer Science
FIT Building 4-609-7, Tsinghua University
Beijing 100084, P. R. China
phone: +86 10 6279 5843 x1687
email: andrejb at tsinghua.edu.cn
home page: http://projectamericano.com/adib
Employment
Institute for Theoretical Computer Science, Tsinghua University, 2007 —
Postdoctoral researcher in Computer Science
Host: Prof. Andrew Chi-Chih Yao
DIMACS — Rutgers University, 2006 — 2007
Postdoctoral researcher in Computer Science
Host: Prof. Eric Allender
Institute for Advanced Study, Princeton, 2005 — 2006
Postdoctoral researcher in the School of Mathematics
Host: Prof. Avi Wigderson
Education
University of California, Berkeley, 2001 — 2005
Ph. D. in Computer Science
Advisor: Prof. Luca Trevisan
Dissertation: The relation between worst-case and average-case
complexity for NP
Massachusetts Insitute of Technology, 1996 — 2001
B. Sc. and M. Eng. in Computer Science and Engineering, 2001
B. Sc. in Mathematics, 2000
Advisors: Prof. Nancy Lynch and Prof. Stephen Garland
Dissertation: Formal Verification of Simulations Between I/O Automata
Teaching
Institute for Theoretical Computer Science, Tsinghua University, Fall 2007
Course instructor for 80240233, a graduate course in Computational Complexity.
Rutgers, the State University of New Jersey, Spring 2007
Course instructor for 16:198:538, a graduate course on the Complexity of Computation.
University of California, Berkeley, Spring 2005
Full-time Teaching Assistant for CS 170, an undergraduate course in Algorithms and Intractability.
University of California, Berkeley, Fall 2004
Full-time Teaching Assistant for CS 172, an undergraduate course in Computability and Complexity.
Massachusetts Institute of Technology, Fall 2000
Full-time Teaching Assistant for 6.042, an undergraduate course in Discrete Mathematics.
Awards
William A. Martin Memorial Thesis Award for Best M. Eng. Thesis in Computer Science, Honorable Mention, 2002
Publications
Publications in Computational Complexity and Property Testing
Andrej Bogdanov, Zeev Dvir, Elad Verbin, and Amir Yehudayoff: Pseudorandomness for small width branching programs. Manuscript, 2008.
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. To appear.
Andrej Bogdanov and Emanuele Viola: Pseudorandom bits for polynomials. In Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS), 2007. (Invited to SIAM Journal on Computing special issue on 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 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, 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.
Other Publications
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.
Selected Talks
Pseudorandom generators for polynomials. Presented at Mathematisches Forschunginstitut Oberwolfach, 2007; Princeton University, 2007; Tsinghua – Chinese University of Hong Kong joint seminar, Tsinghua University, 2007; the University of Chicago, 2008; the City University of Hong Kong, 2008; the University of Calgary, 2008; California Institute of Technology, 2008.
Average-case complexity for NP. Presented at the University of Toronto, 2007; the Toyota Technological Institute at Chicago, 2007.
Hardness amplification for errorless heuristics. Presented at Tel Aviv University, 2007; the Hebrew University of Jerusalem, 2007; the Weizmann Institute of Science, 2007; DIMACS, Rutgers University, 2007; the Institute for Advanced Study, 2007; Mathematisches Forschunginstitut Oberwolfach, 2007; Columbia University, 2007; the Chinese University of Hong Kong, 2008; University of California, San Diego, 2008.
The P versus NP question and cryptography. Presented at the Faculty of Natural Sciences, Ss. Cyril and Methodius University, Skopje, 2006.
More on non-commutative identity testing. Presented at the 20th Annual Conference on Computational Complexity (CCC), San Jose, California, 2005.
Pseudorandom generators for low-degree polynomials. Presented at the 37th Annual ACM Symposium on the Theory of Computing (STOC), Baltimore, Maryland, 2005; also at IBM Almaden Research Center, 2005; DIMACS, Rutgers University, 2005.
Lower bounds for testing bipartiteness in dense graphs. Presented at the 19th Annual Conference on Computational Complexity (CCC), Amherst, Massachusetts, 2004.
On average-case complexity and pseudo-randomness. Presented at University of California, Berkeley, 2004.
On worst-case to average-case reductions for NP problems.Presented at the 34th Annual Symposium on Foundations of Computer Science (FOCS), Cambridge, Massachusetts, 2003; also at Microsoft Research, Silicon Valley Center, 2005; the Institute for Advanced Study, 2006; New York University, 2006.
A lower bound for testing 3-colorability in bounded degree graphs. Presented at the 33rd Annual Symposium on Foundations of Computer Science (FOCS), Vancouver, Canada, 2002.
Mechanical translation of I/O automaton specifications into first-order logic. Presented at the 22nd IFIP WG 6.1 International Conference on Formal Techniques for Networked and Distributed Systems (FORTE), Houston, Texas, 2002.
Journal reviews
Journal of the ACM; SIAM Journal on Computing; Computational Complexity; Theory of Computing; Algorithmica