Por Navid Talebanfard (University of Sheffield).
What is the largest number of satisfying assignments of minimum Hamming weight in a k-CNF with no satisfying assignment of Hamming weight less than n/2? This problem is intimately related to the exact complexity of k-SAT as well as depth-3 circuit complexity of the Majority function. We give a new randomized algorithm to enumerate these satisfying assignments for k = 3.
Joint work with Mohit Gurumukhani, Ramamohan Paturi, Pavel Pudlák, and Michael Saks.