
PreviousNext
In this primarily expository
paper, we discuss the connections between two popular and useful
tools in theoretical computer science, namely,
universal hashing and pairwise
independent random variables; and classical combinatorial stuctures
such as error-correcting codes, balanced incomplete block designs,
difference matrices
...
more >>>
The main result of this paper is a Omega(n^{1/4}) lower bound
on the size of a sigmoidal circuit computing a specific AC^0_2 function.
This is the first lower bound for the computation model of sigmoidal
circuits with unbounded weights. We also give upper and lower bounds for
the ...
more >>>
PreviousNext