Searching for Falsified Clause in Random (log n)-CNFs is Hard for Randomized Communication

2025/07/16 by Riazanov, Artur, Sofronova, Anastasia, Sokolov, Dmitry +1
#Computational Complexity (cs.CC) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2507.12124

Abstract

We show that for a randomly sampled unsatisfiable O(log n)-CNF over n variables the randomized two-party communication cost of finding a clause falsified by the given variable assignment is linear in n.

Citations

• Supercritical Tradeoffs for Monotone Circuits
• Truly Supercritical Trade-offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler-Leman
• Quantum Communication Advantage in TFNP
• Query-to-Communication Lifting for BPP
• Extension Complexity of Independent Set Polytopes
• Communication Lower Bounds via Critical Block Sensitivity
• Adventures in Monotone Complexity and TFNP

Related

• Improved Bounds for Sampling Solutions of Random CNF Formulas
• Faster Random k-CNF Satisfiability
• Unsatisfiable Linear CNF Formulas Are Large and Complex
• Learning CNF formulas from uniform random solutions in the local lemma regime
• A novel weighting scheme for random k-SAT