Timeline for Detecting slow growth in a finite number of queries
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 10, 2020 at 11:19 | comment | added | Erel Segal-Halevi | I agree, and added a proof. Sorry for using the language of queries - this is the language I am used to. It comes from papers such as this: combinatorics.org/ojs/index.php/eljc/article/view/735 | |
| Sep 8, 2020 at 21:05 | comment | added | Iosif Pinelis | @ErelSegal-Halevi : I'd guess that even for general $s,t$ there is no finite solution even in the adaptive query model. | |
| Sep 8, 2020 at 18:50 | comment | added | Erel Segal-Halevi | Very interesting! In the language of queries, it seems that your formalization corresponds to "non-adaptive queries". This means that the algorithm has to decide in advance what queries to ask, i.e., the sequences $x_n$ and $y_n$ are pre-determined. There is a different model called "adaptive queries", in which the algorithm may decide what queries to ask based on the replies to previous queries, i.e., $x_j$ and $y_j$ may depend on $g(x_1),\ldots,g(x_{j-1})$ and $g(y_1),\ldots,g(y_{j-1})$. When $s=t$, there is no finite solution even in the adaptive query model (see the original question). | |
| Sep 7, 2020 at 19:14 | history | edited | Iosif Pinelis | CC BY-SA 4.0 |
added 77 characters in body
|
| Sep 7, 2020 at 18:56 | history | edited | Iosif Pinelis | CC BY-SA 4.0 |
added 16 characters in body
|
| Sep 7, 2020 at 18:50 | history | answered | Iosif Pinelis | CC BY-SA 4.0 |