Better Lower Bound on a Well-Leveled Circuit for AND function

Assumption: The fanin of each gate is at most two

Level (i-1)

Level i

a

b

3(i-1)

3

Level (i-1)

Level i

a

b

2(i-1)

2

Non-zero number of nodes with fanout ɭ

Previous slide

Next slide

Back to first slide

View graphic version