Example demonstrating the power of non-deterministic circuits A non-deterministic Boolean circuit has, in addition to the ordinary inputs $x = (x_1,\dots,x_n)$, a set of "non-deterministic" inputs $y=(y_1,\dots,y_m)$. A non-deterministic circuit $C$ accepts input $x$ if there exists $y$ such that the circuit output $1$ on $(x,y)$.
Analogous to $P/poly$ (the class of languages decidable by polynomial size circuits), $NP/poly$ can be defined as the class of languages decidable by polynomial size non-deterministic circuits. It is widely believed that non-deterministic circuits are more powerful than deterministic circuits, in particular $NP \subset P/poly$ imply that the polynomial hierarchy collapses.


  Is there an explicit (and unconditional) example in the literature
  showing that non-deterministic circuits are more powerful than
  deterministic circuits?
  
  In particular, do you know of a function family $\{f_n\}_{n &gt; 0}$
  computable by non-deterministic circuits of size $cn$, but not
  computable by deterministic circuits of size $(c+\epsilon)n$?
If this problem has no progress, I have an answer.

--

I also have considered this problem since my COCOON'15 paper (before your question).

Now, I have a proof strategy, and it immediately gives the following theorem:
There is a Boolean function $f$ such that the nondeterministic $U_2$-circuit complexity of $f$
is at most $2n + o(n)$ and the deterministic $U_2$-circuit complexity of $f$ is $3n - o(n)$.

I apologize that I haven't written the paper.
The proof sketch below might be enough to explain my proof strategy.
I aim to write the paper with more results by the STACS deadline (Oct. 1).

[Proof Sketch]

Let $f = \lor_{i=0}^{\sqrt{n}-1}{Parity_{\sqrt{n}}(x_{\sqrt{n} \cdot i + 1}, \ldots, x_{\sqrt{n} \cdot i + \sqrt{n}}})$.

The deterministic lower bound proof is based on a standard gate elimination method with a little modification.

The nondeterministic upper bound proof is a construction of such nondeterministic circuit.


Construct a circuit computing $Parity_{\sqrt{n}}$. (The number of gates is $o(n)$.)
Construct a circuit selecting $\sqrt{n}$ inputs nondeterministically. (The number of gates is $2n + o(n)$.)
Combine the two circuits.