Quiet Planting for $k$-SAT, Multiple Solutions of Arbitrary Geometry

Ali Ahmadi, Kiarash Banihashem, Iman Gholami, Mohammad Taghi Hajiaghayi, Jan Olkowski
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:75-105, 2026.

Abstract

Recent work on “quiet planting” in combinatorial optimization aims to generate instances with a hidden solution that is hard to recover, typically by making the planted distribution statistically indistinguishable from uniform for specific algorithms, such as statistical queries. A prominent example is planted $k$-SAT, where $O(n^{k/2})$ clauses can be planted while maintaining indistinguishability from uniform instances, evidenced by prior hardness results which also align with findings in SAT refutation. Despite extensive research and practical use in benchmarking SAT solvers, the challenge of quietly planting multiple solutions while preserving hardness has remained an open problem. This work initiates the study of quiet planting with an arbitrary number of solutions, proposing the first method to construct quiet planting distributions for $k$-SAT formulas that accommodate more than one solution. We provide statistical query lower bounds for distinguishing these planted instances from uniform ones, and our method allows for planting solutions with arbitrary geometric relationships, including varying Hamming distances. A key innovation facilitating multiple solutions is the ability to incorporate arbitrary correlations between variable selection in clauses and their negation patterns, departing from prior approaches. We also investigate the worst-case complexity of SAT by showing the difficulty in distinguishing satisfiable instances with numerous solutions from unsatisfiable ones, addressing an open problem of Hsieh, Mohanty, and Xu (CCC’22). From a technical standpoint, we generalize the concept of $(r-1)$-wise uniformness in clause distributions, proving hardness holds if the marginal distribution over negation patterns is $(r-1)$-wise uniform, and reveal a connection to binary linear codes, demonstrating how a $[k, t, r]$ code can guide the planting of up to $2^t - 1$ solutions on $k$ variables with $(r-1)$-wise uniform negation distributions.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-ahmadi26a, title = {Quiet Planting for $k$-SAT, Multiple Solutions of Arbitrary Geometry}, author = {Ahmadi, Ali and Banihashem, Kiarash and Gholami, Iman and Hajiaghayi, Mohammad Taghi and Olkowski, Jan}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {75--105}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/ahmadi26a/ahmadi26a.pdf}, url = {https://proceedings.mlr.press/v336/ahmadi26a.html}, abstract = {Recent work on “quiet planting” in combinatorial optimization aims to generate instances with a hidden solution that is hard to recover, typically by making the planted distribution statistically indistinguishable from uniform for specific algorithms, such as statistical queries. A prominent example is planted $k$-SAT, where $O(n^{k/2})$ clauses can be planted while maintaining indistinguishability from uniform instances, evidenced by prior hardness results which also align with findings in SAT refutation. Despite extensive research and practical use in benchmarking SAT solvers, the challenge of quietly planting multiple solutions while preserving hardness has remained an open problem. This work initiates the study of quiet planting with an arbitrary number of solutions, proposing the first method to construct quiet planting distributions for $k$-SAT formulas that accommodate more than one solution. We provide statistical query lower bounds for distinguishing these planted instances from uniform ones, and our method allows for planting solutions with arbitrary geometric relationships, including varying Hamming distances. A key innovation facilitating multiple solutions is the ability to incorporate arbitrary correlations between variable selection in clauses and their negation patterns, departing from prior approaches. We also investigate the worst-case complexity of SAT by showing the difficulty in distinguishing satisfiable instances with numerous solutions from unsatisfiable ones, addressing an open problem of Hsieh, Mohanty, and Xu (CCC’22). From a technical standpoint, we generalize the concept of $(r-1)$-wise uniformness in clause distributions, proving hardness holds if the marginal distribution over negation patterns is $(r-1)$-wise uniform, and reveal a connection to binary linear codes, demonstrating how a $[k, t, r]$ code can guide the planting of up to $2^t - 1$ solutions on $k$ variables with $(r-1)$-wise uniform negation distributions.} }
Endnote
%0 Conference Paper %T Quiet Planting for $k$-SAT, Multiple Solutions of Arbitrary Geometry %A Ali Ahmadi %A Kiarash Banihashem %A Iman Gholami %A Mohammad Taghi Hajiaghayi %A Jan Olkowski %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-ahmadi26a %I PMLR %P 75--105 %U https://proceedings.mlr.press/v336/ahmadi26a.html %V 336 %X Recent work on “quiet planting” in combinatorial optimization aims to generate instances with a hidden solution that is hard to recover, typically by making the planted distribution statistically indistinguishable from uniform for specific algorithms, such as statistical queries. A prominent example is planted $k$-SAT, where $O(n^{k/2})$ clauses can be planted while maintaining indistinguishability from uniform instances, evidenced by prior hardness results which also align with findings in SAT refutation. Despite extensive research and practical use in benchmarking SAT solvers, the challenge of quietly planting multiple solutions while preserving hardness has remained an open problem. This work initiates the study of quiet planting with an arbitrary number of solutions, proposing the first method to construct quiet planting distributions for $k$-SAT formulas that accommodate more than one solution. We provide statistical query lower bounds for distinguishing these planted instances from uniform ones, and our method allows for planting solutions with arbitrary geometric relationships, including varying Hamming distances. A key innovation facilitating multiple solutions is the ability to incorporate arbitrary correlations between variable selection in clauses and their negation patterns, departing from prior approaches. We also investigate the worst-case complexity of SAT by showing the difficulty in distinguishing satisfiable instances with numerous solutions from unsatisfiable ones, addressing an open problem of Hsieh, Mohanty, and Xu (CCC’22). From a technical standpoint, we generalize the concept of $(r-1)$-wise uniformness in clause distributions, proving hardness holds if the marginal distribution over negation patterns is $(r-1)$-wise uniform, and reveal a connection to binary linear codes, demonstrating how a $[k, t, r]$ code can guide the planting of up to $2^t - 1$ solutions on $k$ variables with $(r-1)$-wise uniform negation distributions.
APA
Ahmadi, A., Banihashem, K., Gholami, I., Hajiaghayi, M.T. & Olkowski, J.. (2026). Quiet Planting for $k$-SAT, Multiple Solutions of Arbitrary Geometry. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:75-105 Available from https://proceedings.mlr.press/v336/ahmadi26a.html.

Related Material