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

Randomly Supported Independence and ResistancePrimeFaces.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});
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}); 2009 (English)In: STOC'09: PROCEEDINGS OF THE 2009 ACM SYMPOSIUM ON THEORY OF COMPUTING, NEW YORK: ASSOC COMPUTING MACHINERY , 2009, 483-492 p.Conference paper (Refereed)
##### Abstract [en]

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

NEW YORK: ASSOC COMPUTING MACHINERY , 2009. 483-492 p.
##### National Category

Computer Science
##### Identifiers

URN: urn:nbn:se:kth:diva-30772DOI: 10.1145/1536414.1536481ISI: 000268182000054ScopusID: 2-s2.0-70350701826ISBN: 978-1-60558-613-7OAI: oai:DiVA.org:kth-30772DiVA: diva2:404749
##### Conference

41st Annual ACM Symposium on Theory of Computing Bethesda, MD, MAY 31-JUN 02, 2009
#####

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

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

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

We prove that for any positive integer k, there is a constant C-k such that a randomly selected set of c(k)n(k) log n Boolean vectors with high probability supports a balanced k-wise independent distribution. In the case of k <= 2 a more elaborate argument, gives the strong-er bound ckn(k). Using a recent, result. by Austrin and Mossel this shows that a predicate on t, bits. Chosen at, random among predicates accepting c(2)t(2) input, vectors, is, assuming the Unique Games Conjecture, likely to be approximation resistant. These result's are close to tight,: we show that there are other constants, c(k)(1), such that a randomly selected set of points is unlikely to support a balanced k-wise. independent distribution and for some c > 0, a random predicate accepting ct(2)/log t input, vectors is is non-trivially approximable with high probability. In a different application of the result of Austrin and Mossel we prove that, again assuming the Unique Games Conjecture, any predicate on t bits accepting at least (32/33) - 2(t) inputs is approximation resistant. The results extend front the Boolean domain to larger finite domains.

QC 20110318

Available from: 2011-03-18 Created: 2011-03-04 Last updated: 2016-04-27Bibliographically approvedReferences$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_lower_j_idt1080",{id:"formSmash:lower:j_idt1080",widgetVar:"widget_formSmash_lower_j_idt1080",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:lower:referencesLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_lower_j_idt1081_j_idt1083",{id:"formSmash:lower:j_idt1081:j_idt1083",widgetVar:"widget_formSmash_lower_j_idt1081_j_idt1083",target:"formSmash:lower:j_idt1081:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});