CiteExport$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_upper_j_idt144",{id:"formSmash:upper:j_idt144",widgetVar:"widget_formSmash_upper_j_idt144",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:upper:exportLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt145_j_idt147",{id:"formSmash:upper:j_idt145:j_idt147",widgetVar:"widget_formSmash_upper_j_idt145_j_idt147",target:"formSmash:upper:j_idt145:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

Simulation Beats Richness: New Data-Structure Lower BoundsPrimeFaces.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();
}
}
2018 (English)In: STOC'18: PROCEEDINGS OF THE 50TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING / [ed] Diakonikolas, I Kempe, D Henzinger, M, ASSOC COMPUTING MACHINERY , 2018, p. 1013-1020Conference paper, Published paper (Refereed)
##### Abstract [en]

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

ASSOC COMPUTING MACHINERY , 2018. p. 1013-1020
##### Keywords [en]

Communication complexity, data structures, lifting theorem, simulation theorem, richness method, vector-matrix-vector product
##### National Category

Computational Mathematics
##### Identifiers

URN: urn:nbn:se:kth:diva-244579DOI: 10.1145/3188745.3188874ISI: 000458175600087Scopus ID: 2-s2.0-85049876529OAI: oai:DiVA.org:kth-244579DiVA, id: diva2:1294158
##### Conference

50th Annual ACM Symposium on Theory of Computing, STOC 2018; Los Angeles; United States; 25 June 2018 through 29 June 2018
#####

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

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

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

We develop a technique for proving lower bounds in the setting of asymmetric communication, a model that was introduced in the famous works of Miltersen (STOC'94) and Miltersen, Nisan, Safra and Wigderson (STOC'95). At the core of our technique is a novel simulation theorem: Alice gets a p x n matrix x over F-2 and Bob gets a vector y is an element of F-2(n). Alice and Bob need to evaluate f (x center dot y) for a Boolean function f : {0, 1}(p) -> {0, 1}. Our simulation theorems show that a deterministic/randomized communication protocol exists for this problem, with cost C center dot n for Alice and C for Bob, if and only if there exists a deterministic/randomized parity decision tree of cost Theta As applications of this technique, we obtain the following results: (i) The first strong lower-bounds against randomized data-structure schemes for the Vector-Matrix-Vector product problem over F-2. Moreover, our method yields strong lower bounds even when the data-structure scheme has tiny advantage over random guessing. (ii) The first lower bounds against randomized data-structures schemes for two natural Boolean variants of Orthogonal Vector Counting. (iii) We construct an asymmetric communication problem and obtain a deterministic lower-bound for it which is provably better than any lower-bound that may be obtained by the classical Richness Method of Miltersen et al.. This seems to be the first known limitation of the Richness Method in the context of proving deterministic lower bounds.

QC 20190306

Available from: 2019-03-06 Created: 2019-03-06 Last updated: 2019-03-06Bibliographically approved
doi
urn-nbn$(function(){PrimeFaces.cw("Tooltip","widget_formSmash_j_idt1156",{id:"formSmash:j_idt1156",widgetVar:"widget_formSmash_j_idt1156",showEffect:"fade",hideEffect:"fade",showDelay:500,hideDelay:300,target:"formSmash:altmetricDiv"});});

CiteExport$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_lower_j_idt1209",{id:"formSmash:lower:j_idt1209",widgetVar:"widget_formSmash_lower_j_idt1209",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:lower:exportLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_lower_j_idt1210_j_idt1212",{id:"formSmash:lower:j_idt1210:j_idt1212",widgetVar:"widget_formSmash_lower_j_idt1210_j_idt1212",target:"formSmash:lower:j_idt1210:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});