The Taub Faculty of Computer Science Events and Talks

e study the complexity of computational problems when multiple instances are given, and the instances are *correlated*. Such instances arise for example when they are derived from one "underlying source". Does this make the problem easier? We study this question in the domain of constraint satisfaction problems (CSPs). For example: given several CSP instances with solutions that are 99% the same, and for which the constraints are 95% the same, is it easier to find the solutions? We investigate both the case where we are told which bits differ between the different solutions, and the possibly more interesting case where the differences are unknown. For several variants of CSPs, we show that significant computational advantage can be gained when solving correlated instances. We believe that correlation is a natural phenomena in practice, and exploiting correlation has potential widespread algorithmic benefits beyond CSPs. Our work suggests exploring correlation as a new dimension for achieving algorithmic goals.

Joint work with Shafi Goldwasser and Huijia Rachel Lin.

Bio: Irit Dinur is a theoretical computer scientist at the Weizmann Institute. She received her PhD in 2001 from Tel-Aviv University. She has recently-ish returned from two years on sabbatical in Boston where the above work was done.