"Symmetry detection techniques in Constraint Satisfaction Problems and their Application in Databases"

12/09/05: 10:30 AM, webcast
11th Floor Large Conference Room
Host: Patrick Pantel, schedule

Abstract: In this talk, I will discuss symmetry detection in finite Constraint Satisfaction Problems (CSPs), focusing on a local and tractable form called neighborhood interchangeability. I will argue that computing neighborhood interchangeability dynamically during search reduces the cost of search while yielding multiple, robust solutions, and discuss how we generalize this process to non-binary CSPs. Finally, I will show the utility of this approach in databases with an algorithm for join-query computation that yields compact results.

About Berthe Choueiry: Berthe Y. Choueiry is Associate Professor of Computer Science and Engineering at the University of Nebraska-Lincoln (UNL), where she is the founder and director of the Constraint Systems Laboratory (consystlab.unl.edu). She holds an MS in Electrical Engineering (1986) and a PhD in Computer Science (1994) both from the Swiss Federal Institute of Technology in Lausanne (EPFL). Prior to joining UNL in 1999, she was a research associate at EPFL (1995-1996), a visiting scholar at Stanford University (1997-1999), and an invited scientist at the Electrotechnical Laboratory in Tsukuba, Japan (1998). She received a fellowship for young researchers (1986-1987) and a fellowship for advanced researchers (1997-1998) from the "Fonds National Suisse pour la Recherche Scientifique." She is the recipient of the "Fritz Kutter-Fonds der ETHZ" prize for the best doctoral dissertation in Computer Science in Switzerland (1995), and of a CAREER award from the National Science Foundation (2002).

Last updated: Mon Jun 19 17:44:06 2006