Sublinear computing

Research output: Chapter in Book/Report/Conference proceedingConference 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 languageEnglish (US)
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditorsUri Zwick, Giuseppe di Battista
PublisherSpringer Verlag
Pages1
Number of pages1
ISBN (Print)3540200649, 9783540200642
DOIs
StatePublished - 2003
Event11th Annual European Symposium on Algorithms, ESA 2003 - Budapest, Hungary
Duration: Sep 16 2003Sep 19 2003

Publication series

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

Conference

Conference11th Annual European Symposium on Algorithms, ESA 2003
Country/TerritoryHungary
CityBudapest
Period9/16/039/19/03

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Sublinear computing'. Together they form a unique fingerprint.

Cite this