3 ms·
Measuring 1/3, 1/2, and 2/3 does not tell you which 1/3 of the range you should look. There are 3 cases to consider: 1. f(1/3) is the biggest. In this case you
by jacobolus 16y ago
Measuring 1/3, 1/2, and 2/3 does not tell you which 1/3 of the range you should look. There are 3 cases to consider:
1. f(1/3) is the biggest. In this case you learn that m is between 0 and 1/2.
2. f(1/2) is the biggest. In this case you learn that m is between 1/3 and 2/3.
3. f(2/3) is biggest. You learn that m is between 1/2 and 1.
* * *
Edit: as for measuring 1/2 + epsilon, it’s no worse for “adversarial input”. You just need to remember that your first pair of measurements tell you that either 0 ≤ m ≤ .5+ε or else .5 ≤ m ≤ 1
- deleted 16y ago[deleted]