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.

Fighting over shiny toys

A recent article in the Guardian extols the wonder of The Algorithm:

And since computers are increasingly dominant in our lives, algorithms are increasingly important - and nowhere is this more apparent than on the internet. In the online world, mathematical analysis isn't just important: the algorithm is king. Everywhere you turn online, companies are using algorithms in their quest for success. From Google's search results and Apple's music recommendations to Amazon telling you that "customers who bought this item also bought ... " algorithms are at work.

The article itself is pretty tame, a kind of knurd version of Bernard's article. What's funny is that the last line in the article, 'Mathematicians rule' got some people into a tizzy.

Two letters appeared in the Guardian following this article:

Bobbie Johnson (Go figure ..., 23 February) highlights the ever-increasing role the mathematics of algorithms plays in our daily lives, including Google's page ranking. "Mathematicians rule!" concludes Johnson. So a reader inspired by your article may seek to contact an expert in algorithms in the mathematics department of their local university. In this, the article will have misled them, as expertise in this area is to be found predominantly in departments of computer science and informatics.

and

Bobbie Johnson describes algorithms as "jealously guarded mathematical recipes that increasingly dictate how we lead our lives". What he's actually describing is operational research - the discipline of applying appropriate, often advanced, analytical methods to help make better decisions. Executives in every kind of organisation - from two-person start-ups to FTSE 100 leaders - are using OR to structure their problems, unlock the value of their data, model complex problems and make better decisions with less risk and better outcomes.

Of course, the first letter comes from the faculty of the CS department at Edinburgh, and the second from a member of the Operations Research Society. I wait for all the data mining and machine learning enthusiasts to start complaining next.

Wordles for STOC/FOCS/SODA/SoCG

A wordle is a visualization of the words in a text, organized to give more frequent words higher priority. It's a cute way of illustrating the repeated concepts in a text.

My student Parasaran Raman made wordles for the paper titles for FOCS 2008 and STOC/SODA/SoCG 2009. You can click on each image to get a larger view. Draw your own conclusions :)

FOCS 2008:


STOC 2009:


SODA 2009:


SoCG 2009:

On the best use of stimulus research dollars

John Langford has a post up advocating that research dollars ought to go to industrial research labs. My first temptation was to write a counter-post advocating that research dollars ought to go to university researchers in less-than-well-known mountainous locations, especially pre-tenure refugees from industrial research labs hungry for the money and willing to do lots of work.

But more seriously, I think there's plenty wrong with John's argument. He argues that the Bell Labs model of the 1900s and earlier has the main components of a successful research agenda: access to cutting edge problems, free time for researchers, and concentration, and infers from this that the best use of government funding is to fund basic research at companies that have such labs (MS, ATT, Lucent, IBM, Yahoo, Google are cited).

Along the way, he throws out various statements that I have problems with:

Some research universities manage to achieve at least access and concentration to some extent, but hidden difficulties exist. For example, professors often don't work with other professors, because they are both too busy with students and they must make a case for tenure based on work which is unambiguously their own.

This is partly true: there's less collaboration in universities than in labs, but much of the collaboration in research labs is also by necessity: to get some things done takes a number of people, and you don't really have access to a ready supply of slaves students. Collaborative research is not by definition better.

at least research at national labs have had relatively little impact on newer fields such as computer science.

