Cover Image

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

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Riazanov, Artur, Sofronova, Anastasia, Sokolov, Dmitry, Yuan, Weiqiang
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Pseudodeterministic Communication Complexity
by: Göös, Mika, et al.
Published: (2025)

Top-Down Lower Bounds for Depth-Four Circuits
by: Göös, Mika, et al.
Published: (2023)

Monotone Circuit Complexity of Matching
by: Cavalar, Bruno, et al.
Published: (2025)

Sampling Permutations with Cell Probes is Hard
by: Alekseev, Yaroslav, et al.
Published: (2025)

Better Boosting of Communication Oracles, or Not
by: Harms, Nathaniel, et al.
Published: (2024)

Equality is Far Weaker than Constant-Cost Communication
by: Göös, Mika, et al.
Published: (2025)

Partial Minimum Branching Program Size Problem is ETH-hard
by: Glinskih, Ludmila, et al.
Published: (2024)

Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity
by: de Rezende, Susanna F., et al.
Published: (2026)

Bounded-Depth Frege Lower Bounds for Random 3-CNFs via Deterministic Restrictions
by: Gryaznov, Svyatoslav, et al.
Published: (2024)

Local Quantum Search Algorithm for Random $k$-SAT with $Ω(n^{1+ε})$ Clauses
by: Wu, Mingyou
Published: (2024)

Resolution Over Linear Equations: Combinatorial Games for Tree-like Size and Space
by: Gryaznov, Svyatoslav, et al.
Published: (2024)

Decision DNNFs with imbalanced conjunction cannot efficiently represent CNFs of bounded width
by: Razgon, Igor
Published: (2025)

Hardness of Random Reordered Encodings of Parity for Resolution and CDCL
by: Chew, Leroy, et al.
Published: (2024)

Spiky Rank and Its Applications to Rigidity and Circuits
by: Hambardzumyan, Lianna, et al.
Published: (2026)

Small unsatisfiable $k$-CNFs with bounded literal occurrence
by: Zhang, Tianwei, et al.
Published: (2024)

Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case
by: Guruswami, Venkatesan, et al.
Published: (2025)

Quantum Advantages in (n,d)->1 Random Access Codes
by: Ambainis, Andris, et al.
Published: (2015)

No Complete Problem for Constant-Cost Randomized Communication
by: Fang, Yuting, et al.
Published: (2024)

SVP$_p$ is Deterministically NP-Hard for all $p > 2$, Even to Approximate Within a Factor of $2^{\log^{1-\varepsilon} n}$
by: Hair, Isaac M., et al.
Published: (2025)

No Constant-Cost Protocol for Point--Line Incidence
by: Göös, Mika, et al.
Published: (2026)

Total Search Problems in $\mathsf{ZPP}$
by: Fleming, Noah, et al.
Published: (2025)

Communication with Imperfectly Shared Randomness
by: Canonne, Clément L., et al.
Published: (2014)

A Graphical #SAT Algorithm for Formulae with Small Clause Density
by: Laakkonen, Tuomas, et al.
Published: (2022)

Testing for Renamability to Classes of Clause Sets
by: Brandl, Albert, et al.
Published: (2025)

Proving Unsatisfiability with Hitting Formulas
by: Filmus, Yuval, et al.
Published: (2023)

More Efficient $k$-wise Independent Permutations from Random Reversible Circuits via log-Sobolev Inequalities
by: Gretta, Lucas, et al.
Published: (2024)

Anticoncentrated $n$-bit distribution from $\log(n)$ qubits
by: Zhang, Bingzhi, et al.
Published: (2025)

Random Permutations in Computational Complexity
by: Hitchcock, John M., et al.
Published: (2025)

Search-Driven Clause Learning for Product-State Quantum $k$-SAT (PRODSAT-QSAT)
by: González-Castillo, Samuel, et al.
Published: (2026)

A nearly-$4\log n$ depth lower bound for formulas with restriction on top
by: Wu, Hao
Published: (2024)

The Randomness Deficiency Function and the Shift Operator
by: Epstein, Samuel
Published: (2023)

PCF Learned Sort: a Learning Augmented Sort Algorithm with $O(n \log\log n)$ Expected Complexity
by: Sato, Atsuki, et al.
Published: (2024)

Direct Product Theorems for Randomized Query Complexity
by: Ben-David, Shalev, et al.
Published: (2025)

Aaronson-Ambainis Conjecture Is True For Random Restrictions
by: Bhattacharya, Sreejata Kishor
Published: (2024)

Strongly Refuting Random CSP without Literals
by: Chan, Siu On, et al.
Published: (2026)

Hilbert Functions and Low-Degree Randomness Extractors
by: Golovnev, Alexander, et al.
Published: (2024)

Lift-and-Project Integrality Gaps for Santa Claus
by: Bamas, Etienne
Published: (2024)

Randomized Communication and Implicit Graph Representations
by: Harms, Nathaniel, et al.
Published: (2021)

An $Ω( (\log n / \log \log n)^2 )$ Cell-Probe Lower Bound for Dynamic Boolean Data Structures
by: Ko, Young Kun
Published: (2026)

How to Construct Random Unitaries
by: Ma, Fermi, et al.
Published: (2024)