Tag Archives: Circuit complexity

Cody Murray and Ryan Williams’ new ACC breakthrough: Updates from Oded Goldreich’s Choices

Thanks to Irit Dinur for telling me about the following: Oded Goldreich’s recent choice is about the paper: Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP, by Corry Murray and Ryan Williams. Ryan Williams … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Updates | Tagged , , | 9 Comments

The AC0 Prime Number Conjecture

Möbius randomness and computational complexity Last spring Peter Sarnak gave a thought-provoking lecture in Jerusalem. (Here are the very interesting slides of a similar lecture at I.A.S.) Here is a variation of the type of questions Peter has raised. The Prime … Continue reading

Posted in Algebra and Number Theory, Computer Science and Optimization | Tagged , , , , | 14 Comments