Falsified-clause search in random O(log n)-CNFs requires Ω(n) randomized two-party communication, with high probability over the formula and variable partition.
Many hard examples for resolution
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
fields
cs.CC 1years
2025 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Searching for Falsified Clause in Random (log n)-CNFs is Hard for Randomized Communication
Falsified-clause search in random O(log n)-CNFs requires Ω(n) randomized two-party communication, with high probability over the formula and variable partition.