Krzysztof Krawiec



edit SideBar

This page contains the accompanying material to the currently reviewed paper Distance Metric Ensemble Learning and the Andrews-Curtis Conjecture, by Jerry Swan and me. Here is the abstract of this paper.

The Andrews-Curtis conjecture (ACC) was made in 1965, motivated by the search for a counterexample to the Poincare conjecture in 3 and 4 dimensions. The Andrews-Curtis conjecture is generally suspected to be false, but small potential counterexamples are not so numerous, so attention has turned to eliminating them. This can be treated as a combinatorial optimization problem: but success has 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. By this means, we eliminate 19 potential counterexamples, the status of which had been unknown for some years.

Keywords: Andrews-Curtis conjecture; computer search; machine learning.

This PDF document contains the complete list of counterexamples to ACC we eliminated in that study, including the actual evolved sequences of trivializing moves.

Powered by PmWiki