Bryan T. Wilkinson

Property Testing on Linked Lists

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

Documents

  • ECCE-187

    Submitted manuscript, 603 KB, PDF document

Links

We define a new property testing model for algorithms that do not have arbitrary query access to the input, but must instead traverse it in a manner that respects the underlying data structure in which it is stored. In particular, we consider the case when the underlying data structure is a linked list, and the testing algorithm is allowed to either sample randomly from the list, or walk to nodes that are adjacent to those already visited. We study the well-known monotonicity testing problem in this model, and show that (n13) queries are both necessary and sufficient to distinguish whether a list is sorted (monotone increasing) versus a constant distance from sorted. Our bound is strictly greater than the (logn) queries required in the standard testing model, that allows element access indexed by rank, and strictly less than the (n12) queries required by a weak model that only allows random sampling.
Original languageEnglish
JournalElectronic Colloquium on Computational Complexity
VolumeTR13-187
Number of pages12
ISSN1433-8092
Publication statusPublished - 2013

See relations at Aarhus University Citationformats

Download statistics

No data available

ID: 69900062