0
$\begingroup$

I am interested in proving lower bounds for AM-like languages. The usual techniques for lower bounds in non-probabilistic machines don't work for probabilistic machines.

Intuitively, when I think about showing lower bounds I usually think about showing for any algorithm $A$ some "bad input" that would contradict either its correctness or would take more time than the bound we want to show. But for randomized algorithms, a "bad input" for $A$ might still be correct and within the time bound, but only with some probability. This confuses me on how I should approach proving such lower bounds, as it looks much harder to show that the "bad input" is "bad" with high probability, and not only "bad" for one specific coin toss.

I would be glad if you could give me an example of a language with such a lower bound, and how to prove it.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ The only general approach I personally know of is Yao Principle. For problems like "does there exist element with property $P$ in input", a somewhat common approach is to generate an example where $X$ doesn't exist and with probability $0.5$ add an element with property $P$ to it. E.g., IIRC, for the orthogonal vector problem a hard distribution would be to generate vectors randomly (with random $n/3$ coordinates, so that they are not orthogonal whp) and then with probability $0.5$ add an orthogonal vector. BTW, what are "AM-like languages"? $\endgroup$ – Dmitry Feb 11 at 2:34
  • $\begingroup$ Thanks. I will take a deeper look at Yao's principle. When I said AM-like languages I specifically meant the AM variation of distributed computation. $\endgroup$ – nir shahar Feb 11 at 10:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.