Complexity and property testing
- 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 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 polynomial
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, and 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:
On the relation between worst-case and average-case
complexity for NP.
Ph. D. Thesis, University of California, Berkeley, 2005.
- Andrej Bogdanov, Elitza Maneva, and Samantha Riesenfeld:
Power-aware base station positioning
for sensor networks.
In Proceedings of INFOCOM 2004.
- Andrej Bogdanov, Stephen J. Garland, and Nancy A. Lynch:
Mechanical translation of I/O
automaton specifications into first-order logic.
FORTE 2002: 364-368, 2002.
- Andrej Bogdanov:
Formal verification of simulations
between I/O automata.
Master of Engineering Thesis, Massachusetts Institute of Technology,
2001.
Shorts