Abstract

Instances of computational problems often do not exist in isolation. Rather, multiple and correlated instances of the same problem arise naturally in the real world. For example, this has been demonstrated to be the case in cryptography for public-keys generated in practice and will arise in the context of error correction when a hard drive may contain encodings of multiple files within small edit-distance from each other.

We ask how one can gain computational advantage from instance correlations when they exist.  We will be interested in settings where significant computational gain can be made in solving a single primary instance by having access to additional auxiliary instances which are correlated to the primary instance via the solution space.

In this work, we focus on studying this question for constraint satisfaction problems (CSPs) with access to multiple instances with correlated solutions.
We consider a variety of naturally occurring worst case and average case CSPs, and show how availability of a small number of auxiliary instances generated through a natural generating process that produces instances with correlated solutions, radically changes the complexity of solving the primary instance, from intractable to expected polynomial time. Essentially, the availability of a logarithmic number of auxiliary instances enables a close polynomial time approximation of the primary solution, and when in addition the "difference vector" between the primary and the auxiliary solution is known, the primary solution can be exactly found. Furthermore, knowing even a single auxiliary instance already enables finding the exact primary solution for a large class of CSPs.

We hope this work is the first step in a wider study of how to exploit correlations in available inputs.

Joint work with Irit Dinur and Rachel Lin. 

Video Recording