Copertina

Strong Inapproximability for a Promise Rank Problem

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Guruswami, Venkatesan, Ren, Xuandi, Tang, Shaoxuan
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

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

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

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

Scheduling Problems with Constrained Rejections
di: Davies, Sami, et al.
Pubblicazione: (2025)

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

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

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

New constructions of pseudorandom codes
di: Ghentiyala, Surendra, et al.
Pubblicazione: (2024)

Structure Theorems (and Fast Algorithms) for List Recovery of Subspace-Design Codes
di: Goyal, Rohan, et al.
Pubblicazione: (2025)

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

Punctured Low-Bias Codes Behave Like Random Linear Codes
di: Guruswami, Venkatesan, et al.
Pubblicazione: (2021)

Classification of Non-redundancy of Boolean Predicates of Arity 4
di: Brakensiek, Joshua, et al.
Pubblicazione: (2026)

New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs
di: Brakensiek, Joshua, et al.
Pubblicazione: (2026)

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

Hardness of Learning Boolean Functions from Label Proportions
di: Guruswami, Venkatesan, et al.
Pubblicazione: (2024)

$\ell_p$-Spread and Restricted Isometry Properties of Sparse Random Matrices
di: Guruswami, Venkatesan, et al.
Pubblicazione: (2021)

Explicit Constant-Alphabet Subspace Design Codes
di: Goyal, Rohan, et al.
Pubblicazione: (2026)

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

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

Communication with Imperfectly Shared Randomness
di: Canonne, Clément L., et al.
Pubblicazione: (2014)

Constant Inapproximability for PPA
di: Deligkas, Argyrios, et al.
Pubblicazione: (2022)

The PCP-like Theorem for Sub-linear Time Inapproximability
di: Ma, Hengzhao, et al.
Pubblicazione: (2021)

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

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

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

Constant Inapproximability for Fisher Markets
di: Deligkas, Argyrios, et al.
Pubblicazione: (2026)

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

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

Explicit optimal-length locally repairable codes of distance 5
di: Beemer, Allison, et al.
Pubblicazione: (2018)

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

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

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

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

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

The Richness of CSP Non-redundancy
di: Brakensiek, Joshua, et al.
Pubblicazione: (2025)

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

Tight Inapproximability of Target Set Reconfiguration
di: Ohsaka, Naoto
Pubblicazione: (2024)

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

The Complexity of Promise Constraint Satisfaction Problem Seen from the Other Side
di: Asimi, Kristina, et al.
Pubblicazione: (2024)