Imagen de Portada

Limits of Sequential Local Algorithms on the Random $k$-XORSAT Problem

Fuente: arXiv

Guardado en:

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

Ejemplares similares

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

$\#$W[1] = $\text{FPT}$: Fixed-Parameter Tractable Exact Algorithms for the $\#k$-Matching Problem
por: Yi, Yongming
Publicado: (2026)

Trading Determinism for Time: The k-Reach Problem
por: Bhadra, Ronak, et al.
Publicado: (2024)

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

Is Graph Local Complementation Inherently Sequential?
por: Concha-Vega, Pablo
Publicado: (2025)

P-time Algorithms for Typical #EO Problems
por: Meng, Boning, et al.
Publicado: (2024)

An Efficient Algorithm for Solving the 2-MAXSAT Problem
por: Chen, Yangjun
Publicado: (2023)

Average-Case Hardness of Parity Problems: Orthogonal Vectors, k-SUM and More
por: Dalirrooyfard, Mina, et al.
Publicado: (2025)

Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems
por: Lichter, Moritz, et al.
Publicado: (2024)

Limits of structures and Total NP Search Problems
por: Ježil, Ondřej
Publicado: (2023)

Quantum k-SAT Related Hypergraph Problems
por: Kremer, Simon-Luca, et al.
Publicado: (2025)

Analogy between List Coloring Problems and the Interval $k$-$(γ,μ)$-choosability property: theoretical aspects of complexity
por: Gama, Simone Ingrid Monteiro, et al.
Publicado: (2025)

The Optimization of Random Tree Codes for Limited Computational Resources
por: Bacinoglu, B. Tan
Publicado: (2025)

MaxMin Separation Problems: FPT Algorithms for $st$-Separator and Odd Cycle Transversal
por: Gaikwad, Ajinkya, et al.
Publicado: (2025)

Intrinsic Sequentiality in P: Causal Limits of Parallel Computation
por: Wei, Jing-Yuan
Publicado: (2026)

Tighter Bounds for the Randomized Polynomial-Time Simplex Algorithm for Linear Programming
por: Gibor, Daniel
Publicado: (2025)

On the Complexity of the Succinct State Local Hamiltonian Problem
por: Waite, Gabriel, et al.
Publicado: (2025)

The Guided Local Hamiltonian Problem for Stoquastic Hamiltonians
por: Waite, Gabriel
Publicado: (2025)

Algorithms for the Diverse-k-SAT problem: the geometry of satisfying assignments
por: Austrin, Per, et al.
Publicado: (2024)

On Approximability of Satisfiable k-CSPs: V
por: Bhangale, Amey, et al.
Publicado: (2024)

Pseudodeterministic Algorithms for Minimum Cut Problems
por: Agarwala, Aryan, et al.
Publicado: (2025)

Network Satisfaction Problems Solved by k-Consistency
por: Bodirsky, Manuel, et al.
Publicado: (2023)

Complexity Classification of Product State Problems for Local Hamiltonians
por: Kallaugher, John, et al.
Publicado: (2024)

Improved Hardness Results for the Guided Local Hamiltonian Problem
por: Cade, Chris, et al.
Publicado: (2022)

A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
por: Buhrman, Harry, et al.
Publicado: (2025)

Reconstructing Sets of Strings from Their k-way Projections: Algorithms & Complexity
por: Tate, Elise, et al.
Publicado: (2025)

Near Optimal Hardness of Approximating $k$-CSP
por: Minzer, Dor, et al.
Publicado: (2025)

Width Hierarchy for k-OBDD of Small Width
por: Khadiev, Kamil
Publicado: (2015)

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

Virtual Qudits for Simon's Problem: Dimension-Lifted Algorithms on Qubit Hardware
por: Semre, Abed, et al.
Publicado: (2025)

On Extremal Properties of k-CNF: Capturing Threshold Functions
por: Gurumukhani, Mohit, et al.
Publicado: (2024)

Constant-Cost Communication is not Reducible to k-Hamming Distance
por: Fang, Yuting, et al.
Publicado: (2024)

Near Optimal Algorithms for Noisy $k$-XOR under Low-Degree Heuristic
por: Mao, Songtao
Publicado: (2026)

Almost Polynomial Factor Inapproximability for Parameterized k-Clique
por: S., Karthik C., et al.
Publicado: (2021)

On the Hardness of Approximation of the Fair k-Center Problem
por: Thejaswi, Suhas
Publicado: (2026)

Complexity of Paired Domination Problems on Circle and $k$-Polygon Graphs
por: Mu, Ta-Yu, et al.
Publicado: (2024)

Identifying Codes Kernelization Limitations
por: Banik, Aritra, et al.
Publicado: (2025)

Complexity of Local Search for Euclidean Clustering Problems
por: Manthey, Bodo, et al.
Publicado: (2023)

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

A Faster Randomized Algorithm for Vertex Cover: An Automated Approach
por: Clinch, Katie, et al.
Publicado: (2025)