:: Library Catalog

Buchumschlag

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Ma, Hengzhao, Li, Jianzhong
Format:	Preprint
Veröffentlicht:	2021
Schlagworte:	Computational Complexity
Online-Zugang:	https://arxiv.org/abs/2107.01520
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Can Almost Everybody be Almost Happy? PCP for PPAD and the Inapproximability of Nash
von: Babichenko, Yakov, et al.
Veröffentlicht: (2015)

A Zero-Knowledge PCP Theorem
von: Gur, Tom, et al.
Veröffentlicht: (2024)

Fisher Markets with Approximately Optimal Bundles and the Need for a PCP Theorem for PPAD
von: Deligkas, Argyrios, et al.
Veröffentlicht: (2026)

Constant Inapproximability for PPA
von: Deligkas, Argyrios, et al.
Veröffentlicht: (2022)

Baby PIH: Parameterized Inapproximability of Min CSP
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2023)

Strong Inapproximability for a Promise Rank Problem
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2026)

Constant Inapproximability for Fisher Markets
von: Deligkas, Argyrios, et al.
Veröffentlicht: (2026)

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

PCP-free APX-Hardness of Nearest Codeword and Minimum Distance
von: Bhattiprolu, Vijay, et al.
Veröffentlicht: (2025)

Pure-Circuit: Tight Inapproximability for PPAD
von: Deligkas, Argyrios, et al.
Veröffentlicht: (2022)

Constant Inapproximability of Pacing Equilibria in Second-Price Auctions
von: Chen, Xi, et al.
Veröffentlicht: (2025)

The status of the quantum PCP conjecture (games version)
von: Natarajan, Anand, et al.
Veröffentlicht: (2024)

Inapproximability of the independent set polynomial in the complex plane
von: Bezakova, Ivona, et al.
Veröffentlicht: (2017)

Superconstant Inapproximability of Decision Tree Learning
von: Koch, Caleb, et al.
Veröffentlicht: (2024)

Optimal Inapproximability of Generalized Linear Equations over a Finite Group
von: Bhangale, Amey, et al.
Veröffentlicht: (2026)

Quasi-quantum states and the quasi-quantum PCP theorem
von: Arad, Itai, et al.
Veröffentlicht: (2024)

Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and Lattices
von: Bhattiprolu, Vijay, et al.
Veröffentlicht: (2024)

Optimal Inapproximability of Promise Equations over Finite Groups
von: Butti, Silvia, et al.
Veröffentlicht: (2024)

Treedepth Inapproximability and Exponential ETH Lower Bound
von: Bonnet, Édouard, et al.
Veröffentlicht: (2025)

Inapproximability of Maximum Diameter Clustering for Few Clusters
von: Fleischmann, Henry, et al.
Veröffentlicht: (2023)

Tight Inapproximability of Nash Equilibria in Public Goods Games
von: Dinh, Jérémi Do, et al.
Veröffentlicht: (2024)

PCPP-Based Reconfiguration Inapproximability: Query Complexity vs. Soundness Gap Trade-offs
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2025)

Tight Inapproximability of Target Set Reconfiguration
von: Ohsaka, Naoto
Veröffentlicht: (2024)

On the Inapproximability of Finding Minimum Monitoring Edge-Geodetic Sets
von: Bilò, Davide, et al.
Veröffentlicht: (2024)

From Chinese Postman to Salesman and Beyond II: Inapproximability and Parameterized Complexity
von: Frei, Fabian, et al.
Veröffentlicht: (2025)

Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems
von: Hirahara, Shuichi, et al.
Veröffentlicht: (2023)

Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration
von: Hirahara, Shuichi, et al.
Veröffentlicht: (2025)

Asymptotically Optimal Inapproximability of Maxmin $k$-Cut Reconfiguration
von: Hirahara, Shuichi, et al.
Veröffentlicht: (2024)

Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all $\ell_p$ Norms
von: Bennett, Huck, et al.
Veröffentlicht: (2022)

Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
von: Gharibian, Sevag, et al.
Veröffentlicht: (2021)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2023)

On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
von: S., Karthik C., et al.
Veröffentlicht: (2024)

Guidable Local Hamiltonian Problems with Implications to Heuristic Ansätze State Preparation and the Quantum PCP Conjecture
von: Weggemans, Jordi, et al.
Veröffentlicht: (2023)

Treewidth Inapproximability and Tight ETH Lower Bound
von: Bonnet, Édouard
Veröffentlicht: (2024)

Encoding of algebraic geometry codes with quasi-linear complexity $O(N\log N)$
von: Li, Songsong, et al.
Veröffentlicht: (2024)

A Strong Direct Sum Theorem for Distributional Query Complexity
von: Blanc, Guy, et al.
Veröffentlicht: (2024)

KRW Composition Theorems via Lifting
von: de Rezende, Susanna F., et al.
Veröffentlicht: (2020)

Direct Product Theorems for Randomized Query Complexity
von: Ben-David, Shalev, et al.
Veröffentlicht: (2025)

Sorting by pile shuffles on queue-like and stack-like piles can be hard
von: Treleaven, Kyle B.
Veröffentlicht: (2025)

A Refinement of the McCreight-Meyer Union Theorem
von: Fox, Matthew, et al.
Veröffentlicht: (2024)