NSF Workshop: Electronic Design Automation

I'm currently at an NSF Worshop on Electronic Design Automation (the thing that used to be called VLSI design). I'm here as part of the 'theory audience' along with Vijaya Ramachandran and Dick Lipton (blogger power!).

Thankfully, Dick has posted an extensive summary of the day of talks, so I don't have to. Our mandate here is to listen in on the discussions and come up with a response that suggests avenues where theory folk might have something useful to contribute.

From a purely biased algorithms perspective, one thing that strikes me about the EDA community (at least in the formal methods/verification realm) is their unwillingness to give up in the face of beyond-NP-completeness. What I mean is this: most of my training in algorithms (and this is likely true for you as well) is in the polynomial-time regime: all the algorithic paradigms we learn are effective at reducing the complexity of an algorithm from one polynomial to another.

When we engage with NP-hardness, we switch modes to approximations, and focus on the issue of quality: even the approximation algorithms themselves run in poly time. There are very few people (David Eppstein comes to mind) who work on algorithms in the exponential/subexponential realm and will worry about (say) reducing the base of the exponent for SAT or graph coloring or other hard problems.

The verification folks don't necessarily solve their (very hard) problems exactly, but they do design all kinds of tricks (and heuristics) to deal with these problems, because they actually need to solve them ! In my view, it wouldn't be a bad idea for students learning algorithms to learn at least a few tricks for designing algorithms that might run in exponential time, but are efficient. Remember that exponential might be better than n^100 for many values of n.

One thing that came to mind as I listened to talks. With the exception of a talk by Rupak Mazumdar on faulty computations, and a talk by Ed Clarke (yes, that Ed Clarke) on statistical model checking (based on the Neyman-Pearson hypothesis testing framework), there was little talk of the role that randomization might have to play in the problems of EDA.

A second thought was how the lessons of massive data analysis might be useful in the realm of DA. One speakr described one critical problem as being the degree of complexity associated with current DA tools: there are over 4000 "knobs" to turn in one such tool ! It's believed that these knobs are not independent, and might even be contradictory. If we think of each "run" of the DA tool, outputing some kind of chip layout, as a point in this 4000+ dimensional space, I wonder whether techniques for dimensionality reduction and manifold analysis might be useful to find a set of "core knobs" that control the process.

I have to say that it's nice to attend a workshop with a community that throws out terms like NP-Complete, \Sigma_2, and PSPACE so freely :).

FOCS 2009 results.

