Testable Algorithms for Self-Avoiding Walks
Title | Testable Algorithms for Self-Avoiding Walks |
Publication Type | Technical Report |
Year of Publication | 1993 |
Authors | Randall, D., & Sinclair A. |
Other Numbers | 843 |
Abstract | We present a polynomial time Monte Carlo algorithm for almost uniformly generating and approximately counting self-avoiding walks in rectangular lattices. These are classical problems that arise, for example, in the study of long polymer chains. While there are a number of Monte Carlo algorithms used to solve these problems in practice, these are heuristic and their correctness relies on unproven conjectures. In contrast, our algorithm relies on a single, widely-believed conjecture that is simpler than preceding assumptions, and, more importantly, is one which the algorithm itself can test. Thus our algorithm is reliable, in the sense that it either outputs answers that are guaranteed, with high probability, to be correct, or finds a counterexample to the conjecture. |
URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1993/tr-93-055.pdf |
Bibliographic Notes | ICSI Technical Report TR-93-055 |
Abbreviated Authors | D. Randall and A. Sinclair |
ICSI Publication Type | Technical Report |