Searching for Falsified Clause in Random ( log ( n ) ) (\log{n}) -CNFs is Hard for Randomized Communication
2025
Read Searching for Falsified Clause in Random ( log ( n ) ) (\log{n}) -CNFs is Hard for Randomized Communication (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-12124.txt.
Introduction
Artur Riazanov and co-authors prove a hard limit on teamwork in a 2025 paper. Two parties hold pieces of a puzzle: a random logical formula, built from short clauses over many variables, that no assignment can satisfy, plus an assignment to test. Their shared job is to find one clause the assignment breaks. Randomized chatter is allowed, and the formula's shape follows the classic random pattern at logarithmic clause width.
The result is a wall: any randomized two-party protocol needs communication growing linearly with the number of variables. In plain terms, no clever shortcut of hints and summaries can shrink the search; the parties must effectively pool a constant share of everything they hold. The bound hardens a known frontier in proof complexity and communication, where random formulas at this width resist every distributed shortcut.
Catalog record
| YEAR | 2025 |
|---|---|
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 45 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-12124
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Searching for Falsified Clause in Random ( log ( n ) ) (\log{n}) -CNFs is Hard for Randomized Communication Abstract We show that for a randomly sampled unsatisfiable O ( log n ) O(\log n) -CNF over n n variables the randomized two-party communication cost of finding a clause falsified by the given variable assignment is linear in n n . 1 Introduction This paper studies the communication complexity of Falsified Clause Search Problem . Definition 1 ( [ LNNW95 ] ). Let X,Y be two disjoint sets of boolean variables and \varphi be a CNF formula over the variables X\sqcup Y . We define Falsified Clause Search Problem or \mathrm{Search}_{\varphi} associated with formula \varphi in the following way: input: a pair (x,y)\in\{0,1\}^{X}\times\{0,1\}^{Y} ; output: a clause C\in\varphi that is violated by the input (x,y) . Communication lower bounds for search problems have applications in many areas of complexity theory. We consider two areas that are the most relevant and explain the applicability of communication lower bounds. Proof complexity. This area of complexity theory studies how hard it is to prove that a given formula \varphi is unsatisfiable; in other words, what is the length of the shortest proof in a certain proof system. Lower bounds for the proof systems often correspond to lower bounds on a run-time of SAT-solvers, and there are intricate connections to other areas of complexity theory, such as, for example, circuit complexity. There is a general framework for obtaining lower bounds on the length of the shortest proofs via communication. Suppose that, for an unsatisfiable CNF formula \varphi , we divide the variables into two disjoint groups X and Y in an arbitrary way. For a fixed proof system \mathfrak{C} we can try to transform efficient proof of \varphi into an efficient communication protocol for \mathrm{Search}_{\varphi} . A lower bound on the communication complexity of \mathrm{Search}_{\varphi} then implies a lower bound on the length of a proof of \varphi in \mathfrak{C} . This framework seems to originate from [ LNNW95 ] . Following this reduction, lower bounds for many different proof systems were obtained, for example: tree-like Cutting Planes [ IPU94 , HN12 , dRNV16 , BW25 ] , tree-like Threshold proof system [ BPS07 ] , tree-like \mathrm{Res}(\oplus) [ IS20 ] , etc. [ HN12 , GP18a ] . Depending on the communication model, even dag-like proofs can be analyzed via this framework [ Kra97 , Pud97 , HP17 , FPPR22 , GGKS20 , Sok24 ] . The lower bounds that can be achieved via this technique depend on the power of the communication model: the more powerful model we consider, the bigger class of proof systems we get the lower bound for. The choice of the formula \varphi is important here as well, in a sense that we need to be able to show the lower bound on the communication complexity of \mathrm{Search}_{\varphi} . Typically, \varphi is artificially built for this purpose. In this paper, we show a communication lower bound for the natural class of formulas (without usage of ad hoc constructions) that is a candidate for being hard for all propositional proof systems. Circuit complexity. Natural embedding of \mathrm{Search}_{\varphi} into a monotone Karchmer–Wigderson relation [ KW90 , Raz90 ] gives us the opportunity to use it for proving lower bounds for the monotone models of computation. From communication lower bounds, strong results are known for monotone formulas [ RPRC16 ] , monotone circuits [ GGKS20 , LMM+22 ] , monotone span programs [ RPRC16 , PR18 ] , etc. Communication is also the main instrument for showing separation between those models [ PR18 , GKRS19 ] , and trade-off results [ dRFJ+25 , GMRS25 ] . These type of results are based on ad hoc constructions of the formulas \varphi . Namely, \varphi is designed in order to able to show communication lower bound. 1.1 Random CNF To be more precise we start with the definition of random CNF formulas. Definition 2 . Let \mathfrak{F}(m,n,\Delta) denote the distribution of random \Delta -CNF on n variables obtained by sampling m clauses (out of the \binom{n}{\Delta}2^{\Delta} possible clauses) uniformly at random with repetitions. The famous result of Chvátal–Szemerédi says that if we pick a formula from this distribution with the proper parameters, the resulting formula will be unsatisfiable with high probability. Theorem 3 (Chvátal–Szemerédi, [ CS88 ] ). For any \Delta\geq 3 whp \bm{\varphi}\sim\mathfrak{F}(m,n,\Delta) is unsatisfiable if m\geq\ln 2\cdot 2^{\Delta}n . These types of distributions appear not only in most of the areas in computer science, but in general mathematics and physics as well [ MPZ02 ] . An interesting application is due to Feige [ Fei02 ] , who conjectured the following statement: no polynomial time algorithm may prove whp the unsatisfiability of a random O(1) -CNF formula with arbitrary large constant clause density. Assuming Feige’s conjecture, it is known that some problems are hard to approximate: vertex covering, PAC learning DNFs [ DSS16 ] , etc. As a candidate to be hard to refute in all proof systems, random CNFs are actively studied and lower bounds are known for many different proof systems [ Gri01 , BKPS02 , AR03 , Ale11 , SS22 ] . Recent developments in this direction utilize the connection between proof complexity of \varphi and communication complexity of \mathrm{Search}_{\varphi} . In particular, lower bounds for the Cutting Planes proofs of random O(\log n) -CNF [ HP17 , FPPR22 , Sok24 ] follow this strategy. However, these results only consider lower bounds on deterministic dag-like communication complexity of \mathrm{Search}_{\varphi} based on random O(\log n) -CNF. In this paper, we analyse the randomized tree-like communication of this problem that is incomparable with deterministic dag-like communication. This is a natural problem in a natural model, which also provides a way to explore how techniques used for structured formulas might extend to more typical instances like random CNFs. The main result is the following. Theorem 4 . Let c>0 be a large enough constant, n>0,\Delta\geq c\log n,m=O(n2^{\Delta}) . If \bm{\varphi}\sim\mathfrak{F}(m,n,\Delta) and \bm{X},\bm{Y}\subseteq[n] is a partition of variables that is taken uniformly at random, then whp over choice of \bm{\varphi} and partition \bm{X},\bm{Y} the randomized communication complexity of \mathrm{Search}_{\bm{\varphi}} is \Omega(n) . 1.2 Prior Results and Technique For several types of formulas \varphi , the randomized communication complexity of \mathrm{Search}_{\varphi} is well-studied. The approach for proving such bounds is the reduction of Unique Disjointness function to \mathrm{Search}_{\varphi} . The main success in this direction is the reduction based on critical block sensitivity [ HN12 , GP18b ] , we also include some earlier results, though there is some difference in the technique [ BPS07 ] . More precisely, for this technique one should assume that \varphi=\psi\circ g (we take some formula \psi and, in place of each variable, we substitute a carefully chosen gadget g with fresh variables). Assuming that \mathrm{Search}_{\psi} has critical block sensitivity m (that is a generalization of the block sensitivity measure), it is possible to reduce instances of unique disjointness of size \mathrm{poly}(m) to \mathrm{Search}_{\varphi} . The general framework for working with such formulas of \psi\circ g is called lifting , and the idea is to “lift” the hardness of \psi with respect to another