Buchumschlag

PCPP-Based Reconfiguration Inapproximability: Query Complexity vs. Soundness Gap Trade-offs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Guruswami, Venkatesan, Ren, Xuandi, Wu, Kewen
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

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

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)

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

Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2024)

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

Scheduling Problems with Constrained Rejections
von: Davies, Sami, et al.
Veröffentlicht: (2025)

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)

Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles
von: Alrabiah, Omar, et al.
Veröffentlicht: (2024)

Structure Theorems (and Fast Algorithms) for List Recovery of Subspace-Design Codes
von: Goyal, Rohan, et al.
Veröffentlicht: (2025)

New constructions of pseudorandom codes
von: Ghentiyala, Surendra, et al.
Veröffentlicht: (2024)

Punctured Low-Bias Codes Behave Like Random Linear Codes
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2021)

Classification of Non-redundancy of Boolean Predicates of Arity 4
von: Brakensiek, Joshua, et al.
Veröffentlicht: (2026)

Hardness of Learning Boolean Functions from Label Proportions
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2024)

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

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

$\ell_p$-Spread and Restricted Isometry Properties of Sparse Random Matrices
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2021)

Explicit Constant-Alphabet Subspace Design Codes
von: Goyal, Rohan, et al.
Veröffentlicht: (2026)

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)

Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2025)

Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $\sqrt{n}$ Dimension Threshold
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2024)

Communication with Imperfectly Shared Randomness
von: Canonne, Clément L., et al.
Veröffentlicht: (2014)

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

The PCP-like Theorem for Sub-linear Time Inapproximability
von: Ma, Hengzhao, et al.
Veröffentlicht: (2021)

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

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

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

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

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

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

New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs
von: Brakensiek, Joshua, et al.
Veröffentlicht: (2026)

Explicit optimal-length locally repairable codes of distance 5
von: Beemer, Allison, et al.
Veröffentlicht: (2018)

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)

Query Complexity with Unknowns
von: Mande, Nikhil S., et al.
Veröffentlicht: (2024)

Gap Amplification for Reconfiguration Problems
von: Ohsaka, Naoto
Veröffentlicht: (2023)

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

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

Information-Based Complexity vs Computational Complexity in Phaseless Polynomial Interpolation
von: Przybyłek, Michał R., et al.
Veröffentlicht: (2026)