National labs play an important role on lots of large-scale visualization work (I know this because I'm at one of tthe best viz places in the country, and they have extensive collaborations with national labs). National labs compete like universities for research money, and often have the inside track on funding from places like the DoE. Their sweet spot is the kind of large-scale infrastructure work that's hard to do at universities or at industrial labs.

Some people might think that basic research done at a university is inherently more desirable than the same in industry. I don't see any reason for this. For example, it seems that patentable research is about as likely to be patented at a university as elsewhere, and hence equally restricted for public use over the duration of a patent. Other people might think that basic research only really happens at universities or national labs, but that simply doesn't agree with history.

This is a strawman: I don't know who 'some people' is, but I think any reasonable position would argue that the kind of research is different: someone once told me that the ideal industrial project involves 3-5 people: any larger or smaller is best done at a university. Whether the research is basic or not depends on the work: I don't know of many industrial labs that support research in complexity theory (except MSR) which is arguably basic research, but there's very fundamental research done at many labs in areas like auctions, ad modelling, large-scale computing, and so on.

But quibbling over statements aside, I think that the best use for stimulus money is neither universities (though I'm very grateful for the $3B) or industrial labs. I think the best use is in places where its already going: the so-called "shovel-ready" projects in green tech/renewable energy. The kind of funding that leads to direct economic impact is not going to come out of either universities (which naturally take a longer time line) or industrial research labs (that have lots of sloth and bureaucracy). It's going to come from VC-type funding for energetic startups that actually make things happen. Yes, there'll be research, but presumably the projects being funded will be well beyond the research stage and ready to make things happen now, or in the next few years. That is after all the point of the stimulus.

The budget will be coming out soon, and I hope that attention is paid to a longer-term reversal of the depredations in science funding in the US. But the stimulus package is about the present and the short term.

Other notes:
* In the comments, Hal argues that education is an important mandate of the NSF, and that's why resources get channelled to universities. I'd also add that I don't see why taxpayers should fund a corporation's bottom-line: money for Yahoo helps Yahoo, whereas money to fund students helps generates more expertise.

John says: "In economic terms, these companies have for reasons of their own decided to provide a public good. As long as we are interested, as a nation, or as a civilization, in subsidizing this public good, it is desirable to do this as efficiently as possible.". Permit me to snigger. Bell Labs had a monopoly on the telephone network for eons, and having a research arm was good PR for them. Once the monopoly collapsed, so did the dedication to provide a public good. Having worked at AT&T these many years, I am deeply grateful for the opportunities I had there, but there was a clear focus on research that helps the company bottom line. Even the much vaunted Google Research makes no secret of its focus on company-specific projects (the 20% rule implies an 80%!) (disclaimer: I occasionally consult for Google).

Post your comments here, or over at the original thread.

Theory "vs" Practice

Today's Wild Side science column from the NYT (guest blogged by Stephen Quake) is an interesting Roscharch test for which side you fall on in the 'theory-practice' divide. The article in fact argues a very valid point: that great research is often done by moving smoothly between theoretical study and practical applications, rather than privileging one over the other. Along the way, he cites Gauss, Kelvin, Archimedes and others as examples of people doing solid theoretical work inspired by, and inspiring, more practical considerations.

I mention the Roscharch test because (like with political commentary) one often tends to read bias or skew into neutral statements. For example, practitioners will find much to be happy about in this opening:

The snobbish idea that pure science is in some way superior to applied science dates to antiquity

and theoreticians will be consoled by:

The stereotyped view is that the applied scientists control the lion’s share of funding, while the basic scientists control the most prestigious journals and prizes.

but if you can get beyond your reflexes, it's a fair article about the need to think broadly about the "impact" of your work both theoretically and practically, and how this can lead to solid research on both counts.

Postdoc opportunity

Kirk Pruhs writes in with another postdoc position. There's no immediate deadline for applications, but the subject of the postdoc relates to the previously mentioned NSF workshop on power management, now (re)rescheduled for Apr 9-10:

I want to investigate algorithmic issues for optimization problems related to power management. [..]

But I am looking to broaden the range of power management problems that I work on. If you are at all interested, I encourage you to attend the NSF Workshop on the Science of Power Management that I am organizing in DC on April 9-10. The workshop participants will consist of leaders in the practice and science of power management, and the purpose of the workshop is to provoke discussion among experts, identify key research directions, and report key findings to NSF. I have funds to support travel to the workshop. [..]

The research will involve searching for algorithmically interesting problems in this area, and solving these problems. It is certainly not necessary for you have any research experience related to power management. What is necessary is that you [are] the type of person that likes to expand their interests into new, exciting, areas of research.

Ketan Mulmuley at the Center for Intractability

The Center for Intractability recently hosted Ketan Mumuley for a 3-part talk series on his attack on P vs NP via geometric complexity theory. The videos are now online here.

And let me just add here that I think it's fantastic that the center posts video for all the talks. It takes some work to get videos produced for web delivery, and it's so much nicer than reading a paper (or 10).

Maybe I need to reconsider this open access biz

I was lukewarm to Joachim's proposal for an open access journal, but I'm changing my mind, after seeing the latest shenanigans being perpetrated by the scientific publishers in collusion with Congress. There's a new bill making its way through the house that would overturn the NIH open access policy (all papers should be placed on a public site within 12 months of publication), as well prohibit the government from obtaining a license to post such works on the internet.

Time to call your congressman, or use the (in)famous Obama outreach program.

A new open access CG journal

The last few years has seen many attempts by researchers to break free from the shackles of (commercial) journal publishers. There's the whole-sale exodus that produced the ACM Transactions on Algorithms, as well as other journals, and technology aided creation of open-access free journals like the Theory of Computing. There's also a movement to create an open access computational linguistics journal, spearheaded by my colleague Hal Daume here at the U. of Utah.

Joachim Gudmundsson and Pat Morin have been investigating the feasibility of making such a journal for Comp. Geom, motivated by costs, and copyright issues with current journals. Here are posts one, two and three on the topic.

They've worked out most of the logistical issues involved in creating such a journal, and are now trying to reach out to the community to see what kind of interest there is. After all, the main currency of a journal is its reputation, and that comes from community participation (and then perception). So if you have any opinion on the matter, hop over to Dense Outliers, take the poll and post a comment (don't post comments here).

My personal view: I think open access is a great idea in principle, but I'm not seeing a pressing need within CG itself for such a journal at this point in time. (Disclaimer: I'm involved with the International Journal for Comp. Geom and Applications).

Making sausage

No, not that kind.

By now, many of you have probably heard of the massively collaborative math experiment being conducted by Timothy Gowers on his blog (with offshoots on Terry Tao's blog). The idea is to mount a serious attack on a conjecture in combinatorics called the density Hales-Jewett conjecture (go to Gowers' site for more details).

Michael Nielsen points out something that I had been thinking about while perusing the initial thread: this is an EXCELLENT way to show students how research gets done. I remember a while back that Sean Carroll from Cosmic Variance had done a post explaining how one of his papers got written, but the post-facto description lacked the immediacy and the messiness of a usual research process, and probably (just even through faulty memories) even missed out on some the paths not taken in the course of the research.

