arXiv:1111.1261cs.CC
I will discuss the recent proof that the complexity class NEXP (nondeterministic exponential time) lacks nonuniform ACC circuits of polynomial size. The proof will be described from the perspective of someone trying to discover it.
Linked by 2 identifiable commenters in 3 comments across 3 threads, from May 2014 to Jun 2024.
There is a large, emerging body of research in which one proves the impossibility of solving problem A by finding an algorithm for solving a different problem B. For Mulmuley et al. (it's been a while since I was in the thick of this) it's finding an algorithm for computing a…
I recently read a paper of Ryan Williams explaining how one discovers the biggest breakthrough in circuit complexity in the last decade. http://arxiv.org/abs/1111.1261
Connected through shared HN threads, not inferred similarity or a recommendation.
The next step book wise is Arora and Barak, Computational Complexity: a modern approach. Of course that book is already out of date. The breakthrough that comes to mind is Ryan Williams' circuit lower bounds. He wrote a nice explanation of the proof here…
ccppurcellView on HNParent context