tag:blogger.com,1999:blog-5363281391146594625.post2345178873640434519..comments2011-10-19T00:16:06.071-07:00Comments on Theory Chat: Wish ListJagadishhttp://www.blogger.com/profile/08614978065099775243noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-5363281391146594625.post-73912902484941542362011-10-19T00:16:06.071-07:002011-10-19T00:16:06.071-07:00Talks I would like to present:
1. Wedge products ...Talks I would like to present:<br /><br />1. Wedge products and the proof of skew Bollobás' theorem.<br />2. Online graph traversal and its equivalence with MSS.<br /><br />Topic I would like to understand through discussions in theorychat: Dinur's proof of PCP theorem.Ashish Chiplunkarhttps://www.blogger.com/profile/11182987978496475494noreply@blogger.comtag:blogger.com,1999:blog-5363281391146594625.post-47834555864591443862011-10-09T07:08:55.546-07:002011-10-09T07:08:55.546-07:00I've sent you an invite.
> Can you be more...I've sent you an invite.<br /><br />> Can you be more specific about "exploiting planarity" in algorithm design?<br /><br />A specific classes of graphs usually have some nice properties that are useful in designing fast algorithms. For example, running intersection property of chordal graphs, umbrella property for proper interval graphs, etc. I would like to know which properties, if any, of planar graphs make them amenable to efficient algorithms.Jagadishhttps://www.blogger.com/profile/08614978065099775243noreply@blogger.comtag:blogger.com,1999:blog-5363281391146594625.post-77358107925259869382011-10-07T09:31:33.393-07:002011-10-07T09:31:33.393-07:00@Jagadish:
The topics look interesting. About you...@Jagadish:<br /><br />The topics look interesting. About your wish list - I can present expanders and related stuff. I think Ayush is interested in presenting SDPs.<br />Can you be more specific about "exploiting planarity" in algorithm design?<br /><br />I am not able to create a post, so I'll mention my list of topics here:<br /><br />Topics I'd like to see presented:<br /><br />1. The paper "A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations" by Daniele Micciancio and Panagiotis Voulgaris, a breakthrough result on the shortest vector problem.<br />Link: http://cseweb.ucsd.edu/~daniele/papers/Voronoi.pdf<br /><br />2. Proof(s) of the Borsuk Ulam theorem, a generalization of Brouwer's fixed point theorem to arbitrary dimensions.<br />Link: http://www.math.neu.edu/~king_chris/Borsuk-Ulam.pdf<br />Another excellent source is the book by Matousek, titled "Using the Borsuk-Ulam theorem".<br /><br />3. An intro to entropy and information theory<br />4. Szemeredi's regularity lemma and applications<br /><br />Note: I am willing to discuss on the Micciancio-Voulgaris paper.<br /><br />Topics I'd like to present:<br /><br />1. Expanders.<br />2. Linear algebraic methods in combinatorics.<br /><br />3. The Guth-Katz bound on the Erdős distance problem: Terrence Tao has a nice expository post at http://terrytao.wordpress.com/2010/11/20/the-guth-katz-bound-on-the-erdos-distance-problem/.<br />This is a complex proof and I could use some help.<br /><br />4. Extractors and derandomization.Aravindhttps://www.blogger.com/profile/09357354222720290987noreply@blogger.com