Circuits with arbitrary gates for random operators

Details Circuits with arbitrary gates for random operators Circuits with arbitrary gates for random operators

2010-04-29

arxiv.org/abs/1004.5236v1

Computer Science

Computational Complexity

7 pages

Scientific paper

We consider boolean circuits computing n-operators f:{0,1}^n --> {0,1}^n. As gates we allow arbitrary boolean functions; neither fanin nor fanout of gates is restricted. An operator is linear if it computes n linear forms, that is, computes a matrix-vector product y=Ax over GF(2). We prove the existence of n-operators requiring about n^2 wires in any circuit, and linear n-operators requiring about n^2/\log n wires in depth-2 circuits, if either all output gates or all gates on the middle layer are linear.

Affiliated with

Also associated with

No associations

Rating

Circuits with arbitrary gates for random operators does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Circuits with arbitrary gates for random operators, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Circuits with arbitrary gates for random operators will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-284805