Back to search

FRINATEK-Fri prosj.st. mat.,naturv.,tek

Symbolic Algorithms: A Parameterized Approach

Alternative title: Symboliske algoritmer: En parameterisert tilnærming

Awarded: NOK 12.0 mill.

The vast majority of research in algorithms is devoted to the development of algorithms for computational problems whose instances are represented explicitly. For example, consider the problem of summing two vectors x and y. The most natural, and explicit, way of representing such input vectors is to specify each coordinate of each vector individually. The result of the summation is then the vector x+y obtained by summing each entry of x with its corresponding entry of y. Symbolic algorithms, on the other hand, work with computational problems whose instances are represented implicitly. Intuitively, an implicit representation of an input is a compressed version of the input. In the example given above, the goal would be to develop an algorithm that takes compressed representations C(x) and C(y) of the vectors x and y respectively and computes a representation C(x+y) of the result x+y. Ideally, such a symbolic algorithm would compute C(x+y) without the need to ever decompress C(x) and C(y). This may lead to a significant economy of computational resources. The goal of this project is to initiate a systematic study of symbolic algorithms using tools from the field of parameterized complexity theory. We envision that our results will shed new light on important challenges arising in the field of artificial intelligence.

The goal of this project is to initiate a systematic study of the field of symbolic algorithms using tools from parameterized complexity theory. By symbolic algorithms, we mean algorithms that are used to decide properties about objects that are implicitly represented using data structures such as automata, decision diagrams, circuits, linear programs, etc. The main distinction between such algorithms and algorithms that operate on explicitly given data structures is the fact that symbolic data structures may be used to represent combinatorial objects that can be much larger than the size of the input. For instance, certain graphs with 2^O(n) vertices can be represented by decision diagrams with O(n)-bits. In this project, we will develop a new set of tools for the symbolic representation of classes of combinatorial objects and for the development of algorithms deciding combinatorial properties about these classes. We envision applications to the fields of automated deduction, automated theorem proving, knowledge representation, and related subfields of artificial intelligence.

Activity:

FRINATEK-Fri prosj.st. mat.,naturv.,tek