Fall 2016

A Dichotomy Structure Theorem for the Resilience Problem

Tuesday, November 8th, 2016 11:00 am11:30 am

Add to Calendar

Resilience is the problem of removing the minimum number of tuples from the input tables to make a given Boolean query false. In this talk I will define the triad structure and show a dichotomy theorem for resilience when considering conjunctive queries without self-joins. I will also present preliminary complexity results for conjunctive queries with self-joins towards characterizing a dichotomy, which has been showing to be more intricate than the self-join free case.