Buchumschlag

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

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	Yung, Kingsley
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

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

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

Trading Determinism for Time: The k-Reach Problem
von: Bhadra, Ronak, et al.
Veröffentlicht: (2024)

No Complete Problem for Constant-Cost Randomized Communication
von: Fang, Yuting, et al.
Veröffentlicht: (2024)

Is Graph Local Complementation Inherently Sequential?
von: Concha-Vega, Pablo
Veröffentlicht: (2025)

P-time Algorithms for Typical #EO Problems
von: Meng, Boning, et al.
Veröffentlicht: (2024)

An Efficient Algorithm for Solving the 2-MAXSAT Problem
von: Chen, Yangjun
Veröffentlicht: (2023)

Average-Case Hardness of Parity Problems: Orthogonal Vectors, k-SUM and More
von: Dalirrooyfard, Mina, et al.
Veröffentlicht: (2025)

Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems
von: Lichter, Moritz, et al.
Veröffentlicht: (2024)

Limits of structures and Total NP Search Problems
von: Ježil, Ondřej
Veröffentlicht: (2023)

Quantum k-SAT Related Hypergraph Problems
von: Kremer, Simon-Luca, et al.
Veröffentlicht: (2025)

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

The Optimization of Random Tree Codes for Limited Computational Resources
von: Bacinoglu, B. Tan
Veröffentlicht: (2025)

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

Intrinsic Sequentiality in P: Causal Limits of Parallel Computation
von: Wei, Jing-Yuan
Veröffentlicht: (2026)

Tighter Bounds for the Randomized Polynomial-Time Simplex Algorithm for Linear Programming
von: Gibor, Daniel
Veröffentlicht: (2025)

On the Complexity of the Succinct State Local Hamiltonian Problem
von: Waite, Gabriel, et al.
Veröffentlicht: (2025)

The Guided Local Hamiltonian Problem for Stoquastic Hamiltonians
von: Waite, Gabriel
Veröffentlicht: (2025)

Algorithms for the Diverse-k-SAT problem: the geometry of satisfying assignments
von: Austrin, Per, et al.
Veröffentlicht: (2024)

On Approximability of Satisfiable k-CSPs: V
von: Bhangale, Amey, et al.
Veröffentlicht: (2024)

Pseudodeterministic Algorithms for Minimum Cut Problems
von: Agarwala, Aryan, et al.
Veröffentlicht: (2025)

Network Satisfaction Problems Solved by k-Consistency
von: Bodirsky, Manuel, et al.
Veröffentlicht: (2023)

Complexity Classification of Product State Problems for Local Hamiltonians
von: Kallaugher, John, et al.
Veröffentlicht: (2024)

Improved Hardness Results for the Guided Local Hamiltonian Problem
von: Cade, Chris, et al.
Veröffentlicht: (2022)

A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
von: Buhrman, Harry, et al.
Veröffentlicht: (2025)

Reconstructing Sets of Strings from Their k-way Projections: Algorithms & Complexity
von: Tate, Elise, et al.
Veröffentlicht: (2025)

Near Optimal Hardness of Approximating $k$-CSP
von: Minzer, Dor, et al.
Veröffentlicht: (2025)

Width Hierarchy for k-OBDD of Small Width
von: Khadiev, Kamil
Veröffentlicht: (2015)

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

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

On Extremal Properties of k-CNF: Capturing Threshold Functions
von: Gurumukhani, Mohit, et al.
Veröffentlicht: (2024)

Constant-Cost Communication is not Reducible to k-Hamming Distance
von: Fang, Yuting, et al.
Veröffentlicht: (2024)

Near Optimal Algorithms for Noisy $k$-XOR under Low-Degree Heuristic
von: Mao, Songtao
Veröffentlicht: (2026)

Almost Polynomial Factor Inapproximability for Parameterized k-Clique
von: S., Karthik C., et al.
Veröffentlicht: (2021)

On the Hardness of Approximation of the Fair k-Center Problem
von: Thejaswi, Suhas
Veröffentlicht: (2026)

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

Identifying Codes Kernelization Limitations
von: Banik, Aritra, et al.
Veröffentlicht: (2025)

Complexity of Local Search for Euclidean Clustering Problems
von: Manthey, Bodo, et al.
Veröffentlicht: (2023)

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

A Faster Randomized Algorithm for Vertex Cover: An Automated Approach
von: Clinch, Katie, et al.
Veröffentlicht: (2025)