**CSP Solver Projects
**
Several exciting research projects are available suitable for
undergraduate and graduate students.

Prerequisites:
If you would like to do one of those projects, please send mail to Karl Lieberherr.

An example of an earlier project on CSP solvers which resulted in a LNCS publication:

@ARTICLE{lieber-vavasis:dortmund,
AUTHOR = "Karl J. Lieberherr and
S. Vavasis",
TITLE = "Analysis of polynomial approximation algorithms for
constraint expressions",
JOURNAL = "Lecture Notes in Computer Science",
YEAR = 1983,
PAGES = "187-197",
VOLUME = 145,
NOTE="6th Gl-Conference Dortmund, January 5-7"
}

Steve Vavasis was back then an undergraduate at Princeton University and he
is now a professor at Cornell.
Abbreviations used:
CSP = Constraint Satisfaction Problem
SAT = Satisfiability

**Projects related to publications
**
http://www.ccs.neu.edu/research/demeter/papers/publications.html
contains many ideas for projects. Take a look at the most
recent papers from our research group and talk to me to identify
a suitable project.
(We are just writing the first paper in this space)

**Compute P-optimal thresholds. Solve the MaxCSP game for
relations of rank 3.
**
Consider a set of relations Gamma and the CSP problem CSP(Gamma).
Find the optimal solution for the MaxCSP game:
Player One selects a CSP(Gamma) instance with less than one million variables
and gives it to player Two.
Two computes the maximal assignment and wins the fraction of the satisfied
constraints in million of dollars. (if the fraction is 1/2
it is 1/2 million dollars). What is the optimal strategy for player One?
This game is related to computing the P-optimal threshold t[Gamma].
We focus on computing the P-optimal thresholds for sets of relations
Gamma that are of at most rank 3.
Write a program that takes as input any subset Gamma
of the 256 relations of rank 3. The output is a program that computes
t[Gamma} to any desired accuracy.
First consider a Gamma that contains exactly one relation.
For example, t[{OneInThree}] = 4/9.
Then consider pairs of relations and then triples. Etc.

** Combining Superresolution and Optimally Biased Coins
**
Develop an implementation based on superresolution and algorithm MAXMEAN
that beats other CSP and SAT algorithms on several benchmarks.
In other words, we want to translate the theoretical advantages
(P-optimality, efficient relation manipulation, learning) into
a practical advantage.