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/

Zendy Plus

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

Zendy Tools

Zendy Open

In 1997, Håstad showed NP-hardness of (1 − &epsi;, 1&sol;q &plus; δ)-approximating Max-3Lin(Zq); however, it was not until 2007 that Guruswami and Raghavendra were able to show NP-hardness of (1 − &epsi;, δ)-approximating Max-3Lin(Z). In 2004, Khot--Kindler--Mossel--O’Donnell showed UG-hardness of (1 − &epsi;, δ)-approximating Max-2Lin(Zq) for q &equals; q(&epsi;, δ) a sufficiently large constant; however, achieving the same hardness for Max-2Lin(Z) was given as an open problem in Raghavendra’s 2009 thesis. In this work, we show that fairly simple modifications to the proofs of the Max-3Lin(Zq) and Max-2Lin(Zq) results yield optimal hardness results over Z. In fact, we show a kind of “bicriteria” hardness: Even when there is a (1 − &epsi;)-good solution over Z, it is hard for an algorithm to find a δ-good solution over Z, R, or Zm for any m &ges; q(&epsi;, δ) of the algorithm’s choosing.

Hardness of Max-2Lin and Max-3Lin over Integers, Reals, and Large Cyclic Groups