dblp.uni-trier.dewww.uni-trier.de

Andrej Bogdanov

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeer - CSB - Google - MSN - Yahoo

2008
19EEAndrej Bogdanov, Elchanan Mossel, Salil P. Vadhan: The Complexity of Distinguishing Markov Random Fields. APPROX-RANDOM 2008: 331-342
2007
18EEAndrej Bogdanov, Emanuele Viola: Pseudorandom Bits for Polynomials. FOCS 2007: 41-51
17EEAndrej Bogdanov, Muli Safra: Hardness Amplification for Errorless Heuristics. FOCS 2007: 418-426
16EEAndrej Bogdanov, Emanuele Viola: Pseudorandom bits for polynomials. Electronic Colloquium on Computational Complexity (ECCC) 14(081): (2007)
15EEAndrej Bogdanov, Muli Safra: Hardness amplification for errorless heuristics. Electronic Colloquium on Computational Complexity (ECCC) 14(102): (2007)
2006
14EEAndrej Bogdanov, Luca Trevisan: Average-Case Complexity CoRR abs/cs/0606037: (2006)
13EEAndrej Bogdanov, Luca Trevisan: Average-Case Complexity. Electronic Colloquium on Computational Complexity (ECCC) 13(073): (2006)
12EEAndrej Bogdanov, Luca Trevisan: Average-Case Complexity. Foundations and Trends in Theoretical Computer Science 2(1): (2006)
11EEAndrej Bogdanov, Luca Trevisan: On Worst-Case to Average-Case Reductions for NP Problems. SIAM J. Comput. 36(4): 1119-1159 (2006)
2005
10EEAndrej Bogdanov, Hoeteck Wee: More on Noncommutative Polynomial Identity Testing. IEEE Conference on Computational Complexity 2005: 92-99
9EEAndrej Bogdanov: Pseudorandom generators for low degree polynomials. STOC 2005: 21-30
8EEAndrej Bogdanov, Luca Trevisan: On Worst-Case to Average-Case Reductions for NP Problems Electronic Colloquium on Computational Complexity (ECCC)(015): (2005)
2004
7EEAndrej Bogdanov, Hoeteck Wee: A Stateful Implementation of a Random Function Supporting Parity Queries over Hypercubes. APPROX-RANDOM 2004: 298-309
6EEAndrej Bogdanov, Luca Trevisan: Lower Bounds for Testing Bipartiteness in Dense Graphs. IEEE Conference on Computational Complexity 2004: 75-81
5EEAndrej Bogdanov, Elitza N. Maneva, Samantha Riesenfeld: Power-aware base station positioning for sensor networks. INFOCOM 2004
2003
4EEAndrej Bogdanov, Luca Trevisan: On Worst-Case to Average-Case Reductions for NP Problems. FOCS 2003: 308-317
2002
3EEAndrej Bogdanov, Kenji Obata, Luca Trevisan: A Lower Bound for Testing 3-Colorability in Bounded-Degree Graphs. FOCS 2002: 93-102
2EEAndrej Bogdanov, Stephen J. Garland, Nancy A. Lynch: Mechanical Translation of I/O Automaton Specifications into First-Order Logic. FORTE 2002: 364-368
1EEAndrej Bogdanov, Luca Trevisan: Lower Bounds for Testing Bipartiteness in Dense Graphs Electronic Colloquium on Computational Complexity (ECCC)(064): (2002)

Coauthor Index

1Stephen J. Garland [2]
2Nancy A. Lynch [2]
3Elitza N. Maneva [5]
4Elchanan Mossel [19]
5Kenji Obata [3]
6Samantha Riesenfeld [5]
7Muli Safra [15] [17]
8Luca Trevisan [1] [3] [4] [6] [8] [11] [12] [13] [14]
9Salil P. Vadhan [19]
10Emanuele Viola [16] [18]
11Hoeteck Wee [7] [10]

Colors in the list of coauthors

Copyright © Sun May 17 03:24:02 2009 by Michael Ley (ley@uni-trier.de)