Seeing research done "live" as it were, by professional high-caliber mathematicians, is as exciting as watching live professional sports, and is even better in the sense that you see the the false starts, the high level strategizing and plans of attack, the multitude of possible ideas that get formed, and even the growth of more stable, promising lines of attack on related problems.

One of the things I'm pondering right now is the best way to show students how research is done, and this is a great example to illustrate the messy, convoluted, and yet highly sophisticated ways in which experts ply their trade.

O'Rourke's Art Gallery book

Joe O'Rourke mentions that his classic on art gallery problems is now available for free online. Download it now ! And while you're at it, buy his book on folding (with Erik Demaine). I just bought the folding book (and have already assigned one class project from it).

Levels of hell (heaven?) when writing practically motivated theoretical papers

I was going to post this as a comment on Michael's post, but it started getting longer and longer.

The main question being discussed there is: how do you balance the theory and practical sides of your work effectively from a point of view of getting and keeping faculty jobs ? it's good to remember that not every problem is amenable to a joyous merge of theory and practice: There are levels of hell (heaven?) involved here, that go something like:

* prove fundamental new result, and this leads to breakthrough implementation for a problem people couldn't solve (this happens usually in an area relatively untouched by theory thus far, and can really make you famous) (I'd imagine RSA/Diffie-Helman fall in this category)
* Brand new result: leads to improvements in efficiency AND accuracy of known methods by orders of magnitude
* Brand new result: improves on efficiency OR accuracy of known methods, by orders of magnitude.

Below this line, you're unlikely to get a theory publication out of the contribution:

* Observation that known approaches (or derivations thereof) lead to improvements in efficiency AND/or accuracy by orders of magnitude
* New theory result, some improvements in efficiency AND accuracy

And here's where it gets positively hellish:
* mildly new theory result, reasonable improvement in efficiency and accuracy, but not orders of magnitude, and you go up against an entrenched, highly optimized heuristic (k-means, anyone ?)

At this point you really have to choose which you care about, the problem or the theory, and then branch out accordingly. Papers in this last realm are really difficult to publish anywhere, even when they nontrivially improve the state of the art.

ACM Fellows, 2008 edition

ACM has announced its Fellows for 2008. Familar names on the list include:

• Sanjeev Arora
• Ken Clarkson.
• Steve Cook
• Michel Goemans
• Ian Munro
• Madhu Sudan

In the related area of game theory, Xiaotie Deng and Tuomas Sandholm were honored as well. Congratulations to all the winners !

(HT: Michael Trick)

A "Green" conference...

(Update 2/17/09: Workshop dates changed to Apr 9-10)

Kirk Pruhs asks me to mention what I'll call the first "green" workshop of 2009:

Workshop on the Science of Power Management (Mar 26-27)

The rapidly increasing power consumption associated with information technology (IT) results in a myriad of adverse impacts including high utility costs, unsustainable thermal densities, poor space usage, and a substantial carbon footprint. In view of this, reducing IT power consumption has become a pressing priority at all levels of computer technology from semiconductor materials and processes all the way up to the design of entire data centers.

Although there is already significant research and development activity around power management in academia and industry, power remains a very difficult subject to deal with in a scientific and formal way. A grand challenge for the scientific community is to understand the trade-offs between power consumption and computability at a much more fundamental level. Ideally one would like to determine the limits of computability under power/thermal constraints, design systems that approach these limits and quantify corresponding performance tradeoffs.

This is a "NSF CFP generating workshop": the idea is for the workshop to generate material for a funding call. For more info, do contact Kirk, or Sandy Irani.

SODA news: American Association of Chiropractors in a deep funk...

As promised, there was no hard copy proceedings at the conference this year, causing spinal columns everywhere to heave a huge sigh of relief. What's even more amazing is that ALL the papers from the conference are online: I downloaded them all last night ! Bill Gasarch has this, and more on why he enjoyed SODA, which apparently disturbed Lance so much he had to snark in the post immediately after :)

p.s the comment linked above points out that Las Vegas was the "first choice" for SODA in 2010, even though Austin was the "realistic second" that ultimately won.

SODA location news

No Salt Lake City, alas: however,

SODA 2010 in Austin, Texas, and SODA 2011 in Paris, France (of course unless SIAM and SODA steering committee will change the outcome of the majority vote, what is most likely to happen, in which case it should be San Francisco)

Somehow, I can't see David Johnson the SODA steering committee agreeing on Paris.

Update: More on the vote: it was Paris (60), the Virgin Islands (!) (50), San Francisco (46) and SLC (44). Clearly, I should have attended SODA and brought a student with me :)

On a related note: Virgin Islands ? What, have we given up on Puerto Rico as the token 'ain't gonna happen in a million years' location ?

Update: see the comment by Luc Devroye for some pushback to my claim that VI is an unreasonable location.

SODA Days 0/1...

• Michael Lugo confirms that Analytic Combinatorics IS out !
• David E reports on two interesting theory-experimental papers from ALENEX
• David E mentions in passing a new result by Gabriel Nivasch on DS sequences, giving very tight upper and lower bounds for order 3 and higher.
  

That's it for now: come on, CS bloggers !

