View in EDS

CROSSING THE LOGARITHMIC BARRIER FOR DYNAMIC BOOLEAN DATA STRUCTURE LOWER BOUNDS.

Saved in:
Bibliographic Details
Title: CROSSING THE LOGARITHMIC BARRIER FOR DYNAMIC BOOLEAN DATA STRUCTURE LOWER BOUNDS.
Authors: LARSEN, KASPER GREEN1 larsen@cs.au.dk, WEINSTEIN, OMRI2 omri@cs.columbia.edu, HUACHENG YU3 yuhch123@gmail.com
Source: SIAM Journal on Computing. 2020, Vol. 49 Issue 5, p323-367. 45p.
Subjects: IEEE Computer Society, Computational geometry, Data structures, Boolean functions, Rectangles
Geographic Terms: New York (State)
Abstract: This paper proves the first superlogarithmic lower bounds on the cell probe complexity of dynamic Boolean (also known as decision) data structure problems, a long-standing milestone in data structure lower bounds. We introduce a new method for proving dynamic cell probe lower bounds and use it to prove an \~\Omega (lg1.5 n) lower bound on the operational time of a wide range of Boolean data structure problems, most notably, on the query time of dynamic range counting over F2 [M. Patrascu, Lower bounds for 2-dimensional range counting, in STOC 2007, ACM, New York, 2007, pp. 40--46]. Proving an \omega (lg n) lower bound for this problem was explicitly posed as one of five important open problems in the late Mihai P\v atra\c scu's obituary [M. Thorup, Bull. Eur. Assoc. Theor. Comput. Sci., 109 (2013), pp. 7--13]. This result also implies the first \omega (lg n) lower bound for the classical 2-dimensional (2D) range counting problem, one of the most fundamental data structure problems in computational geometry and spatial databases. We derive similar lower bounds for Boolean versions of dynamic polynomial evaluation and 2D rectangle stabbing, and for the (non-Boolean) problems of range selection and range median. Our technical centerpiece is a new way of ''weakly"" simulating dynamic data structures using efficient one-way communication protocols with small advantage over random guessing. This simulation involves a surprising excursion to low-degree (Chebyshev) polynomials which may be of independent interest, and offers an entirely new algorithmic angle on the ''cell sampling"" method of Panigrahy, Talwar, and Wieder [Lower bounds on near neighbor search via metric expansion, FOCS 2010, IEEE Computer Society, Los Alamitos, CA, 2010, pp. [ABSTRACT FROM AUTHOR]
Copyright of SIAM Journal on Computing is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 147613065
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: CROSSING THE LOGARITHMIC BARRIER FOR DYNAMIC BOOLEAN DATA STRUCTURE LOWER BOUNDS.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22LARSEN%2C+KASPER+GREEN%22">LARSEN, KASPER GREEN</searchLink><relatesTo>1</relatesTo><i> larsen@cs.au.dk</i><br /><searchLink fieldCode="AR" term="%22WEINSTEIN%2C+OMRI%22">WEINSTEIN, OMRI</searchLink><relatesTo>2</relatesTo><i> omri@cs.columbia.edu</i><br /><searchLink fieldCode="AR" term="%22HUACHENG+YU%22">HUACHENG YU</searchLink><relatesTo>3</relatesTo><i> yuhch123@gmail.com</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22SIAM+Journal+on+Computing%22">SIAM Journal on Computing</searchLink>. 2020, Vol. 49 Issue 5, p323-367. 45p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22IEEE+Computer+Society%22">IEEE Computer Society</searchLink><br /><searchLink fieldCode="DE" term="%22Computational+geometry%22">Computational geometry</searchLink><br /><searchLink fieldCode="DE" term="%22Data+structures%22">Data structures</searchLink><br /><searchLink fieldCode="DE" term="%22Boolean+functions%22">Boolean functions</searchLink><br /><searchLink fieldCode="DE" term="%22Rectangles%22">Rectangles</searchLink>
– Name: SubjectGeographic
  Label: Geographic Terms
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22New+York+%28State%29%22">New York (State)</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: This paper proves the first superlogarithmic lower bounds on the cell probe complexity of dynamic Boolean (also known as decision) data structure problems, a long-standing milestone in data structure lower bounds. We introduce a new method for proving dynamic cell probe lower bounds and use it to prove an \~\Omega (lg1.5 n) lower bound on the operational time of a wide range of Boolean data structure problems, most notably, on the query time of dynamic range counting over F2 [M. Patrascu, Lower bounds for 2-dimensional range counting, in STOC 2007, ACM, New York, 2007, pp. 40--46]. Proving an \omega (lg n) lower bound for this problem was explicitly posed as one of five important open problems in the late Mihai P\v atra\c scu's obituary [M. Thorup, Bull. Eur. Assoc. Theor. Comput. Sci., 109 (2013), pp. 7--13]. This result also implies the first \omega (lg n) lower bound for the classical 2-dimensional (2D) range counting problem, one of the most fundamental data structure problems in computational geometry and spatial databases. We derive similar lower bounds for Boolean versions of dynamic polynomial evaluation and 2D rectangle stabbing, and for the (non-Boolean) problems of range selection and range median. Our technical centerpiece is a new way of ''weakly"" simulating dynamic data structures using efficient one-way communication protocols with small advantage over random guessing. This simulation involves a surprising excursion to low-degree (Chebyshev) polynomials which may be of independent interest, and offers an entirely new algorithmic angle on the ''cell sampling"" method of Panigrahy, Talwar, and Wieder [Lower bounds on near neighbor search via metric expansion, FOCS 2010, IEEE Computer Society, Los Alamitos, CA, 2010, pp. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of SIAM Journal on Computing is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=147613065
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1137/18M1198429
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 45
        StartPage: 323
    Subjects:
      – SubjectFull: IEEE Computer Society
        Type: general
      – SubjectFull: Computational geometry
        Type: general
      – SubjectFull: Data structures
        Type: general
      – SubjectFull: Boolean functions
        Type: general
      – SubjectFull: Rectangles
        Type: general
      – SubjectFull: New York (State)
        Type: general
    Titles:
      – TitleFull: CROSSING THE LOGARITHMIC BARRIER FOR DYNAMIC BOOLEAN DATA STRUCTURE LOWER BOUNDS.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: LARSEN, KASPER GREEN
      – PersonEntity:
          Name:
            NameFull: WEINSTEIN, OMRI
      – PersonEntity:
          Name:
            NameFull: HUACHENG YU
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 09
              Text: 2020
              Type: published
              Y: 2020
          Identifiers:
            – Type: issn-print
              Value: 00975397
          Numbering:
            – Type: volume
              Value: 49
            – Type: issue
              Value: 5
          Titles:
            – TitleFull: SIAM Journal on Computing
              Type: main
ResultId 1