IBM Israel Research Seminars

I will describe a scheme called SampleSearch-SIR for generating randomly solutions from a uniform distribution over the solutions of a Boolean satisfiability formula or a constraint expression. The scheme builds upon a new sampling scheme, SampleSearch, which uses constraint-based search to overcome the rejection problem of various importance sampling methods. It also uses the principle of Sampling Importance Resampling (SIR) to reduce the approximation error. Empirical evaluation demonstrating the power of this scheme will be given.

About the Speaker
Rina Dechter is a professor of Computer Science at the University of California, Irvine. She received her PhD in Computer Science at UCLA in 1985, a MS degree in Applied Mathematics from the Weizmann Institute and a B.S in Mathematics and Statistics from the Hebrew University, Jerusalem. Her research centers on computational aspects of automated reasoning and knowledge representation including search, constraint processing and probabilistic reasoning. Professor Dechter is an author of the book "Constraint Processing" published by Morgan Kaufmann, 2003, and has authored over 100 research papers, and has served on the the editorial boards of: Artificial Intelligence, the Constraint Journal, Journal of Artificial Intelligence Research and the Encyclopedia of AI. She was awarded the Presidential Young investigator award in 1991 and is a fellow of the American association of Artificial Intelligence. She was a Radcliffe fellow 2005-2006 and the 2007 ACP (Association of Constraint Programmong) research excellence award.