no SODA blogging :(

I'm not at SODA/ALENEX this year, so no blogging :(. If anyone is blogging/tweeting/facebooking from the conference, let me know and I'll post a link here. Michael Lugo from God Plays Dice will be at ANALCO, and will hopefully have more on the 'Impatiemment Attendu' :)

Flying While Brown, in 2009...

No beards, no scarfs, and DEFINITELY no discussion of safe places to sit:

Mr. Irfan turned to his wife, Sobia Ijaz, as they boarded AirTran Flight 175 at Reagan National Airport near Washington Thursday afternoon, and wondered aloud where the safest place to sit on the airplane would be — the front? The rear? Over the wing? 

But passengers sitting behind them evidently overheard the remark, saw Mr. Irfan’s beard and his wife’s head scarf, and grew concerned. Mr. Irfan and his wife, along with six members of their extended family, are Muslims, and were on their way to a religious conference in Orlando when they boarded the flight.

The worried passengers contacted flight attendants, who contacted Transportation Security Administration officials, and soon, Mr. Irfan and his wife were off the plane and being questioned in the jetway. The six remaining family members in the traveling party were taken off the plane as well, along with a family friend who happened to be on the same flight and who happens to be a lawyer for the Library of Congress. 

Next, the nine Muslim passengers — all but one are United States-born American citizens — were taken to a quarantine area in the passenger lounge where they were questioned by F.B.I. agents. Mr. Irfan’s three small nephews were denied access to food in the family’s carry-on luggage. 

Before long, Mr. Irfan told The Lede in an interview Friday morning, the F.B.I. concluded that the incident was obviously just a misunderstanding, and told AirTran officials that the family was cleared to travel. But he said AirTran still refused to rebook them, offering only to refund their tickets. The F.B.I. agents helped the family get on a later USAirways flight to Orlando, but those seats cost them twice as much.

Happy new year, same as the old year.

More experiments in algo-teaching

(ed. note: think of this as a 'theory'-chaser to take the bad taste of cricket-blogging out of your mouth)

Another experiment that I continued this time was a set of lectures on "fun topics". The idea is to convey some ideas about a fun topic in theoryCS without too much jargon, but with enough meat to indicate that there's something deeper going on beneath the fun stuff.

I run these lectures at the end of the semester (when everyone's worn out already :)), and throw them open to the general public: both times I did this, I got substantial attendance from people not in my class, and at least in one case, someone who attended the lecture last year actually decided to take my class this year.

Not all topics are amenable to such a treatment, but my hope is to build up a suite of such lectures: the nice thing is that they can then be reused for other venues: for example, I've given variants of these talks to freshmen and high school students, and will do an undergraduate colloquium in the math department next semester.

For all of these lectures, I've pilfered shamelessly from the original works, as well as great websites developed by the authors. This post can be viewed as a shout-out and a thank you.

1. Pancake flipping:
Brian Hayes wrote a great article on pancake flipping for the American Scientist. In it, he links it to the problem of genomic rearrangement, and in doing so, ends up with a beautiful tale of the interaction between theoretical problems and practical constraints, all told in context of a topic that everyone can relate to.

I made two-color pancakes in different sizes, and distributed them to the students at the start of class: I briefly described the problem, and let them go at it. It was quite entertaining, and put the more formal discussion later on in context.

2. Zero knowledge proofs
ZK proofs are great for this kind of setting: they are completely counter-intuitive, (and so have the 'bizarre' factor), and are easily explained using popular metaphors. I used Moni Naor's Sudoku demo page, as well as the version of the proof that involves slicing and dicing the puzzle. This was done with class participation (I was the prover, and there were multiple verifiers).

The second demo I ran was the Yao protocol for the Millionaire's problem (how do two millionaires determine which is richer, without either knowing the worth of the other). Again, I did this interactively with class volunteers and an RSA applet to speed things along. More details here.

3. Quantum Computing
No demos for this one, but I gave a crude high level view of what quantum computing is about (about one-step up from the "do everything in parallel" explanation). The main goal here was to convey the basic ideas of what a qubit is, what a quantum circuit looks like, and how the Bell inequalities show that quantum computing is much more bizarre than classical randomness. Here, Dave Bacon/Umesh Vazirani lecture notes proved indispensable, coupled with the Nielsen-Chuang book, and a recent blog post by Michael Nielsen.

4. Computational Origami
I haven't quite worked the kinks out of this one, but the basic idea is to demonstrate the principles behind computational origami (and where the 'computation' comes in) by looking at the question: What shapes can you make by folding, followed by a single cut.

There's a cool backstory to this: essentially the first example of such an algorithm was how Betsy Ross designed the 5 point star for the American Flag, and it lends itself to a nice demo in class.

Secondly, it's a classic example of resource-bounded computation: limiting yourself to one cut. Thus, it makes for a good illustration of how computation appears in all kinds of problems.

Thirdly, computational origami actually shows up in many real-world problems, most notable one involving folding mirrors for a telescope to be launched into space. If we're trying to convey a sense of computational thinking, this is a great example.

The actual problem itself was solved in this paper by Demaine, Demaine and Lubiw. Unfortunately, I have yet to find a way of explaining it that will make sense to non-expert geometers, and that's one weakness with this particular story: Erik's page has some nice examples to demo, but it's hard to convey the deeper algorithmics behind the problem.

Lessons learned:

• As always, know your audience. What works for a graduate class doesn't work for sophomores, and certainly doesn't work for eigth-graders :)
• Interactivity is key: if you allow people to participate, they're more involved, and will probably take away something positive
• Keep it light: resist the urge to get too mathematical. There are many beautiful topics in theoryCS that can be explained without jargon, and many others for which with some effort, jargon can be removed.
  
