Tuesday, November 23, 2010

Guest Post: Distinct distances, and the use of continuous mathematics in discrete geometry.

Nabil Mustafa specializes in problems of discrete geometry, and has spent time on problems related to the distinct distance problem. He offers a broader perspective on the new distinct distances result and related breakthroughts in discrete geometry. For a detailed breakdown of the Guth/Katz paper, see Terry Tao's latest opus.As usual, I take responsibility for any mistakes introduced in the editing process.

I think the days when the "Feynman method" was all that was needed to make progress on basic problems in Discrete Geometry are over. Recently there have been a slew of results which make progress on long-standing open problems in Discrete and Computational Geometry that use techniques from a variety of areas in mathematics: algebraic geometry, algebraic topology, complex analysis and so on.

This is wonderful news for the field. Though, two things to consider:

1. So far, apart from the kind of work going in "Computational Topology", this has mostly been a one-way street. There have been fewer cases of discrete and computational geometers going into topology, algebraic geometry etc. and making a similar impact there. Similarly, there are very few collaborations between mathematicians in other areas, and discrete geometers (ed: Mulmuley also argues that the GCT program will only come to fruition when this reverse direction starts happening)

2. From my experience, current graduate students, by-and-large, still seem to be stuck with the general outlook that "If I'm clever enough, and think hard enough, I can solve any problem directly". Such optimism alwayscheers me up. I used to think that too, but the more I learn about other areas, and as the recent work reveals power of techniques, it has become clear to me that it is misguided to think that. I would really advise students to take courses in algebraic topology, differential geometry and so on.

Below I list some such recent breakthroughs.

First-selection Lemma. 
 Given n points in $R^d$, can one find a point in "many" simplices spanned by these points ?
This has been studied for more than 30 years, with several partial results. The current best result was published this year by M. Gromov, which in fact proves a stronger topological  theorem, with better bounds than for restricted earlier cases. Matousek and Wagner have improved this bound slightly for 3D by improving a combinatorial part of Gromov's argument.  Gromov's argument is a complicated topological argument that I did not have the background to follow. J. Matousek gave a nice talk at the Bernoulli conference in September with the title "Also Sprach Gromov"!

