Blogging has been slow this summer as I (surprise surprise) was actually working. Today the semester starts, so I expect to be blogging more as I attempt to clear my head from the detritus of semester minutiae.
Terry Tao has a new post up in the "tricks wiki" started by Timothy Gowers. The "trick" can be summarized concisely as: if you want to prove an inequality of the form X < Y, but can only prove X < CY, then take "tensor powers" of the objects X and Y and prove the weaker inequality, and then take a "root".
What's interesting to me is that this is none other than a generalization of the "standard" amplification trick that is most commonly used in hardness results. The easiest application is the proof that CLIQUE admits no absolute approximation: if it did, take graph powers, find the additive-error number, and take square roots, and you have an exact solution (since the value must be integral). Generalizations exist: you can use the same argument to show that CLIQUE admits no constant factor approximation, and even more intricately (invoking the PCP theorem) that independent set has no polynomial-factor approximation.
It makes me wonder what other "standard" analysis tricks draw their lineage from generalizations in the world of "real math". For example, tricks involving building exponentially growing covers tend to show up frequently in topology and analysis.
I was just reading your Geometry of Information Spaces wiki. It linked me to Guy Lebanon's thesis, which I scanned quickly, and saw the definition for n-simplex right below the definition for the n-sphere and upper half plane. It reminded me that I still don't get the idea of a simplex or simplicial complexes and can't relate them to my experience.
ReplyDeleteSo I googled. And voila, the simplex wiki is the clearest, most concise thing I've read about it. [To be fair, I've never read a geometry textbook] And now, it's starting to make sense. So, you get the thanks^(1/3) [for being three steps upstream from the simplex wiki].