• A 'bizarro' factor helps: In general lectures that I've given, I find that presenting something completely counter to people's expectations catches their attention immediately, and leaves a lasting impression. ZK proofs have that property. Bell's inequality sort of does, but the impact would be more immediate if I could actually run a quantum experiment to demonstrate violation of Bell's inequality ;)
• Relate it to the real world: again, it's not enough to cite applications: one should try to show them as far as possible. In this regard, the Betsy Ross story is great, because it relates to something everyone (in this country) knows.
  

My goal is to add one or two such lectures to my arsenal each time I teach the class. For next time, I'm seriously considering running a live auction of some kind to demonstrate some concept in algorithmic game theory (suggestions on how best to do this are always welcome). Are there other such topics that might lend themselves to an entertaining, edifiying and educational experience ?

On run-chases

(ed. note: this is about cricket, not algorithms, or geometry, or computer science. you have been warned)

South Africa, the Netherlands of cricket, finally won a big game, beating Australia in Perth after a historic run-chase of 414. This of course follows India's famous run-chase, beating England in Chennai by chasing down 387. As Cricinfo points out, 9 of the top 25 run chases have come in the last 8 years (in a tally that dates back to 1902).

There's a detailed statistical analysis of these chases, but no speculation as to why they're becoming more frequent. The answer seems obvious to me though: the increasing scores in one-day cricket. A quick search of Statsguru indicates that of the 258 overall scores above 300 (first or second team) one 1-day games, 179 of these happened after 2000. Even to a casual observer, it's clear that the scores in 1-day games have gone up (and don't get me started on Powerplays).

Frankly, when all this fuss was being made about India's run chase, I couldn't quite understand why, because if you think of this as a one-day game, it's not too hard (and in fact India's coaches thought the same way!).

All in all, two exciting Test matches (and how often have we been able to say that)

Videotaping talks

Videolectures.net is a company that has taken on the job of videotaping and packaging conference talks. They're based out of Slovenia, and offer a good service: they take your talk and your slides, and sync up the talk video and slides so someone watching later on can follow along.

For examples, you can see my talk at ETVC, and here are the other talks. I first heard about this company when I was googling a paper and discovered that the ICML talk was online.

I originally thought that they only handle events in Europe, but they appear to have covered this year's KDD as well (although the coverage appears strangely limited).

Practical applications of 1-medians

From Optimal Home Location:

Have you been looking across many different neighborhoods for a place to buy or rent? Have you been contemplating whether to buy closer to your job, your spouse's job or your kids' school? Do not worry - this is not a simple geometric triangulation but a centuries old mathematical problem. Optimal Home Location tool is synthesizing math algorithms and Google Maps together in order to pinpoint optimal home location for any commute scenario. It is easy to use and fun to play with. All you need to do it [sic] enter all the addresses your family routinely visits throughout the day and then click on the map icons to define commute route for each member of your family. The tool automatically computes optimal home location that will minimize total combined commute for all members of your family

NSF bleg

This appears in the supplemental documents section of the upcoming CISE call:

In the Supplementary Documents Section, include a list of all PIs, Co-PIs, Senior Personnel, paid Consultants, Collaborators and Postdocs to be involved in the project. This list should be numbered and include (in this order) Full name, Organization(s), and Role in the project, with each item separated by a semi-colon. Each person listed should start a new numbered line.

Does anyone know what a "Collaborator" is ? is it merely your other-institution co-PI on a collaborative proposal ?

I had a number of responses to people from my programming project post: I thought I'd post the responses here, rather than in comment fields.

* On rolling your own: I'm intrigued by the many suggestions to use Sphere Online. I've heard of topcoder and Project Euler before, and decided not to use topcoder for ease of pedagogy (I wanted problems where the key algorithmic idea was "preidentified", so I could give a DP problem in the homework on dynamic programming). I was also not convinced that topcoder focused on the algorithmic aspects of the problem as opposed to raw speed: the fact that it was set up as a time limited competition by default was also a pain in the neck.

* On copying: this is an unsolvable problem IMO. Since I was choosing problems from the pre-canned list at the ACM server, I was at the mercy of the online solution providers. Judging by the results, my students are either very honest, or don't know how to find these sites :). I've spied on the related forums, and they tend to be somewhat militaristic about not letting people post code directly, although hints are always supplied. As an aside, for theory problems this is a royal pain: I've had to mask things in various ways to prevent a google search, and I have my own way of creating problems that I'm happy to reveal to someone who asks me directly :).

* on what to do for geometry: the problem is not the lack of a good code base. In fact it's the reverse problem. CGAL for example has many quality solutions already pre-coded, so I can't even ask students to use CGAL as a base framework. Given the limited time I have before semester starts, its debatable how much coding and test generation I can do on my own, so stay tuned...

I am less than smart :)

