:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Author:	Yung, Kingsley
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2404.17775
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

The Guided Local Hamiltonian Problem for Stoquastic Hamiltonians
by: Waite, Gabriel
Published: (2025)

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

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

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

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

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

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

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

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

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

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

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

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

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

Width Hierarchy for k-OBDD of Small Width
by: Khadiev, Kamil
Published: (2015)

On the Complexity of the Minimum-($k,ρ$)-Shortcut Problem
by: Avila, Tatiana Rocha, et al.
Published: (2026)

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

Some Applications and Limitations of Convex Optimization Hierarchies for Discrete and Continuous Optimization Problems
by: Ghosh, Mrinalkanti
Published: (2025)

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

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

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