Ben-Eliezer, O;
Canonne, CL;
Letzter, S;
Waingarten, E;
(2019)
Finding Monotone Patterns in Sublinear Time.
In:
Proceedings of the 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS).
(pp. pp. 1469-1494).
The Institute of Electrical and Electronics Engineers (IEEE)
Preview |
Text
main-arxiv.pdf - Accepted Version Download (685kB) | Preview |
Abstract
We study the problem of finding monotone subsequences in an array from the viewpoint of sublinear algorithms. For fixed k ϵ N and ε > 0, we show that the non-adaptive query complexity of finding a length-k monotone subsequence of f : [n] → R, assuming that f is ε-far from free of such subsequences, is Θ((log n) ^{[log_2k]}). Prior to our work, the best algorithm for this problem, due to Newman, Rabinovich, Rajendraprasad, and Sohler (2017), made (log n) ^{O(k2)} non-adaptive queries; and the only lower bound known, of Ω(log n) queries for the case k = 2, followed from that on testing monotonicity due to Ergün, Kannan, Kumar, Rubinfeld, and Viswanathan (2000) and Fischer (2004).
| Type: | Proceedings paper |
|---|---|
| Title: | Finding Monotone Patterns in Sublinear Time |
| Event: | 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) |
| Location: | Baltimore (MD), USA |
| Dates: | 9th-12th November 2019 |
| ISBN-13: | 978-1-7281-4952-3 |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1109/focs.2019.000-1 |
| Publisher version: | https://doi.org/10.1109/FOCS.2019.000-1 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher's terms and conditions. |
| Keywords: | property testing; algorithms; lower bounds; onesided testing; monotone patterns; forbidden patterns |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10107270 |
Archive Staff Only
 |
View Item |