2. Colored Tverberg Theorem. 
Let C_1,\cdots,C_{d+1} be disjoint subsets of R^d, called colors, each of cardinality at least t. A (d+1)-subset S of \bigcup^{d+1}_{i=1}C_i is said to be multicolored if S\cap C_i\not=\emptyset for i=1,\cdots,d+1. Let r be an integer, and let T(r,d) denote the smallest value t such that for every collection of colors C_1,\cdots,C_{d+1} of size at least t there exist r disjoint multicolored sets S_1,\cdots,S_r such that \bigcap^r_{i=1}{\rm conv}\,(S_i)\not=\emptyset 
The conjecture is that $T(r,d) = r$, and this was proved recently via topological arguments (for all $r$ such that $r+1$ is prime) by  Blagojevic, Matschke, and Ziegler (see Gil Kalai's blog for a detailed post on this). Matousek, Tancer and Wagner have translated this argument to a geometric proof. As they state in the abstract, "The purpose of this de-topologization is to make the proof more concrete and intuitive, and accessible to a wider audience."

3. Distinct Distances problem. 

The Guth-Katz dramatically improves the best known bound via techniques from algebraic geometry. Terry Tao has more details on this.

4. Joints problem. 
A joint is a point formed by the intersection of three non-coplanar lines in 3D. What is the maximum number of joints achievable by a collection of $n$ lines in 3D ? 
This was again solved by Guth and Katz via techniques from algebraic geometry. It was subsequently simplified wonderfully by Elekes, Kaplan and Sharir, and Kaplan, Sharir and Shustin.

5. Lower-bounds for eps-nets. 

It was very widely believed that for "natural"  geometric objects, eps-nets of linear-size should exist. Shockingly, Alon showed that an easy application of Hales-Jewett density version immediately gives a non-linear lower-bound for a simple geometric-system in the plane. While DHJ is a combinatorial result, it was first "proved by Furstenberg and Katznelson in 1991 by means of a significant extension of the ergodic techniques that had been pioneered by Furstenberg in his proof of Szemeredi's theorem". Like earlier proofs, it is possible to "de-ergodicize" it (the polymath project).

6. Regression-depth partitioning conjecture. 

(ed: see here for a description of regression depth - it's similar to halfspace depth)

Partial results were shown by Amenta-Bern-Eppstein-Teng in 2000. Recently almost proven by Karasev using topological techniques that I do not understand.

This is just a partial list, there are probably several others that I have missed.

Monday, November 22, 2010

Workshop on Parallelism, and a "breakthrough" in combinatorial geometry

In the blog world, you're either fast, or dead. I waited a few days to post a note about the upcoming DIMACS workshop on parallelism, and was beaten to the punch by Muthu and Dick Lipton.

At this point, you probably know the major points. Phil Gibbons, Howard Karloff and Sergei Vassilvitskii are organizing a DIMACS workshop on a long-range vision for parallelism, with an emphasis on interaction between practitioners and theoreticians in the area. The workshop looks to be quite interesting, and similar in spirit to the one organized by Uzi Vishkin at STOC 2009 on multicore algorithms.

Utah has a major presence in the world of high performance parallel computing, and we're hiring in this area this year ! From my vantage point, I get a fly-on-the-wall view of developments in the area, and it makes me wonder:
Is the field is now moving too fast for models to even make sense ? 
A case in point: Google's MapReduce infrastructure has taken the world by storm, and you can even run MapReduce "in the cloud" on Amazon's servers. Howard, Sergei and Sid Suri had a very interesting paper on MapReduce at SODA last year, and there's a ton of academic work on algorithm design (in theory and practice) in this model. But if new reports are to be taken seriously, Google itself is moving on from MapReduce to other distributed data management systems.

The most recent "alternative model of computing" that we've encountered is the stream model, and while it had strong links to practice, it's survived this long because of the incredibly interesting theoretical challenges it poses, as well as the rich arsenal of theory concepts that got deployed in the process. I'm curious to see if something similar can happen with these new models of parallelism and multicore computing (over and above PRAM and NC of course)

In other news: readers of Gil Kalai's blog will have heard of the exciting new breakthrough in the realm of combinatorial geometry on the tantalizingly simple problem first posed by Erdos in 1946:
What is the minimum number of distinct distances achievable by a set of n points in the plane ? 
I hope to have a longer guest post up soon on this, so I won't say much right now. What's neat is that this result is the implementation of a larger program/line of attack laid out by Gyorgy Elekes, who sadly died in 2008 before seeing this come to fruition. Micha Sharir has a beautiful writeup with the history of this approach (it predates the new results though). Bill Gasarch has a nice page collecting together the major developments in this area, including links to the Kakeya problem.

p.s Note to other CG bloggers: please do not talk about this problem otherwise Mihai will scold us all ;)

Friday, November 12, 2010

What can the ACM do for you ?

I kid, of course. While the ACM is a popular punching bag in hallway conversations, they do help the CS community in many ways, not the least of which is the digital library, the conference management services, the lobbying efforts in Congress (where I think though that the CRA has them beat), and so on.

But there's this constant running joke that the ACM is always trying to drag us kicking and screaming into the 1970s :). More importantly, while the DL has been spiffed up with comment feeds, all kinds of social sharing and what not (but no RSS for comments - COME ON !!), I think that the ACM could use its considerable weight to really help the research community. In both of the ideas I'm listing, the ACM has particular advantages as an organization with brand recognition, and an imprimatur of authority. They also have resources far beyond what other groups might be able to do.

A Pubmed for CS
More than six years ago, I was complaining about the lack of a Pubmed-style single location to dump all CS papers (titles, abstracts and keywords, with links back to original source). While the arxiv is becoming a better and better place for people to post preprints, what we really need is a single point to view and browse published papers, across journals and conferences.

The DL already maintains paper listings across a variety of publications, and many CS conferences are run by the ACM, so it shouldn't be that hard to do. The DL itself isn't quite there yet, mainly because of the lousy search features that it has, and because it's not quite complete.

I don't know if Dan Wallach's proposal for a central hub for papers is going anywhere, but that's another model that the ACM could help make a reality. 

A Mathematical Reviews clone
This one is possibly more localized to theoryCS, and requires more resources. But it's getting ever more important. It's really hard to keep track of the flood of papers showing up in conferences, journals and on the arxiv, and a service that generated short reviews of papers would be great. Plus, as theoryCS gets more fractured and more diverse, this kind of thing becomes ever more important.

It seems like the ACM is getting the 'social bug' if the DL redesign is any indication. I'd argue that these two items are probably the best kind of 'social web' that the ACM can contribute to.

Friday, November 05, 2010

Odds and Ends

Glencora Borradaile makes her recommendations for FOCS videos to watch (can we have all our conferences do videos, please ? My 40 minutes on the bus will take on a whole new dimension). I like the idea of starring speakers who do a good job: might increase the competitive pressure. Come to think of it, here's another perk of having videos for conferences: sheer embarrassment will make sure that speakers improve their presentations.

The cstheory Q&A site rolls on. Those of you at FOCS might have noticed the little sheets in your registration packets, but I don't know if it actually encouraged new people to visit. If you're one of them, do drop a note in the comments. Three points of interest:
  • We have a collaboratively edited article that we just submitted to SIGACT News (you can read the draft here). The article highlights some of the recent fascinating questions, answers and discussions on the site - do check it out
  • This is purely anecdotal, but I've been hearing both at FOCS and on the site that people are having to avoid visiting the site because it's so addictive ! Don't worry - it isn't that bad - as a matter of fact I only spent 6 hours last night ! down from.. (never mind)..
  • Another sign of catastrophic success: our first incident of undergrads in a theory class systematically trying to get their homework questions answered by posting on the site. Many alert users were able to close down the questions, but occasionally answers slip by. If you're an undergraduate and read this blog (HA ! blogs are for old fogies !), be warned...
Finally, because I'd be remiss not to do so, some neat questions (and answers) to chew on:

Thursday, November 04, 2010

All FOCS talks are online

All FOCS 2010 talks are now online, at ieee-focs.org and http://techtalks.tv/focs/2010. The player works fine on firefox (the picture is embedded in one corner of the slides) and I find the talks particularly pleasant to listen to if you have  a nice backing track :)

Disqus for The Geomblog