19 citations · 26 across the 5 of their papers we have counts for
Showing 2010Show all
2 papers · 1 filter
cs.DS2010★ 1 cited
A better tester for bipartiteness?
Andrej Bogdanov, Fan Li
Alon and Krivelevich (SIAM J. Discrete Math. 15(2): 211-227 (2002)) show that if a graph is ε-far from bipartite, then the subgraph induced by a random subset of O(1/ε) vertices is…
cs.DS2010★ 5 cited
The Computational Complexity of Estimating Convergence Time
Nayantara Bhatnagar, Andrej Bogdanov, Elchanan Mossel
An important problem in the implementation of Markov Chain Monte Carlo algorithms is to determine the convergence time, or the number of iterations before the chain is close to sta…