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 Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

In this paper, we address the question of whether the recent derandomizationresults obtained by the use of the low-degree long code can be extended toother product settings. We consider two settings: (1) the graph product resultsof Alon, Dinur, Friedgut and Sudakov [GAFA, 2004] and (2) the "majority isstablest" type of result obtained by Dinur, Mossel and Regev [SICOMP, 2009] andDinur and Shinkar [In Proc. APPROX, 2010] while studying the hardness ofapproximate graph coloring.  In our first result, we show that there exists a considerably smallersubgraph of $K_3^{\otimes R}$ which exhibits the following property (shown for$K_3^{\otimes R}$ by Alon et al.): independent sets close in size to themaximum independent set are well approximated by dictators.  The "majority is stablest" type of result of Dinur et al. and Dinur andShinkar shows that if there exist two sets of vertices $A$ and $B$ in$K_3^{\otimes R}$ with very few edges with one endpoint in $A$ and another in$B$, then it must be the case that the two sets $A$ and $B$ share a singleinfluential coordinate. In our second result, we show that a similar "majorityis stablest" statement holds good for a considerably smaller subgraph of$K_3^{\otimes R}$. Furthermore using this result, we give a more efficientreduction from Unique Games to the graph coloring problem, leading to improvedhardness of approximation results for coloring.

Derandomized Graph Product Results using the Low Degree Long Code