I posted my note on programming assignments, and then wondered why there were no comments. It turns out that I forgot to monitor my moderation list, and when I checked, there were tons of comments ! apologies to all the commenters: your comments are available now, and I'll start replying shortly.

programming assignments

Inspired in part by Michael Mitzenmacher's exhortation:

Here's my claim: theory does untold damage to itself every year by not having programming assignments in the introductory classes on algorithms and data structures.

I tried an experiment in my algorithms class this year. Using the ACM programming competition online judge as an evaluation tool, I assigned one programming assignment in each of the first three assignments in my class (later assignments went into approximations and randomization, which the site didn't really cater to). Coupled with this, I used the ACM Programming challenges book by Skiena and Revilla to guide my choice (they break the problems down nicely by dominant technique).

The way the system works is this: you're given a problem definition and an input/output specification. You write your code in one of three languages, using a specific compiler flag sequence, and then upload your code. The system runs your code through a battery of tests, and then reports whether you had

• compile-time errors
• failure to terminate in the prespecified time limit
• incorrect answers
• run-time errors
• all correct answers
  

What worked:

• Students actually liked the idea of programming assignments: I received numerous variations of the comment, "I didn't understand the algorithm, but once I coded it...". They were less enthused by the server, but more on that later.
• People started getting quite competitive: the site maintains stats on the best implementation thus far, and even after students satisfied the requirements of the assignment, by matching the desired time limit, they tried to optimize their code further.
• The questions are well-designed, and usually need algorithmic tricks rather than hacks. For example, one question is to compute the closest pair, and any optimized brute force algorithm will fail, but the standard deterministic divide and conquer will work fine.
  

What didn't:

• The server would occasionally flake, especially a few hours before assignment deadline time :)
• I/O specifications were often tricky: the problem specifications would leave out details about what one could assume about the input, so simple things like "don't assume that when a range [x,y] is given in the input, that x <=y" needed to be discovered.
• The error messages are cryptic to a fault. Compile time errors are linked to the point in the code where this happens, but for any other kind of error, you are merely told that an error occurred. This caused major frustration.
• With Java especially, getting a correct implementation within the time bound seemed harder than with C/C++. Since Java is often the first language students learn, this is annoying, especially since the whole point of such exercises is to abstract away as far as possible the particular idiosyncracies of a language.
• From a grading point of view, it's very painful to evaluate each person's submission. There's no easy way except to do it manually.
  

Overall, my experience was mixed-to-slightly-positive: I'll probably do this again, but I might also include examples where I design the test inputs and do local evaluation. For some problems (like with randomization) I might have to design the problem from scratch.

Now what I'd like is something similar for my computational geometry class :)

While in Paris...

My latest reason for being off the air has to do with the amazingly bad internet capabilities of Paris hotels. Yes, I'm in Paris, city of lovers, but certainly not of lovers of wifi. There are at least 30 networks visibile wherever you go, but they're all secure, so no mooching. The hotel-provided wifi is actually a generic service that costs 22 E/day for connectivity, with all kinds of bandwidth caps and a very slow connection. If I were to splurge for the "business" level, I get the luxury of paying 27 E/day, with unclear benefits (presumably I can now download my bootleg bittorrents (just kidding)).

Other things I've noticed since I last came to Paris: (which is not to say that they are new, just that I just noticed them):

• Every second store on the podunk street my hotel is on is a fancy clothing store. Clearly the world-wide economic collapse has not hit.
• Speaking of world-wide economic collapses, it really hurts to have a weak dollar. $7 espressos, sigh...
• ....but it's always a pleasure to walk into a cafe and order a 'cafe' and just know that something good will appear. This is in contrast to the unbounded depth circuit needed to specify a proper cup of coffee at Starbucks.
• Speaking of Starbucks, how on earth can they even survive in Paris ? I mean, you go to a Starbucks here, and you get the same experience as in the US, ending with a paper cup of coffee of questionable quality that you drink perched on a high bar stool. On the other hand, you go to a cafe, and they serve you with nice cups, and a little cookie, and let you sit there for hours nursing your coffee, and will even give you the WEP key for their secured WiFi. It's no contest !
• You can change the world while nursing your coffee. I was staying in the 14th Arrondissement (the Montparnasse area) and had to have a coffee at the Dome cafe, a place apparently frequented by Lenin and Trotsky before the Revolution. I have to say that at the time I went, the clientele looked like they were plotting a revolution... in 1907.... I'd link to a verification of this, but I can't make any sense out of the search results on google.fr
• Speaking of which, how does one tell google NOT to return results in french ? every time I edit the URL to go to google.com, it sends me back to google.fr. Suivant !!!

And why am I blogging from Paris, you might ask ? Well here's why. I'm an invited speaker, no less. Conference blogging was limited because there was no wifi at the conference site either. It's a long story involving military schools (and maybe even NASA). Details will appear shortly.

Coffee..

On the evolution of coffee drinking, by Malcolm Gladwell (he of The Tipping Point and Blink). I particularly like this line about Trotsky:

Give a man enough coffee and he's capable of anything.

Items...

I've noticed an inverse correlation between blogging frequency and "actual work", so boy must I have been working hard !!

Two items of note, as my blog and I pass in the night:

• Michael Nielsen links to a great way of advertising a speaker: use Wordle on their work (delicious feeds/research papers)
  
