The art of shaving logs

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

There have been many instances in the literature where an algorithm with running time of the form O(na) is improved to an algorithm with running time O(na / logb n) for some constants a and b. The "four Russians" algorithm for Boolean matrix multiplication is perhaps one of the most well known examples. In this talk, we will look at a few selected recent examples of this phenomenon, including the 3-SUM problem, the problem of detecting affine degeneracy in a point set, Klee's measure problem, and the all-pairs shortest paths problem. (The selection is not comprehensive but is biased towards the speaker's own expertise.) Bit tricks, table lookups, and constructions of small decision trees are used to achieve many of these polylogarithmic-factor speedups, but often the applications of these techniques require interesting ideas.

Original languageEnglish (US)
Title of host publicationAlgorithms and Data Structures - 13th International Symposium, WADS 2013, Proceedings
Number of pages1
DOIs
StatePublished - Aug 12 2013
Externally publishedYes
Event13th International Symposium on Algorithms and Data Structures, WADS 2013 - London, ON, Canada
Duration: Aug 12 2013Aug 14 2013

Publication series

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

Other

Other13th International Symposium on Algorithms and Data Structures, WADS 2013
CountryCanada
CityLondon, ON
Period8/12/138/14/13

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'The art of shaving logs'. Together they form a unique fingerprint.

  • Cite this

    Chan, T. M. (2013). The art of shaving logs. In Algorithms and Data Structures - 13th International Symposium, WADS 2013, Proceedings (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8037 LNCS). https://doi.org/10.1007/978-3-642-40104-6_20