We obtain the following full characterization of constructive dimension
in terms of algorithmic information content. For every sequence A,
cdim(A)=liminf_n (K(A[0..n-1])/n.

more >>>

In 1957 Markov proved that every circuit in $n$ variables
can be simulated by a circuit with at most $\log(n+1)$ negations.
In 1974 Fischer has shown that this can be done with only
polynomial increase in size.

In this note we observe that some explicit monotone functions ... more >>>

Informally, an <i>obfuscator</i> <b>O</b> is an (efficient, probabilistic)
"compiler" that takes as input a program (or circuit) <b>P</b> and
produces a new program <b>O(P)</b> that has the same functionality as <b>P</b>
yet is "unintelligible" in some sense. Obfuscators, if they exist,
would have a wide variety of cryptographic ... more >>>