By the same authors

Distance Metric Ensemble Learning and the Andrews-Curtis Conjecture

Research output: Other contribution



Publication details

DatePublished - 2016
Number of pages11
Original languageEnglish


Motivated by the search for a counterexample to the Poincaré conjecture in three and four dimensions, the Andrews-Curtis conjecture was proposed in 1965. It is now generally suspected that the Andrews-Curtis conjecture is false, but small potential counterexamples are not so numerous, and previous work has attempted to eliminate some via combinatorial search. Progress has however been limited, with the most successful approach (breadth-first-search using secondary storage) being neither scalable nor heuristically-informed. A previous empirical analysis of problem structure examined several heuristic measures of search progress and determined that none of them provided any useful guidance for search. In this article, we induce new quality measures directly from the problem structure and combine them to produce a more effective search driver via ensemble machine learning. By this means, we eliminate 19 potential counterexamples, the status of which had been unknown for some years.

Discover related content

Find related publications, people, projects, datasets and more using interactive charts.

View graph of relations