# A query regarding the paper/statement: P=BPP unless E has sub-exponential circuits

I was going thorough this paper: (P=BPP unless E has sub-exponential circuits: https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/IW97/proc.pdf) and I am somewhat struggling with some basics from the paper that I quote below:

Definition 1: Let $$m$$ and $$l$$ be positive integers. Let $$f:\{{0,1}\}^m→\{{0,1}\}^l$$. $$S(f)$$, the worst-case circuit complexity of $$f$$, is the minimum number of gates for a circuit $$C$$ with $$C(x)=f(x)$$ for every $$x∈\{{0,1}\}^m$$.

2.2 Hardness versus Randomness: For this section only, we use $$f,g,h$$ to denote a Boolean function on strings of all lengths, and by $$f_n,g_n,h_n$$ their segments on n-bit strings. Also, let $$E=DTIME(2^{O(n)})$$.

Theorem 2: If there is a Boolean function $$f∈E$$ with $$S(f_n )=2^{Ω(n)}$$ then $$P=BPP$$.

Query 1: I am assuming the boolean function is given by its truth table of size $$2^m.l$$ with all possible entries. I am unclear what it means by this truth table (denoted by $$f$$) $$f∈E/DTIME(2^{O(n)})$$? How do you assign the truth table its runtime without having some circuit represent it? I am clear about the fact that $$S(f)$$ represents the size(i.e. the number of gates in) the smallest possible circuit that represents/calculates $$f$$.

Query 2: Can someone please explain and simplify the theorem ("if...then") part? I am clear about the complexity classes $$P$$ and $$BPP$$, but I am struggling with the condition?

• A function maps binary strings (of arbitrary length) to binary strings. A Boolean function is the special case where the output is a single bit. The restriction of $f$ to inputs of length $n$ is denoted $f_n$. Nov 8, 2021 at 22:26
• This paper is not a good starting point for complexity theory. I suggest starting with something simpler. Nov 8, 2021 at 22:27

The function $$f$$ is a Boolean function. It maps an input of arbitrary length to a single bit. Its signature is $$f\colon \{0,1\}^* \to \{0,1\}.$$ We denote its restriction to $$n$$-bit inputs by $$f_n$$, whose signature is $$f_n\colon \{0,1\}^n \to \{0,1\}.$$ For example, the parity function returns the parity of its inputs: $$f(x_1,\ldots,x_m) = x_1 \oplus \cdots \oplus x_m,$$ where $$m \geq 0$$ is arbitrary. The restriction for inputs of length $$n$$ is $$f_n(x_1,\ldots,x_n) = x_1 \oplus \cdots \oplus x_n.$$ Here the input length is fixed.
The main theorem states that P=BPP if there is some function $$f$$ such that
1. There is a constant $$C > 0$$ and a Turing machine computing $$f$$ which runs in time $$C2^{Cn}$$ on inputs of length $$n$$.
2. There is a constant $$c > 0$$ such that for all $$n$$, any circuit computing $$f_n$$ has size at least $$c2^{cn}$$.