Revealing and Utilizing the Hidden Structure for Solving Hard Problems in AI

At the core of many areas of AI and reasoning are hard-to-solve computational problems, such as processing constraints, carrying out sound reasoning tasks, and verifying the correctness of procedures and protocols. This four-year research project at TU Wien tackled these challenges with impressive results. The project team demonstrated that many problems considered practically unsolvable contain a certain hidden structure. When this structure is found and cleverly exploited, the problem suddenly becomes solvable. A concrete example: When processing logical programs, computation time often grows exponentially with the number of variables, making larger inputs impossible to solve. The researchers developed a method that tames this explosion in computation time. The results speak for themselves: over a hundred scientific publications and several award-winning software systems. The DPDB system uses database technology for demanding computations, while another system broke records on finding the smallest circuits that compute a given Boolean function. The team also developed groundbreaking new theoretical concepts. One method cleverly decomposes complex formulas into smaller parts that are each easy to solve, like breaking a large puzzle into manageable pieces. Another breakthrough came with twin-width, where they developed the first practical computational methods to determine this invariant exactly. A nice side effect: more efficient algorithms mean less power consumption. When a problem is solved in minutes instead of days, the climate benefits too. All software from the project is freely available: open science in practice. The research continues with two new funded projects building on these results, and the international collaborations remain active. The future of AI becomes a bit more manageable with these advances.