The FOCS list is out, (with abstracts). 73 papers accepted. Some papers that popped up on my radar screen (post more in the comments since I'll probably miss many good ones):

• Matt Gibson and Kasturi Varadarajan. Decomposing Coverings and the Planar Sensor Cover Problem.
  
  This paper continues a line of work that I like to think we started in a SODA paper a few years ago. The problem is this: you're given a collection of sensors that monitor a region. But they have limited battery life, and they're also redundant (many different subsets of sensors have the range to cover the region). Can you schedule the sensors to go on and off so that at all times, the entire region is covered, and the region is covered for as long as possible ?
  
  Early work on this problem formulated it in a combinatorial setting, which immediately led to things like log n-approximability lower bounds via set cover variants. Our belief was that the geometry of the regions would make things a bit easier. We made some small progress, getting a sublogarithmic approximation ratio for intervals on the line, and a constant factor for ranges with special structure. Subsequent work made steady improvements, and this work has brought things down to a constant for general classes of regions in the plane
• Saugata Basu and Thierry Zell. Polynomial hierarchy, Betti numbers and a real analogue of Toda's Theorem
  
  Betti number computation has been a hot topic in computational geometry of late, but the idea of using Betti numbers to bound the (algebraic complexity) of basic geometric operations dates back to work by Dobkin and Lipton that relates the complexity of certain computations to the number of connected components of "invariant paths" in a computation. Ben-Or generalized these results to more complicated algebraic computation trees, and noting that "number of connected components" is the zero-th Betti number of the set of computations, asked whether higher-order Betti numbers might be useful for proving lower bounds. A series of results by Bjorner, Lovasz and Yao, Bjorner and Lovasz, and finally Yao showed that indeed the higher-order Betti numbers can be used to lower bound the complexity of algebraic computations.
  
  So Betti numbers are important as a measure of "counting" in algebraic complexity. This paper reinforces this intuition, by relating #P over the reals to the complexity of computing Betti numbers over semi-algebraic sets. Interestingly, this paper mentions the difficult nature of Toda's original proof, and Lance just recently tweeted a new very simple proof of Toda's theorem that he just published in ToC.
  


• David Arthur, Bodo Manthey and Heiko Roeglin. k-Means has Polynomial Smoothed Complexity
  
  Read my post on k-means for more on the significance of such results. This paper finally resolves the smoothed complexity issue, giving a polynomial bound (expected).
  


• Peyman Afshani, Jeremy Barbay and Timothy M. Chan. Instance-Optimal Geometric Algorithms
  
  An interesting result that seems to be able to take away order-dependence from some geometric problems.
  


• T.S. Jayram and David Woodruff. The Data Stream Space Complexity of Cascaded Norms
  
  Cascaded norms (where you compute one aggregate on each of a collection of streams, and compute another aggregate on these aggregates) are tricky for streaming algorithms, and this paper provides some interesting results. Again, I'm waiting for the document to show up, and I'd be interesting in seeing the kinds of techniques they use.
  

Papers I'd like to learn more about:

• Ravindran Kannan. A new probability using typical moments and concentration results
• Hans Bodlaender, Fedor Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh and Dimitrios Thilikos. (Meta) Kernelization
• Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, Alessandro Panconesi and Prabhakar Raghavan. Models for the compressible Web

Comments ?

Clustering: k-means...

(this is part of an occasional series of essays on clustering: for all posts in this topic, click here)

k-means (also known as Lloyd's algorithm) is probably the most well known clustering algorithm, and as such, deserves some discussion of its own. We've already seen that it's part of the "I don't like you" family of clustering formulations. How does the method work ?

We start with a set of points in R^d. The algorithm is really simple: Fix a collection of k centers. Now perform the following alternating optimization till you reach a steady state: (1) assign each point to its nearest center (2) for each group of points assigned to the same center, compute a new center by taking the centroid of the points.

More importantly, what problem does this algorithm solve ? The quick answer is: none ! Yes, that's right: k-means gives no answer with any provable guarantee for a generic set of points for any cost measure. Pretty dismal, isn't it ? And yet, it's a really popular algorithm, a state of affairs that generally drives theoreticians to tears. So what's the deal ? The answer, as always, lies in the details, and is a good story of how theoretical work has managed to make some sense of an algorithm that was notoriously hard to analyze properly.

The underlying problem that k-means attempts to solve is the one I mentioned in the last post: let a cluster cost be the sum of squared distances to the cluster center, and minimize the sum of cluster costs over all k-clusterings. Now here are some of the bad things that we CAN say about k-means:

• It might take exponential time to converge, even in the plane
• It can get stuck in a local minimum that has an arbitrarily bad cost.

Running Time:

Let's first consider the problem of guaranteeing running time. Although k-means can take exponential time to converge, a smoothed complexity result says that w.h.p, a perturbed input will converge in polynomial time (for those not familiar with the concept, the smoothed complexity of a problem is its (expected) running time after the inputs have been perturbed randomly by a small amount). The smoothed complexity results suggest one reason why k-means converges quickly "in practice". The kinds of careful constructions (high dimensional, and low dimensional) needed to force super polynomial convergence times are very artificial.

A crucial initialization:

So what about the quality of the results produced ? One unspecified aspect of the k-means algorithm is how the initial set of k centers is created. Two recent works have indicated that the key to extracting good performance from k-means is by being very careful with this initial choice.The idea is very neat, and really should be getting more play in the experimental community than I think it does.

Recall the Gonzalez algorithm for the k-center problem: pick a point, and then its furthest neighbor, and then the point whose closest neighbor in this set is as far as possible, and so on. Consider the following randomized variant:

Pick the next candidate center with probability proportional to its minimum distance squared from the current set of clusters.

Papers by Arthur and Vassilvitski, and by Ostrovksy, Rabani, Swamy and Schulman both show that this simple seeding strategy allows for provable guarantees on the quality of the solution returned by k-means. The actual results are slightly different, and give two different views of the behaviour of the algorithm:

1. The Ostrovsky et al paper starts with the assumption that the point set is epsilon-separated: the intuition behind this definition is that the cost of a k-clustering is significantly better than the cost of a (k-1)-clustering (controlled by a parameter epsilon). Under these conditions, they show that the initial seeding gives a PTAS for the clustering problem.
   
   I'm eliding a number of details about their algorithm. One interesting feature of their algorithm is what they do after the initial seeding: rather than run Lloyd's iterative step, they fix a radius around each center (different for each center) and compute the centroid of the portion of the set within this ball. They also use a more complicated procedure to convert this into a PTAS, and in my mind that makes their approach a lot less practical.
   


2. The Arthur/Vassilvitski paper starts with the same initialization procedure, but they assume no epsilon-separation result. Their algorithm is simply: run the initialization, and then run regular k-means. The guarantee they get is weaker (a log k approximation ratio), but they also provide empirical results showing the superiority of their approach compared to standard k-means. I think it'd be interesting to compare their approach with the 'ball k-means' approach by Ostrovsky et al to see which work better on benchmark data sets.
   

Another pleasing property of the k-means algorithm is its relationship to mixture modelling and the EM algorithm. I'll have more to say about EM later on, but the gist of the matter is this: The twin steps of finding new centroids and assigning points to nearest neighbours have direct analogs in the world of maximum likelihood concepts and distribution-generated data. There is a general procedure that takes a given exponential family (Gaussian, Poisson and the like), and generates a distance function d such that the density described by the distribution can be expressed as exp(-d(x, mu)), where mu is the mean of the distribution, and x is the point whose probability we're evaluating. ML folks will recognize the Bregman distances here, and the punchline is that for Gaussian distributions, the corresponding distance function is squared Euclidean distance (the exact function used in the k-means evaluation).

What does this all mean ? It means that the k-means process has a semantic meaning in the context of clustering data drawn from a mixture of Gaussians: what's even neater is that a k-means-like algorithm works for data drawn from other distributions, as long as you replace squared Euclidean distance by the appropriate (Bregman) distance function.

Apart from the simplicity of the algorithm, there are some aspects that make it attractive, regardless of lack of guaranteed bounds. From a heuristic-design standpoint, k-means is a particularly atractive example of a technique that's often called alternating optimization.

Notes:

• I was asked if there were standard data sets for benchmarking clustering algorithms. I don't often see papers doing this in a systematic manner, but a good source of data sets for experimentation is the UCI Machine Learning Repository: there aren't too many clustering data sets, but they can be found here (look for clustering under the default task).
  

Next up: hierarchical methods...

SODA 2010 submission server

Remember: abstracts are due today at 5pm ET.

Clustering: The "I don't like you" view

(this is part of an occasional series of essays on clustering: for all posts in this topic, click here)

Any clustering problem starts with a data set. And you can basically tell what algorithm you're going to need by asking, 'what structure do I have on the data ?'. The bare minimum you need is some way of taking two items and returning a number that tells you how similar they are, or more usefully, how far apart they are.

Of course, if I know that A and B are a certain distance apart, and B and C are a certain distance apart, I might like to infer something about the distance between A and C. This is what the triangle inequality gives you, and so the most elementary form of clustering takes items and a metric defined on these items (humans actually DON'T think about distances in this manner, as many psychological studies have shown: more on that later on).

I find it convenient to view clustering algorithms from a pop-psychology self-help perspective, and so I'll deem algorithms that operate with a distance metric the 'I don't like you' methods. The general goal with such methods is to group the items into "clusters" where there isn't too much hatred :).

There are many ways to quantify this "lack of hatred". The one most natural to theoreticians is the 'minimize the worst-case angst' viewpoint: in other words, find k clusters such that over all clusters, the maximum pairwise distance between points in a cluster is minimized. This is the well-known k-center problem.

If you don't like the lack of robustness (one point can mess up the cost), you could instead sum up all the pairwise distances to assign the cost for a cluster. This gives a variant of what's normally considered the k-median problem.

A third way of measuring cluster cost is to sum the squares of distances, rather than the distances themselves. This gives you a cost function that looks a lot like what k-means attempts to solve.

It's often useful to define a representative of a cluster: in the k-center view of the world, the center of a cluster is a point whose maximum distance to all points in the cluster is minimum. Note that by triangle inequality, this is within a factor of two of the k-center cluster cost, so it's often convenient to use this as the definition of the cluster cost (the cluster radius, instead of diameter, if you will). In the sum-of-all-costs view, the center correspondingly can be defined as as the point whose sum of all distances to all other points is minimized. Similarly for the case of sum-of-square-costs.

Remarks on complexity:
There is an elegant 2-approximation for the k-center problem by Gonzalez. The algorithm itself is the essence of simplicity: pick any point in the space, take its furthest neighbor, take the point furthest from these two, and so on. The first k points picked in this manner yield the desired cluster centers, and a simple triangle inequality argument yields the 2-approximation.

The k-median problem is a little harder to solve. The best known bound in a general metric space is a 3+eps approximation, and it's known that you can't get a PTAS. The approximation algorithm itself is not too hard: it's a local search heuristic that gets closer and closer to 3 as you permit larger and larger sets of centers to be swapped out.

Going to Euclidean space, or what's in a name ?
General metrics come either from some kind of similarity function between pairs of elements or from the induced shortest path metric on a graph (there are other metrics one can induce from a graph, and we'll talk about them later). But what if you have more information ? There's a general principle of clustering that's worth enunciating here: more structure on the data can lead you to more targeted algorithms that will probably work better, so resist the urge to be too general.

The most natural space to consider is a Euclidean space, and it is this space that explains the names 'median' and 'mean'. It's well known that on the line, the point minimizing the sum of distances to a set of points (the 1-median) is given by the actual median of the numbers. This explains why the problem of minimizing sum of distances is called the k-median problem. Similarly, the point that minimizes the sum of squared Euclidean distance is the centroid or the 'mean', giving rise to the k-means problem.

There's a long line of results on clustering under various measures in Euclidean space. In brief, for most of the above formulations, you can get a PTAS in Euclidean space, but you end up playing whack-a-mole with the parameters n, d, epsilon, and k (that is to say, something ends up exhibiting exponential dependence, and which parameter it is depends on what you care most about).

The Voronoi trick
But there's a general principle that governs much of the algorithm design for these problems. It's the so-called Voronoi trick, and can be summarized by pointing out that you can always improve the clustering cost by making sure that each point is assigned to its nearest neighbor. Effectively this means that the clusters define a Voronoi partition, with the center as a site, and all points within a Voronoi cell being assigned to the corresponding site. First of all, this means that the number of possible outcomes reduces from k^n (the number of ways of partitioning n things into k groups) to n^{kd} (since the number of Voronoi partitions is much smaller than the number of partitions). Secondly, it suggests a simple heuristic for improvement: Take a given clustering: reassign points so that each point is assigned to its nearest cluster center, and then recompute the center for the cluster associated with all points in the (erstwhile) Voronoi cell. Rinse and repeat....

This heuristic is the basis of the k-means algorithm, and is also the basis for a heuristic for the k-median problem clumsily named the k-medoids algorithm.

Notes:

• all the above algorithms have the parameter k for the number of clusters. It's obvious why: all the above cost measures can be minimized by placing each item in a cluster by itself, but the resulting answer is meaningless, and "no man is an island"
• In a general metric space defined over a finite set of points, the cluster centers will by default by elements of the input. This is often a desirable property, if you want representatives to be from the input. But in a smooth space like a Euclidean space, there's no reason to limit yourselves to data points, and this creates a dichotomy between the so-called discrete and continuous variants of a clustering problem. Often, you can use triangle inequality to argue that the answers don't differ significantly in cost, but it's important to ask yourself which variant you care about. The discrete problem can often be "easier" to solve, because you can enumerate over the choices, but this "easier" can be expensive: for example, minimizing the sum of squares is easy in a (continuous) Euclidean space, but is more expensive in a (discrete) metric space.
  
• For some unknown reason, it's common to describe clustering problems by the algorithm used to "solve" them, which causes no end of confusion. I lost count of the number of times I had to point out that k-means is an algorithm that attempts to optimize a specific cost function. This is more than just pedantry, because unless you realize the difference between a problem and a specific solution, you'll never be able to conceive of an alternate approach, and you'll never even try to abstract out what's special about your problem. To theoreticians, this might be obvious, but it isn't really obvious IRL.

Next up: everything you ever wanted to know about k-means.

p.s this is written in a much more breezy style than I'd use for any formal document, but the organization and thinking reflects how I'd like to structure the material. Comments, as always, are welcome.

"Bloggers", the media and science reporting.

Sometimes I read an article that I just cannot understand. The words make sense, and I can understand the logical flow, but the entire premise just escapes me. Consider the following exhibit: an article in Nature News on the "problem" of blogging from a conference. A snippet from the article (which I recommend reading in its entirety):

By disseminating scientific results far beyond the lecture hall, blogging and social networking blurs the line between journalists and researchers. Scientists in competitive fields may be more reluctant to discuss new findings if they can be posted on the Internet within seconds.

and then later:

MacArthur's comprehensive postings were read by many scientists but they irked journalists attending the meeting. The meeting rules stated that reporters had to seek permission from speakers before publishing material on their work, rules that Cold Spring Harbor instituted in part because some journals, such as Nature, discourage scientists from talking to the press before their work is published. But those rules didn't apply to scientist-bloggers like MacArthur and, after he posted details from a few talks, reporters contacted Stewart for clarification on the policies. The complaint was a wake-up call: "For the first time, I became aware that people were blogging about the data at the meeting," Stewart says.

If I understand this correctly, the premise of the article is that blogging from a conference is bad because it

• "scoops" the poor journalists under embargo ?
  
• disseminates information faster than someone might like ?

to which my only response is "HUH " ? Isn't the whole point of a PUBLIC presentation to disseminate results to - you kn0w- THE PUBLIC ? and how on earth does it matter how fast this happens ? And although I feel for the journalists who agree to weird embargo rules by control-freak journals, why on earth should I, as a researcher who happens to blog from conferences, care about this ?

Sometimes I think the media needs to get over itself....

Clustering: An Occasional Series

Clustering is one of those areas that epitomizes the 'ooze' principle in data mining: it's 3 miles wide and an inch deep. Every year, copious ink get spilt on some clustering method or another, and yet it's not really clear what key ideas are driving the field forward.

I ran a seminar this spring on clustering. I wanted to see if there was a way of organizing material on clustering in a way that was broad without necessarily being exhaustive, but that hit the "eigenvectors" of the field, so to speak. I was surprised that for a topic as important and broad-based as clustering, there was little out there in the way of textbook-level source material to work from. Most texts that I did find were too specialized for my taste, and didn't have the kind of broad perspective of clustering that I felt was critical to really understanding the area.

So I organized my material, and was surprised to find that there actually was a way of collecting the base material on the topic in a way that could be covered in a semester format without leaving crucial pieces out. What I did not try to do:

• Cover the details of the best/greatest/fastest algorithm for each problem. In other words, I made a conscious decision to shy away from theoretical overkill.
• Try to cover all the variants of different clustering methods. I felt that as long as one knew what k-means was, and what spectral clustering was, there was no real need to study papers that tried to put them together in strange ways.

What I did try to do was:

• Where possible, try to evaluate the practical significance of the methods (so a linear time clustering algorithm that actually had a running time doubly exponential in epsilon would not necessarily make the cut, unless it had some other redeeming features)
• Try to view the methods from the perspective of the user: given some data, with some structure, what are your options in terms of clustering algorithms ?

The results of this organization can be found here. I was relatively happy with the outcome, and I think the students were too. In fact, many of the discussions in class were interesting enough that I put them together in a collection of notes.

What I want to do in this occasional series is sketch out the "top-level" view of clustering as I see it, and as inspired by our seminar. My vague idea was that these notes might eventually be converted into some kind of monograph, or at the very least a web document that others might find useful. So I'm going to "test-drive" the ideas here, in the hope that my very well-informed readers will add to the discussion, and improve it (as usually happens).

First up: the basic trinity - k-(center/median/means).

"I, for one, welcome our new TCS overlords"

Via Richard Ladner:

I am pleased to announce the new SIGACT officers for the term beginning July 1, 2009 and ending in three years, June 30, 2012.

SIGACT Chair
Lance Fortnow, Northwestern University

Members-at-large
Cynthia Dwork , Microsoft Research
Anna Lysyanskaya, Brown University
Michael Mitzenmacher, Harvard University
Mike Saks, Rutgers University

Quick hits

• If you limit yourself to actually reading one Terry Tao post each week (I'm told this frequency prevents brain explosion), then read this one.
• Joachim Gudmundsson wants to remind you that jausage is much taster than sausage. Oh yes, and JoCG is open for submissions.
• Get those SODA papers in (but not too many, I have work to do !)
• I kid, I kid....
• I wanted to spend more time talking about Robert Lang's talk on origami. It had deliciously beautiful pictures, and some even more juicy mathematics, and he pitched it at JUST the right level. No slides available, alas.
  
• Lecture notes on streaming from a workshop in Barbados...
• I had to explain to someone that Denmark is not a city in Sweden. And this after watching the Denmark-Sweden world cup qualifying game in a bar with a hundred roaring Danes, and feeling like I had been transported to a Viking battlefield.

And because I can't help myself, "SKÅL"

SoCG 2009: Local search, geometric approximations and PTASs

I planned on this post coming a lot sooner after the last three, but got caught up in my own version of a Danish flu. sigh....

So let's get greedy. In the last post, I talked about new developments in the epsilon-net route to approximating covering/hitting problems. The problem with these approaches though (as Saurabh Ray pointed out) is that they (at best) get you to "some" constant. They don't get you down to a specific constant (unless you can really optimize the net-construction) and they certainly don't give you a PTAS.

So what's a poor approximator to do if their livelihood depends on getting a 1+epsilon-approximation ? Two papers at SoCG 2009 answer this question independently using essentially the same idea, and there's already a third paper that applies this idea as well. You know what they say: "three applications doth a general technique make" (or at least they should say it !), and the technique is so neat that I thought I'd spend some time outlining the basic principle.

But first, a detour. What follows is my own take on the underlying argument, and I'm the only one responsible for all the inaccuracies in interpretation and exposition. Consider the problem of computing a maximum cardinality matching in a bipartite graph. As we all know, this can solved using a max-flow algorithm. A well-known "spin" on this result is the following:

Suppose we construct a max flow F_k using augmenting paths of length at most 2k+1. Then OPT <= (1 + 1/(k+1)) F_k

Or in other words, F_k is a 1 + 1/(k+1) approximation to the true answer. The proof is fairly easy: consider any augmenting path of length at least 2k+3 that could increase the total matching size. Because we've tried all augmenting paths of length 2k+1, it must be that this path alternates between OPT (red) and algorithm (blue) edges, starting and ending in a red edge. In other words, if X is the number of blue edges along this path, then 2X+1= 2k+3, and X = k+1. This means that the number of optimal edges is at most (1 + 1/(k+1)) times the number of algorithm edges. Note that all augmenting paths must be disjoint, so some algebra yields the above result.

Another way of viewing the above fact about alternation is that if we think of the edges as vertices of a bipartite graph, (colored as the edges were), then each red set is adjacent to a reasonable number of blue vertices (in fact if this were not the case, the analysis would break). The edge-disjointness then allows us to scale things up to the entire graph

Notice that the process of generating longer and longer augmenting paths can be viewed as a local search operation. Starting from a given path, we modify it by constructing an alternating path using the current edges.In other words, we're able to make claims about local search yielding optimal solutions because we can control the way OPT interacts with the results of the algorithm, with the interaction parametrized by the "degree of locality".

Now let's return to the papers, keeping this in mind.

Mustafa and Ray apply this idea to get a PTAS for hitting set problems. Specifically, they show that for r-admissible regions in the plane and for halfspaces in R^3, the hitting set problem admits a PTAS that runs in time O(mn^(1/eps^2)) (m: number of regions, n: number of points). A collection of regions in the plane is r-admissible if any pair intersect in at most r points, and the differences are connected (these are often called non-piercing collections for that reason).

Chan and Har-Peled use the idea to get a PTAS for max-independent-set problems for pseudo-disks in the plane (which are 2-admissible). Their running time is similar.

Both papers run the following algorithm, parametrized by a number b. Take any feasible solution, and call it L. Now check all sets that differ from L in at most b places and see if any of them can be used to improve the quality of L by at least one unit. If so, make the swap and repeat. This process will terminate in at most n steps, and at each stage, you need to do a search over at most n^b sets. We'll call such a solution "b-local"

The idea that roughly governs both analyses is this: Consider the solution you're currently at (let's call it red) and the optimal solution (color it blue). Think of building a bipartite graph (this works slightly differently for the different problems) which contains the red and blue objects as vertices, and connects two (differently colored) objects by an edge if there's a range that contains both (for the hitting set problem) or if they intersect (for the MIS) (call this a 'locality property' as Mustafa and Ray do) Then they show some things:

1. This graph is planar
2. It "expands": neighborhoods of blue sets of size at most b are large
   
3. As a consequence of 1,2, the size of the blue set is upper bounded by (1+1/sqrt(b))(size of red set)

See the resemblance to the max flow argument ? (or maybe not ;)). A reasonably quick corollary then shows that by setting b = 1/eps^2, the desired PTAS follows (since by 3), the optimal solution is reasonably close to the current solution. 2) holds by the locality argument, i.e if it weren't true, then there'd be some way to locally improve the red set using a "lookahead" of size at most b. 1) is case-by-case, but works for these problems. The proof of 3) itself requires separator machinery for planar graphs.

