Deterministic algorithms for skewed matrix products

Konstantin Kutzkov

doi:10.4230/LIPIcs.STACS.2013.466

Deterministic algorithms for skewed matrix products

Konstantin Kutzkov

Research output: Journal Article or Conference Article in Journal › Journal article › Research › peer-review

Abstract

Recently, Pagh presented a randomized approximation algorithm for the multiplication of
real-valued matrices building upon work for detecting the most frequent items in data streams.
We continue this line of research and present new deterministic matrix multiplication algorithms.

Original language	English
Conference proceedings	Dagstuhl Seminar Proceedings
Number of pages	12
ISSN	1862-4405
DOIs	https://doi.org/10.4230/LIPIcs.STACS.2013.466
Publication status	Published - 2013

Keywords

approximate deterministic memory-efficient matrix multiplication

Access to Document

10.4230/LIPIcs.STACS.2013.466

http://www.itu.dk/people/konk/papers/dmm_stacs.pdf

MaDaMS: Massive Data Mining by Sampling
Pagh, R. (PI), Stöckel, M. (CoI) & Pham, N. D. (CoI)
Independent Research Fund Denmark
01/01/2011 → 31/12/2014
Project: Research

Cite this

@article{e578bba77c5f46c1846e19efb9788c76,

title = "Deterministic algorithms for skewed matrix products",

abstract = "Recently, Pagh presented a randomized approximation algorithm for the multiplication of real-valued matrices building upon work for detecting the most frequent items in data streams. We continue this line of research and present new deterministic matrix multiplication algorithms.",

keywords = "approximate deterministic memory-efficient matrix multiplication, approximate deterministic memory-efficient matrix multiplication",

author = "Konstantin Kutzkov",

note = "@inproceedings\{DBLP:conf/stacs/Kutzkov13, author = \{Konstantin Kutzkov\}, title = \{Deterministic algorithms for skewed matrix products\}, booktitle = \{STACS\}, year = \{2013\}, pages = \{466-477\}, ee = \{http://dx.doi.org/10.4230/LIPIcs.STACS.2013.466\}, crossref = \{DBLP:conf/stacs/2013\}, bibsource = \{DBLP, http://dblp.uni-trier.de\} \} @proceedings\{DBLP:conf/stacs/2013, editor = \{Natacha Portier and Thomas Wilke\}, title = \{30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013, February 27 - March 2, 2013, Kiel, Germany\}, booktitle = \{STACS\}, publisher = \{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik\}, series = \{LIPIcs\}, volume = \{20\}, year = \{2013\}, isbn = \{978-3-939897-50-7\}, ee = \{http://drops.dagstuhl.de/opus/portals/lipics/index.php?semnr=13002\}, bibsource = \{DBLP, http://dblp.uni-trier.de\} \} ",

year = "2013",

doi = "10.4230/LIPIcs.STACS.2013.466",

language = "English",

journal = "Dagstuhl Seminar Proceedings",

issn = "1862-4405",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH",

}

TY - JOUR

T1 - Deterministic algorithms for skewed matrix products

AU - Kutzkov, Konstantin

N1 - @inproceedings{DBLP:conf/stacs/Kutzkov13, author = {Konstantin Kutzkov}, title = {Deterministic algorithms for skewed matrix products}, booktitle = {STACS}, year = {2013}, pages = {466-477}, ee = {http://dx.doi.org/10.4230/LIPIcs.STACS.2013.466}, crossref = {DBLP:conf/stacs/2013}, bibsource = {DBLP, http://dblp.uni-trier.de} } @proceedings{DBLP:conf/stacs/2013, editor = {Natacha Portier and Thomas Wilke}, title = {30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013, February 27 - March 2, 2013, Kiel, Germany}, booktitle = {STACS}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}, series = {LIPIcs}, volume = {20}, year = {2013}, isbn = {978-3-939897-50-7}, ee = {http://drops.dagstuhl.de/opus/portals/lipics/index.php?semnr=13002}, bibsource = {DBLP, http://dblp.uni-trier.de} }

PY - 2013

Y1 - 2013

N2 - Recently, Pagh presented a randomized approximation algorithm for the multiplication of real-valued matrices building upon work for detecting the most frequent items in data streams. We continue this line of research and present new deterministic matrix multiplication algorithms.

AB - Recently, Pagh presented a randomized approximation algorithm for the multiplication of real-valued matrices building upon work for detecting the most frequent items in data streams. We continue this line of research and present new deterministic matrix multiplication algorithms.

KW - approximate deterministic memory-efficient matrix multiplication

U2 - 10.4230/LIPIcs.STACS.2013.466

DO - 10.4230/LIPIcs.STACS.2013.466

M3 - Journal article

SN - 1862-4405

JO - Dagstuhl Seminar Proceedings

JF - Dagstuhl Seminar Proceedings

ER -

Deterministic algorithms for skewed matrix products

Abstract

Keywords

Access to Document

Fingerprint

Projects

MaDaMS: Massive Data Mining by Sampling

Cite this