The Library
Coarse-grained complexity for dynamic algorithms
Tools
Bhattacharya, Sayan, Nanongkai, Danupon and Saranurak, Thatchaphol (2020) Coarse-grained complexity for dynamic algorithms. In: 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Salt Lake City, Utah, U.S., 5-8 Jan 2020. Published in: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) pp. 476-494. ISBN 9781611975994. doi:10.1137/1.9781611975994.29
|
PDF
WRAP-coarse-grained-complexity-dynamic-algorithms-Bhattacharya-2020.pdf - Accepted Version - Requires a PDF viewer. Download (1022Kb) | Preview |
Official URL: https://doi.org/10.1137/1.9781611975994.29
Abstract
To date, the only way to argue polynomial lower bounds for dynamic algorithms is via fine-grained complexity arguments. These arguments rely on strong assumptions about specific problems such as the Strong Exponential Time Hypothesis (SETH) and the Online Matrix-Vector Multiplication Conjecture (OMv). While they have led to many exciting discoveries, dynamic algorithms still miss out some benefits and lessons from the traditional “coarse-grained” approach that relates together classes of problems such as P and NP. In this paper we initiate the study of coarse-grained complexity theory for dynamic algorithms. Below are among questions that this theory can answer.
Item Type: | Conference Item (Paper) | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | |||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||
Library of Congress Subject Headings (LCSH): | Computer algorithms, Computational complexity | |||||||||
Journal or Publication Title: | Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) | |||||||||
Publisher: | Society for Industrial and Applied Mathematics | |||||||||
ISBN: | 9781611975994 | |||||||||
Official Date: | January 2020 | |||||||||
Dates: |
|
|||||||||
Page Range: | pp. 476-494 | |||||||||
DOI: | 10.1137/1.9781611975994.29 | |||||||||
Status: | Peer Reviewed | |||||||||
Publication Status: | Published | |||||||||
Reuse Statement (publisher, data, author rights): | Published in Proceedings of ACM-SIAM Symposium on Discrete Algorithms, published by the Society for Industrial and Applied Mathematics (SIAM) Copyright © 2020 by SIAM. Unauthorized reproduction of this article is prohibited. | |||||||||
Access rights to Published version: | Restricted or Subscription Access | |||||||||
Date of first compliant deposit: | 28 November 2019 | |||||||||
Date of first compliant Open Access: | 2 December 2019 | |||||||||
RIOXX Funder/Project Grant: |
|
|||||||||
Conference Paper Type: | Paper | |||||||||
Title of Event: | 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) | |||||||||
Type of Event: | Conference | |||||||||
Location of Event: | Salt Lake City, Utah, U.S. | |||||||||
Date(s) of Event: | 5-8 Jan 2020 | |||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year