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});});

Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication ConjecturePrimeFaces.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}); 2015 (English)In: STOC '15 Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, ACM Press, 2015, p. 21-30Conference paper, Published paper (Refereed)
##### Abstract [en]

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

ACM Press, 2015. p. 21-30
##### National Category

Computer Sciences
##### Identifiers

URN: urn:nbn:se:kth:diva-165846DOI: 10.1145/2746539.2746609Scopus ID: 2-s2.0-84958762655OAI: oai:DiVA.org:kth-165846DiVA, id: diva2:808913
##### Conference

STOC 2015: 47th Annual Symposium on the Theory of Computing,Portland, OR, June 15 - June 17 2015
#####

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

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

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

Consider the following *Online Boolean Matrix-Vector Multiplication* problem: We are given an n x n matrix M and will receive n column-vectors of size n, denoted by v_{1}, ..., v_{n}, one by one. After seeing each vector v_{i}, we have to output the product Mv_{i} before we can see the next vector. A naive algorithm can solve this problem using O(n^{3}) time in total, and its running time can be slightly improved to O(n^{3}/log^{2} n) [Williams SODA'07]. We show that a conjecture that there is no *truly subcubic* (O(n^{3-ε})) time algorithm for this problem can be used to exhibit the underlying polynomial time hardness shared by many dynamic problems. For a number of problems, such as subgraph connectivity, Pagh's problem, d-failure connectivity, decremental single-source shortest paths, and decremental transitive closure, this conjecture implies tight hardness results. Thus, proving or disproving this conjecture will be very interesting as it will either imply several tight unconditional lower bounds or break through a common barrier that blocks progress with these problems. This conjecture might also be considered as strong evidence against any further improvement for these problems since refuting it will imply a major breakthrough for combinatorial Boolean matrix multiplication and other long-standing problems if the term "combinatorial algorithms" is interpreted as "Strassen-like algorithms" [Ballard et al. SPAA'11].

The conjecture also leads to hardness results for problems that were previously based on diverse problems and conjectures -- such as 3SUM, combinatorial Boolean matrix multiplication, triangle detection, and multiphase -- thus providing a uniform way to prove polynomial hardness results for dynamic algorithms; some of the new proofs are also simpler or even become trivial. The conjecture also leads to stronger and new, non-trivial, hardness results, e.g., for the fully-dynamic densest subgraph and diameter problems.

QC 20150811

Available from: 2015-04-29 Created: 2015-04-29 Last updated: 2018-01-11Bibliographically approved
doi
urn-nbn$(function(){PrimeFaces.cw("Tooltip","widget_formSmash_j_idt1256",{id:"formSmash:j_idt1256",widgetVar:"widget_formSmash_j_idt1256",showEffect:"fade",hideEffect:"fade",showDelay:500,hideDelay:300,target:"formSmash:altmetricDiv"});});

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