References$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_upper_j_idt152",{id:"formSmash:upper:j_idt152",widgetVar:"widget_formSmash_upper_j_idt152",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:upper:referencesLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt153_j_idt156",{id:"formSmash:upper:j_idt153:j_idt156",widgetVar:"widget_formSmash_upper_j_idt153_j_idt156",target:"formSmash:upper:j_idt153:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

Super-polylogarithmic hypergraph coloring hardness via low-degree long codesPrimeFaces.cw("AccordionPanel","widget_formSmash_some",{id:"formSmash:some",widgetVar:"widget_formSmash_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_all",{id:"formSmash:all",widgetVar:"widget_formSmash_all",multiple:true}); PrimeFaces.cw("SelectBooleanButton","widget_formSmash_j_idt197",{id:"formSmash:j_idt197",widgetVar:"widget_formSmash_j_idt197",onLabel:"Hide others and affiliations",offLabel:"Show others and affiliations"});
function selectAll()
{
var panelSome = $(PrimeFaces.escapeClientId("formSmash:some"));
var panelAll = $(PrimeFaces.escapeClientId("formSmash:all"));
panelAll.toggle();
toggleList(panelSome.get(0).childNodes, panelAll);
toggleList(panelAll.get(0).childNodes, panelAll);
}
/*Toggling the list of authorPanel nodes according to the toggling of the closeable second panel */
function toggleList(childList, panel)
{
var panelWasOpen = (panel.get(0).style.display == 'none');
// console.log('panel was open ' + panelWasOpen);
for (var c = 0; c < childList.length; c++) {
if (childList[c].classList.contains('authorPanel')) {
clickNode(panelWasOpen, childList[c]);
}
}
}
/*nodes have styleClass ui-corner-top if they are expanded and ui-corner-all if they are collapsed */
function clickNode(collapse, child)
{
if (collapse && child.classList.contains('ui-corner-top')) {
// console.log('collapse');
child.click();
}
if (!collapse && child.classList.contains('ui-corner-all')) {
// console.log('expand');
child.click();
}
}
PrimeFaces.cw("AccordionPanel","widget_formSmash_responsibleOrgs",{id:"formSmash:responsibleOrgs",widgetVar:"widget_formSmash_responsibleOrgs",multiple:true}); 2014 (English)In: Proceedings of the Annual ACM Symposium on Theory of Computing, 2014, 614-623 p.Conference paper (Refereed)
##### Abstract [en]

##### Place, publisher, year, edition, pages

2014. 614-623 p.
##### Series

, Proceedings of the Annual ACM Symposium on Theory of Computing, ISSN 0737-8017
##### Keyword [en]

Hardness of approximation, Hypergraph coloring, Short code, Codes (symbols), Color, Coloring, Forward error correction, Fourier analysis, Hardness, Number theory, Binary Reed-Muller codes, Fourier coefficients, Pseudo-random properties, Quantitative bounds, Short codes, Structural restrictions, Graph theory
##### National Category

Computer Science
##### Identifiers

URN: urn:nbn:se:kth:diva-167512DOI: 10.1145/2591796.2591882ScopusID: 2-s2.0-84904294260ISBN: 9781450327107OAI: oai:DiVA.org:kth-167512DiVA: diva2:819762
##### Conference

4th Annual ACM Symposium on Theory of Computing, STOC 2014, 31 May 2014 through 3 June 2014, New York, NY
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt455",{id:"formSmash:j_idt455",widgetVar:"widget_formSmash_j_idt455",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt461",{id:"formSmash:j_idt461",widgetVar:"widget_formSmash_j_idt461",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt467",{id:"formSmash:j_idt467",widgetVar:"widget_formSmash_j_idt467",multiple:true});
##### Note

We prove improved inapproximability results for hypergraph coloring using the low-degree polynomial code (aka, the"short code" of Barak et. al. [FOCS 2012]) and the techniques pro-posed by Dinur and Guruswami [FOCS 2013] to incorporatethis code for inapproximability results. In particular, we prove quasi-NP-hardness of the following problems on n-vertex hypergraphs: • Coloring a 2-colorable 8-uniform hypergraph with 2 2Ω(√log log n) colors. • Coloring a 4-colorable 4-uniform hypergraph with 22Ω(√ log log n) colors. • Coloring a 3-colorable 3-uniform hypergraph with (log n) Ω(1√ log log log n) colors. In each of these cases, the hardness results obtained are (at least) superpolynomially stronger (if not exponentially stronger as in the third case) than what was previously known for the respective cases. In fact, prior to this result, (log n)O(1) colors was the strongest quantitative bound on the number of colors ruled out by inapproximability results for O(1)-colorable hypergraphs. The fundamental bottleneck in obtaining coloring in approximability results using the low-degree long code was a ultipartite structural restriction in the PCP construction of Dinur-Guruswami. We are able to get around this restriction by simulating the multipartite structure implicitly by querying just one partition (albeit requiring 8 queries), which yields our result for 2-colorable 8-uniform hypergraphs. The result for 4-colorable 4-uniform hypergraphs is obtained via a "query doubling" method exploiting additional properties of the 8-query test. For 3-colorable 3-uniform hyper-graphs, we exploit the ternary domain to design a test with an additive (as opposed to multiplicative) noise function, and analyze its efficacy in killing high weight Fourier coefficients via the pseudorandom properties of an associated quadratic form. The latter step involves extending the key algebraic ingredient of Dinur-Guruswami concerning testing binary Reed-Muller codes to the ternary alphabet.

QC 20150611

Available from: 2015-06-11 Created: 2015-05-22 Last updated: 2015-06-11Bibliographically approvedReferences$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_lower_j_idt1196",{id:"formSmash:lower:j_idt1196",widgetVar:"widget_formSmash_lower_j_idt1196",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:lower:referencesLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_lower_j_idt1197_j_idt1199",{id:"formSmash:lower:j_idt1197:j_idt1199",widgetVar:"widget_formSmash_lower_j_idt1197_j_idt1199",target:"formSmash:lower:j_idt1197:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});