Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




Author, Editor

Author(s):

Milosavljevic, Nikola
Morozov, Dmitriy
Skraba, Primoz

dblp
dblp
dblp

Not MPG Author(s):

Morozov, Dmitriy
Skraba, Primoz

Editor(s):





BibTeX cite key*:

Milosavljevic2011Zigzag

Title, Booktitle

Title*:

Zigzag Persistent Homology in Matrix Multiplication Time

Booktitle*:

Proceedings of the 27th Annual Symposium on Computational Geometry (SCG'11)

Event, URLs

URL of the conference:

http://socg2011.inria.fr/

URL for downloading the paper:

http://doi.acm.org/10.1145/1998196.1998229

Event Address*:

Paris, France

Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

13 June 2011

Event End Date:

15 June 2011

Publisher

Name*:

ACM

URL:


Address*:

New York, NY

Type:


Vol, No, Year, pp.

Series:


Volume:


Number:


Month:

June

Pages:

216-225

Year*:

2011

VG Wort Pages:


ISBN/ISSN:

978-1-4503-0682-9

Sequence Number:


DOI:

10.1145/1998196.1998229



Note, Abstract, ©


(LaTeX) Abstract:

We present a new algorithm for computing zigzag persistent homology, an algebraic structure which encodes changes to homology groups of a simplicial complex over a sequence of simplex additions and deletions. Provided that there is an algorithm that multiplies two $n \times n$ matrices in $M(n)$ time, our algorithm runs in $O(M(n) + n^2 \log^2 n)$ time for a sequence of $n$ additions and deletions. In particular, the running time is $O(n^{2.376})$, by result of Coppersmith and Winograd. The fastest previously known algorithm for this problem
takes $O(n^3)$ time in the worst case.

Keywords:

Zigzag persistent homology, matrix multiplication.

Copyright Message:

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
Copyright 2011 ACM 978-1-4503-0682-9/11/06 ....$10.00.


Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Milosavljevic2011Zigzag,
AUTHOR = {Milosavljevic, Nikola and Morozov, Dmitriy and Skraba, Primoz},
TITLE = {Zigzag Persistent Homology in Matrix Multiplication Time},
BOOKTITLE = {Proceedings of the 27th Annual Symposium on Computational Geometry (SCG'11)},
PUBLISHER = {ACM},
YEAR = {2011},
PAGES = {216--225},
ADDRESS = {Paris, France},
MONTH = {June},
ISBN = {978-1-4503-0682-9},
DOI = {10.1145/1998196.1998229},
}


Entry last modified by Jennifer Müller, 05/11/2012
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
03/22/2011 09:53:12 PM
Revisions
5.
4.
3.
2.
1.
Editor(s)
Jennifer Müller
Anja Becker
Anja Becker
Nikola Milosavljevic
Nikola Milosavljevic
Edit Dates
11.05.2012 15:33:09
13.02.2012 14:27:38
13.02.2012 14:26:35
03/22/2011 10:54:43 PM
03/22/2011 09:56:02 PM
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section