Copertina

On SAT information content, its polynomial-time solvability and fixed code algorithms

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Drozdowski, Maciej
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Computational Complexity Information Theory F.2
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

SARRIGUREN: a polynomial-time complete algorithm for random $k$-SAT with relatively dense clauses
di: Sarriguren, Alfredo Goñi
Pubblicazione: (2024)

A Polynomial Time Algorithm for 3SAT
di: Quigley, Robert
Pubblicazione: (2024)

An MDL-Style Cost Functional KC, Distribution-Preserving Reductions ($A2^d$), and an $AC^0$+log Lower Bound for 3SAT via Balanced 3XOR
di: Lela, Marko
Pubblicazione: (2025)

Optimal lower bounds for Quantum Learning via Information Theory
di: Hadiashar, Shima Bab, et al.
Pubblicazione: (2023)

Quasi-linear time decoding of RS and AG codes for burst errors up to the Singleton bound
di: Li, Songsong, et al.
Pubblicazione: (2025)

A polynomial-time classical algorithm for noisy quantum circuits
di: Schuster, Thomas, et al.
Pubblicazione: (2024)

Deterministic list decoding of Reed-Solomon codes
di: Chatterjee, Soham, et al.
Pubblicazione: (2025)

$\rm P$ has polynomial-time finite-state verifiers
di: Gezer, M. Utkan, et al.
Pubblicazione: (2023)

Fast list recovery of univariate multiplicity and folded Reed-Solomon codes
di: Goyal, Rohan, et al.
Pubblicazione: (2025)

Fast list-decoding of univariate multiplicity and folded Reed-Solomon codes
di: Goyal, Rohan, et al.
Pubblicazione: (2023)

PAC codes with Bounded-Complexity Sequential Decoding: Pareto Distribution and Code Design
di: Moradi, Mohsen, et al.
Pubblicazione: (2024)

Complexity of Unambiguous Problems in $Σ^P_2$
di: Gilboa, Matan, et al.
Pubblicazione: (2025)

Recovering polynomials over finite fields from noisy character values
di: Kopparty, Swastik
Pubblicazione: (2026)

The Complexity of Graph Exploration Games
di: Fuchs, Janosch, et al.
Pubblicazione: (2023)

A proof of P != NP (New symmetric encryption algorithm against any linear attacks and differential attacks)
di: Ming, Gao
Pubblicazione: (2022)

A lower bound on the field size of convolutional codes with a maximum distance profile and an improved construction
di: Chen, Zitan
Pubblicazione: (2023)

Adjusted Kolmogorov Complexity of Binary Words with Empirical Entropy Normalization
di: Vidakovic, Brani
Pubblicazione: (2025)

Pauli measurements are not optimal for single-copy tomography
di: Acharya, Jayadev, et al.
Pubblicazione: (2025)

Set Theory in the Foundation of Math; Internal Classes and External Sets
di: Levin, Leonid A.
Pubblicazione: (2022)

Maximum Partial List H-Coloring on P_5-free graphs in polynomial time
di: Lokshtanov, Daniel, et al.
Pubblicazione: (2024)

A Note On The Natural Range Of Unambiguous-SAT
di: Pay, Tayfun
Pubblicazione: (2023)

Towards universally optimal sorting algorithms
di: Sen, Sandeep
Pubblicazione: (2025)

On the Complexity of the Conditional Independence Implication Problem With Bounded Cardinalities
di: Makowski, Michał
Pubblicazione: (2024)

Simple Stochastic Stopping Games: A Generator and Benchmark Library
di: Rudich, Avi, et al.
Pubblicazione: (2024)

On the Complexity of the Optimal Correlated Equilibria in Extensive-Form Games
di: Cheval, Vincent, et al.
Pubblicazione: (2025)

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
di: Lela, Marko
Pubblicazione: (2025)

Implementation of Polynomial NP-Complete Algorithms Based on the NP Verifier Simulation Framework
di: Lee, Changryeol
Pubblicazione: (2026)

Matrix-by-matrix multiplication algorithm with $O(N^2log_2N)$ computational complexity for variable precision arithmetic
di: Paszyński, Maciej
Pubblicazione: (2024)

Transversal non-Clifford gates for quantum LDPC codes on sheaves
di: Lin, Ting-Chun
Pubblicazione: (2024)

Explicit optimal-length locally repairable codes of distance 5
di: Beemer, Allison, et al.
Pubblicazione: (2018)

Expansion of higher-dimensional cubical complexes with application to quantum locally testable codes
di: Dinur, Irit, et al.
Pubblicazione: (2024)

NP-hardness of p-adic linear regression
di: Baker, Gregory D.
Pubblicazione: (2026)

A universal bound on the space complexity of Directed Acyclic Graph computations
di: Bilardi, Gianfranco, et al.
Pubblicazione: (2024)

Fast Simulation of Cellular Automata by Self-Composition
di: Natal, Joseph, et al.
Pubblicazione: (2024)

NP-Completeness Proofs of Puzzles using the T-Metacell Framework
di: Kiatchaipipat, Nattapol, et al.
Pubblicazione: (2025)

When Does Sparsity Help for k-Independent Set in Hypergraphs and Other Boolean CSPs?
di: Fritsch, Timo, et al.
Pubblicazione: (2026)

Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
di: Gupta, Chetan, et al.
Pubblicazione: (2025)

On the Asymptotic Nonnegative Rank of Matrices and its Applications in Information Theory
di: Chee, Yeow Meng, et al.
Pubblicazione: (2023)

Direct Sums for Parity Decision Trees
di: Besselman, Tyler, et al.
Pubblicazione: (2024)

Quantum algorithms through graph composition
di: Cornelissen, Arjan
Pubblicazione: (2025)