• ICML 2009 is going to a reviewing model where you can specify which area chairs you want your papers directed to (area chairs and interest areas will be listed). John Langford, one of the area chairs, goes further with what is essentially a personalized reviewer manifesto. An excellent idea ! He lays out his principles, and authors are fore-warned.
  

STOC abstracts due today !

According to Michael M, there are 150 and counting already. Papers are due next week. And here's where you do it !

SODA 2009 South Pacific Event

A note from Howard Karloff (please email him for more information):

To SODA '09 attendees:

I have reserved, for SODA attendees and their friends/spouses/significant others, 50 tickets in the loge section at Lincoln Center for the 7:00 PM, Tuesday, Jan. 6 show of "South Pacific," so popular a show that already both Saturday Jan. 3 performances are sold out. If you want to buy one or two tickets, send mail to howard@research.att.com with "South Pacific" as the subject field, specifying the number of tickets you want in the body of the e-mail. Tickets will go to the first SODA attendees who pay by credit card via PayPal. I'll send instructions by e-mail. The tickets are $120 each--the face value is $115, and the extra $5 is to cover the PayPal fee--and are NONREFUNDABLE: once you pay, there will be no refunds. However, I imagine someone at SODA, some random theatregoer, or an ebay user would be thrilled to take tickets to such a popular show off your hands.

So, please, start those e-mails coming. Should the demand far exceed 50 tickets, I may arrange a second outing, to a different play, either Saturday or Tuesday. A few reminders:

"South Pacific" starts at 7PM, not the typical 8PM start
time, on the last day of SODA.

The venue is Lincoln Center, not in the heart of Broadway.

Once you pay, there's no backing out.

See you in New York in a couple months!

Howard Karloff

Announcements

• Sanjeev Khanna reminds us that FOCS early registration deadline is Oct 3, 2008. Get your cheesesteak on !
• CFP for the 2009 sausage convention (with beer!!): Deadline is Nov 24 (abstracts), Dec 1 (papers)

About that whole political outreach business

that I was talking about in this post, here's what I find in my RSS reader today:

The names of seven distinguished scientists nominated by the President to serve on the National Science Board (NSB) were sent to the Senate for confirmation on September 16, 2008. Drawn from industry and universities, and representing a variety of science and engineering disciplines and geographic areas, these four new and three incumbent NSB members were selected for their preeminence in research, education or public service. When confirmed by the Senate, they will serve six-year terms to expire in May of 2014.
...

Diane L. Souvaine, of Massachusetts

Diane Souvaine is a computational geometer, who is professor and department chair of computer science at Tufts University, and holds a secondary appointment in the department of mathematics. Her current research focuses on the design and complexity analysis of geometry algorithms to solve problems from a variety of venues, ranging from computational statistics to geometric modeling to self-assembly of nano-structures. She also directs summer week-long institutes involving computational thinking for middle school mathematics teachers, funded by the Massachusetts Board of Higher Education. From 1992 to mid-1994, she served first as acting associate director and then as acting director of the NSF's Science and Technology Center on Discrete Mathematics and Theoretical Computer Science (DIMACS), while she was associate professor of computer science at Rutgers University. She has been a Fellow at the Radcliffe Institute for Advanced Study, and a member of the School of Mathematics at the Institute for Advanced Study in Princeton, NJ

Very cool indeed...

Loading Image

Click anywhere to cancel

Image is Unavailable

CS advocacy in the political realm

Two articles caught my eye recently:

• A posting on the CCC blog about why computer scientists should publish in magazines like Science, Nature and PNAS
• A Wired Science blog entry about Barack Obama's science advisors (John McCain has not revealed his list of science advisors)

In the first article, Peter Lee makes the argument (with an assist from Peter Harsha) that there are good political reasons for CS folks to publish in Science, Nature and the like (even if many of us snigger at the kinds of CS research that ends up there: I know I have horror stories about articles that are accepted over the objections of the specialist CS reviewers). One argument is that of influence: whether we like it or not, CACM is not the preferred reading material for Congressional aides and staffers that have the ears of elected representatives, but Science/Nature are on the radar. Moreover, these publications have well-honed PR engines to get articles out to reporters: often embarassingly overhyped, but hey, you know what they say about publicity :).

Which brings me to the second article on Barack Obama's science advisors. What's interesting is that 4 of 5 of them are from the life sciences. This is not to demean the importance of life sciences in the current policy environment (GMO crops, stem cells and biofuels are all on the political radar), but there are a good number of technical hot-button issues as well (voting machines, copyright issues, electronic eavesdropping, privacy), and it definitely wouldn't hurt to have a CS-oriented person near the "ear of the man", so to speak, to articulate a view of the importance of these issues and how the research community is dealing with them.

I'm a lowly untenured professor, who used to be a lowly lab researcher, so I have no good ideas on getting personally involved in such matters. But I can see (partially thanks to CCC and the SIGACT Theory group) how advocacy can, over time, lead to fundamental changes in the landscape of support for our efforts, so at the very least, I can consider the idea of disseminating my work (when appropriate) beyond our "incremental" conferences and exhort others to do the same.

SODA list is out

Some happy, some not so happy :)

Kudos to Claire Mathieu and the PC for not only including the list of papers, but also the list of abstracts !! Finally !!

