- Petros Drineas is now an AF program director at the NSF. Congrats, Petros !
- STOC 2011 might experiment with a poster session with a different call for submissions. That's a great idea - I hope they decide to go ahead with it
- Not one person felt that FOCS should continue to have printed proceedings. As recently as a few years ago, at least a third of the audience at theory conferences would have asked for printed proceedings. Times they are a'changin' !!!
Monday, October 25, 2010
FOCS Day 1: some notes
Three newsworthy items from the FOCS business meeting: (for more details follow the focs2010 tag on twitter)
Journals, Conferences, and non-galactic algorithms
Does our lack of attention to journal publications influence the "impracticality" of our algorithms ?
I've been thinking about algorithms, applications and the dreaded "practicality" issue. And the following thought occurred to me.
We have a well-known aversion to journal papers in our community. I won't rehash the arguments for and against. But it is definitely true that in a conference paper we elide many details of the algorithm construction and proof. It's not uncommon for a 10-page conference paper to blow up to a nearly 100 page journal paper (cough cough MST cough cough).
So suppose you have this snazzy new algorithm for a problem. You're happy with your handwavy conference version, and you don't bother to write the journal version. When you do, you realize to your horror that your snazzy 1-page procedure has become this 12 page lumbering beast of an algorithm that's so insanely complicated that you'd be ashamed to even call it 'galactic'. Now this might motivate you to come up with a simpler algorithm, or it might motivate someone else !
I've been thinking about algorithms, applications and the dreaded "practicality" issue. And the following thought occurred to me.
We have a well-known aversion to journal papers in our community. I won't rehash the arguments for and against. But it is definitely true that in a conference paper we elide many details of the algorithm construction and proof. It's not uncommon for a 10-page conference paper to blow up to a nearly 100 page journal paper (cough cough MST cough cough).
So suppose you have this snazzy new algorithm for a problem. You're happy with your handwavy conference version, and you don't bother to write the journal version. When you do, you realize to your horror that your snazzy 1-page procedure has become this 12 page lumbering beast of an algorithm that's so insanely complicated that you'd be ashamed to even call it 'galactic'. Now this might motivate you to come up with a simpler algorithm, or it might motivate someone else !
But if you don't write the journal version with full details, how is anyone to know ?
While this is in part about practicality (since practical almost always equals simple), it's more than that. Clarity in algorithm design is useful even if there's no practical value, because it aids in understanding. So this is in my mind a completely different reason for why we should write more journal papers. It might make our algorithms simpler !!
p.s Yes, I am aware that very often the hard part of a paper is PROVING that an algorithm is correct, and not the algorithm itself. Obviously this would not apply to those cases. But even there, having to contemplate the monstrosity of the proof you end up writing would motivate you to simplify it. After all, proofs are about understanding, not fireworks and fountains at the Bellagio.
FOCS Day 1: Clustering
A long time ago I realized that if I took blogging duties too seriously, I'd be exhausted trying to report on talks that I attended. So I'm not going to even try. I will talk about a pair of talks on clustering though.
A core question of clustering is this: learn a mixture of $k$ $d$-dimensional Gaussians with different means and covariance matrices from samples drawn from the mixture.A long line of research, starting with a paper by Sanjoy Dasgupta back in 1999, produced variations on the following result:
These two papers take a slightly more general tack, in different ways. They both eliminate the conditional nature of prior bounds ("if the Gaussians are well separated"), instead replacing this by an unconditional bound ("poly in a parameter capturing the separation").
The first, by Moitra and Valiant (both Ph.D students!) measures the separation between the distributions via their statistical distance, and gives a bound for learning in terms of the reciprocal of this distance. Their main insight is to project the distributions onto a few directions (i.e 1D), learn what they can, and then recurse on the data that doesn't appear to be well-separated enough to learn properly. This takes a lot of technical skill to do correctly.
The second paper, by Belkin and Sinha, takes a different approach. They pay more attention to the parameters of the distribution. This can be a problem in general because closeness in distribution does not imply closeness in parameter space. However, they show that the set of all distributions with fixed moments forms a nice algebraic variety, and that the above problem can be quantified by determining how closely this variety folds in on itself (intuitively, if the variety intersects itself, then two far away parameter sets yield the same distribution). Using some standard (but not trivial) results in algebraic geometry, they can bound the complexity of the resulting structures (so that they can estimate the number of samples needed to get to a distiinct region of the space). There's more detail involved in the estimation of parameters and moments and so on.
While both papers are impressive achievements that essentially resolve the theoretical aspects of learning mixtures of distributions, I came away not entirely sure how to compare them. On the one hand, the Moitra/Valiant paper is more explicit and is likely to be less "galactic" in nature. But it appears to be limited to Gaussians. The Sinha/Belkin paper is more general, but uses more abstract machinery that is unlikely to be useful in practice.
So what remains is stilll an effective way of learning Gaussians or other families of distributions, and also a better understanding of how these bounds relate to each other.
A core question of clustering is this: learn a mixture of $k$ $d$-dimensional Gaussians with different means and covariance matrices from samples drawn from the mixture.A long line of research, starting with a paper by Sanjoy Dasgupta back in 1999, produced variations on the following result:
If the Gaussians are "well separated" and have "nice" shapes, then a "small number" of samples suffices to determine the parameters of the system.Here, "parameters" would be means, covariance matrix elements, and relative weights. As time went on, the separations got smaller, the niceness reduced, and the "small number" got better.
These two papers take a slightly more general tack, in different ways. They both eliminate the conditional nature of prior bounds ("if the Gaussians are well separated"), instead replacing this by an unconditional bound ("poly in a parameter capturing the separation").
The first, by Moitra and Valiant (both Ph.D students!) measures the separation between the distributions via their statistical distance, and gives a bound for learning in terms of the reciprocal of this distance. Their main insight is to project the distributions onto a few directions (i.e 1D), learn what they can, and then recurse on the data that doesn't appear to be well-separated enough to learn properly. This takes a lot of technical skill to do correctly.
The second paper, by Belkin and Sinha, takes a different approach. They pay more attention to the parameters of the distribution. This can be a problem in general because closeness in distribution does not imply closeness in parameter space. However, they show that the set of all distributions with fixed moments forms a nice algebraic variety, and that the above problem can be quantified by determining how closely this variety folds in on itself (intuitively, if the variety intersects itself, then two far away parameter sets yield the same distribution). Using some standard (but not trivial) results in algebraic geometry, they can bound the complexity of the resulting structures (so that they can estimate the number of samples needed to get to a distiinct region of the space). There's more detail involved in the estimation of parameters and moments and so on.
While both papers are impressive achievements that essentially resolve the theoretical aspects of learning mixtures of distributions, I came away not entirely sure how to compare them. On the one hand, the Moitra/Valiant paper is more explicit and is likely to be less "galactic" in nature. But it appears to be limited to Gaussians. The Sinha/Belkin paper is more general, but uses more abstract machinery that is unlikely to be useful in practice.
So what remains is stilll an effective way of learning Gaussians or other families of distributions, and also a better understanding of how these bounds relate to each other.
Sunday, October 24, 2010
FOCS Day 0
I'm in Las Vegas for FOCS 2010. It's been a while since I've attended FOCS, and the short distance from Salt Lake was definitely a factor.
Kudos to the organizing committee for the tutorial sessions today. I've long whined about the lack of non-paper-presenting events at theory conferences, and the topics for today were great ones. Unfortunately, a spectacular debacle on the part of the hotel restaurant meant that I (and 11 other poor souls) missed most of Mihai's tutorial on data structures.
But the first tutorial by Ketan Mulmuley was fantastic. Let's be clear. It's impossible to convey any depth of material on GCT in 1.5 hours, but he hit (to me) just the right level of high level exposition and low-level technical conjectures. I also learnt something brand new from the presentation, which I'll try to summarize.
In Godel's incompleteness theorem, we all know that the key step is phrasing a statement of the form "I am not true". The self-referentiality of this statement is what drives the paradox within the logical system that allows you to frame it.
The part that's important to remember is that the logical system has to be powerful enough in the first place, so that it's possible to even do self-referencing. A weak logical system can't do that, which is why Godel's theorem only kicks in once the system is strong enough (a very Greek tragedy concept this, that it is your own power that sows the seeds to destroy you).
It turns out that a similar mechanism comes into play with P vs NP. Mulmuley starts with a "trivial proof of hardness" for a function f. Write down all circuits of small complexity, and for each circuit write down some input for which C(x) != f(x). This table is of course of exponential size, but never mind that.
He now introduces the flip operation. This is the idea that instead of trying to manipulate this large table, we actually store a smaller table of certificates, with the property that from one such certificate, you can reconstruct efficiently a set of circuit and witness pairs from the table, and the set of such certificates cover the entire table. You also need to able to decode these certificates efficiently and quickly verify that an input produced in this manner actually does demonstrate a counter example.
There's a problem with the flip operation though. We're using this flip structure to show that P != NP (nonuniformly for now). On the other hand, the success of the flip operation requires us to construct a mapping from the certificates to the table that can also be verified in polynomial time. But since f is an NP-complete problem, what we are essentially saying is that we can efficiently construct short witnesses of membership or non-membership, which means that we've collapsed P and NP !
You could of course retort by saying, "well I don't want to use the flip operation then !". It turns out that you can't ! He states a result saying that ANY proof separating P and NP will essentially look like a flip-based proof. So no matter what you do, you have to deal with the self-contradicting structure of the flip. The geometric construction (GCT) is his program for constructing the flip so that this cycle of referencing can be broken.
But that's not where the analogy to Godel's theorem comes from. When we start digging into separating the permanent from the determinant, we can translate the problem into an embedding problem over algebraic varieties. This is because both the permanent and determinant have unique characterizations as the only polynomials satisfying certain properties over matrices.
Now the separation problem can be framed as the problem of finding an efficient obstruction that demonstrates the separation between these two varieties. What's even more bizarre is that ANY proof that separates the permanent and the determinant will end up producing such an algebraic-geometric obstruction, even if the proof itself doesn't use algebraic geometry.
So let's review. Any proof of P vs NP will induce a "flip" construction that generates small certificates that explicitly show hardness of a problem. The permanent is one such hard problem, and lends itself to an invariant representation that yields a key obstacle that we need to construct in polynomial time in order to make the flip work.
In other words, we need to be able to construct an object in polynomial time (that to date we don't know how to do in less than triply exponential time) in order to show that these very same poly-time computations CANNOT solve the permanent.
And this is the core paradox at the heart of the program. Our inability to prove that P != NP is because we can't show that P is strong enough to express within itself the certificate that it is NOT strong enough to capture NP.
Mulmuley makes another very interesting point at the end of the tutorial. Many people have wondered why the GCT framework can't be used to prove "easier" bounds for other separations. While he mentions some examples of problems (matrix multiplication) where people are attempting to use the GCT framework to show poly lower bounds, he also points out that it is only because of the beautiful invariant representations of the permanent and determinant that we can bring the machinery of algebraic geometry to bear on the problem. As he says, we got lucky.
Kudos to the organizing committee for the tutorial sessions today. I've long whined about the lack of non-paper-presenting events at theory conferences, and the topics for today were great ones. Unfortunately, a spectacular debacle on the part of the hotel restaurant meant that I (and 11 other poor souls) missed most of Mihai's tutorial on data structures.
But the first tutorial by Ketan Mulmuley was fantastic. Let's be clear. It's impossible to convey any depth of material on GCT in 1.5 hours, but he hit (to me) just the right level of high level exposition and low-level technical conjectures. I also learnt something brand new from the presentation, which I'll try to summarize.
In Godel's incompleteness theorem, we all know that the key step is phrasing a statement of the form "I am not true". The self-referentiality of this statement is what drives the paradox within the logical system that allows you to frame it.
The part that's important to remember is that the logical system has to be powerful enough in the first place, so that it's possible to even do self-referencing. A weak logical system can't do that, which is why Godel's theorem only kicks in once the system is strong enough (a very Greek tragedy concept this, that it is your own power that sows the seeds to destroy you).
It turns out that a similar mechanism comes into play with P vs NP. Mulmuley starts with a "trivial proof of hardness" for a function f. Write down all circuits of small complexity, and for each circuit write down some input for which C(x) != f(x). This table is of course of exponential size, but never mind that.
He now introduces the flip operation. This is the idea that instead of trying to manipulate this large table, we actually store a smaller table of certificates, with the property that from one such certificate, you can reconstruct efficiently a set of circuit and witness pairs from the table, and the set of such certificates cover the entire table. You also need to able to decode these certificates efficiently and quickly verify that an input produced in this manner actually does demonstrate a counter example.
There's a problem with the flip operation though. We're using this flip structure to show that P != NP (nonuniformly for now). On the other hand, the success of the flip operation requires us to construct a mapping from the certificates to the table that can also be verified in polynomial time. But since f is an NP-complete problem, what we are essentially saying is that we can efficiently construct short witnesses of membership or non-membership, which means that we've collapsed P and NP !
You could of course retort by saying, "well I don't want to use the flip operation then !". It turns out that you can't ! He states a result saying that ANY proof separating P and NP will essentially look like a flip-based proof. So no matter what you do, you have to deal with the self-contradicting structure of the flip. The geometric construction (GCT) is his program for constructing the flip so that this cycle of referencing can be broken.
But that's not where the analogy to Godel's theorem comes from. When we start digging into separating the permanent from the determinant, we can translate the problem into an embedding problem over algebraic varieties. This is because both the permanent and determinant have unique characterizations as the only polynomials satisfying certain properties over matrices.
Now the separation problem can be framed as the problem of finding an efficient obstruction that demonstrates the separation between these two varieties. What's even more bizarre is that ANY proof that separates the permanent and the determinant will end up producing such an algebraic-geometric obstruction, even if the proof itself doesn't use algebraic geometry.
So let's review. Any proof of P vs NP will induce a "flip" construction that generates small certificates that explicitly show hardness of a problem. The permanent is one such hard problem, and lends itself to an invariant representation that yields a key obstacle that we need to construct in polynomial time in order to make the flip work.
In other words, we need to be able to construct an object in polynomial time (that to date we don't know how to do in less than triply exponential time) in order to show that these very same poly-time computations CANNOT solve the permanent.
And this is the core paradox at the heart of the program. Our inability to prove that P != NP is because we can't show that P is strong enough to express within itself the certificate that it is NOT strong enough to capture NP.
Mulmuley makes another very interesting point at the end of the tutorial. Many people have wondered why the GCT framework can't be used to prove "easier" bounds for other separations. While he mentions some examples of problems (matrix multiplication) where people are attempting to use the GCT framework to show poly lower bounds, he also points out that it is only because of the beautiful invariant representations of the permanent and determinant that we can bring the machinery of algebraic geometry to bear on the problem. As he says, we got lucky.
Wednesday, October 20, 2010
On outreach to applied communities
There's an argument playing out on cstheory (yes, we need a better name) on whether we should encourage or discourage questions like "how can I model X phenomenon theoretically", or "Are applied questions off-topic"
While Scott Aaronson posted an eloquent defense of why we should always entertain such questions, the general tone of the responses has been negative. The main fear has been a 'slippery slope' - that if we allow one modelling question, then the site would be overrun by modelling questions.
I think this sentiment is particularly interesting in the context of David Johnson's post requesting examples where approximation algorithms were deployed usefully in practice (and that he couldn't come up with many good examples)
The truth is that outreach to more applied communities is not about taking your algorithms hammer and beating their heuristic over the head with it. As I've said before, you have to have a DRAMATIC improvement in performance before people will change their standard practices.
It's firstly about communicating a style of asking and answering questions, even if the actual answers are "trivial". A collaboration where you persuade someone to use max flows might not be theoretically very splashy, but it has a huge impact in how people think about algorithms, theory and problem solving.
Doing this first prepares the ground for future collaborations. If you want someone to use your new and snazzy approximation for vertex cover, you have to first convince them that vertex cover makes sense, and before that you have to convince them that even modelling the problem as a graph makes sense. Believe me when I say that the very notion of defining a problem formally before solving it is not how work gets done in many applied areas.
Michael Mitzenmacher makes a similar point in a comment to the above post, where he says:
While Scott Aaronson posted an eloquent defense of why we should always entertain such questions, the general tone of the responses has been negative. The main fear has been a 'slippery slope' - that if we allow one modelling question, then the site would be overrun by modelling questions.
I think this sentiment is particularly interesting in the context of David Johnson's post requesting examples where approximation algorithms were deployed usefully in practice (and that he couldn't come up with many good examples)
The truth is that outreach to more applied communities is not about taking your algorithms hammer and beating their heuristic over the head with it. As I've said before, you have to have a DRAMATIC improvement in performance before people will change their standard practices.
It's firstly about communicating a style of asking and answering questions, even if the actual answers are "trivial". A collaboration where you persuade someone to use max flows might not be theoretically very splashy, but it has a huge impact in how people think about algorithms, theory and problem solving.
Doing this first prepares the ground for future collaborations. If you want someone to use your new and snazzy approximation for vertex cover, you have to first convince them that vertex cover makes sense, and before that you have to convince them that even modelling the problem as a graph makes sense. Believe me when I say that the very notion of defining a problem formally before solving it is not how work gets done in many applied areas.
Michael Mitzenmacher makes a similar point in a comment to the above post, where he says:
I do think, however, that sometimes the focus of theorists -- to get the best constant-approximation or to shave log or log log factors off -- obscures rather than highlights a good part of what I see as the real "practical value" of this line of research. Focusing on what algorithmic ideas underlie the approximation, and more implementation and experimentation, would (I think) give more real-world power to this theoretical work.
Tuesday, October 19, 2010
Practical Applications of Approximation Algorithms
(Guest Post by David Johnson)
In my Knuth Prize Lecture on approximation algorithms at the last STOC conference, I celebrated the many great theoretical advances we have seen in the area of approximation algorithms over the last four decades, but lamented the apparent paucity of practical applications of this work. We motivate our work in this area as a way of coping with NP-hardness, but how many people who actually have to do such coping in practice are
using our ideas?
In my talk I could only come up with a few examples, these from our work at AT&T Labs - Research, where we have adapted the Goeman-Williamson primal-dual approximation algorithm for the Prize Collecting Steiner Tree problem for use in tools that help design access networks, and where exponential potential function methods for approximating multicommodity flows are being exploited in a proposed content-distribution scheme. I also noted that of the 14 Kanellakis "Theory and Practice Awards" given out so far, of which some 6 or 7 have been for algorithms, only one, that to Freund and Schapire for their statistical "boosting" technique, could be viewed as related to approximation algorithms, and the boosting research is typically classified instead as Learning Theory.
So, I think many viewed my talk as a rather negative exercise. Certainly, practical impact is only one dimension along which to evaluate a field, and, if we relied only on practical motivations, we would not have developed the deep and informative theory we now have. However, practicality IS an important dimension, and I hope that my inability to identify many examples of practical impact was more a fault of my own ignorance, than one of the field. Giving a talk about this to a primarily theoretical audience did not develop many new leads, so I'm hoping that a blog posting will be more successful.
In particular, I would like to collect
For both types of stories, I'd like as much detail as possible - who did the work, where, etc., and citations if known. You can post your nominations/comments on this blog, or send them directly to me (dsj@research.att.com). If you post as a comment, please do not do so anonymously, as I may want to contact you for more information.
Assuming I get a good response, I plan to prepare a survey paper (or at least another blog posting) summarizing what I learn.
Thanks! David Johnson (dsj@research.att.com)
In my Knuth Prize Lecture on approximation algorithms at the last STOC conference, I celebrated the many great theoretical advances we have seen in the area of approximation algorithms over the last four decades, but lamented the apparent paucity of practical applications of this work. We motivate our work in this area as a way of coping with NP-hardness, but how many people who actually have to do such coping in practice are
using our ideas?
In my talk I could only come up with a few examples, these from our work at AT&T Labs - Research, where we have adapted the Goeman-Williamson primal-dual approximation algorithm for the Prize Collecting Steiner Tree problem for use in tools that help design access networks, and where exponential potential function methods for approximating multicommodity flows are being exploited in a proposed content-distribution scheme. I also noted that of the 14 Kanellakis "Theory and Practice Awards" given out so far, of which some 6 or 7 have been for algorithms, only one, that to Freund and Schapire for their statistical "boosting" technique, could be viewed as related to approximation algorithms, and the boosting research is typically classified instead as Learning Theory.
So, I think many viewed my talk as a rather negative exercise. Certainly, practical impact is only one dimension along which to evaluate a field, and, if we relied only on practical motivations, we would not have developed the deep and informative theory we now have. However, practicality IS an important dimension, and I hope that my inability to identify many examples of practical impact was more a fault of my own ignorance, than one of the field. Giving a talk about this to a primarily theoretical audience did not develop many new leads, so I'm hoping that a blog posting will be more successful.
In particular, I would like to collect
(A) Stories about algorithms or algorithmic approaches developed by approximation algorithm theorists that were implemented and applied, either directly or in modified form, by people to solve real-world problems.
(B) Stories about the analysis of algorithms developed by others (for example, the greedy algorithm for SET COVER) that influenced the use of these algorithms in practice, or at least helped explain their performance and hence was cited in "Applications" papers.The algorithms need not be restricted to NP-hard problems -- I am also interested in approximation algorithms for problems with polynomial-time optimization algorithms that can be too slow for some practical applications.
For both types of stories, I'd like as much detail as possible - who did the work, where, etc., and citations if known. You can post your nominations/comments on this blog, or send them directly to me (dsj@research.att.com). If you post as a comment, please do not do so anonymously, as I may want to contact you for more information.
Assuming I get a good response, I plan to prepare a survey paper (or at least another blog posting) summarizing what I learn.
Thanks! David Johnson (dsj@research.att.com)
SoCG deadline, and a new NSF rule
SoCG CFP is out:
In unrelated news, the NSF appears to have a new policy for 'data management' and will require a new supplementary document to this effect. Note that since it's a mandatory document, it will affect theory proposals as well:
- Titles/abstracts: Nov 22
- Papers: Dec 1
- Notification: Feb 14
- June 13-15, conference.
Anticipating the usual high overall quality of submissions, the programMy optimistic side is excited by this, and I really hope we can see more papers on diverse topics. My pessimistic side is grumping "yes, that means any papers that aren't mine". sigh...
committee intends to accept more papers than was typical in previous years. Also, we intend to interpret the scope of the conference broadly, and will accept all papers of high quality that are of significant interest to our research community. The conference venue in Paris is attractive and allows a bigger conference than previous years.
In unrelated news, the NSF appears to have a new policy for 'data management' and will require a new supplementary document to this effect. Note that since it's a mandatory document, it will affect theory proposals as well:
Plans for data management and sharing of the products of research. Proposals must include a supplementary document of no more than two pages labeled “Data Management Plan.” This supplement should describe how the proposal will conform to NSF policy on the dissemination and sharing of research results (see AAG Chapter VI.D.4), and may include:
* The types of data, samples, physical collections, software, curriculum materials, and other materials to be produced in the course of the project
* The standards to be used for data and metadata format and content (where existing standards are absent or deemed inadequate, this should be documented along with any proposed solutions or remedies)
* Policies for access and sharing including provisions for appropriate protection of privacy, confidentiality, security, intellectual property, or other rights or requirements
* Policies and provisions for re-use, re-distribution, and the production of derivatives
* Plans for archiving data, samples, and other research products, and for preservation of access to them
Tuesday, October 05, 2010
Absolutely terrible news: Partha Niyogi passes away
(Via Lance) Partha Niyogi just passed away.
I first met Partha at SoCG 2007 in Gyeongju, where he gave an invited presentation on geometric perspectives in machine learning. We also spent a very pleasant day playing hookey from the conference, wandering around the nearby tourist spots, and talking about geometry and machine learning. He was a brilliant researcher with an impatience and drive that led him to do some truly excellent work.
Anyone who's ever dabbled in machine learning knows about the strong connections between ML and geometry, dating back to the very notion of VC dimension. But while the connections between the areas are manifest and plentiful, there haven't been many people who could successfully navigate both realms. Partha was one of those unusual people, who coupled deep mathematical insight with a strong vision for problems in ML. Most recently, he organized a wonderful summer school in machine learning and geometry, whose syllabus is worth perusing to get a sense of the depth of this interaction.
In many circles, he's most known for his work in manifold learning, where in collaboration with Misha Belkin, Steve Smale and others, he laid out a series of rigorous results on the problem of how to "learn" a low dimensional manifold given access to samples of points from it. The work on Laplacian Eigenmaps is a key marker in this area, and has had tremendous influence in the realm of "non-Euclidean" data analysis. Among his other recent contributions in theory-land are a neat result from FOCS 2006 with Belkin and Narayanan on sampling the surface of a convex polytope using heat flow and the Laplace operator.
It's a great loss.
I first met Partha at SoCG 2007 in Gyeongju, where he gave an invited presentation on geometric perspectives in machine learning. We also spent a very pleasant day playing hookey from the conference, wandering around the nearby tourist spots, and talking about geometry and machine learning. He was a brilliant researcher with an impatience and drive that led him to do some truly excellent work.
Anyone who's ever dabbled in machine learning knows about the strong connections between ML and geometry, dating back to the very notion of VC dimension. But while the connections between the areas are manifest and plentiful, there haven't been many people who could successfully navigate both realms. Partha was one of those unusual people, who coupled deep mathematical insight with a strong vision for problems in ML. Most recently, he organized a wonderful summer school in machine learning and geometry, whose syllabus is worth perusing to get a sense of the depth of this interaction.
In many circles, he's most known for his work in manifold learning, where in collaboration with Misha Belkin, Steve Smale and others, he laid out a series of rigorous results on the problem of how to "learn" a low dimensional manifold given access to samples of points from it. The work on Laplacian Eigenmaps is a key marker in this area, and has had tremendous influence in the realm of "non-Euclidean" data analysis. Among his other recent contributions in theory-land are a neat result from FOCS 2006 with Belkin and Narayanan on sampling the surface of a convex polytope using heat flow and the Laplace operator.
It's a great loss.
Monday, October 04, 2010
We're hiring !
The School of Computing is looking for three ! count 'em ! THREE ! tenure-track faculty this year, in a broad search with interests in:
For theory folks, probably the most relevant of the three areas of interest is the big data search, especially if you're interested in data mining/machine learning/statistics and other forms of data analysis. But if you have strengths in any of the other two areas, then make sure to highlight that.
Email me if you have any questions about this. I'm very excited about growing our large-data program by getting strong algorithms folks. rec
algorithms, concurrent software, data bases, data mining, formal verification, large data analysis, machine learning, performance verification, parallel systems, robotics, and theory.We're looking for interdisciplinary folks with interests in possily more than one of the above, and there are nominally three "areas of interest" that we are looking in: parallel computing, robotics and big data.
For theory folks, probably the most relevant of the three areas of interest is the big data search, especially if you're interested in data mining/machine learning/statistics and other forms of data analysis. But if you have strengths in any of the other two areas, then make sure to highlight that.
Email me if you have any questions about this. I'm very excited about growing our large-data program by getting strong algorithms folks. rec
Monday, September 27, 2010
FOCS travel awards and registration deadline: Apply SOON !
Paul Beame reminds me that the FOCS early registration deadline and hotle registration deadline are coming up soon (this Thursday). Don't forget that FOCS has three tutorials on Saturday before the conference starts, by Ketan Mulmuley, Mihai Patrascu, and Tim Roughgarden (which will be on geometric complexity theory, algorithmic game theory, and how to annoy everyone with your blog - sorry Mihai, I'm joking :))
Travel awards are also still available for the conference: Quoting Paul (emphasis mine):
Travel awards are also still available for the conference: Quoting Paul (emphasis mine):
There is still a bunch of NSF travel support money available for students/postdocs because we can only fund one person per US institution. All the award decisions have been made at institutions where someone applied by Sept 23rd but we are still open to new applications for travel support (not including registration) from other institutions. There is no hard deadline but people should please apply ASAP (ideally by the end of this week) because we will make final decisions on awards soon. Follow the Travel Support link at: http://www.egr.unlv.edu/~larmore/FOCS/focs2010/p.s cstheory Q&A has been sucking up all the time that I should have been spending blogging ... ahem.. doing research. We're at 1500+ users and counting, so come on in and join Lance's students and all the others :).
Thursday, September 02, 2010
Geometry @ Barriers
Bill Gasarch's summary of the Barriers II workshop omitted discussion of the geometry session, and Piotr Indyk kindly agreed to write a brief summary for your entertainment. Here it is, lightly edited and with links added. If there are talks I'm missing links for, do let me know and I'll add them in.
The "(Geo)metric Algorithms" workshop took place on Monday, August 30, at Princeton. It was the last day of the Barriers II Workshop, dedicated to geometric and metric algorithms.
Sariel Har-Peled was the opening act. He spoke about various structures in geometry that approximate properties of large point-sets, such as epsilon-nets, epsilon-approximations and core-sets. He started by stating that finding a needle in a haystack is a problem with many solutions, e.g., one can burn it down and sift through the ashes. He did not implement any of the solutions though (and the Princeton Fire Department was very grateful for that). He finished by asking for which problems we can (efficiently) find short certificates of near-optimality.
Alex Andoni spoke next, about high-dimensional nearest neighbors. He gave an overview of the state of the art, for Euclidean and other spaces. He asked whether we can construct a partitioning of R^t into "round" cells that supports point location in poly(t) time. Such structure could make the recent theoretically-optimal Locality-Sensitive Hashing scheme practical. He was also wondering whether we can find better embeddings of various metrics (edit distance, Earth-Mover Distance) into various simpler spaces (L1 or product spaces).
Jeff Erickson was the last one before the lunch. He spoke about computational topology, focusing mostly on algorithms for bounded genus graphs. He covered shortest paths, maxflow and mincut, charming the audience with exquisitely drawn multi-dimensional homology diagrams, and a mesh dragon (ed: what ? no bunnies?). He presented an algorithm for max flow with running time of the form (quote) "n UglyPoly(g,log n, log C)" where g is the genus, C is the capacity bound and n is the number of points. He was wondering whether there was any way to make the bound less ugly, perhaps by making the algorithm combinatorial.
After lunch, Anupam Gupta spoke about doubling metrics and their algorithmic applications. Surprisingly many geometric algorithms can be generalized to work for arbitrary such metrics. In his talk, Anupam covered labeling schemes and optimization problems. He finished by asking whether there is a PTAS for TSP in doubling metrics, generalizing the result by Arora-Mitchell for the Euclidean spaces.
Finally, James Lee talked about the sparsest cut problem and its generalizations. Progress on this problem has often led to many fascinating developments in mathematics and TCS. The problem is closely related to embeddings of certain classes of metric spaces into L1. The main question now is to determine whether the best known approximation/distortion bounds for these problems ($\sqrt{\log n}$) are optimal.
All in all it was a fun event (although I helped organizing it, so what do I know). The videos of the talks will be available shortly.
No haystacks were harmed while filming this workshop.
The "(Geo)metric Algorithms" workshop took place on Monday, August 30, at Princeton. It was the last day of the Barriers II Workshop, dedicated to geometric and metric algorithms.
Sariel Har-Peled was the opening act. He spoke about various structures in geometry that approximate properties of large point-sets, such as epsilon-nets, epsilon-approximations and core-sets. He started by stating that finding a needle in a haystack is a problem with many solutions, e.g., one can burn it down and sift through the ashes. He did not implement any of the solutions though (and the Princeton Fire Department was very grateful for that). He finished by asking for which problems we can (efficiently) find short certificates of near-optimality.
Alex Andoni spoke next, about high-dimensional nearest neighbors. He gave an overview of the state of the art, for Euclidean and other spaces. He asked whether we can construct a partitioning of R^t into "round" cells that supports point location in poly(t) time. Such structure could make the recent theoretically-optimal Locality-Sensitive Hashing scheme practical. He was also wondering whether we can find better embeddings of various metrics (edit distance, Earth-Mover Distance) into various simpler spaces (L1 or product spaces).
Jeff Erickson was the last one before the lunch. He spoke about computational topology, focusing mostly on algorithms for bounded genus graphs. He covered shortest paths, maxflow and mincut, charming the audience with exquisitely drawn multi-dimensional homology diagrams, and a mesh dragon (ed: what ? no bunnies?). He presented an algorithm for max flow with running time of the form (quote) "n UglyPoly(g,log n, log C)" where g is the genus, C is the capacity bound and n is the number of points. He was wondering whether there was any way to make the bound less ugly, perhaps by making the algorithm combinatorial.
After lunch, Anupam Gupta spoke about doubling metrics and their algorithmic applications. Surprisingly many geometric algorithms can be generalized to work for arbitrary such metrics. In his talk, Anupam covered labeling schemes and optimization problems. He finished by asking whether there is a PTAS for TSP in doubling metrics, generalizing the result by Arora-Mitchell for the Euclidean spaces.
Finally, James Lee talked about the sparsest cut problem and its generalizations. Progress on this problem has often led to many fascinating developments in mathematics and TCS. The problem is closely related to embeddings of certain classes of metric spaces into L1. The main question now is to determine whether the best known approximation/distortion bounds for these problems ($\sqrt{\log n}$) are optimal.
All in all it was a fun event (although I helped organizing it, so what do I know). The videos of the talks will be available shortly.
No haystacks were harmed while filming this workshop.
Wednesday, August 25, 2010
Latest news from the unnamed-but-working-on-it theoryCS Q&A site
4 days in (public) beta, and the theoryCS Q&A site (or as someone described it, the 21st century Usenet) is chugging along. There are nearly 600 users now, with nearly 300 "active" users - people who've posted, asked a question, commented, etc. Since there isn't a way to broadcast to the user community directly, I'm taking the liberty of doing it here.
If you're enjoying using the site, please visit the meta site (click the small 'meta' on the top banner). If you don't like how the site is working, please visit the meta site. In both cases, you'll find important discussions about how the site is working and should work, and your input will shape how it evolves. For example,
Another reminder: please use your votes liberally. In fact, if you think a question is worthy of being read, it probably deserves an upvote (and the same for an answer). Frequent voting makes the whole system run smoothly.
And now, back to your regularly scheduled theoryCS programming: some interesting recent questions for your entertainment (please comment at the question links, rather than here):
If you're enjoying using the site, please visit the meta site (click the small 'meta' on the top banner). If you don't like how the site is working, please visit the meta site. In both cases, you'll find important discussions about how the site is working and should work, and your input will shape how it evolves. For example,
- What's the appropriate level for questions on the site ?
- How should questions be tagged (for easy searching and indexing)
- Who should be moderating ?
- Which questions should be closed (deactivated) if any ?
Another reminder: please use your votes liberally. In fact, if you think a question is worthy of being read, it probably deserves an upvote (and the same for an answer). Frequent voting makes the whole system run smoothly.
And now, back to your regularly scheduled theoryCS programming: some interesting recent questions for your entertainment (please comment at the question links, rather than here):
Monday, August 23, 2010
cstheory Q&A site now open to the public !
The theoryCS Q&A site, in private beta the last seven days, is now open to the public. Please visit, ask questions, answer them, and hopefully we can make this a valuable resource for the community. There are currently over 100 questions, 300 answer, and 300+ users ! Some of the questions that I thought were quite interesting:
- Analogs of compressed sensing
- The importance of Integrality Gap
- Surprising Results in Complexity
- How hard is unshuffling a string (now with a bounty!)
Monday, August 16, 2010
cstheory q&a site now open !
After a long wait, the theoryCS q&a site is now open. It's in private beta for the next 7 days, so if you didn't commit already, you'll have to wait till next Monday.
Please visit the site, ask your questions, and answer other questions. Some points to note from experience with Mathoverflow:
Please visit the site, ask your questions, and answer other questions. Some points to note from experience with Mathoverflow:
- If you're so inclined, please participate in the meta site as well. That's the place for discussions about the site itself, and is a good place to get involved and help shape the community.
- Please vote liberally and often. Especially in the beginning, voting questions and answers up when appropriate helps encourage others to stick around and participate more. If a question seems interesting enough to read, it deserves an upvote !
Saturday, August 14, 2010
Social theoryCS...now 98% better...
Whatever you may think of the P vs NP hullabaloo over the past week, it has to be said that as a social experiment in peer review, this was an exhilarating and magnificent process to watch. There's enough chatter in the media about how this might point the way forward for peer review, and I'm skeptical of drawing too many conclusions from this one experiment with arguably the most important problem in our field.
But I'm encouraged by both the level of participation, and the enthusiasm it has generated about the field. I can't troll through the over 800 comments to find them, but I read numerous comments about how watching this process unfold made the commenter ever more excited about getting into theoryCS. Bob Sloan made a brief cameo to point out the value of this discussion as an outreach tool.
This is a long way of coming around to the news that the theoryCS Q&A site is now at 98% commitment, which means that some time in the next few days it'll go into beta. The beta stage starts with a 'private' seven day period, in which only those who committed (and therefore have promised to answer/ask a total of 10 questions over the entire beta duration of 90 days) get to use the site. After that seven day period, the doors will open for any interested participants.
The initial seven day period will have strong administrative elements (seeding the site with questions, discussing meta issues about the scope of questions etc), and while no major issues will be resolved, you can have some influence about how the forum gets shaped if you get in early. So if you haven't committed yet, do so, otherwise you'll have to wait the 7 days to get in.
But I'm encouraged by both the level of participation, and the enthusiasm it has generated about the field. I can't troll through the over 800 comments to find them, but I read numerous comments about how watching this process unfold made the commenter ever more excited about getting into theoryCS. Bob Sloan made a brief cameo to point out the value of this discussion as an outreach tool.
This is a long way of coming around to the news that the theoryCS Q&A site is now at 98% commitment, which means that some time in the next few days it'll go into beta. The beta stage starts with a 'private' seven day period, in which only those who committed (and therefore have promised to answer/ask a total of 10 questions over the entire beta duration of 90 days) get to use the site. After that seven day period, the doors will open for any interested participants.
The initial seven day period will have strong administrative elements (seeding the site with questions, discussing meta issues about the scope of questions etc), and while no major issues will be resolved, you can have some influence about how the forum gets shaped if you get in early. So if you haven't committed yet, do so, otherwise you'll have to wait the 7 days to get in.
Wednesday, August 11, 2010
P vs NP: What I've learnt so far...
(ed: note. it is somewhat embarrassing to be categorized as someone "trying to unravel what is up with the claimed proof". All I've really helped with is getting the wiki set up, and I'm very impressed with the amount of work that everyone is putting into keeping it current)
Whether or not Deolalikar's proof turns out to work, I have to say that in a span of three days, I've learnt a heck of a lot about the individual components in his paper.
My take is slightly different. While none of the "revelations" listed above are new to people in the relevant areas, they're certainly new to me, and given how unlikely it is that I'd be able to pigeon-hole the relevant experts one-on-one to explain these ideas to me, the discussion is serving an important purpose. In effect, it has created a virtual workshop with even more discussion than a real one !
We've spent a lot of time over the past few years bemoaning the fragmentation of theoretical computer science, and have spent many blog-hours arguing over how to make STOC a destination conference for theoreticians again. But what the discussion over this paper has done is bring together experts in very different areas to talk with each other and exchange ideas, results and the crucial "mental frameworks" that are usually impossible to share except in oral discussions.
And that, in my view, is a net plus regardless of what happens with the proof.
Whether or not Deolalikar's proof turns out to work, I have to say that in a span of three days, I've learnt a heck of a lot about the individual components in his paper.
- Like everyone else, I learnt my descriptive complexity back in the day, and marvelled at the fact that P, NP and PSPACE could be characterized syntactically. The discussions about the subtleties of the order relation in LFP have been fascinating though, and while the issue remains unresolved, there's a wealth of new(er) material that I've now been exposed to.
- Similarly, while I was familiar with the idea that hardness could be captured as a phase transition in random k-SAT, the bizarreness of the landscape (clustering! freezing! condensation!) was quite new to me, and it's been illuminating to learn from the experts.
- The relationship between the solution space for k-SAT and error-correcting codes is also something that I was not aware of. And it might be the source of yet another issue with the paper.
- A point made by Terry Tao is even more intriguing:
If nothing else, this whole experience has highlighted a “philosophical” barrier to P != NP which is distinct from the three “hard” barriers of relativisation, natural proofs, and algebraisation, namely the difficulty in using average-case (or “global”) behaviour to separate worst-case complexity, due to the existence of basic problems (e.g. k-SAT and k-XORSAT) which are expected to have similar average case behaviour in many ways, but completely different worst case behaviour. (I guess this difficulty was well known to the experts, but it is probably good to make it more explicit.)
My take is slightly different. While none of the "revelations" listed above are new to people in the relevant areas, they're certainly new to me, and given how unlikely it is that I'd be able to pigeon-hole the relevant experts one-on-one to explain these ideas to me, the discussion is serving an important purpose. In effect, it has created a virtual workshop with even more discussion than a real one !
We've spent a lot of time over the past few years bemoaning the fragmentation of theoretical computer science, and have spent many blog-hours arguing over how to make STOC a destination conference for theoreticians again. But what the discussion over this paper has done is bring together experts in very different areas to talk with each other and exchange ideas, results and the crucial "mental frameworks" that are usually impossible to share except in oral discussions.
And that, in my view, is a net plus regardless of what happens with the proof.
Tuesday, August 10, 2010
A 'polymath' home for analysis of the Deolalikar proof
In collaboration with the Polymath project (and many thanks to Terry Tao for making this happen, and putting in lots of editing work in short order), there's now a new wiki to collect various threads of the discussion on the Deolalikar P != NP paper (which has been updated). With a lot of help from Terry, I've seeded the wiki with the initial discussion points that have come up. Please continue to edit this page as new ideas come up, or there's other discussion of the paper.
This wiki replaces the Google doc that I had originally set up: it's a lot easier to edit, and Google was struggling under the weight of all the people trying to view the file.
The Lipton/Regan posts will continue to host the main research threads. If you are so inclined, you can use this post for "meta"-discussions as is customary in polymath land. Content will be transferred over to the wiki periodically, and more discussion threads can be forked if things start getting unwieldy (the first Lipton post is pushing 117 comments already).
This wiki replaces the Google doc that I had originally set up: it's a lot easier to edit, and Google was struggling under the weight of all the people trying to view the file.
The Lipton/Regan posts will continue to host the main research threads. If you are so inclined, you can use this post for "meta"-discussions as is customary in polymath land. Content will be transferred over to the wiki periodically, and more discussion threads can be forked if things start getting unwieldy (the first Lipton post is pushing 117 comments already).
Monday, August 09, 2010
On the Deolalikar proof: Crowdsourcing the discussion ?
Update: the google doc has been replaced by a wiki. Please read this post.
By now everyone knows about the new proposed proof that P $\ne$ NP by Vinay Deolalikar. Better minds than mine are on the case right now, and little snippets of questions are coming out in comments (especially on Dick Lipton's original post).
It's a little hard to keep track of all the discussions, so I thought I'd try a crowd-sourcing experiment. At this link is a google doc that contains some of the initial discussion topics being raised around the proof. It's crudely organized, with a section for each major set of issues, and paragraphs for each person's comment, with sourcing via URL.
It's editable, so here's the idea. As you see issues get raised and resolved, enter that into the doc. The following rules apply:
Let's see if this works !
By now everyone knows about the new proposed proof that P $\ne$ NP by Vinay Deolalikar. Better minds than mine are on the case right now, and little snippets of questions are coming out in comments (especially on Dick Lipton's original post).
It's a little hard to keep track of all the discussions, so I thought I'd try a crowd-sourcing experiment. At this link is a google doc that contains some of the initial discussion topics being raised around the proof. It's crudely organized, with a section for each major set of issues, and paragraphs for each person's comment, with sourcing via URL.
It's editable, so here's the idea. As you see issues get raised and resolved, enter that into the doc. The following rules apply:
- No discussions: this should be comment/resolution only !
- No personal, or nontechnical commentary. This is purely for discussion of the mathematics involved, and nothing else
- Add references (urls, or whatever) whenever possible, and quote all context so as not to cause miscommunication.
Let's see if this works !
Thursday, July 08, 2010
TheoryOverflow: An Update
Now that I'm done with SODA (any word on number of actual submissions?), I thought I'd do a brief update on the proposed theoryCS Q&A site (currently laboring under the inelegant name of TheoryOverflow). I've had various questions from people, and have wondered about others. So rather than force you all to trawl meta.stackoverflow.com for answers, I thought I'd dish them out here.
- I want my TO site ! When is it coming ?
The site is going through what is called a 'commit' stage. The StackExchange overlords (the people providing the service) have in their infinite wisdom decided that the success of such sites is predicated on people committing (with their names and email) to participating, and so we're slowly building up enough commit mojo to get into a trial stage
- But we have more commits than the average attendance at STOC !
Ok. firstly, that's rude ! Secondly, there's a complicated formula by which the system determines whether we have enough commits to move into a beta stage. it's also being throttled right now at 90% of its true value because the software for making the sites is still being tested on the few sites that are already in beta.
- At this rate (248 commits, 27% progress), we'd need 1000 commits to get to beta. That's larger than the attendance at STOC, FOCS and SODA put together !
Say after me three times: theory conferences are all fine, and we don't have to do anything to change anything about them. Feeling better now ? So the process by which commit progress is calculated is very complicated, involving your reputation on related sites, the number of "badges" you've earned, how friendly you are with Lady Gaga, and other such mysterious parameters. So while there's some correlation with the number of commits, high-reputation users on related sites can bump up the progress meter, under the rationale that people used to Q&A sites are more likely to help this site get off the ground.
- But my mathoverflow rep doesn't appear to count ?
No it doesn't. there appear to be technical complications involved in this, because MO used an older version of the software. I personally question this approach to the commit phase, but it's not my software.
- This is silly: why can't we all just go over to mathoverflow ?
This is a tricky point. The MO folks have been more than welcoming to theoryCS, and they've explicitly said that they'd be happy to have us over at their site. While I personally would not mind at all if we just started using MO more regularly, I feel that we might get drowned out in the much larger universe of MO, and if we can get our own site, it might be easier to navigate and find interesting questions/answers. But it's always an option.
- We're computer scientists, aren't we ? why can't we roll our own ?
Um, well, ... we're THEORETICAL computer scientists, so theoretically we could. Oh wait, you actually want us to do it now ? how annoyingly practical !
More seriously, there is actually an open source system called OSQA that's powering the new machine learning Q&A site called metaoptimize. I didn't hear about this till a few days ago, but it's definitely something that we can consider if the theoryoverflow site appears to stall.
- So what now ?
For now, we (that means YOU!) continue to drum up support and commits for theoryoverflow. In terms of average number of commits/day, we're still doing quite well, and the StackExchange folks have indicated that they're likely to change the formula for commit progress based on how the sites already in beta are doing. If a few more weeks go by and things look stalled, we can revisit the matter.
Saturday, July 03, 2010
Tools every modern conference needs
(while I procrastinate on my SODA edits)
- Crowdvine: an all-encompassing social network solution for conferences that includes schedule planning, networking, activity monitors (who's coming to my talk) etc
- A paper discussion site (could be within crowdvine, or even something like Mark Reid's ICML discussion site)
- A good paper submission/review manager like HotCRP (not CMT !)
- Videolectures.net
- Facebook/twitter/blog for official announcements.
- At the very least, a website with all the papers for download. If necessary,zip or torrent links for downloading proceedings (especially if videos are involved).
And no, we did none of these for SoCG 2010. But a guy can dream, no ? While I'd be shocked to see crowdvine at any theory conference (price, culture, you name it), I think videolectures.net would be a valuable resource, and many of the rest require time but are otherwise free.
Subscribe to:
Posts (Atom)