Index of /home/lieber/p-optimal

[ICO]NameLast modifiedSizeDescription
[PARENTDIR]Parent Directory   -  
[ ]karl-algo-extremal.pdf 2006-09-05 19:28 5.2M 
[ ]JACM1981.pdf 2003-04-07 15:08 658K 
[ ]p-opt.ps 1998-02-04 09:39 122K 
[ ]p-opt.ppt 1998-02-04 09:39 117K 
[TXT]hastad-connection.html 2003-04-21 17:23 6.6K 
[TXT]max-mean.html 2006-10-02 16:29 6.4K 
[ ]related-Rajmohan 1998-03-19 10:40 4.5K 
[TXT]to-microsoft 1998-02-19 08:30 2.7K 
[ ]mail-message 2003-04-18 21:08 2.2K 
[TXT]latest-paper.html 2006-08-30 14:57 1.6K 
[TXT]multi-party 2008-04-28 16:59 1.6K 
[TXT]proof 2003-04-11 18:28 631  
[TXT]binomial-distributio..>2006-10-05 10:01 571  
[DIR]poster/ 2006-11-01 10:13 -  
[DIR]partial-sat-II/ 2012-09-05 12:05 -  
[DIR]ernst/ 2012-06-02 14:16 -  
[DIR]applications/ 2006-10-26 22:59 -  
Karl Lieberherr's and Ernst Specker's Work on Partial Satisfaction

P-Optimal Algorithms / Local versus Global Satisfaction

To practice experiential learning and derive the theory yourself, play the Specker Challenge Game also called the Scientific Community Game (SCG) or the predecessor game: Evergreen Game or Evergreen Game for Life Scientists.

Microsoft Research picks up a theme on which I worked in the late seventies and early eighties: Transition points for NP-complete problems: points where easy problems suddenly become hard to solve, or vice versa. (see IEEE Computer, January 1998, page 58.) There are two kinds of transition points: phase transition points, based on parameter-controlled randomly generated instances, and dichotomy transition points, based on a continuous parameter that has a transition point where the complexity switches from polynomial to NP-complete. Our work is in the space of dichotomy transition points. If you are interested in phase transition points, according to Berthe Choueiry, work on the phase transition in CSP has seen a big boom after a 1991 paper by Cheeseman, Kanefsky and Taylor.

The theory of P-optimal algorithms is about finding transition points for a large family of constraint-based decision problems (generalized satisfiability problems where any set of finite relations may be used to express the constraints and where all variables have the same domain). The transition points are of the nature: We have a set of instances I(f) for f a real number ranging between 0 and 1. Evergreen Game or Evergreen Game for Life Scientists.

Microsoft Research picks up a theme on which I worked in the late seventies and early eighties: Transition points for NP-complete problems: points where easy problems suddenly become hard to solve, or vice versa. (see IEEE Computer, January 1998, page 58.) There are two kinds of transition points: phase transition points, based on parameter-controlled randomly generated instances, and dichotomy transition points, based on a continuous parameter that has a transition point where the complexity switches from polynomial to NP-complete. Our work is in the space of dichotomy transition points. If you are interested in phase transition points, according to Berthe Choueiry, work on the phase transition in CSP has seen a big boom after a 1991 paper by Cheeseman, Kanefsky and Taylor.

The theory of P-optimal algorithms is about finding transition points for a large family of constraint-based decision problems (generalized satisfiability problems where any set of finite relations may be used to express the constraints and where all variables have the same domain). The transition points are of the nature: We have a set of instances I(f) for f a real number ranging between 0 and 1. For instances I(f) the problem is easy if f < T (T a transition point) and for instances I(f) the problem is NP-complete if f >= T+e for e arbitrarily small.

Ernst Specker and I developed this theory in the late 1970's and early 1980's at ETH Zurich and it was completed at Princeton University. Our initial paper was the Golden Ratio result for the Satisfiability Problem which was published at FOCS and in the Journal of the ACM. Lieberherr/Specker JACM 1981 

