ECCC-Report TR13-187https://eccc.weizmann.ac.il/report/2013/187Comments and Revisions published for TR13-187en-usSat, 28 Dec 2013 04:53:15 +0200
Revision 1
| Property Testing on Linked Lists |
Kevin Matulef,
Peyman Afshani,
Bryan Wilkinson
https://eccc.weizmann.ac.il/report/2013/187#revision1We 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.Sat, 28 Dec 2013 04:53:15 +0200https://eccc.weizmann.ac.il/report/2013/187#revision1
Paper TR13-187
| Property Testing on Linked Lists |
Kevin Matulef,
Peyman Afshani,
Bryan Wilkinson
https://eccc.weizmann.ac.il/report/2013/187We 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.Fri, 27 Dec 2013 11:41:43 +0200https://eccc.weizmann.ac.il/report/2013/187