You are currently browsing the monthly archive for June 2009.

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


Lance Fortnow has a new blog post about “Nondeterministic NC.” He responds to a reader question:

Can we define a class NNC such that NC ⊆ RNC ⊆ NNC. Is NNC known by some other name? It is clear that NNC ⊆ NP, but the reverse is not obvious.

We are not meeting tomorrow (Thursday), as Suresh is still ill with a mystery bug. We will reconvene Monday (June 22). I have updated the Wiki.

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.