Pseudo-Boolean function: Difference between revisions

Revision as of 10:43, 8 July 2023

Revision as of 10:44, 8 July 2023

Line 35:

===Polynomial Compression Algorithms===

Consider a pseudo-Boolean function <math> f </math> as a mapping from <math>\{-1,1\}^n</math> to <math>\mathbb{R}</math>. Then <math>f(x)= \sum_{I\subseteq [n]}\hat{f}(I)\prod_{i\in I}x_i.</math> Assume that each coefficient <math>\hat{f}(I)</math> is integral. Then for an integer <math>k</math> the problem P of deciding whether <math> f(x) </math> is more or equal to <math>k</math> is NP-complete. It is proved in <ref name="crow"Crowston2011>{{cite journal |last1=Crowston et|first1=R. al|last2=Fellows |first2=M., |last3=Gutin |first3=G. |last4=Jones |first4=M. |last5=Rosamond |first5=F. |last6=Thomasse |first6=S. |last7=Yeo |first7=A. |year=2011 |title=Simultaneously Satisfying Linear Equations Over GF(2): MaxLin2 and Max-r-Lin2 Parameterized Above Average. |journal=Proc. Of FSTTCS 2011 |arxiv=1104.1135 |bibcode=2011arXiv1104.1135C}}</ref> that in polynomial time we can either solve P or reduce the number of variables to <math> O(k^2\log k).</math> Let <math>r</math> be the degree of the above multi-linear polynomial for <math>f</math>. Then <ref name=crow>Crowston et al., 2011<Crowston2011/ref> proved that in polynomial time we can either solve P or reduce the number of variables to <math>r(k-1)</math>.

==See also==

Line 45:

==References==

* {{cite journal |last1=Crowston |first1=R. |last2=Fellows |first2=M. |last3=Gutin |first3=G. |last4=Jones |first4=M. |last5=Rosamond |first5=F. |last6=Thomasse |first6=S. |last7=Yeo |first7=A. |year=2011 |title=Simultaneously Satisfying Linear Equations Over GF(2): MaxLin2 and Max-r-Lin2 Parameterized Above Average. |journal=Proc. Of FSTTCS 2011 |arxiv=1104.1135 |bibcode=2011arXiv1104.1135C}}

* {{cite journal |last=Ishikawa |first=H. |year=2011 |title=Transformation of general binary MRF minimization to the first order case |journal=[[IEEE Transactions on Pattern Analysis and Machine Intelligence]] |doi=10.1109/tpami.2010.91 |pmid=20421673 |citeseerx=10.1.1.675.2183 |s2cid=17314555 |volume=33 |number=6 |pages=1234–1249}}

* {{cite journal |last=O'Donnell |first=Ryan |year=2008 |title=Some topics in analysis of Boolean functions |journal=ECCC |issn=1433-8092 |url=https://eccc.weizmann.ac.il/report/2008/055/}}