Hmm, okay, I'm clearly taking too quick a glace then. Just to check myself, am I right in thinking U and V are the change of basis matrices which diagonalize H and K? So e^(iUHU*) will be diagonal with e^{i lambda} entries on the diagonal?
-
-
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.