Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR13-187 | 28th December 2013 04:53

Property Testing on Linked Lists

RSS-Feed




Revision #1
Authors: Peyman Afshani, Kevin Matulef, Bryan Wilkinson
Accepted on: 28th December 2013 04:53
Downloads: 1055
Keywords: 


Abstract:

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 $\Theta(n^{1/3})$ 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 $\Theta(\log n)$ queries required in the standard testing model, that allows element access indexed by rank, and strictly less than the $\Theta(n^{1/2})$ queries required by a weak model that only allows random sampling.



Changes to previous version:

The paper is unchanged. This update merely corrects a typo in the abstract on ECCC.


Paper:

TR13-187 | 27th December 2013 03:12

Property Testing on Linked Lists





TR13-187
Authors: Peyman Afshani, Kevin Matulef, Bryan Wilkinson
Publication: 27th December 2013 11:41
Downloads: 1524
Keywords: 


Abstract:

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 \Theta(n^1/3) 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 \Theta(log n) queries required in the standard testing model, that allows element access indexed by rank, and strictly less than the \Theta(n) queries required by a weak model that only allows random sampling.



ISSN 1433-8092 | Imprint