Imagen de Portada

Decision DNNFs with imbalanced conjunction cannot efficiently represent CNFs of bounded width

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autor principal:	Razgon, Igor
Formato:	Preprint
Publicado:	2025
Materias:	Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

On complexity of restricted fragments of Decision DNNF
por: Calí, Andrea, et al.
Publicado: (2025)

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

FPT Parameterisations of Fractional and Generalised Hypertree Width
por: Lanzinger, Matthias, et al.
Publicado: (2025)

Searching for Falsified Clause in Random (log n)-CNFs is Hard for Randomized Communication
por: Riazanov, Artur, et al.
Publicado: (2025)

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

Relative-error testing of conjunctions and decision lists
por: Chen, Xi, et al.
Publicado: (2025)

Enumeration and updates for conjunctive linear algebra queries through expressibility
por: Muñoz, Thomas, et al.
Publicado: (2023)

Space-bounded quantum state testing via space-efficient quantum singular value transformation
por: Gall, François Le, et al.
Publicado: (2023)

Deterministic and Strongly Nondeterministic Decision Trees for Decision Tables from Closed Classes
por: Ostonov, Azimkhon, et al.
Publicado: (2023)

Hazard-free Decision Trees
por: Benson, Deepu, et al.
Publicado: (2025)

Lower bounds for planar Arithmetic Circuits
por: Ramya, C., et al.
Publicado: (2025)

From FPT Decision to FPT Enumeration
por: Creignou, Nadia, et al.
Publicado: (2025)

Simple general magnification of circuit lower bounds
por: Atserias, Albert, et al.
Publicado: (2025)

Exponential lower bound via exponential sums
por: Bhattacharjee, Somnath, et al.
Publicado: (2026)

Stable algorithms cannot reliably find isolated perceptron solutions
por: Gong, Shuyang, et al.
Publicado: (2026)

Explaining the Ubiquity of Phase Transitions in Decision Problems
por: Jackson, Andrew
Publicado: (2025)

Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width
por: Kluk, Kacper, et al.
Publicado: (2025)

Depth lower bounds in Stabbing Planes for combinatorial principles
por: Dantchev, Stefan, et al.
Publicado: (2021)

Search versus Decision for $\mathsf{S}_2^\mathsf{P}$
por: Fortnow, Lance
Publicado: (2025)

The computational power of discrete chemical reaction networks with bounded executions
por: Doty, David, et al.
Publicado: (2024)

Complexity lower bounds for succinct binary structures of bounded clique-width with restrictions
por: Geniet, Colin, et al.
Publicado: (2026)

Phase Transitions in Decision Problems Over Odd-Sized Alphabets
por: Jackson, Andrew
Publicado: (2025)

Upper and Lower Bounds on $T_1$ and $T_2$ Decision Tree Model
por: Alhamdan, Yousef M.
Publicado: (2025)

Circuit metaconstruction in logspace for Rice-like complexity lower bounds in ANs and SGRs
por: Goubault-Larrecq, Aliénor, et al.
Publicado: (2025)

A note on Jerabek's paper "A simplified lower bound for implicational logic"
por: Gordeev, Lev, et al.
Publicado: (2026)

Lower Bounds on Cardinality of Reducts for Decision Tables from Closed Classes
por: Ostonov, Azimkhon, et al.
Publicado: (2024)

The complexity of finding and enumerating optimal subgraphs to represent spatial correlation
por: Enright, Jessica, et al.
Publicado: (2020)

Boolean Circuit Complexity and Two-Dimensional Cover Problems
por: Cavalar, Bruno P., et al.
Publicado: (2025)

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

On Condensation of Block Sensitivity, Certificate Complexity and the $\mathsf{AND}$ (and $\mathsf{OR}$) Decision Tree Complexity
por: Nalli, Sai Soumya, et al.
Publicado: (2026)

Fast and simple multiplication of bounded twin-width matrices
por: Kozma, László, et al.
Publicado: (2026)

A linear bound for the size of the finite terminal assembly of a directed non-cooperative tile assembly system
por: Ivanov, Sergiu, et al.
Publicado: (2024)

Decision algorithms for reversibility of one-dimensional non-linear cellular automata under null boundary conditions
por: Junchi, Ma, et al.
Publicado: (2024)

$C_{2k+1}$-coloring of bounded-diameter graphs
por: Piecyk, Marta
Publicado: (2024)

Query complexity lower bounds for local list-decoding and hard-core predicates (even for small rate and huge lists)
por: Ron-Zewi, Noga, et al.
Publicado: (2024)

Debate is efficient with your time
por: Brown-Cohen, Jonah, et al.
Publicado: (2026)

Lower bounds for set-blocked clauses proofs
por: Yolcu, Emre
Publicado: (2024)

A characterization of efficiently compilable constraint languages
por: Berkholz, Christoph, et al.
Publicado: (2023)

Decision Tree Learning on Product Spaces
por: Moakahr, Arshia Soltani, et al.
Publicado: (2026)

Space-bounded online Kolmogorov complexity is additive
por: Bauwens, Bruno, et al.
Publicado: (2025)