Complexity of 2-bit AND-OR

• Classical Las Vegas: qemax=3

  • derived from [Saks and Wigderson 1986]

• Classical Monte Carlo: for qemax=1, pemax�1/3

  • derived from [Santha 1991]

Previous slide

Next slide

Back to first slide

View graphic version