An upcoming paper by Gibson, Kanade, Krohn and Varadarajan applies the same idea for the 1.5D terrain guarding problem (one of the few nontrivial art gallery problems that has yielded to approximation attacks). They produce a planar graph that satisfies the locality property, and then apply the rest of the local search machinery as before. What's neat is that the machinery really does apply just as before: "all they have to do" (and I'm not trying to minimizing the effort here, just pointing out the smoothness of the technique) is construct the planar graph.

Some thoughts:

• There's some room for improvement in the running time perhaps, at least down to a linear dependence on 1/epsilon in the exponent. We can't get a poly dependence because of strong-NP-completeness
• I don't think the weighted versions of these problems would fall to the same "trick": indeed the Chan-Har-Peled paper considers a neat LP-based approach for the weighted MIS.
  

There have been numerous PTASs for geometric problems: the Arora/Mitchell TSP approximation is the most famous of course. But this technique is a relatively new kind of generic tool, and has demonstrated immediate applicability for different problems, which makes it noteworthy. Secondly, it's a way of reasoning about the efficacy of local search, which is always neat, since local search algorithms are generally not that complicated.

SoCG 2009: Epsilon-nets and covering/hitting problems.

The 30,000 horsepower engine of approximation algorithms is linear programming. The fact that an LP gives you a bound on the cost of an NP-hard problem has been the major force behind ever more sophisticated methods for proving approximation guarantees.

