Sublinear computing

Bernard Chazelle

doi:10.1007/978-3-540-39658-1_1

Sublinear computing

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Denied preprocessing and limited to a tiny fraction of the input, what can a computer hope to do? Surprisingly much, it turn sout. A blizzard of recent results in property testing, streaming, and sublinear approximation algorithms have shown that, for a large class ofproblems, all but a vanishing fraction of the input data is essentially unnecessary. While grounding the discussion on a few specific examples, I will review some of the basic principles at play behind this “sublinearity” phenomenon.

Original language	English (US)
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Editors	Uri Zwick, Giuseppe di Battista
Publisher	Springer Verlag
Pages	1
Number of pages	1
ISBN (Print)	3540200649, 9783540200642
DOIs	https://doi.org/10.1007/978-3-540-39658-1_1
State	Published - 2003
Externally published	Yes
Event	11th Annual European Symposium on Algorithms, ESA 2003 - Budapest, Hungary Duration: Sep 16 2003 → Sep 19 2003

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2832
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	11th Annual European Symposium on Algorithms, ESA 2003
Country/Territory	Hungary
City	Budapest
Period	9/16/03 → 9/19/03

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-540-39658-1_1

Cite this

Chazelle, B. (2003). Sublinear computing. In U. Zwick, & G. di Battista (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 1). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2832). Springer Verlag. https://doi.org/10.1007/978-3-540-39658-1_1

Chazelle, Bernard. / Sublinear computing. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). editor / Uri Zwick ; Giuseppe di Battista. Springer Verlag, 2003. pp. 1 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{248667336a8d4ee095e4c59fd814516c,

title = "Sublinear computing",

abstract = "Denied preprocessing and limited to a tiny fraction of the input, what can a computer hope to do? Surprisingly much, it turn sout. A blizzard of recent results in property testing, streaming, and sublinear approximation algorithms have shown that, for a large class ofproblems, all but a vanishing fraction of the input data is essentially unnecessary. While grounding the discussion on a few specific examples, I will review some of the basic principles at play behind this “sublinearity” phenomenon.",

author = "Bernard Chazelle",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2003.; 11th Annual European Symposium on Algorithms, ESA 2003 ; Conference date: 16-09-2003 Through 19-09-2003",

year = "2003",

doi = "10.1007/978-3-540-39658-1_1",

language = "English (US)",

isbn = "3540200649",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "1",

editor = "Uri Zwick and {di Battista}, Giuseppe",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

address = "Germany",

}

Chazelle, B 2003, Sublinear computing. in U Zwick & G di Battista (eds), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2832, Springer Verlag, pp. 1, 11th Annual European Symposium on Algorithms, ESA 2003, Budapest, Hungary, 9/16/03. https://doi.org/10.1007/978-3-540-39658-1_1

Sublinear computing. / Chazelle, Bernard.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). ed. / Uri Zwick; Giuseppe di Battista. Springer Verlag, 2003. p. 1 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2832).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Sublinear computing

AU - Chazelle, Bernard

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2003.

PY - 2003

Y1 - 2003

N2 - Denied preprocessing and limited to a tiny fraction of the input, what can a computer hope to do? Surprisingly much, it turn sout. A blizzard of recent results in property testing, streaming, and sublinear approximation algorithms have shown that, for a large class ofproblems, all but a vanishing fraction of the input data is essentially unnecessary. While grounding the discussion on a few specific examples, I will review some of the basic principles at play behind this “sublinearity” phenomenon.

AB - Denied preprocessing and limited to a tiny fraction of the input, what can a computer hope to do? Surprisingly much, it turn sout. A blizzard of recent results in property testing, streaming, and sublinear approximation algorithms have shown that, for a large class ofproblems, all but a vanishing fraction of the input data is essentially unnecessary. While grounding the discussion on a few specific examples, I will review some of the basic principles at play behind this “sublinearity” phenomenon.

UR - http://www.scopus.com/inward/record.url?scp=0142245902&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0142245902&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-39658-1_1

DO - 10.1007/978-3-540-39658-1_1

M3 - Conference contribution

AN - SCOPUS:0142245902

SN - 3540200649

SN - 9783540200642

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 1

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - Zwick, Uri

A2 - di Battista, Giuseppe

PB - Springer Verlag

T2 - 11th Annual European Symposium on Algorithms, ESA 2003

Y2 - 16 September 2003 through 19 September 2003

ER -

Chazelle B. Sublinear computing. In Zwick U, di Battista G, editors, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag. 2003. p. 1. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-39658-1_1

Sublinear computing

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this