|Links' Seminars and Public Events|
Fri 10th Nov
Momar Sakho: "Complexity of Certain Query Answering on Hyperstreams"
A hyperstream is a sequence of streams with references to others. We study the complexity of computing certain answers for queries defined by automata and evaluated on hyperstreams of words. We show that the problem is PSPACE-complete for deterministic query automata, but that it can be solved in PTime for linear hyperstreams even with factorization.
Fri 3rd Nov
Joanna Ochremiak, Paris 7: "Proof complexity of constraint satisfaction problems"
Many natural computational problems, such as satisfiability and
systems of equations, can be expressed in a unified way as constraint
satisfaction problems (CSPs). In this talk I will show that the usual
reductions preserving the complexity of the constraint satisfaction
problem preserve also its proof complexity. As an application, I will
present two gap theorems, which say that CSPs that admit small size
refutations in some classical proof systems are exactly the constraint
satisfaction problems which can be solved by Datalog.
This is joint work with Albert Atserias.