# Tag Info

2

In a trivial sense, no, because circuits have a fixed input size. To compute the same function as a Turing machine, you need an infinite family of circuits, one for each input size. So a single circuit can't even "simulate" one Turing machine. So let's restrict ourselves then to inputs just of size $n$, then the question is just are there two ...

2

In the average case, you want the circuit to succeed in computing the function for a large portion of all possible inputs. Since a constant function always succeeds for at least half the inputs (the majority of $f$), the interesting case in where you can achieve advantage which is greater than $\frac{1}{2}$. In the worst case, you want the circuit to succeed ...

1

A language $L$ is in $\mathsf{NP}$ if there exists a polynomial $p$ and a deterministic Turing machine $T$, running in polynomial time, such that: $x \in L$ if and only if there exists $y$ of length $p(|x|)$ such that $T(x,y) = 1$. Usually we assume that $|y| \leq p(|x|)$, but we can get this version using a simple padding argument, which slightly ...

1

Theorem 1 in [Nisan Wigderson 1988] implies: For any function $l\le s(l)\le 2^l$, the following are equivalent: For some $c>0$, there exists a quick PRG $G: l\to s(l^c)$. For some $c>0$, there exists a function $f$ in EXPTIME with hardness $s(l^c)$. Although their definition of (quick) PRG and hardness are slightly different from yours, I think the ...

1

Let $C$ be a fixed function, and let $f$ be a random function. For $z \in \{0,1\}^n$, let $X_z = 1$ if $C(z) = f(z)$, and $X_z = -1$ otherwise. Thus $$2^{-n} \sum_z X_z = \Pr[C(z) = f(z)] - \Pr[C(z) \neq f(z)] = 2\Pr[C(z) = f(z)] - 1.$$ Therefore $\Pr[C(z) = f(z)] \geq 1/2+\delta$ iff $2^{-n} \sum_z X_z \geq 2\delta$. According to Bernstein's inequality, ...

Only top voted, non community-wiki answers of a minimum length are eligible