Andrej Bogdanov

Institute for Theoretical Computer Science
FIT Building 4-609-7, Tsinghua University
Beijing 100084, P. R. China

phone: 86-10-62795843 x1687

email: andrejb@tsinghua.edu.cn

home page: http://projectamericano.com/adib/

Employment

ITCS, Tsinghua University, 2007 —. 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

Computational Complexity, ITCS, Tsinghua University, Fall 2007

CS 538: Complexity of Computation, Rutgers, the State University of New Jersey, Spring 2007

Awards

William A. Martin Memorial Thesis Award for Best M. Eng. Thesis in Computer Science, Honorable Mention, 2002

Publications

  1. Andrej Bogdanov and Emanuele Viola: Pseudorandom bits for polynomials via the Gowers norms. To appear in Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS), 2007.
  2. Andrej Bogdanov and Muli Safra: Hardness amplification for errorless heuristics. To appear in Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS), 2007.
  3. 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.
  4. 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.)
  5. Andrej Bogdanov and Hoeteck Wee: More on non-commutative identity testing. In Proceedings of the 20th Annual Conference on Computational Complexity (CCC), 2005.
  6. Andrej Bogdanov: Pseudorandom generators for low-degree polynomials. In Proceedings of the 37th Annual ACM Symposium on the Theory of Computing (STOC), 2005.
  7. 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.
  8. 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.
  9. Andrej Bogdanov, Elitza Maneva, Samantha Riesenfeld: Power-aware base station positioning for sensor networks. In Proceedings of INFOCOM 2004.
  10. 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.
  11. 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.


Back