Ester Livshits

Research Associate at School of Informatics, University of Edinburgh

Hello, my name is Ester Livshits

I am a Postdoctoral Research Associate in the School of Informatics at the University of Edinburgh. Prior to this, I was a postdoctoral fellow at Technion, Israel.

I did my PhD under the supervision of Prof. Benny Kimelfeld in the Computer Science Faculty at Technion, Israel.

My research interests lie primarily in the area of database theory, particularly inconsistent data management and explanations in databases.

    Publications Journal Articles
  • Logical Methods in Computer Science (LMCS) The Shapley Value of Tuples in Query Answering
    Authors: Ester Livshits, Leopoldo Bertossi, Benny Kimelfeld, and Moshe Sebag
    View To appear
  • SIGMOD Record (Research Highlights) Query Games in Databases
    Authors: Ester Livshits, Leopoldo Bertossi, Benny Kimelfeld, and Moshe Sebag
    View Published : 2021
  • Journal of Computer and System Sciences (JCSS) Counting Subset Repairs with Functional Dependencies
    Authors: Ester Livshits, Benny Kimelfeld, and Jef Wijsen
    View Published : 2021
  • Proceedings of the VLDB Endowment (PVLDB) Approximate Denial Constraints
    Authors: Ester Livshits, Alireza Heidari, Ihab F. Ilyas, and Benny Kimelfeld
    View Published : 2020
  • Theoretical Computer Science Counting and Enumerating Preferred Database Repairs
    Authors: Benny Kimelfeld, Ester Livshits, and Liat Peterfreund
    View Published : 2020
  • ACM Transactions on Database Systems (TODS) Computing Optimal Repairs for Functional Dependencies
    Authors: Ester Livshits, Benny Kimelfeld, and Sudeepa Roy
    View Published : 2020
  • Conference Papers (Fully Reviewed)
  • ACM SIGMOD International Conference on Management of Data Properties of Inconsistency Measures for Databases
    Authors: Ester Livshits, Rina Kochirgan, Segev Tsur, Ihab Ilyas, Benny Kimelfeld, and Sudeepa Roy
    View To appear
  • 24th International Conference on Database Theory, ICDT The Shapley Value of Inconsistency Measures for Functional Dependencies
    Authors: Ester Livshits and Benny Kimelfeld
    View Published : 2021
  • 24th International Conference on Database Theory, ICDT Database Repairing with Soft Functional Dependencies
    Authors: Nofar Carmeli, Martin Grohe, Benny Kimelfeld, Ester Livshits, and Muhammad Tibi
    View Published : 2021
  • ACM Symposium on Principles of Database Systems, PODS The Impact of Negation on the Complexity of the Shapley Value in Conjunctive Queries
    Authors: Alon Reshef, Benny Kimelfeld, and Ester Livshits
    View Published : 2020
  • 23rd International Conference on Database Theory, ICDT The Shapley Value of Tuples in Query Answering
    Authors: Ester Livshits, Leopoldo Bertossi, Benny Kimelfeld, and Moshe Sebag
    View Published : 2020
  • ACM Symposium on Principles of Database Systems, PODS Computing Optimal Repairs for Functional Dependencies
    Authors: Ester Livshits, Benny Kimelfeld, and Sudeepa Roy
    View Published : 2018
  • ACM Symposium on Principles of Database Systems, PODS Counting and Enumerating (Preferred) Database Repairs
    Authors: Ester Livshits and Benny Kimelfeld
    View Published : 2017
  • 20th International Conference on Database Theory, ICDT Detecting Ambiguity in Prioritized Database Repairing
    Authors: Benny Kimelfeld, Ester Livshits, and Liat Peterfreund
    View Published : 2017
PhD Thesis

The Complexity of Database Inconsistency Measures.

Supervisor: Prof. Benny Kimelfeld.
Invited Talks
June 1, 2021 Database Tuples Play Cooperative Games
Data and Knowledge Seminar, University of Oxford, UK

We consider two situations where we wish to quantify the responsibility of individual database tuples to the outcome. The first is query answering, where we wish to provide an explanation as to why we obtained a specific answer. The second is database inconsistency, where the goal is to identify the most problematic tuples. Some tuples may contribute more than others to the outcome, which can be a bit in the case of a Boolean query, a tuple or a number for conjunctive and aggregate queries, respectively, or a number indicating how inconsistent the database is (i.e., an inconsistency measure). To quantify the contribution of tuples, we use the well-known Shapley value that was introduced in cooperative game theory in the 1950s and has found applications in a plethora of domains. We investigate the applicability of the Shapley value in the two settings, as well as the computational aspects of its calculation in terms of complexity, algorithms, and approximation.

Presentation
November 13, 2019 The Shapley Value of Database Tuples
EMERGING CHALLENGES IN DATABASES AND AI RESEARCH (DBAI), Santa Cruz, Chile

The Shapley value is a widely known numerical measure in cooperative game theory and in many applications of game theory for assessing the contribution of a player to a coalition game. It has been established already in the 1950s, and is theoretically justified by being the very single wealth-distribution measure that satisfies some natural axioms. While this value has been investigated in several areas, it received little attention in data management. In this talk, we will discuss the application of the Shapley value to quantifying the contribution of tuples to query results by defining corresponding coalition games.

Presentation
October 3, 2018 Algorithmic Aspects of Least-Effort Database Repairing
2018 CROSS Research Symposium, UC Santa Cruz, CA, USA

An inconsistent database is a database that violates a given set of constraints. A minimum repair of an inconsistent database is a consistent database obtained from it by a minimum number of cleaning operations (e.g. tuple deletions, value updates). The importance of computing a minimum repair arises in the challenge of data cleaning, where the goal is to eliminate errors and dirt from the database. In a fully automated cleaning system, a minimum repair is a good candidate, while in a cleaning system that involves the user, the cost of a minimum repair can serve as an educated estimate for the amount of effort needed to complete the cleaning process. This talk will cover complexity and algorithmic aspects of the problem of computing a minimum repair.

Presentation
Teaching
2014 – 2020 Network Security (TA)
Academic Activity
PC member PODS 2022
Reviewer The VLDB Journal 2021, TODS 2020, VLDB 2020, TOCS 2019, ICDT 2019, PODS 2018
Publicity chair ICDT 2022
Awards and Recognition
  • 2021

    The ACM SIGMOD Research Highlight Award.

  • 2019

    First place in the Technion’s Computer Science Department Research Day.

  • 2017 – 2019

    Technion Hiroshi Fujiwara cyber security research center graduate student scholarship.

  • Winter 2016 – 2017, 2017-2018, 2018-2019

    Computer Science Faculty Excellence Scholarship.

  • 2010 – 2014

    4 x Rector’s List of Excellent Students, 2 x Dean’s List of Excellent Students, Technion.

  • 2015 – 2016

    Irwin and Joan Jacobs Fellowship for excellence in graduate studies and research.

All rights reserved © Ester Livshits