You are currently browsing the tag archive for the ‘circuits’ tag.

It’s a draft, but contains much of what we’ve been talking about re: circuit lower bounds.

Hi all,
I’ve posted the reading for Monday Jun 15. We’ll continue with circuits, specifically chapter 13.2 in the online draft (the proof that PARITY cannot be computed with a poly-size circuit family that includes MOD(3) gates).

I don’t know if we’ll be able to get through the entire proof on Monday. Let’s see how far we can go.