Introduction to Modern Cryptography - INFR11131

Sample exam question

Suppose there is an oracle that answers with Yes or No to a specific question, and answers correctly with probability 1/2 + α. You can ask the oracle as many times as you wish for the same question. How many queries do you have to make in order to guarantee that you will decide what is the correct answer with probability at least 1-ε?

Answer as in p.12 of the notes (Example (Guessing with a Majority)).