1
$\begingroup$

I am considering the following class of algorithms:

The algorithm has access to some probabilistic oracle (procedure) $f$ in addition to input.

The answer of procedure $f$ (we may assume it is boolean) may be incorrect with probability at most $p<1/3$. The error of different calls to $f$ are independent (thus we may increase the confidence of the result by repeatedly calling $f$ with the same argument and taking majority).

The algorithm can call multiple times $f$ with any values.

We request that whatever the bound on error probability $p$ (unknown to the algorithm), the algorithm itselft must return its correct answer with error probability at most $p$.

The question is: Is there any standard name for that class of 'confidence-preserving' algorithms?

For the sake of illustration, if we want to find the maximum of $3$ items and only have access to the items through some probabilistic oracle $f$ for comparing any pair of items, we can compare each pair $3$ times and take majority vote. The probability that each pair is ordered incorrectly is at most $3p^2$, hence the probability that we do not deduce the maximum correctly is at most $9p^2$. This is less than $p$ so the algorithm belongs to our class.

Improve this question
$\endgroup$
8
  • $\begingroup$ These are called Monte-Carlo algorithms. You can find out more here or on Wikipedia. $\endgroup$
    – Raphael ♦
    Jul 31, 2014 at 14:23
  • 2
    $\begingroup$ I do not agree. The Monte-Carlo classification and BPP class seem unrelated to my question. Here my question is about how the algorithm propagates the error of a probabilistic oracle. $\endgroup$
    – Joseph Stack
    Jul 31, 2014 at 16:48
  • $\begingroup$ Well, the oracle is a Monte Carlo algorithm (kind of, 1/3 may be troublesome). About your algorithm we can not say anything since you don't give it. "Exploit repeatedly" is too vague. If you are only interested in the name for the property of answering correctly with a certain probability, we are back at BPP/Monte-Carlo. $\endgroup$
    – Raphael ♦
    Jul 31, 2014 at 17:04
  • $\begingroup$ I am interested in the name of the property "the algorithm answers correctly with 90% probability as long as each oracle call is correct with 90% probability, and with 99% probability if each oracle call is correct with 99% probability". I think this is unrelated to BPP/Monte Carlo as it is a property of how the oracle is exploited $\endgroup$
    – Joseph Stack
    Jul 31, 2014 at 18:05
  • 1
    $\begingroup$ I don't know whether this kind of algorithm has a name. Why do you want to know the name? How will you use that information? It's possible that you might fare better on this site by posing a technical question, rather than a terminology question. $\endgroup$
    – D.W. ♦
    Jul 31, 2014 at 20:58

1 Answer 1

Reset to default
1
$\begingroup$

I'm not familiar with any standard name for this type of algorithm. Go ahead and write your research paper and define a class with a name of your own choice (confidence-preserving seems like a quite good name to me).

Improve this answer
$\endgroup$
7
  • $\begingroup$ One might add that the class as described may be "boring" since there is no "only if". There are myriads of algorithms whose confidence is not at all impacted by a bad oracle. Also, as mentioned in the question success probability can be increased by repetition. Are there examples of algorithm (which are not obviously bad) that don't have the described property? $\endgroup$
    – Raphael ♦
    Aug 3, 2014 at 17:30
  • $\begingroup$ @Raphael, good points. Since you asked: A non-trivial example would be the Goldreich-Levin Theorem. Naive algorithms like Gaussian elimination don't work at all if the oracle is even slightly noisy (wrong with even modest probability); it takes some non-trivial ideas to deal with an oracle that is wrong with probability $1/4$, and even more to deal with an oracle that is wrong with probability $1/2-\epsilon$. So I think the naive algorithms like Gaussian elimination count as examples of algorithms that aren't obviously bad, and that don't have the described property. $\endgroup$
    – D.W. ♦
    Aug 4, 2014 at 6:43
  • $\begingroup$ @Raphael Remember that 1) I am describing a class/property of algorithms, I am not asking which problems admit such algorithms, and 2) the algorithm must satisfy the property for all (small enough) $p$ even though $p$ is not known. There is a logarithmic cost to increase confidence. It is for instance not trivial to evaluate in linear time a boolean formula to guarantee the confidence-preserving property when variables are evaluated with a probabilistic oracle. $\endgroup$
    – Joseph Stack
    Aug 4, 2014 at 9:17
  • $\begingroup$ I would even say quite the opposite: there are very few algorithms that satisfy the property when each input variable is accessed through a probabilistic oracle, because errors are cumulative unless some appropriate redundancy is introduced. $\endgroup$
    – Joseph Stack
    Aug 4, 2014 at 9:27
  • $\begingroup$ @JosephStack I was thinking of all deterministic ones, all Las Vegas algorithms, and most M-C algorithms (after repetition). Noisy inputs don't appear in your question, and that certainly changes things. I say again, I think you need to define your model resp. algorithm class more precisely. $\endgroup$
    – Raphael ♦
    Aug 4, 2014 at 10:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.