Outputs (2)

On the approximation complexity hierarchy. (2011)
Presentation / Conference Contribution
Bordewich, M. (2010, September). On the approximation complexity hierarchy. Presented at 8th International Workshop on International Workshop on Approximation and Online Algorithms, WAOA 2010, Liverpool

This paper presents an extension of Ladner’s Theorem to the approximation complexity hierarchy. In 1975 Ladner proved that if P≠NP, then there exists an incomplete problem A which is neither in P nor NP-complete. Here we show that if RP≠NP, then ther... Read More about On the approximation complexity hierarchy..

Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width (2011)
Book Chapter
Bordewich, M., & Kang, R. (2011). Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width. In L. Aceto, M. Henzinger, & J. Sgall (Eds.), Automata, languages and programming (533-544). Springer Verlag. https://doi.org/10.1007/978-3-642-22006-7_45

Motivated by the ‘subgraphs world’ view of the ferromagnetic Ising model, we develop a general approach to studying mixing times of Glauber dynamics based on subset expansion expressions for a class of graph polynomials. With a canonical paths argume... Read More about Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width.