Coin Tossing Algorithms for Integral Equations and Tractability.

Integral equations with Lipschitz kernels and right-hand sides are intractable for deterministic methods, the complexity increases exponentially in the dimension d. This is true even if we only want to compute a single function value of the solution. For this latter problem we study coin tossing algorithms (or restricted Monte Carlo methods), where only random bits are allowed. We construct a restricted Monte Carlo method with error e that uses roughly ε^-2 function values and only d log² ε random bits. The number of arithmetic operations is of the order ε^-2 + d log² ε. Hence, the cost of our algorithm increases only mildly with the dimension d, we obtain the upper bound C ⋅ (ε^-2 + d log² ε) for the complexity. In particular, the problem is tractable for coin tossing algorithms. [ABSTRACT FROM AUTHOR]