Cover Image

The PCP-like Theorem for Sub-linear Time Inapproximability

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Ma, Hengzhao, Li, Jianzhong
Format:	Preprint
Published:	2021
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

A Zero-Knowledge PCP Theorem
by: Gur, Tom, et al.
Published: (2024)

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

Baby PIH: Parameterized Inapproximability of Min CSP
by: Guruswami, Venkatesan, et al.
Published: (2023)

Strong Inapproximability for a Promise Rank Problem
by: Guruswami, Venkatesan, et al.
Published: (2026)

Constant Inapproximability for PPA
by: Deligkas, Argyrios, et al.
Published: (2022)

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

Constant Inapproximability for Fisher Markets
by: Deligkas, Argyrios, et al.
Published: (2026)

PCP-free APX-Hardness of Nearest Codeword and Minimum Distance
by: Bhattiprolu, Vijay, et al.
Published: (2025)

Optimal Inapproximability of Generalized Linear Equations over a Finite Group
by: Bhangale, Amey, et al.
Published: (2026)

Constant Inapproximability of Pacing Equilibria in Second-Price Auctions
by: Chen, Xi, et al.
Published: (2025)

Pure-Circuit: Tight Inapproximability for PPAD
by: Deligkas, Argyrios, et al.
Published: (2022)

Inapproximability of the independent set polynomial in the complex plane
by: Bezakova, Ivona, et al.
Published: (2017)

The status of the quantum PCP conjecture (games version)
by: Natarajan, Anand, et al.
Published: (2024)

Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and Lattices
by: Bhattiprolu, Vijay, et al.
Published: (2024)

Optimal Inapproximability of Promise Equations over Finite Groups
by: Butti, Silvia, et al.
Published: (2024)

Superconstant Inapproximability of Decision Tree Learning
by: Koch, Caleb, et al.
Published: (2024)

PCPP-Based Reconfiguration Inapproximability: Query Complexity vs. Soundness Gap Trade-offs
by: Guruswami, Venkatesan, et al.
Published: (2025)

Quasi-quantum states and the quasi-quantum PCP theorem
by: Arad, Itai, et al.
Published: (2024)

Treedepth Inapproximability and Exponential ETH Lower Bound
by: Bonnet, Édouard, et al.
Published: (2025)

Tight Inapproximability of Nash Equilibria in Public Goods Games
by: Dinh, Jérémi Do, et al.
Published: (2024)

Inapproximability of Maximum Diameter Clustering for Few Clusters
by: Fleischmann, Henry, et al.
Published: (2023)

On the Inapproximability of Finding Minimum Monitoring Edge-Geodetic Sets
by: Bilò, Davide, et al.
Published: (2024)

Tight Inapproximability of Target Set Reconfiguration
by: Ohsaka, Naoto
Published: (2024)

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

From Chinese Postman to Salesman and Beyond II: Inapproximability and Parameterized Complexity
by: Frei, Fabian, et al.
Published: (2025)

Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems
by: Hirahara, Shuichi, et al.
Published: (2023)

Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration
by: Hirahara, Shuichi, et al.
Published: (2025)

Asymptotically Optimal Inapproximability of Maxmin $k$-Cut Reconfiguration
by: Hirahara, Shuichi, et al.
Published: (2024)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
by: Guruswami, Venkatesan, et al.
Published: (2023)

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

Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
by: Gharibian, Sevag, et al.
Published: (2021)

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

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

A Strong Direct Sum Theorem for Distributional Query Complexity
by: Blanc, Guy, et al.
Published: (2024)

KRW Composition Theorems via Lifting
by: de Rezende, Susanna F., et al.
Published: (2020)

Direct Product Theorems for Randomized Query Complexity
by: Ben-David, Shalev, et al.
Published: (2025)

Treewidth Inapproximability and Tight ETH Lower Bound
by: Bonnet, Édouard
Published: (2024)

A Refinement of the McCreight-Meyer Union Theorem
by: Fox, Matthew, et al.
Published: (2024)

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