Ofc I love the spectral theorem - it's coincidentally the result I've proven most often in public writing - but this result of Thompson's is very different (and seems to be much harder).
-
-
In general, a huge problem in computational complexity (classical and quantum) is that there's no powerful notion known of "accumulated progress", of what it means to get closer to a target operation.
-
Thompson's theorem tells us that in fact the spectrum does behave in a well-behaved way, and so does give a useful measure of progress. Unf. there's good reasons to think it's not powerful enough to prove the kinds of things
-
you'd really like (e.g., superlinear lower bounds for 3SAT).
-
(Terribly embarrassing: AFAIK, the best circuit lower bounds for 3SAT are _linear_. I.e., we can't even prove it takes n log n gates. Basically, we know that you need to examine the input, and not much else...)
End of conversation
New conversation -
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.