Ironically enough, given the geometric nature of an LP, this engine has not been particularly useful for geometric approximation problems. The high level reason (somewhat over-simplified) is that it is generally hard to encode specifics about geometry in a linear program. What this means is that (for example) if you want to solve a geometric covering problem and can't encode the geometry in your LP, you're stuck with the log n approximation that combinatorial set cover gives you, inspite of the fact that there are numerous examples of problems where throwing geometry in actually improves the approximation bound considerably.

To put it mildly, this is a pain in the neck. It basically means that you have to design methods that work for a specific problem, and there are only a few general purpose techniques available, many of them outlined in this survey.

But if your problem can be framed as a covering/hitting problem, then there's a general body of work that has provided better and better results, (and for an added bonus, actually has an LP-formulation). The story dates back to a paper on iterative reweighting by Clarkson, and actually goes back even earlier if you jump to the ML literature: Arora, Hazan and Kale have a nice survey on this general approach.

But I digress: the paper by Bronnimann and Goodrich put the technique in the language we're familiar with today: in short,

Given a range space that admits epsilon-nets of size (1/epsilon)f(1/epsilon), you can solve the hitting set problem to an approximation of f(OPT).

In particular, range spaces that admit epsilon-nets of size 1/epsilon admit constant-factor approximations for the hitting set problem. This led to a "formula" for approximating these problems: find an epsilon-net of an appropriate size, and declare victory. There's been much work on constructing epsilon-nets since then, partly motivated by this.

Another angle to this story was put forward by Clarkson and Varadarajan in their 2005 SoCG paper: the brief summary from that paper was:

Given a range space in which you can bound the complexity of the union of a random subcollection of size r by rf(r), you can find an epsilon net of size (1/epsilon)f(1/epsilon).

This approach gave another tool for finding good approximations for covering problems (and in particular gave a nice constant factor approximation for a thorny guarding problem).

At SoCG 2009, Kasturi Varadarajan presented an improved bound along these lines: his main result improves the transfer complexity: modulo some technical details,

Given a range space in which you can bound the complexity of the union of a random subcollection of size r by rf(r), you can find an epsilon net of size (1/epsilon)log f(1/epsilon).

Although this doesn't improve results in the constant factor regime, where f() is a constant, it makes a significant difference when f() is non-constant.

The interesting story here is that Kasturi's result was simultaneous with another paper by Aronov, Ezra, and Sharir that just appeared in STOC 2009. They get the same bound without the technical details that limit his result, however their methods are quite different.

Returning to LPs, what I failed to mention is that the epsilon-net construction technique used by Bronnimann and Goodrich can be seen as a byproduct of an LP-algorithm, as was shown by Even, Rawitz and Shahar, and Philip Long before that (thanks, Sariel)

SoCG 2009: A neat lower bound example

I've had a number of posts queued up to write (for those who ask me "how do you get the time?", the answer is sometimes, "I don't !"). This SoCG was full of really interesting papers, and even collections of papers that together moved our understanding forward in very nontrivial ways. Definitely read David E's post from earlier today.

Gabriel Nivasch has been doing some great work on lower bound constructions. He recently had a paper on analysing upper and lower bounds for Davenport-Schinzel sequences (got a best student paper award at SODA 2009), and the kind of tight bounds he gets are very impressive (upto terms involving powers of alpha(n) in the exponent). Here, he presented joint work with Boris Bukh and Jiri MatousekMicha Sharir on a new lower bound for weak epsilon-nets.

A central construction here, that might be useful for other lower bound constructions is a very fast growing exponential grid. Roughly speaking, if we think of how it would map to a "regular grid", then the point (i1, i2, ....) on the [0..m] grid maps to the point whose jth coordinate is x_j = 2^{i_j * [m^{j-1} + m^{j-2} + ... + 1]d}. So things start getting really jumpy as the coordinates go up. A couple of observations do the heavy lifting for this grid:

