English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

A seminal result of H\r{a}stad [J. ACM, 48(4):798--859, 2001] shows that itis NP-hard to find an assignment that satisfies $\frac{1}{|G|}+\varepsilon$fraction of the constraints of a given $k$-LIN instance over an abelian group,even if there is an assignment that satisfies $(1-\varepsilon)$ fraction of theconstraints, for any constant $\varepsilon>0$. Engebretsen et al. [TheoreticalComputer Science, 312(1):17--45, 2004] later showed that the same hardnessresult holds for $k$-LIN instances over any finite non-abelian group.  Unlike the abelian case, where we can efficiently find a solution if theinstance is satisfiable, in the non-abelian case, it is NP-complete to decideif a given system of linear equations is satisfiable or not, as shown byGoldmann and Russell [Information and Computation, 178(1):253--262. 2002].  Surprisingly, for certain non-abelian groups $G$, given a satisfiable $k$-LINinstance over $G$, one can in fact do better than just outputting a randomassignment using a simple but clever algorithm. The approximation factorachieved by this algorithm varies with the underlying group. In this paper, weshow that this algorithm is {\em optimal} by proving a tight hardness ofapproximation of satisfiable $k$-LIN instance over {\em any} non-abelian $G$,assuming $P \neq NP$.  As a corollary, we also get $3$-query probabilistically checkable proofs withperfect completeness over large alphabets with improved soundness.

Optimal Inapproximability of Satisfiable $k$-LIN over Non-Abelian Groups