Image de couverture de livre

Optimal Inapproximability of Generalized Linear Equations over a Finite Group

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Bhangale, Amey, Zhang, Yezhou
Format:	Preprint
Publié:	2026
Sujets:	Computational Complexity
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Optimal Inapproximability of Promise Equations over Finite Groups
par: Butti, Silvia, et autres
Publié: (2024)

On Approximability of Satisfiable k-CSPs: V
par: Bhangale, Amey, et autres
Publié: (2024)

On Approximability of Satisfiable k-CSPs: IV
par: Bhangale, Amey, et autres
Publié: (2023)

On Approximability of Satisfiable $k$-CSPs: VI
par: Bhangale, Amey, et autres
Publié: (2024)

On Approximability of Satisfiable $k$-CSPs: VII
par: Bhangale, Amey, et autres
Publié: (2024)

Reasonable Bounds for Combinatorial Lines of Length Three
par: Bhangale, Amey, et autres
Publié: (2024)

An Analytical Approach to Parallel Repetition via CSP Inverse Theorems
par: Bhangale, Amey, et autres
Publié: (2025)

Parallel Repetition for $3$-Player XOR Games
par: Bhangale, Amey, et autres
Publié: (2024)

Strong Inapproximability for a Promise Rank Problem
par: Guruswami, Venkatesan, et autres
Publié: (2026)

A 4.509-Approximation Algorithm for Generalized Min Sum Set Cover
par: Bhangale, Amey, et autres
Publié: (2026)

Baby PIH: Parameterized Inapproximability of Min CSP
par: Guruswami, Venkatesan, et autres
Publié: (2023)

Constant Inapproximability for PPA
par: Deligkas, Argyrios, et autres
Publié: (2022)

Equations over Finite Monoids with Infinite Promises
par: Larrauri, Alberto, et autres
Publié: (2025)

The PCP-like Theorem for Sub-linear Time Inapproximability
par: Ma, Hengzhao, et autres
Publié: (2021)

Almost Polynomial Factor Inapproximability for Parameterized k-Clique
par: S., Karthik C., et autres
Publié: (2021)

Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration
par: Hirahara, Shuichi, et autres
Publié: (2025)

Asymptotically Optimal Inapproximability of Maxmin $k$-Cut Reconfiguration
par: Hirahara, Shuichi, et autres
Publié: (2024)

Constant Inapproximability for Fisher Markets
par: Deligkas, Argyrios, et autres
Publié: (2026)

Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all $\ell_p$ Norms
par: Bennett, Huck, et autres
Publié: (2022)

Pure-Circuit: Tight Inapproximability for PPAD
par: Deligkas, Argyrios, et autres
Publié: (2022)

Inapproximability of the independent set polynomial in the complex plane
par: Bezakova, Ivona, et autres
Publié: (2017)

Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and Lattices
par: Bhattiprolu, Vijay, et autres
Publié: (2024)

PCPP-Based Reconfiguration Inapproximability: Query Complexity vs. Soundness Gap Trade-offs
par: Guruswami, Venkatesan, et autres
Publié: (2025)

Treedepth Inapproximability and Exponential ETH Lower Bound
par: Bonnet, Édouard, et autres
Publié: (2025)

Tight Inapproximability of Nash Equilibria in Public Goods Games
par: Dinh, Jérémi Do, et autres
Publié: (2024)

Constant Inapproximability of Pacing Equilibria in Second-Price Auctions
par: Chen, Xi, et autres
Publié: (2025)

Inapproximability of Maximum Diameter Clustering for Few Clusters
par: Fleischmann, Henry, et autres
Publié: (2023)

On the Inapproximability of Finding Minimum Monitoring Edge-Geodetic Sets
par: Bilò, Davide, et autres
Publié: (2024)

Superconstant Inapproximability of Decision Tree Learning
par: Koch, Caleb, et autres
Publié: (2024)

Tight Inapproximability of Target Set Reconfiguration
par: Ohsaka, Naoto
Publié: (2024)

Can Almost Everybody be Almost Happy? PCP for PPAD and the Inapproximability of Nash
par: Babichenko, Yakov, et autres
Publié: (2015)

From Chinese Postman to Salesman and Beyond II: Inapproximability and Parameterized Complexity
par: Frei, Fabian, et autres
Publié: (2025)

Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems
par: Hirahara, Shuichi, et autres
Publié: (2023)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
par: Guruswami, Venkatesan, et autres
Publié: (2023)

On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
par: S., Karthik C., et autres
Publié: (2024)

Low-Rank Tensor Decomposition over Finite Fields
par: Yang, Jason
Publié: (2024)

Local Correction of Linear Functions over the Boolean Cube
par: Amireddy, Prashanth, et autres
Publié: (2024)

On the Computation of the Zariski Closure of Finitely Generated Groups of Matrices
par: Nosan, Klara, et autres
Publié: (2021)

Resolution Over Linear Equations: Combinatorial Games for Tree-like Size and Space
par: Gryaznov, Svyatoslav, et autres
Publié: (2024)

Tight Quantum Depth Lower Bound for Solving Systems of Linear Equations
par: Wang, Qisheng, et autres
Publié: (2024)