• A straight line segment between two points in the stretched grid maps to a collection of d line segments in the "regular" grid: d-1 that goes almost straight up from the first (say lower) point, and another that goes across the final dimension (it's easier to think of this recursively)
• Convex sets in the stretched grid correspond to so-called "stair-convex sets" in the regular grid
• A diagonal in the stretched grid maps to a curve that doesn't touch many points in the regular grid.

Basically, the grid construction allows them to reason about lower bounds by going back to the regular grid. They use these ideas to prove the lower bound for weak epsilon-nets, but also for some incidence problems (using the third property). It seems to me that this construction might prove useful for other lower bounds in the future as well.

Coming up next: max flows, local search and a plethora of PTASs (try saying that fast)...

Probability of a graph being connected...

I ran across the following question in a problem I'm working on, and thought I'd ping the collective wisdom of the blog-reader-o-sphere.

Given an undirected graph G with (possibly different) probabilities on edges, consider the usual random process where we pick each edge independently, but with probability p_e (this is the difference from the standard erdos-renyi model).

What is the probability that the resulting graph is connected ?

This seems possibly to have something to do with the spanning tree polytope, but it seems quite nontrivial. In general, I'm given a subset of vertices S in this graph, and want to ask for the probability that S forms a connected component. Making sure that S is disconnected from the rest of the graph is easy, but then the remainder of the probability comes from the answer to the above question.

I should add that the subset connectivity question is trivial if G is a tree: it's the higher connectivity case that makes things harder.

p.s More SoCG posts should be on their way in the next few days after I return.

SoCG 2009: Day 0

At least in my mind, things have been somewhat overshadowed by the sad news of yesterday, thus preventing me (thankfully) from writing the more frivolous posts that I might have penned.

Today was the 25th anniversary celebration for SoCG (1985-2009), and we had four speakers to do a retrospective on the field.

David Dobkin was first, talking about how some of the first geometric algorithms came to be. He interspersed many fun facts about the early days of SoCG:

• One of the reasons CG is tied to the STOC/FOCS community is because when Michael Shamos first asked him where to publish a geometry paper, STOC was the first conference that came to mind.
• The Preparata-Shamos book only came about because (after Shamos left for law school) Ron Graham brokered a deal for Franco Preparata to write a book based on Shamos' thesis.
• SoCG was almost called the Symposium on Computer Geometry (ugh).

It was interesting to see that even way back then, there was serious intersection between numerical algorithms, the graphics and vision folks, and the nascent geometry area. Some things haven't really changed. It also explains (for me) why there is somewhere deep down a sense that CG doesn't wholly situate within the larger algorithms community, but has a core identity that's slightly different.

One point that David made was very interesting. He talked about how Michael Shamos essentially created a problem book from scratch, listing basic problems in the new area of computational geometry, and methodically solving them one by one. He then asserted that it was the creation of this problem book that played a major role in the unification of the area. I think that makes a lot of sense. It's not so much that a list of problems got created. It's not too hard to do that. What I think was the critical factor was the listing of problems within-reach, that encouraged more people to start thinking about them. Muthu is very good at doing this with any field he jumps into, and I think he's able to jumpstart a lot of research for this exact reason. It's not easy to do: the problems have to be core to the area, but still not that difficult to solve.

Micha Sharir went next with a talk on the evolution of work in arrangements. I've always felt that work on arrangements seems to have reached the point of diminishing returns after some point: that new results were mildly interesting, but didn't necessarily hook into algorithm design in a nontrivial way. I still have somewhat of the same opinion after the talk, but it was good to see the evolution of the problems into higher dimensional surface arrangement questions.

Emo Welzl gave a nice overview of the exciting years between 1987-1992 when randomization began to bloom into a powerful tool for doing geometry. Of course, the very first randomized algorithm was a geometric one (Rabin's closest pair algorithm), but the really powerful methods came into being really with Clarkson's work, and the eps-net work of Haussler and Welzl. It was amusing that almost every single paper mentioned in Emo's talk was written or co-written by Ken: just goes to show his profound influence on the field both for new techniques, as well as new results.
For me, another great influence was Raimund Seidel's amazingly lucid exposition of backwards analysis: there's something to be said for crystal-clear writing and the impact it can have.

The final talk was by Kurt Mehlhorn, on the history that led to the development of LEDA and CGAL. I must confess that I've always felt rather intimidated by CGAL and LEDA: there's something about the phrase "traits class" that strikes fear into my heart. But Kurt's talk was immensely enjoyable: he gave several simple examples of inputs where floating point implementations of geometric algorithms fail spectacularly, and really reinforced the importance of precise implementations, something (if I may add) the rest of the algorithms community often can avoid if they're dealing with graphs or numeric data. I REALLY need to weave CGAL into the next incarnation of my geometry class: must be less lazy, must be less lazy, .....

Notes from the conference: I was fervently hoping that the organizers would lower expectation for next year, but no such luck :(. Impeccable organization, food, and free beer. Sigh......

I'll be tweeting occasionally from the conference. If you're reading this at the conference and want to do the same, please the hashtag #socg so all tweets can be collected in one place.

Rajeev Motwani, R.I.P

Rajeev Motwani passed away unexpectedly yesterday. He will be remembered for many things: his influence on the creation of Google, the foundational randomized algorithms book that he wrote with Prabhakar Raghavan, his role in the PCP theorem, and his extensive presence in the Bay Area investor community. Within the theory community, he will also be remembered by the legion of students he trained, including your humble blogger. Update: Ashish Goel @ Stanford has a page where you can also post comments.

The influence an advisor has on their students can be subtle: as a grad student, I spent much of my time resisting, pushing back, trying to find my own voice. But more and more, as I look back, I see how he influenced my taste in problems and the sensibility I bring to my work.

He had incredible breadth to go along with his depth. I remember scouring his web page in the early years of grad school, and seeing papers in robotics, databases, compilers, parallel systems, as well as in algorithms. Having spent time working in more applied areas, I can appreciate now how difficult it must have been to do that, and have the kinds of impact he had. That kind of incisiveness, that could cut to the heart of a modelling problem, was a hallmark of his more "applied" work.

There's something special that comes with the ability to have a great career and train so many students. There are many famous researchers in the field who do one or the other, and Rajeev had a knack of catalysing the best from his students, and helping them succeed no matter what area they happened to work in. To this day, I'll catch myself thinking, "what did Rajeev do in this situation" when I'm interacting with my own students.

As an advisor, the best way to describe him was 'laid-back'. He wasn't the kind to breathe down your neck, or demand regular updates. But I felt the terror all the same when going into his office to describe what I'd been upto. But he'd sit there with those half-closed eyes staring off into space as I spoke, and then the observations would come, carefully crafted, and enough to make me scurry off and think hard before our next meeting.

As a teacher, he was brilliant. The very first time I took a class with him, I saw this. His style of presentation, how he organized his material, and even his impeccable boardwork: these are all things I teach my students today. His lectures weren't flashy: they were solid, and profound, and in his own mellow way, he was able to convey intuition, rigor and beauty with the kind of clarity one dreams of possessing. To flip the truism about doing and teaching around, he did, and taught even better as a result of it.

I had less contact with him after graduation than I should have had. I was doing the whole 'be your own person, strike out on your own' thing. I'd bump into him occasionally at conferences, but as he got more involved in his investment efforts, he stopped attending conferences regularly (or so it seemed) and even that contact dried up. As someone just said to me in an email today morning, 'Life is fleeting'.

It's a strange feeling, to lose your advisor so suddenly like this, and to hear about it on twitter, of all things. I'm not even sure what I'm feeling, except a sense of numbness, and a feeling that something has shifted, permanently, underneath.

To his wife Asha and his family: my deepest condolences.

New(?) NSF policies

While everyone recovers from what appears to be a gripping STOC, I thought I'd flag two NSF-related items that came my way.

The first, via FSP, is on post-doc mentoring. Now I've always been told that the NSF frowns on inserting post-doc support in proposals, but apparently they don't mind it, and they have a new policy in place for proposals including postdoc support:

Starting this year, NSF proposals that request funding for postdoctoral researchers must include a statement about how the postdoc(s) will be mentored. For a brief time this mentoring statement was supposed to be part of the body of the proposal, but, perhaps in response to complaints, the postdoc mentoring text is now a supplementary document, up to a page in length. As with the required Broader Impacts component of proposals, NSF is serious about the mentoring statement: proposals that request funding for postdocs but that do not contain the mentoring supplement will not even be reviewed.

I'm curious as to what experience people have had with postdoc support in proposals, and whether this is really new, or just a restatement of things that were already tacitly known.

The second item affects us more broadly, and perniciously. A new policy guideline of May vintage appears to suggest (it's somewhat ambiguous) that equipment purchased for grants must be MUCH more closely tied to grant activities than previously expected. Specifically, it essentially rules out the purchase of machines for general PI use (like laptops etc), and raises a number of questions about how to purchase software for old machines, how to upgrade new machines etc. Again, I'm curious to know if people have already run afoul of this new rule, and what the deal is.

more on the zig zag product..

I did an impromptu lunch presentation with my research group on expanders to celebrate the Godel Prize, and in the process dug up some useful reading. There's nothing here that's new to folks familiar with the main results, but if you want a reading list to help with grasping the significance of the results, read on.

• Luca Trevisan's series on expanders and their relation to Cayley graphs (one, two, three, four)
• Terry Tao's summary of expanders inspired by an Avi Wigderson talk.
  
• My note from SODA 2007 on the Alon/Schwartz/Schapira improved analysis of the replacement product.
• Dieter van Melkebeek's course on expanders

There are some aspects of this story that are worth drawing out. First of all, it's actually possible (I think) to get the SL = L result without using the zig zag product directly. In fact, stray comment on a post by Lance suggests as much, and with the new analysis of the replacement product this might be even more likely.

This doesn't mean that the zig-zag product is useless of course. In fact, there's a wonderful 'return to start' story here, which I'll attempt to convey. Essentially, as Luca describes, many early expander constructions proceeded via taking some special non-Abelian group and constructing its Cayley graph, which was then shown to be an expander. The zig-zag product is described "combinatorially" as a construction that takes two graphs and makes a third out of them, and one advantage of this representation is that it gives more explicit expander constructions. But it turned out that at the core of this hides a group operator ! In a certain sense, the zig zag product of the Cayley graph of two groups is the Cayley graph of the semidirect product of the groups ! This is a result of Alon, Lubotsky and Wigderson.

Godel Prize

The ACM site isn't updated yet (here's the press release), but Michael M informs us that Vadhan, Reingold and Wigderson just won the Godel prize, most likely for their paper on the zig-zag graph product, which had a major role in and for Reingold's proof that SL = L. These were inspiration for Dinur's combinatorial PCP theorem.

Congratulations !

Joint distributions aren't that bad

I was reading Noam Nisan's exposition of correlated equilibria. It's interesting to note that finding a correlated equilibrium is easy: you have to solve a linear program in the relevant variables of the underlying distribution. This is in contrast to Nash equilibria.

What struck me is that this is a good example of where a joint distribution isn't that bad. In machine learning especially, trying to "learn" a joint distribution is hard firstly because the number of variables blows up, and because of nasty correlations that one has to account for. In fact, the area of variational methods often uses the trick of replacing a joint distribution by the "closest" product distribution, and optimizing over that instead.

Here though, the "replacing by a product distribution" takes you from a correlated equilibrium problem to a Nash equilibrium problem, and now the individual probabilities actually multiply, yielding a nonlinear problem that's PPAD-Complete.

Physicists understand the web better than us, part 28596

A new physics review site. via the baconmeister:

Physicists are drowning in a flood of research papers in their own fields and coping with an even larger deluge in other areas of physics. The Physical Review journals alone published over 18,000 papers last year. How can an active researcher stay informed about the most important developments in physics?

Physics highlights exceptional papers from the Physical Review journals. To accomplish this, Physics features expert commentaries written by active researchers who are asked to explain the results to physicists in other subfields. These commissioned articles are edited for clarity and readability across fields and are accompanied by explanatory illustrations.

Each week, editors from each of the Physical Review journals choose papers that merit this treatment, aided by referee comments and internal discussion. We select commentary authors from around the world who are known for their expertise and communication skills and we devote much effort to editing these commentaries for broad accessibility.

Physics features three kinds of articles: Viewpoints are essays of approximately 1000–1500 words that focus on a single Physical Review paper or PRL letter and put this work into broader context. Trends are concise review articles (3000–4000 words in length) that survey a particular area and look for interesting developments in that field. Synopses (200 words) are staff-written distillations of interesting and important papers each week. In addition, we intend to publish selected Letters to the Editor to allow readers a chance to comment on the commentaries and summaries.

Physics provides a much-needed guide to the best in physics, and we welcome your comments (physics@aps.org).

What an excellent idea !

Kindle DX

Much well-deserved drooling over the Kindle DX. The killer app is native PDF support: as Michael Trick pointed out, the earlier Kindles didn't do too well with math support (the native Kindle document format is not PDF). I could easily see myself using the DX at conferences, rather than lugging around my laptop, or (worse) printing out copies of papers I wanted.

The Kindle has a nice feature that you can email documents to a specific address and have them synced automatically to the device, but it comes at a price ($0.10/document). If you use a direct transfer over USB though, it's free of course.

What I don't understand is why this has taken so long to happen: it seems to me that the academic market is the killer market for the Kindle: can you imagine transferring ALL your PDF papers to the Kindle for reading ? not to mention books ?

p.s for those of you who will no doubt point out that other readers exist that can read PDF, and are puzzled by all the hype over the Kindle, I leave you to your Archos MP3 players and Opera browsers.

p.p.s I spotted my first Kindle in the wild a month ago at a conference. It was rather cute looking. the DX will be much larger of course.

New open access proceedings archive

Via Luca Aceto, news of a new effort to create an open access electronic proceedings. The idea is that you organize your conference/workshop, and apply for inclusion of your proceedings in the EPTCS: you handle the reviewing, they take the papers and manage the long term archiving (via the arxiv).

I'm imagining this will only be useful for small conferences/workshops, but it's a good way of making sure you don't have a dead-link problem a few years later when the person who hosted the website for the conference leaves their institution and forgets to hand over maintainence to someone else. Also, the arxiv imprimatur will make sure the papers will get more visibility than otherwise.

CG Steering Comittee Elections: Part II

Marc van Kreveld has been taking nominations for the next set of members of the CG steering committee. He now has a list of nominees (people nominated at least twice, and willing to serve). His instructions are these:

To vote, send me an e-mail with at most five names from the list below. Put "Vote SC" (or something similar) in the e-mail subject line, or reply to this message. The possibility to vote ends on May 15. Of course, your votes will be kept confidential.

The list is below: much to my embarrassment, I have been nominated. There are many good folks on this list, and I'm not sure explicit campaigning is in good taste, but I will say that I feel the "divide" between CG and the rest of theory has been made too much of a big deal, and does no one any favors. In whatever ways the steering committee can help to keep us involved and participating in larger theory endeavours, I'd do my best to be involved.

If anyone else on the list below wishes to post anything about their suitability for a spot, I'd be happy to host their posting without comment.

And now, here's the list: you will note that all CG bloggers have been nominated :)

• Dan Halperin
• David Eppstein
• David Mount
• Erik Demaine
• Guenter Rote
• Jack Snoeyink
• Jean-Daniel Boissonnat
• Jeff Erickson
• Joseph Mitchell
• Leo Guibas
• Mark de Berg
• Matthew Katz
• Monique Teillaud
• Otfried Cheong
• Rolf Klein
• Sariel Har-Peled
• Sue Whitesides
• Suresh Venkatasubramanian

WADS paper list

As previously blogged, WADS paper list (sans abstracts ! come on, WADS people, get with the program).
Two interesting observations:

• WADS is no longer a workshop ! It's the Algorithms And Data Structures Symposium (ADSS?). I see that years of complaining that workshops get no respect has had an effect.
  
• There seems to be a preponderance of geometry papers (or should I say, OxDE papers :)). Is WADS (ADSS) becoming a satellite CompGeom conference ? this would not be a bad thing at all, considering that SODA is the only current satellite (I kid, I kid). Or maybe WADS (ADSS) is becoming a satellite of SODA/ESA ? that would be reasonable too.
  

Start your engines for Bethesda: STOC early reg deadline Apr 28

Aravind Srinivasan reminds us that the STOC early registration deadline is Apr 28 (only a week away!), so do go ahead and register.

Aravind also notes:

Especially given the current economic climate, ACM is concerned about
getting enough registrants and booked hotel rooms for STOC.

This is particularly pertinent for me because I've been having similar conversations with ACM about SoCG 2010: they are generally concerned about attendance based on data from conferences being organized right now, and have been tamping down attendance estimates as a result.

Complexity book out !

The Arora-Barak complexity book is out ! Of course they've had the PDF version around for a while, and I've been using it so extensively I almost HAVE to buy the book now.

Many/multi-core research

There's been a great deal of chatter on the blogs about the multicore workshop being organized at UMD. I'll assume that everyone already knows about the workshop, and will jump straight to some thoughts.

First, two points. I'm at a department where there's a LOT of excitement about multicore work from a systems end. For the last two years we've had internal departmental panel discussions on various aspects of multicore research (architecture, compilers, programming languages, verification etc) and I've even chipped in little bits on the potential theoretical ramifications.

Secondly, I spent a good few years working on GPU algorithms ( a kind of precursor to things like the Cell, and multicore in general), both on the practical side of implementing algorithms on a GPU, and on the slightly more theoretical side of trying to abstract out the core metaphors defining "GPU-efficient" algorithms.

To an extent, I know whereof I speak, and I have a kind of guarded curiosity about multicore work. I think it's an excellent time to have this workshop. There's huge interest across the board in CS about multicore: the evangelists believe it's a game changer, and even the skeptics agree that it requires some redesign of our thinking about the entire systems "stack" (chip level, memory level, OS level, programming level, etc).

Why I am guarded though ? It's because the models are changing very rapidly. There's the Cell-style SPU model that looks a lot like a stream processing system. There's the Nvidia CUDA programming model that abstracts a very complicated memory hierarchy over an architecture you don't have direct access to, and there are of course all the actual multicore chips for which the interfaces are evolving. I don't think anyone knows what the right abstractions are for how to think about memory access on multicore system (and from a theory perspective, this is probably the key question), and so there's always the danger of settling on a model that changes before you have time to explore it in depth (this was happening a lot in the early days of GPU work).

But I see no reason why that should stop us from paying close attention and chipping in our contributions. I do think there are abstractions that may not capture all the nitty-gritty of what's happening with multicore systems, but capture some higher-order phenomena that aren't affected too much by the day to day changes. And I think that effective multicore memory modelling could have the same impact as I/O and streaming models of computation did (and these contributions have percolated well beyond the theory community).

The trick here is not to think about multicore in terms of 2/4/8/16 cores, but to imagine a system with millions of cores, small amounts of local memory, and a cost for transferring information. One of the limitations of PRAM in my mind is its ignoring of the real cost of memory access, while focusing on the parallelism: I think a careful modelling of memory transfer is what will make multicore algorithmic research interesting, and in that sense it follows the path from I/O to cache-oblivious models, with streaming thrown in for good measure. Even MapReduce and the MUD models might be useful in this regard.

So do we have a clean model ? No. Should theoreticians stay away ? Well that really depends on your style of operation. Some people like jumping in the mud, and some like to wait till structure emerges. That's really up to the individuals. But if NO ONE jumps in, then we essentially make the statement that theoreticians have no interest in computational models that aren't "sexy". If (as I like to think) algorithms is the true God's language of computation in all its forms, then it's inconsistent to just sit on the sidelines.

I think I just talked myself into attending the workshop.

NSF (and twitter)

Although the NSF has lots of new stimulus money for disbursement, allocation to proposals has been stalled for a while as the agency figures out how much money gets to go where etc. And then a few hours ago came this, on the NSF twitter feed:

Finally, movement! Allocations of the FY09 Funds and ARRA are being finalized, and we expect the apportionment from OMB later this week.

Can I just comment on how cool it is that the NSF has a twitter feed ?

Is HAM SANDWICH PPAD-Complete ?

Reading the algorithmic game theory book, I discover that HAM SANDWICH is in PPAD (not surprising in retrospect when you think of Brouwer's fixed point theorem as the canonical PPAD problem). Is HAM SANDWICH PPAD-Complete ?

Update: I should clarify - this is the problem I'm referring to:

Given n sets of 2n points (each) in n dimensions, is there a single hyperplane that bisects each set (i.e divides it into two sets of size n).

In 2D, the problem is to bisect two sets (the ham and the bread).

P vs NP seminar

I'm thinking of topics to discuss over the summer with students here, and decided on introducing people to complexity theory via the question, "Why haven't we solved the P vs NP problem?". The title is a little tongue-in-cheek: the real idea is to use P vs NP to explore some concepts in complexity theory, for an audience that has no real familiarity with the topic.

Thus far, I'm working off the "diagonalization-oracles-boolean-circuits-razborov-rudich" story line, with an addition at the end for algebraization, and P vs NC. But since this isn't my real area of expertise, I'm throwing out a request for suggestions: what topics am I missing when discussing the various attacks on P vs NP ?

p.s I'm using Scott Aaronson's P vs NP survey as a rough starting guide for references.

Committees and conferences...

FOCS 2009 PC size: 20
SODA 2009 PC size: 27
ICDE 2010 PC size: 230
IJCAI 2009 PC size: 600

SoCG 2008 attendance: ~150
SODA 2008 attendance: ~300

It's an impressive feat when a conference PC is larger than an entire other conference. It also explains why everyone has more PC memberships than I do :)

CG Steering Comittee Elections

Via Marc van Kreveld comes the announcement of CG Steering Committee elections. The way it works is that people send nominations to Marc before Apr 14. He screens them, checks if the nominated individuals are willing to serve, and then starts an election on May 1 for 5 candidates to run the committee for the next three years. Deadline for voting is May 14.

The curent committee is:

• Pankaj Agarwal
• Jeff Erickson
• Marc van Kreveld (secretary)
• Joe Mitchell
• Guenter Rote (chair)

and Marc's email address is marc at cs dot uu dot nl.

More deadlines: ESA 2009

tick tock. ESA 2009 deadline is Apr 12.

MASSIVE !! DATA !! ALGORITHMS !!

Sorry. Just went all Bill G on y'all.

Anyway, this year there's a workshop on massive data algorithmics happening just after SoCG. It's structured like the Fall Workshop (i.e things submitted here can be sent elsewhere - there's no formal proceedings). The Apr 3 deadline is looming, so get those streams, disks, and I/Os ready and send them to Aarhus !

The FOCS submission experiment

Via Muthu, an explanation by Umesh Vazirani of the rationale for the new 'submmary after the deadline' experiment at TOCS. A key paragraph:

To understand the motivation for the abstract and better picture
its contents, think about how often the 20 minute presentation at
STOC/FOCS provides a better insight into the research than the
paper. While preparing the talk, the authors can step back and
try to explain something interesting about their work - either the
core of their proof, or a special case of their theorem, or the
new conceptual framework that they introduce. The one week
period after the mad rush to the STOC/FOCS deadline would
provide a chance to reflect, and additionally there would be an
incentive for the authors (just as in the conference presentations),
to simplify.

I think it's a great idea to try things like this. I hope it will work though. One of the reasons that papers often get written badly for STOC/FOCS is because there's an incentive to obfuscate and make things look rather technical. Whether the post-deadline calm will allow people to see beyond the chest-thumping will decide whether the 2-pages are useful.

SIGACT article by Viola

There's an excellent article by Emmanuel Viola in the latest SIGACT News ($$) on the problem of finding functions that have low correlation with low-degree polynomials over GF(2).

p.s this is the kind of thing that one would merely twitter, but then I'd want it to somehow feed into my blog automatically.

Adjacency matrix of a tree..

Is there a purely algebraic characterization of the adjacency matrix of a tree ? In other words, given an n X n boolean matrix, can I determine whether it's the adjacency matrix of a tree with purely algebraic conditions (rather than writing down the induced graph and checking).

The reason I'd like this is because I want to talk about the space of such matrices, and I'd like to speak algebraically, rather than indirectly via a conversion to a graph. This seems like something that should be fairly well known: I've found some descriptions that involve all determinants of minors, and was hoping there was something more "compact".

(ab)use of wikipedia ?

From IHE:

Recently, a small journal entitled RNA Biology announced that it will now require all authors to also create Wikipedia pages about their discoveries.

Specifically, the journal says:

At least one stub article (essentially an extended abstract) for the paper should be added to either an author's userspace at Wikipedia (preferred route) or added directly to the main Wikipedia space (be sure to add literature references to avoid speedy deletion). This article will be reviewed alongside the manuscript and may require revision before acceptance. Upon acceptance the former articles can easily be exported to the main Wikipedia space. See below for guidelines on how to do this. Existing articles can be updated in accordance with the latest published results.

I'm not a Wikipedia expert (hello 0xDE), but isn't this a violation of the Wikipedia policies on copyrighted material and (non)-publishing of original research ?

Update: As 0xDE points out, Wikipedia is already on top of this.

Trolled from the arXiv... volume estimation...

Just posted on math.PR, math.MG:

A Polynomial Number of Random Points does not Determine the Volume of a Convex Body
Ronen Eldan

We show that there is no algorithm which, provided a polynomial number of random points uniformly distributed over a convex body in R^n, can approximate the volume of the body up to a constant factor with high probability.

Specifically, you can't estimate the volume of a convex body merely by sampling. You need to generate new points that are "near" the old ones, and use a membership oracle as well.

Neat...

Blogroll alert, and some musings on community.

Noam Nisan has a new blog on algorithmic game theory. This is great stuff. I must add that I'm finding Dick Lipton's blog fascinating reading, not only for the heavy research content, but the great historical perspective he brings to a number of well known problems.

p.s (snark alert) It does seem unfortunate that computational geometry blogs (and data structures) don't appear to be recognized as part of the theoretical computer science blogosphere, but in a world where SODA is viewed as a conference not worth attending, I guess this is small potatoes. (end snark alert)

p.p.s From an organizational perspective, it doesn't matter terribly whether geometry papers get published exclusively in SoCG/SODA, appear in STOC/FOCS, etc. Similarly, although Luca is concerned about crypto forking off from STOC/FOCS, I don't think there's a real problem with people naturally aggregating around a common topic area in their own conference. I'm also not too caught up with "name wars" despite my snark above.

The problem is really along other dimensions: the tenure process (what is your field and who evaluates you/writes letters), and even more crucially, the funding process. For many years, geometry was funded from a separate sub program of CCF than the rest of theoryCS (at least theoryA). This was a good thing (more money) and a bad thing (CG was clubbed in with solid modelling, graphics, and symbolic methods).

Now of course geometry has been folded back into the larger Algorithmic Foundations umbrella, and here's where perceptions start to matter. If AF gets defined (de facto) as STOC/FOCS stuff, geometry proposals are going to get short shrift (also because they tend to have more application-oriented material as well). This would be true for any other area that has forked off into its own community.

I didn't submit to the theory program last December, and I don't know how panel deliberations are going, but I'm curious as to whether there's been any noticeable change ?

Class Projects

For some reason, class projects are all the rage in graduate classes here at the U. These are typically used in lieu of a final, and generally involve (for most classes) some kind of software artifact. Students seem to prefer projects to exams in fact.

When I started designing my graduate classes, I had mixed feelings about class projects, but allowed students (especially in my comp. geometry class) to propose various ideas. Two years in, I still have mixed feelings about class projects.

• It seems to me that for theory classes, a "pure theory" class project is difficult to execute. Most students here don't have a 'general theory' background, and so it would be well-nigh impossible for them to execute a class project of the form 'here's an open problem: go attack it'.
  
• A cop-out option is a survey paper on an area. Now in principle survey papers can be an excellent way of distilling the knowledge in an area, organizing it, and then presenting it. But in practice, a survey ends up looking like a sequence of paper summaries, with little to no higher-level organizing
• For some classes (geometry, specifically) a software artifact can make sense. In that regard, having CGAL around is handy because a lot of low-level grunt coding gets taken care of. But invariably the software artifact degenerates into a horse-race for a bunch of techniques, or "let me implement my research project that I'm working on somewhere else, and slap some O() notation on it to make it look like a CG project".
  

The problem a class project (ideally) is trying to solve is providing an avenue to synthesize and apply the concepts being learned in class in some kind of holistic way. But I'm unconvinced that the class projects people are actually doing are effective in that regard. Incidentally, since some of my complaining has to do with topic choice, I should add that I've often given out topics for people to look at: no one likes my topics though :).

I teach the grad intro algorithms class in the fall, and am tempted to do a class project where I require students to do some actual algorithmic modelling drawn from their home area (most students taking this class are not algorithms folk): which is to say, take a "real problem", and analyze it as an algorithms person would if given the problem by an applied researcher - formalize, prove hardness, come up with algorithms, repeat, ....

If it weren't such a pain to design finals that aren't solvable via Google, I'd probably never use projects at all.

Memory exercises and streaming.

The latest guest column on Olivia Judson's "Wild Side" blog at the NYT is on increasing intelligence: Can we do exercises to increase it ? In the article, they describe a test that when performed repeatedly leads to measurable improvement in IQ:

A common way to measure working memory is called the “n-back” task. Presented with a sequential series of items, the person taking the test has to report when the current item is identical to the item that was presented a certain number (n) of items ago in the series. For example, the test taker might see a sequence of letters like

L K L R K H H N T T N X

presented one at a time. If the test is an easy 1-back task, she should press a button when she sees the second H and the second T. For a 3-back task, the right answers are K and N, since they are identical to items three places before them in the list. Most people find the 3-back condition to be challenging.

Of course, to folks who do streaming, this is easily recognized as a simple subcase of detecting a duplicate item in a stream (that problem allows n to vary over the entire stream), which in turn is a special case of the most frequent element estimation problem.

These are hard problems for sublinear space stream algorithms. It's interesting that they're taxing for human working memory as well.

Some SoCG 2010 news

IPCO (Integer Programming and Combinatorial Optimization) is held in the summer, and can occasionally overlap with SoCG. I've been in touch with Friedrich Eisenbrand (organizer of IPCO 2010 in Lausanne) and it looks like the two conferences will be back-to-back and disjoint in case there are people who wish to attend both. Thanks to Friedrich for moving IPCO to earlier in June (9-11) to make this happen.

In even more important news, the Zion Curtain is soon to come down in Utah. All this means for visitors is that you won't have to pretend to become a member of a 'private club' to drink at a bar in Utah any more.

Barbara Liskov wins the Turing Award

Via MM comes this news:

ACM, the Association for Computing Machinery, has named Barbara Liskov of the Massachusetts Institute of Technology (MIT) the winner of the 2008 ACM A.M. Turing Award. The award cites Liskov for her foundational innovations to designing and building the pervasive computer system designs that power daily life. Her achievements in programming language design have made software more reliable and easier to maintain. They are now the basis of every important programming language since 1975, including Ada, C++, Java, and C#. The Turing Award, widely considered the "Nobel Prize in Computing," is named for the British mathematician Alan M. Turing. The award carries a $250,000 prize, with financial support provided by Intel Corporation and Google Inc.

The first U.S. woman to be awarded a Ph.D. from a computer science department (in 1968 from Stanford University), Liskov revolutionized the programming field with groundbreaking research that underpins virtually every modern computer application for both consumers and businesses. Her contributions have led to fundamental changes in building the computer software programs that form the infrastructure of our information-based society. Her legacy has made software systems more accessible, reliable, and secure 24/7.

DBR: moving forward

I have no doubt that people are sick of this subject now, so I'll try not to rehash or re-argue points that many have brought up. It seems to me (as a supporter of DBR) that the objections to DBR can be categorized as

• self-aware: "we are not biased. period. everything is good".
• conservative: "DBR could cause other problems: why replace one flawed system with another"
• logistic: "authors could slyly reveal info, how do we handle self-citations etc"
• irritated: "why are you people rabble rousing: leave us alone"

In this regard, I think people should really try to read Kathryn McKinley's essay on this topic (and the related links). There's much there for all: for us utopian DBR devotees, she points out that the most effective kind is a appears to be a staged unblinding approach, rather than a straight DB approach. For those who think that we can check our own biases, she provides references and evidence for why this goes against what we know about human psychology. For people concerned about logistical issues, she discusses many of the common problems (and also references other disciplines that have made their own attempts to solve this).

A comment I read somewhere (union of Sorelle, Lance, Michael and myself) made what I thought was an excellent point: if people are really committed to trying out DBR, it might be good to experiment in a conference outside the big ones, so we can acquire some level of familiarity with the system (or realize that it's totally useless). As I had mentioned to Sorelle, this ultimately boils down to having a PC chair who wants to experiment in this way: Michael tried doing serious CoI at the STOC PC meeting and received no small amount of flak for doing so, but at least he tried, and it convinced him that it should happen even more.

More on the dynamics of peer review (this at the level of funding panels) comes from a new book reviewed in IHE. The review reveals some of the key findings: nothing entirely surprising, but a clear indication that many "non-technical" factors go into a proposal getting funded (even things like who has a plane to catch and when).
It's reading things like this that makes me impatient with people who claim that bias doesn't exist.

NSF vs NIH stimulus disbursement

From the Chronicle ($$):

In the absence of definitive guidance from either the U.S. Congress or the White House, the nation's two leading providers of federal science money to universities are apparently taking different approaches to what it means to help the U.S. economy.

The National Institutes of Health, which is getting $10.4-billion from the $787-billion economic-stimulus measure signed last week by President Obama, announced it will tweak its science-based distribution guidelines to ensure the largess some measure of geographic parity.

The National Science Foundation, which is getting $3-billion in stimulus money, has concluded that it will not.

"We are sticking to NSF's mission," Arden L. Bement Jr., director of the National Science Foundation, told the agency's board on Tuesday.

I don't have an opinion one way or another on this: just interesting to see the difference. As the article points out later,

The NIH and the NSF are getting the two largest chunks of $21.5-billion in new federal money for research and development contained in the stimulus measure. But while the NSF is an independent federal agency, the NIH is part of the federal Department of Health and Human Services, which makes it more tightly bound to direction by Congress.

On Clustering and Density Estimation

A brief respite from SBR/DBR/DOOR review policies....

I'm running a clustering seminar, and although I thought at first that putting some order on the space of clustering methods was too daunting a task, I'm actually quite happy with the way the course organization has worked out. Obviously I can't cover everything, but what I've done is focus less on the slew of algorithms for a particular clustering formulation, and spend more time on the formulations themselves, comparing and contrasting to get a better sense of "which clustering technique should I be using", rather than "what's the best algorithm for k-median".

Various interesting observations have emerged along the way, some of which I might write about as time goes on. Right now, I want to point you to a post by my colleague Hal Daumé. We were talking about EM and its dual role as density estimation and clustering algorithm, and he has a very interesting observation about the the dangers of conflating the density estimation problem and the cluster-finding problem.

Graph Theory of monopoly

On TechCrunch, Eric Clemons, a professor at Wharton, does an analysis of whether Google could soon face antitrust charges. What's interesting is his analysis of when monopoly power may be viewed to have kicked in for electronic markets, which are apparently harder to analyse than "regular" markets.

His analysis boils down to a separator construction: analyzing two cases of market power that look similar but actually are different, he argues that the key difference is that in one case (airline reservations) the key monopoly-controlling entity separated the customers from the suppliers in a graph sense: all paths from customers to airlines went through the reservation systems. In a different example (bank ATMs), he showed that this was not the case, and in fact no actual monopoly developed, even though the entity had 100% market control.

He uses this to conclude that there is a potential (lots of caveats) antitrust case against Google, based partly on the fact that Google separates customers from companies wishing to ply their services, and controls the advertising mechanisms by which corporations talk to customers. I imagine that claiming that we ONLY search online is a stretch, and also it would be hard to argue that we are forced to use Google for this purpose - he addresses these points as well.

Overall an interesting argument: I was of course most interested in the graph-theoretic reasoning.

Blogroll update alert

My student John Moeller has started a new blog 'On Topology':

My interest in topology comes from two directions: first, it was the reason that I got started in math (and subsequently the topic that broke me), and second, I found out over the last year that topology plays a prominent role in several research areas of computer science. These applications to CS are what really got me interested in the topic again. Algebraic (or combinatorial) topology is useful in studying the structure of data like meshes and graphs. Differential geometry is applicable when your data lives in another space, or on something called a manifold, and you want to do the same kinds of things that you’re used to doing in regular, old-fashioned space. Ultimately, both have to do with geometry, albeit in a very general way. That’s why these topics interest me; I want to know how to better get at the essence of data, and much of the time you can do that geometrically.

He actually enjoys thinking about Cartan-Hadamard manifolds and representation theory, but I don't hold it against him :).

Double Blind Review, again...

Sorelle's excellent post and discussions got me thinking more about DBR, and then I read Michael's post, which captured an important part of what I wanted to distill out. So first, a summary of the summary, and then other important points.

There are a few serious reasons brought up against DBR. I should say up front that I don't view reasons of the form "We are unbiased/Theory papers can be reviewed with subjectivity/We are better than other fields" as serious, because there's ample empirical evidence for the existence of unconscious systematic biases in many fields (no, not in theory specifically, but we're are still human). And as Michael points out, there's sufficient evidence of actual bias (even if it's not considered malevolent)

The serious reasons against DBR are essentially three:

• DBR places an unacceptable restriction on the author's ability to disseminate the work
• There is no way a paper can get a fair review without the reviewers being able to google around to get a sense of the work being produced. Since such a process could easily reveal the names of the authors, this defeats the purpose of DBR, giving an illusion of fairness where none really exists
• You can't do subrefereeing if you don't know who the authors are.

Michael addressed the first in his post, and the second points more to weakness in the review system than DBR itself. There are mechanisms for dealing with the third in conferences with DBR.

But most importantly, I think the objections are missing the point. If the claim was, "SBR is unfair, and here's a perfect system to replace it", then these objections would be reasonable counters to that claim. But in all that I've read, the reason for DBR is:

To replace the systematic biases associated with SBR by a 'equal playing field of problems' when it comes to paper review.

In other words, the point is not to be perfect, but to be imperfect in a fair way, that doesn't unfairly work against group identity that has nothing to do with the quality of the research.

I really think that perspective is important to keep in mind when discussing this. I have yet to hear any argument for significant harm to authors in going from SBR to DBR. Inconvenience yes, but direct harm, no. And any harm is spread "across the board": I am as likely to suffer in this system as a new grad student or a famous researcher. But the benefits are disproportionate, and correct for structural biases, and that's the point.