@ARTICLE{lieber-specker:partial-1,
TITLE = "Complexity of Partial Satisfaction",
AUTHOR = "Karl J. Lieberherr and
Ernst Specker",
JOURNAL = "Journal of the Association for Computing Machinery",
YEAR = 1981,
PAGES = "411-421",
VOLUME = 28,
NUMBER = 2
}
This paper used basic number theory (Bertrand's theorem) and the theory of multiply transitive permutation groups to solve the problem. A later paper in the Journal of Algorithms simplified the proof and generalized the approach to the generalized satisfiability problem proposing an algorithm called MAXMEAN. See reference lieber:algorithms. MAXMEAN is summarized in: http://www.ccs.neu.edu/home/lieber/p-optimal/partial-sat-II/ and an elegant introduction based on a lecture by David Williamson is provided for easier access to the key ideas.

MAXMEAN uses the Method of Conditional Expectations by Erdoes and Selfridge to make a probabilistic algorithm deterministic. MAXMEAN is actually a family of algorithms, one algorithm for each fixed family of relations. MAXMEAN has the desirable property that it is uniform and does not require specialized techniques for different sets of relations. An empirical comparison of MAXMEAN with other MAXSAT algorithms is in preparation.

Follow-on papers were with Steve Vavasis and Ming-Deh Huang. The paper with Ming-Deh Huang (Theoretical Computer Science) considered generalized satisfiability problems with forbidden substructures and how the forbidden substructures influence the transition point.

It is interesting that Microsoft Research does more work in this area. They have a Fields Medal winner (the highest prize in mathematics) working on transition points for NP-complete problems.

Viewgraphs on P-optimal algorithms are available: PowerPoint version, PostScript version. Note that a random assignment will only satisfy 3/8 of the conditions. Therefore, the P-optimal threshold must be equal or greater than 3/8. The viewgraphs show that it is 4/9 for the "One-in-three satisfiability" problem. Poster explaining P-optimality with biased coins.

Latest unpublished paper by Ernst Specker and Karl Lieberherr on Complexity of Partial Satisfaction II. Work done at Princeton University, GTE Laboratories and ETH Zurich. Completed in 1985. See also Reviews etc. for latest unpublished paper by Ernst Specker and Karl Lieberherr Norbert Hungerbuehler from ETH rediscovered the paper and it is now published in the "Elemente der Mathematik" in a special issue on "Remembering Ernst Specker" (Erwin Engeler, Norbert Hungerbuehler and Johann Makowsky, Coordinating Editors). 

@ARTICLE{lieber-specker:partial-2,
TITLE = "{Complexity of Partial Satisfaction II}",
AUTHOR = "Karl J. Lieberherr and Ernst Specker",
JOURNAL = "Elemente der Mathematik",
YEAR = 2012,
PAGES = "134-150",
VOLUME = 67,
NUMBER = 3,
doi = {10.4171/EM/202}
}

Hastad's Work

We posed an open problem in Partial Satisfaction II: (page 2 bottom) which has been partially answered in recent work on this topic published in STOC 1997 and a follow-on seminal JACM paper: J. Hastad, Some optimal inapproximability results, Journal of ACM, Vol. 48, 2001, pp 798--859. Johan Hastad: Some optimal inapproximability results. Hastad's seminal paper generalizes some of the P-optimal results. Connections to Johan Hastad's work shows how Hastad's work compares to our older work.

Emo Welzl's Lecture Notes on Satisfiability

Emo Welzl at ETH Zurich has a thorough treatment of Satisfiability: Boolean Satisfiability: Combinatorics and Algorithms. See pages 35 - 41 for an explanation and discussion of the Golden Ratio result.

See also his Satisfiability Updates for the latest developments.

References.

Some key papers are online for personal use. 

@ARTICLE{lieber:algorithms,
AUTHOR = "Karl J. Lieberherr",
TITLE = "Algorithmic extremal problems
in combinatorial optimization",
JOURNAL = "Journal of Algorithms",
YEAR = 1982,
PAGES = "225-244",
VOLUME = 3
}

http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WH3-4D7JMY4-2X&_coverDate=09%2F30%2F1982&_alid=439770433&_rdoc=1&_fmt=&_orig=search&_qd=1&_cdi=6839&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=35ebd083ebc05f16cc549738dbdd4987

An alternate title for the above paper would be:
On the approximation of generalized maximum satisfiability

Later work on this topic:
M. Yannakakis,
On the approximation of maximum satisfiability, J. Algorithms 17 (1994),
475-502.


@ARTICLE{lieber-huang:tcs-85,
AUTHOR = "M.A. Huang and Karl J. Lieberherr ",
TITLE = "Implications of forbidden structures for
extremal algorithmic problems",
JOURNAL = tcs,
VOLUME = 40,
YEAR = 1985,
PAGES = "195-210"
}

@ARTICLE{lieber-vavasis:dortmund,
AUTHOR = "Karl J. Lieberherr and
S. Vavasis",
TITLE = "Analysis of polynomial approximation algorithms for
constraint expressions",
JOURNAL = lncs,
YEAR = 1983,
PAGES = "187-197",
VOLUME = 145
}

Luca Trevisan's work

Luca Trevisan from Berkeley solved the k-satisfiability problem for CNF formulas. The answer is 3/4. 
@article{984912,
author = {Luca Trevisan},
title = {On Local Versus Global Satisfiability},
journal = {SIAM J. Discret. Math.},
volume = {17},
number = {4}, 
year = {2004},
issn = {0895-4801},
pages = {541--547},
doi = {http://dx.doi.org/10.1137/S0895480197326528},
publisher = {Society for Industrial and Applied Mathematics},
address = {Philadelphia, PA, USA},
}           

See also the earlier versions:
http://academic.research.microsoft.com/Paper/155910.aspx
http://citeseer.ist.psu.edu/cache/papers/cs/1219/http:zSzzSzwww.cs.columbia.eduzSz~lucazSzpubszSzlocal.pdf/trevisan97local.pdf

Further Closely Related Work

2005 Locally Consistent Constraint Satisfaction Problems by Manuel Bodirsky and Daniel Kral. 
@article{Dvorak:2005:LCC:1132633.1132637,
author = {Dvo\v{r}\'{a}k, Zden\v{e}k and Kr\'{a}l, Daniel and Pangr\'{a}c, Ond\v{r}ej},
title = {Locally consistent constraint satisfaction problems},
journal = {Theor. Comput. Sci.},
issue_date = {8 December 2005},
volume = {348},
number = {2},
month = dec,
year = {2005},
issn = {0304-3975},
pages = {187--206},
numpages = {20},
url = {http://dx.doi.org/10.1016/j.tcs.2005.09.012},
doi = {10.1016/j.tcs.2005.09.012},
acmid = {1132637},
publisher = {Elsevier Science Publishers Ltd.},
address = {Essex, UK},
keywords = {2-SAT, CNF formulas, boolean predicates, constraint satisfaction problems},
}
2012 improvement of the Lieberherr-Specker bound (in Algorithmica) with applications to fixed-parameter-tractable (FPT) algorithms.

See: http://rd.springer.com/article/10.1007/s00453-011-9550-1 

@article{,
year={2012},
issn={0178-4617},
journal={Algorithmica},
volume={64},
issue={1},
doi={10.1007/s00453-011-9550-1},
title={A New Lower Bound on the Maximum Number of Satisfied Clauses in Max-SAT and Its Algorithmic Applications},
url={http://dx.doi.org/10.1007/s00453-011-9550-1},
publisher={Springer-Verlag},
keywords={MaxSat; Lower bound; 2-Satisfiable; Fixed parameter tractable; Kernel},
author={Crowston, Robert and Gutin, Gregory and Jones, Mark and Yeo, Anders},
pages={56-68},
language={English}
}

Added 2012

The topic of local versus global satisfaction continues to generate interesting papers. The most surprising result was the paper by Luca Trevisan \cite{984912} (see below) which showed that the global satisfaction ratio only approaches 3/4. Links to several other related papers are on the page \cite{LieberherrSpecker:1985-2012:PartialSatisfaction} (see below). 

@article{984912,
author = {Luca Trevisan},
title = {On Local Versus Global Satisfiability},
journal = {SIAM J. Discret. Math.},
volume = {17},
number = {4}, 
year = {2004},
issn = {0895-4801},
pages = {541--547},
doi = {http://dx.doi.org/10.1137/S0895480197326528},
publisher = {Society for Industrial and Applied Mathematics},
address = {Philadelphia, PA, USA},
}           

@MISC{LieberherrSpecker:1985-2012:PartialSatisfaction,
author = {Lieberherr, Karl},
title = {Work by Karl Lieberherr and Ernst Specker on Partial Satisfaction},
month = jun,
year = {2012},
howpublished={\url{http://www.ccs.neu.edu/home/lieber/p-optimal/README.html}}
}

@ARTICLE{lieber-specker:partial-2,
TITLE = "{Complexity of Partial Satisfaction II}",
AUTHOR = "Karl J. Lieberherr and Ernst Specker",
JOURNAL = "Elemente der Mathematik",
YEAR = 2012,
PAGES = "134-150",
VOLUME = 67,
NUMBER = 3,
doi = {10.4171/EM/202}
}

Professor Karl J. Lieberherr
College of Computer and Information Science, Northeastern University
Internet: lieberherr AT ccs DOT neu DOT edu