max planck institut

informatik

informatik

<< Previous Entry | Next Entry >> | New Event Entry | Edit this Entry | Login to DB (to update, delete) |

Title: | Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture |
---|---|

Speaker: | Thatchaphol Saranurak |

coming from: | KTH Royal Institute of Technology, Sweden |

Speakers Bio: | |

Event Type: | AG1 Mittagsseminar (own work) |

Visibility: | D1, D2, D3, D4, D5, RG1, SWS, MMCI We use this to send out email in the morning. |

Level: | AG Audience |

Language: | English |

Date: | Thursday, 23 July 2015 |
---|---|

Time: | 13:00 |

Duration: | 30 Minutes |

Location: | Saarbrücken |

Building: | E1 4 |

Room: | 024 |

Consider the following Online Boolean Matrix-Vector Multiplication problem: We are given an n × 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− eps} )) 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 longstanding problems if the term “combinatorial algorithms” is interpreted as “Strassen-like algorithms” [Ballard et al. SPAA’11]. |

Name(s): | Parinya Chalermsook |
---|

Video Broadcast: | No | To Location: |
---|

Note: | |
---|---|

Attachments, File(s): |

Created: | Parinya Chalermsook, 07/03/2015 12:01 PM | Last modified: | Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM |

- Parinya Chalermsook, 07/03/2015 12:01 PM -- Created document.