Falsified-clause search in random O(log n)-CNFs requires Ω(n) randomized two-party communication, with high probability over the formula and variable partition.
Razborov, and Avi Wigderson
1 Pith paper cite this work, alongside 107 external citations. Polarity classification is still indexing.
1
Pith paper citing it
107
external citations · OpenAlex
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.