Loading Events

Computer Science Colloquium - "On the Complexity of the Resilience Problem"

Fri, March 1st, 2019
2:30 pm
- 4:00 pm

  • This event has passed.

Friday, March 1st @ 2:35pm in Wege Auditorium (TCL 123)

“On the Complexity of the Resilience Problem”

Various problems in database research, such as causality, explanations, and deletion propagation, examine how interventions in the input of a query impact the query’s output. An intervention constitutes a change (update, addition, or deletion) to the input tuples. In this talk I will present complexity results for the Resilience problem, which is the problem of finding the minimum number of tuple deletions from the database in order to change the result of a query. I will define the problem and present some computational complexity results for conjunctive queries with and without self-joins.

Cibele Freire is the Norma Wilentz Hess Fellow in Computer Science at Wellesley College. Her main research interest lies in database theory and complexity. Her work has focused on the study of the Resilience problem and the related problem of deletion propagation and causality in databases. She received her Ph.D. in Computer Science from UMass Amherst, and her M.S. and B.S in Computer Science from Federal University of Ceara, Brazil.

Event/Announcement Navigation

Related Events