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

This work revisits the PCP Verifiers used in the works of Hastad [Has01],Guruswami et al.[GHS02], Holmerin[Hol02] and Guruswami[Gur00] for satisfiableMax-E3-SAT and Max-Ek-Set-Splitting, and independent set in 2-colorable4-uniform hypergraphs. We provide simpler and more efficient PCP Verifiers toprove the following improved hardness results: Assuming that NP\not\subseteqDTIME(N^{O(loglog N)}),  There is no polynomial time algorithm that, given an n-vertex 2-colorable4-uniform hypergraph, finds an independent set of n/(log n)^c vertices, forsome constant c > 0.  There is no polynomial time algorithm that satisfies 7/8 + 1/(log n)^cfraction of the clauses of a satisfiable Max-E3-SAT instance of size n, forsome constant c > 0.  For any fixed k >= 4, there is no polynomial time algorithm that finds apartition splitting (1 - 2^{-k+1}) + 1/(log n)^c fraction of the k-sets of asatisfiable Max-Ek-Set-Splitting instance of size n, for some constant c > 0.  Our hardness factor for independent set in 2-colorable 4-uniform hypergraphsis an exponential improvement over the previous results of Guruswami etal.[GHS02] and Holmerin[Hol02]. Similarly, our inapproximability of (logn)^{-c} beyond the random assignment threshold for Max-E3-SAT andMax-Ek-Set-Splitting is an exponential improvement over the previous boundsproved in [Has01], [Hol02] and [Gur00]. The PCP Verifiers used in our resultsavoid the use of a variable bias parameter used in previous works, which leadsto the improved hardness thresholds in addition to simplifying the analysissubstantially. Apart from standard techniques from Fourier Analysis, for thefirst mentioned result we use a mixing estimate of Markov Chains based onuniform reverse hypercontractivity over general product spaces from the work ofMossel et al.[MOS13].

Hardness of Finding Independent Sets in 2-Colorable Hypergraphs and of Satisfiable CSPs