As a public service, here's a TeX-formatted PDF of the list of abstracts, for those who find serif font easier to read than a stream of text on a web page. Warning, it's 44 pages long, and will have formatting errors. I wrote a perl script for the overall parsing and did lots of local fixing by hand for math-mode stuff, but it's not perfect.

Fonts !

John Holbo at CT does a not-review of books on fonts (or faces ? I'm confused now). In any case, this is clearly a book I need to get.

The tensor product trick

Blogging has been slow this summer as I (surprise surprise) was actually working. Today the semester starts, so I expect to be blogging more as I attempt to clear my head from the detritus of semester minutiae.

Terry Tao has a new post up in the "tricks wiki" started by Timothy Gowers. The "trick" can be summarized concisely as: if you want to prove an inequality of the form X < Y, but can only prove X < CY, then take "tensor powers" of the objects X and Y and prove the weaker inequality, and then take a "root".

What's interesting to me is that this is none other than a generalization of the "standard" amplification trick that is most commonly used in hardness results. The easiest application is the proof that CLIQUE admits no absolute approximation: if it did, take graph powers, find the additive-error number, and take square roots, and you have an exact solution (since the value must be integral). Generalizations exist: you can use the same argument to show that CLIQUE admits no constant factor approximation, and even more intricately (invoking the PCP theorem) that independent set has no polynomial-factor approximation.

It makes me wonder what other "standard" analysis tricks draw their lineage from generalizations in the world of "real math". For example, tricks involving building exponentially growing covers tend to show up frequently in topology and analysis.

$10 million for complexity theory...

Via His Quantum Holiness, news comes of the NSF Expeditions awards: each award is $10 million, and four were given out. One of them was for complexity theory, and the team is a star-studded list of complexity and algorithms folks, led by Sanjeev Arora. Here's the blurb:

In their Expedition to Understand, Cope with, and Benefit From Intractability, Sanjeev Arora and his collaborators at Princeton University, Rutgers University, New York University and the Institute for Advanced Study will attack some of the deepest and hardest problems in computer science, striving to bridge fundamental gaps in our understanding about the power and limits of efficient algorithms. Computational intractability, a concept that permeates science, mathematics and engineering, limits our ability to understand nature or to design systems. The PIs hope to better understand the boundary between the tractable and the intractable. This has the potential to revolutionize our understanding of algorithmic processes in a host of disciplines and to cast new light on fields such as quantum computing, secure cryptography and pseudorandomness. The research team plans to draw on ideas from diverse fields including algorithms, complexity, cryptography, analysis, geometry, combinatorics and quantum mechanics

Congratulations ! For getting the award, and demonstrating that hard-core complexity theory CAN get funded...

Update: Sanjeev Arora comments...

Math != calculation, part 537...

From the NYT, on scoring the i-can't-believe-it's-not-a-sport sport of gymnastics:

The new system is heavy on math and employs two sets of judges, an A panel and a B panel, to do the computations. Two A-panel judges determine the difficulty and technical content of each routine. Six B-panel judges score routines for execution, artistry, composition and technique.

The A-panel judges’ scorecards start at zero, and points are added to give credit for requirements, individual skills and skills performed in succession.

The A panel counts only the gymnast’s 10 most difficult skills, which are ranked from easiest to most difficult (from A to G for women and from A to F for men). An A-level skill, like a back handspring in the floor exercise, is worth one-tenth of a point. The value increases by one-tenth of a point for each subsequent level, meaning a B-level skill is worth two-tenths and an F-level is worth six-tenths.

Required elements add a maximum of 2.5 points to the score. Extra points, either one-tenth or two-tenths, are given for stringing skills together.

Each judge adds the marks, then the two reach a consensus. Elite gymnasts usually have a difficulty score in the 6’s; the toughest routines generally have difficulty scores in the high 6’s or 7’s.

[...]
The system rewards difficulty. But the mistakes are also more costly.

Which is where the judges on the B panel come in. They rate the execution, artistry and technique of a routine, starting at a score of 10.0 and deducting for errors.

This score, called an execution score, is where the perfect 10.0 still exists. But reaching it is unlikely.

A slightly bent knee can be a deduction of one-tenth of a point. A more drastically bent knee can cost three-tenths. In this system, the deductions jump from one-tenth to three-tenths to five-tenths. A fall costs a gymnast eight-tenths. In the old system, a fall was a five-tenths deduction.

The highest and the lowest of the judges’ scores are thrown out. The remaining four scores are averaged to obtain the final B-panel score.

On the scoreboard, the final score appears in big numbers, just above the gymnast’s marks for difficulty and execution.

Apart from my grumble about the level of 'math', it's an interesting way of doing the scoring.

I wonder if this could work for conferences: replace 'degree of difficulty' by 'hardness of problem, general hotness of the area, etc', and then you could deduct points for things like

• More than two digits after the decimal point in the approximation ratio
• exponent of running time requires the \frac environment
• More than two parameters in the running time
• Gratuitous use of O() notation to hide dependencies you don't like (yes I'm talking to you, high dimensional clustering folk)
• Requiring your winged pigs to be large in dimension, have extra glitter on the wing tips, and carry golden harps in order to make the horses take off (Hi there, complexity denizens)