Randomness is a remarkably powerful tool in the design of algorithms. By giving algorithms the ability to use random bits and letting them err with some small  probability, we can solve many computational problems with remarkable efficiency.

The problem of learning arithmetic circuits is the following: given a polynomial as a black box that is promised to have a small arithmetic circuit computing it, can we find this arithmetic circuit?

Randomness is a vital tool and resource in both classical and quantum information processing. However, constructing random bits is expensive, and hence minimising their use is desirable.

Diophantine sets are defined using Diophantine equations. These sets are important and ubiquitous in number theory.