13th International Conference on Artificial Intelligence and Symbolic Computation


Speaker: James Davenport (University of Bath, UK)

Title: Methodologies of Symbolic Computation


The methodologies of computer algebra are about making algebra (in the broad sense) algorithmic, and efficient as well. There are ingenious algorithms, even in the obvious settings, and also mechanisms where problems are translated into other (generally smaller) settings, solved there, and translated back. Much of the efficiency of modern systems comes from these tramslations, which we outline. One of the major challenges is sparsity, and the complexity of algorithms in the sparse setting is often unknown, as many problems are NP-hard, or much worse.

In view of this, it is argued that traditional complexity-theoretic method of measuring progress has its limits, and computer algebra should look to the work of the SAT community, with its large families of benchmarks and serious contests, for lessons.