Image de couverture de livre

SARRIGUREN: a polynomial-time complete algorithm for random $k$-SAT with relatively dense clauses

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteur principal:	Sarriguren, Alfredo Goñi
Format:	Preprint
Publié:	2024
Sujets:	Data Structures and Algorithms Computational Complexity F.2.2
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Towards universally optimal sorting algorithms
par: Sen, Sandeep
Publié: (2025)

Approximate all-pairs Hamming distances and 0-1 matrix multiplication
par: Kowaluk, Miroslaw, et autres
Publié: (2025)

Realizing temporal graphs from fastest travel times
par: Klobas, Nina, et autres
Publié: (2023)

An Algorithm for a Variation of the Shortest Common Superstring Problem
par: Gilfanov, Arthur
Publié: (2024)

Spanning Trees Minimizing Branching Costs
par: Gargano, Luisa, et autres
Publié: (2024)

Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction
par: Krithika, R., et autres
Publié: (2023)

Identity Testing for Circuits with Exponentiation Gates
par: Li, Jiatu, et autres
Publié: (2025)

A Decomposition Approach to the Weighted $k$-server Problem
par: Ayyadevara, Nikhil, et autres
Publié: (2024)

Graph Threading with Turn Costs
par: Demaine, Erik D., et autres
Publié: (2024)

A Piecewise Approach for the Analysis of Exact Algorithms
par: Clinch, Katie, et autres
Publié: (2024)

Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
par: Dvořák, Pavel, et autres
Publié: (2017)

Fine-Grained Optimality of Partially Dynamic Shortest Paths and More
par: Saha, Barna, et autres
Publié: (2024)

Certificate-Sensitive Subset Sum: Realizing Instance Complexity
par: Salas, Jesus
Publié: (2025)

On Solving Problems of Substantially Super-linear Complexity in $N^{o(1)}$ Rounds in the MPC Model
par: Lingas, Andrzej
Publié: (2026)

On the satisfability of random k-Horn formulae
par: Istrate, Gabriel
Publié: (2000)

NP-Completeness of the Combinatorial Distance Matrix Realisation Problem
par: Fairbairn, David L., et autres
Publié: (2024)

When Votes Change and Committees Should (Not)
par: Bredereck, Robert, et autres
Publié: (2020)

An improved local search based algorithm for $k^-$-star partition
par: Gong, Mingyang, et autres
Publié: (2025)

Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity
par: Liao, Chao, et autres
Publié: (2022)

Exact and Approximate High-Multiplicity Scheduling on Identical Machines
par: Jansen, Klaus, et autres
Publié: (2024)

Mim-Width is paraNP-complete
par: Bergougnoux, Benjamin, et autres
Publié: (2025)

Large cliques and large independent sets: can they coexist?
par: Feige, Uriel, et autres
Publié: (2025)

Maximum Partial List H-Coloring on P_5-free graphs in polynomial time
par: Lokshtanov, Daniel, et autres
Publié: (2024)

A polynomial-time algorithm for recognizing high-bandwidth graphs
par: Varona, Luis M. B.
Publié: (2026)

Kernelization Dichotomies for Hitting Subgraphs under Structural Parameterizations
par: Bougeret, Marin, et autres
Publié: (2024)

Kernelization dichotomies for hitting minors under structural parameterizations
par: Bougeret, Marin, et autres
Publié: (2025)

An Efficient Algorithm for Unbalanced 1D Transportation
par: Gouvine, Gabriel
Publié: (2023)

Balanced Substructures in Bicolored Graphs
par: Ardra, P. S., et autres
Publié: (2024)

Approximation Schemes for k-Subset Sum Ratio and k-way Number Partitioning Ratio
par: Kanellopoulos, Sotiris, et autres
Publié: (2025)

Eliminating Illusion in Directed Networks
par: Jana, Sougata, et autres
Publié: (2026)

Approximation algorithms for scheduling with rejection in green manufacturing
par: Gong, Mingyang, et autres
Publié: (2025)

Approximation algorithms for Job Scheduling with reconfigurable resources
par: Bergé, Pierre, et autres
Publié: (2023)

A faster algorithm for the construction of optimal factoring automata
par: Erlebach, Thomas, et autres
Publié: (2024)

Why Linear Programming cannot solve large instances of NP-complete problems in polynomial time
par: Hofman, Radoslaw
Publié: (2006)

The cost of cyclic permutations and remainder sums in the Euclidean algorithm
par: Blomer, Valentin, et autres
Publié: (2026)

Guarding Polyominoes Under $k$-Hop Visibility
par: Filtser, Omrit, et autres
Publié: (2023)

Approximate Minimum Sum Colorings and Maximum $k$-Colorable Subgraphs of Chordal Graphs
par: DeHaan, Ian, et autres
Publié: (2024)

On modeling NP-Complete problems as polynomial-sized linear programs: Escaping/Side-stepping the "barriers"
par: Diaby, Moustapha, et autres
Publié: (2023)

Tree Containment Parameterized by Scanwidth
par: van Iersel, Leo, et autres
Publié: (2026)

Complexity of Finding and Enumerating Interconnection Trees
par: Demange, Noé, et autres
Publié: (2026)