Date/Time:15 Jan 2020 17:00Venue: S17 #04-06 SR1Speaker: Frank Stephan, National University of SingaporeMeasure and Conquer for Max Hamming Distance XSATThis talk gives an overview of the joint work of the speaker’s ecent work on the Hamming XSAT problem. This problem asks for an algorithm to determine which, given an XSAT instance, determines the maximum Hamming distance between two solutions of this instance. The problem has been studied by Dahloef in 2005 in an ISAAC paper who provided an O(1.83848^n) algorithm for this problem. Later Fu, Zhu and Yin presented at JFCST 2012 an O(1.6760^n) algorithm for the related Max Hamming X3SAT problem where all clauses have at most three literals. The current paper provides for the general Max Hamming XSAT problem an O(1.4983^n) algorithm which applies also the technique “Measure and Conquer” in order to prove a better bound than the algorithm would give otherwise. Furthermore, the algorithm does not only provide the maximum Hamming distance of two solutions of the instance, but instead for each k between 0 and n the number of pairs of solutions which have Hamming distance k. For the special case Max Hamming Distant X3SAT, Hoi, Jain and Stephan have the bound O(1.3298^n) at the conference FSTTCS 2019.Add to calendar:
