Computational thinking in other disciplines.

While we wait for the (literal) flames to die down at the STOC business meeting (who'd have thought a two-tier PC would be so controversial), a thought on "computational thinking". 

I've been on PhD committees for students in other departments far removed from computer science. I'm there partly as an external person, and partly as someone who "understands computation" and can guide the student in a project that involves some nontrivial algorithmic thinking.

It's very striking to see how these students approach the notion of computing. They have strong engineering/math backgrounds, but they tend to view computational problems as black boxes for which the first idea that comes to mind is the correct answer. This is pernicious enough that when I try to nudge them to define the problem more generally, they have no idea what to do.

This is a common theme in disciplines that make use of computation. Everyone has their favorite biology story along these lines, but this article in Science magazine is a good example of the problem of scientists using code. In brief, they tend to use code as a blackbox without really understanding what the code does or why, or how to validate the results.

In my algorithms class, I emphasize the important of naming problems. Especially when one is trying to model a fuzzy real-world problem, it's very important to recognize named problems that might be hidden inside. But this very fundamental idea - that the problem comes first, and that by naming it we can recognize and understand this - is foreign to people not trained to think computationally. Rather, they think in terms of solutions, which is dangerous until they really know what they want to solve.

We talk a lot about computational thinking and the intellectual content of computer science. For anyone without CS training who wishes to make use of computational tools, this is one of the most important lessons to learn: how to name a problem.

NSF Workshop: 8F (Algorithms in the field)

I'm off to DIMACS for the NSF workshop 8F ("Algorithms in the field", AITF, get it?):

Computer Science (CS) is rapidly evolving. We need to understand the evolving CS systems and their algorithmic foundations. This needs close collaboration between the researchers in algorithmic foundations and expert researchers in various areas. The premise is that researchers from different communities should work jointly “in the field”, constantly informing each other, inventing in their respective areas, and forging systems that are simultaneously validated by both algorithmic and systems communities (and without needing to make independent research threads meet ex post).

The purpose of this workshop is to provide a working vision for examples of Algorithms in the Field, near term goals and directions for research in the future. The outcome of this workshop will be a report contributed by the participants that will inform the academic community and future funding programs. Scientifically, we hope bringing people with widely varied research interest together with algorithms researchers will lead to happy collisions, and unexpected directions of research.

There's a great mix of researchers from within theory and from more applied areas, and of course the topic is near and dear. Along with a long list of talks, the idea is to have a number of breakout sessions on different topics in this area. One that I'm involved with is 'Core Algorithms', whose mandate (roughly speaking) is to figure out how basic algorithms research might evolve over the next many years, in relation to events in the larger arena of computing research and technology.

Of course it's a mug's game to make predictions about the future of technology, or worse still, about the future of research. Unlike many other subfields of CS, theoryCS doesn't really lend itself to long-term prognostications or discussions of the 'this is what we should work on' variety.

But from a funding perspective, if we can identify interesting directions to explore even if we look completely stupid in retrospect, this could be a fun exercise. One framing device that we might try to use is:

View core algorithmic developments in two directions. In one direction, there are many concepts from the world of theoryCS that slowly make their way into the more applied realms. In this context, one might ask about which paradigms are either ripe for "tech tranfer", are likely to do so within a few years, or need more 'baking' before they're ready, but have potential.

    The reverse direction is the idea that core algorithmic questions and models are motivated by applications, whether they be models of computation like external memory/streaming/multicore/mapreduce, or conceptual developments like smoothed analysis, complexity classes for iterative algorithms, numerical algorithms and precise computations, and so on.

    In this context, interesting points for discussion would be: what kinds of paradigms do we see approaching from "applied land" and how might they influence the kinds of core algorithmic questions we ponder.

 If you're at the workshop, you can make your opinions known. But even if you're not, you can voice them right here ! I'll incorporate comments posted here into the discussions (and sign your name if you'd like credit). 

Practical Applications of Approximation Algorithms

(Guest Post by David Johnson)
In my Knuth Prize Lecture on approximation algorithms at the last STOC conference, I celebrated the many great theoretical advances we have seen in the area of approximation algorithms over the last four decades, but lamented the apparent paucity of practical applications of this work. We motivate our work in this area as a way of coping with NP-hardness, but how many people who actually have to do such coping in practice are
using our ideas?

In my talk I could only come up with a few examples, these from our work at AT&T Labs - Research, where we have adapted the Goeman-Williamson primal-dual approximation algorithm for the Prize Collecting Steiner Tree problem for use in tools that help design access networks, and where exponential potential function methods for approximating multicommodity flows are being exploited in a proposed content-distribution scheme. I also noted that of the 14 Kanellakis "Theory and Practice Awards" given out so far, of which some 6 or 7 have been for algorithms, only one, that to Freund and Schapire for their statistical "boosting" technique, could be viewed as related to approximation algorithms, and the boosting research is typically classified instead as Learning Theory.

So, I think many viewed my talk as a rather negative exercise. Certainly, practical impact is only one dimension along which to evaluate a field, and, if we relied only on practical motivations, we would not have developed the deep and informative theory we now have. However, practicality IS an important dimension, and I hope that my inability to identify many examples of practical impact was more a fault of my own ignorance, than one of the field. Giving a talk about this to a primarily theoretical audience did not develop many new leads, so I'm hoping that a blog posting will be more successful.

In particular, I would like to collect

(A) Stories about algorithms or algorithmic approaches developed by approximation algorithm theorists that were implemented and applied, either directly or in modified form, by people to solve real-world problems.

(B) Stories about the analysis of algorithms developed by others (for example, the greedy algorithm for SET COVER) that influenced the use of these algorithms in practice, or at least helped explain their performance and hence was cited in "Applications" papers.

The algorithms need not be restricted to NP-hard problems -- I am also interested in approximation algorithms for problems with polynomial-time optimization algorithms that can be too slow for some practical applications.

For both types of stories, I'd like as much detail as possible - who did the work, where, etc., and citations if known. You can post your nominations/comments on this blog, or send them directly to me (dsj@research.att.com). If you post as a comment, please do not do so anonymously, as I may want to contact you for more information.

Assuming I get a good response, I plan to prepare a survey paper (or at least another blog posting) summarizing what I learn.

Thanks! David Johnson (dsj@research.att.com)

"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....

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.

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.

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.

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

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.

The concept of an approximation

We're always searching for new ways to communicate cool ideas in theoryCS to the outside world, and the list gets more and more esoteric each time one thinks about it. But in my interactions with people, people generally unfamiliar with algorithm, and theoretical computer science in general, I'm constantly amazed at how counter-intuitive the very notion of an approximation appears to be.

A typical conversation goes something like this:

Person: Oh this problem is NP-hard so we ran this heuristic
Me: Have you tried approximating it ?
P: What do you mean ? Our heuristic seems to be reasonable.
M: I mean an algorithm that guarantees that it'll get close to optimal.
P: But how can you know that ? It's hard to find the optimal solution, global minimum, yadda yadda yadda...
M: We can often prove an answer is close to OPT without knowing OPT itself.
P: [total silence]

This kind of thing happens often in research conversations, as well as in the classroom (where it's less surprising I guess). In fact, one person was so amazed at the idea that even proving an approximation could be NP-hard that we spent a good semester plowing through the PCP theorem (at least parts of it).

I'm not dissing heuristics: it's often the case that either the approximation guarantees one can show are too weak, or that the claimed bounds don't match the empirical performance. But I do think it's important to at least ask the question of whether provable approximations exist, much in the way people in CS are now reasonable comfortable checking (or asking the resident theoretician !) if a problem is NP-hard.

But you can't ask till you know. This is one of the main reasons I teach a smattering of approximations in my graduate algorithms class (and why I teach some randomization as well). The concept of an approximation (especially when you can't find the actual answer) is a surprisingly slippery conceptual leap, and requires mental agility that goes beyond the standard "algorithms toolkit" that focuses on issues of performance.

Here's your algorithmic lens

In studies of breast cancer cells, [senior investigator Dr. Bert] O'Malley and his colleagues showed how the clock works. Using steroid receptor coactivator-3 (SRC-3), they demonstrated that activation requires addition of a phosphate molecule to the protein at one spot and addition of an ubiquitin molecule at another point. Each time the message of the gene is transcribed into a protein, another ubiquitin molecule is chained on. Five ubiquitins in the chain and the protein is automatically destroyed.

A counter on a separate work tape: neat !

Main article at sciencedaily; link via Science and Reason.

Numb3rs wins NSF award

I used to blog every episode of Numb3rs in its first season, and got bored of doing this soon after. However, I've continued to watch the show; I don't have the heart to avoid watching a show that involves mathematics (and more often than not, computer science). It's been surprisingly decent in its three years, as long as you're willing to concede all kinds of miraculous data mining feats performed in the span of a few hours.

However, I always wondered if it could make it on a mainstream network for very long. After all, ratings are king, and how long could such a tech-heavy series last ? After all, the crime procedural aspects of the show are hardly unique, and with the monster success of CSI, even more scientifically oriented crime series were clogging up the airwaves.

Thus, I was pleasantly surprised to hear that Numb3rs is now the "most-watched show" on Friday nights, clocking in at around 12 million viewers. It's been picked up for a fourth season, and ended season three with a dramatic moment, as well as interesting existential angst for the main characters. In fact, I suspect one of the reasons Numb3rs has done so well is that they've done a fairly realistic job of portraying some of tensions inherent in the life of the researcher (even if the mathematics itself, and the way the characters talk about it, is still somewhat cringeworthy).

The NSF (or technically, the NSB, the board that oversees the NSF) has recognized the success of Numb3rs as well. The show and its creaters were just given a public service award for

...extraordinary contributions to increase public understanding of science. Recipients are chosen for their contributions to public service in areas such as: increasing the public's understanding of the scientific process and its communication; contributing to the development of broad science and engineering policy; promoting the engagement of scientists and engineers in public outreach; and fostering awareness of science and technology among broad segments of the population.

Computer Scientist:Programming::Mathematician:Arithmetic

One of the things that continues to exasperate me on a regular basis is the conflation of computer science with programming. Consider two recent gems (emphasis mine):

1. From a press release for Microsoft TechFest 2007:

   Boku, a virtual robot in a simulated world, debuted as a research project to teach kids basic programming skills in a fun and entertaining way. “There is an ongoing and deepening crisis in computer science,” Rashid said. “Our goal is to stem the tide by showing young kids the magic of software programming.”

2. From an article on changing perceptions of computer science at college and K-12 level:

   East Allen County Schools is working to make sure students are exposed to computer careers, whether they think they might be interested or not. All students are required to take a computer course before graduating, and those who know they are interested can take in-depth courses, including training on Cisco computer networks...

Sigh. Ok people, say after me, slowly: Computer Science IS NOT programming. How many musicians do you think you're going to attract by preaching the exquisite beauty of scales and arpeggios to little kids?

As Lance mentions, the closure of stores like CompUSA is a harbinger of the end of computer science as "television science". The more familiar people get with computers, the more they treat them as appliances rather than as complex devices worthy of worship.

What does this mean ? You aren't going to attract people to a field by saying, "Lookee here! here's a neat television ! Let me show you how to build one. It's FUN!!!!". First of all, people ain't stupid. Secondly, there's a lot more to computer science than programming.

Thankfully, we do see here and there the signs of a manifesto for computer science that doesn't involve actually programming a computer: From Jeanette Wing's CACM article:

Computer science is the study of computation: what can be computed and how to compute it.

Amen to that. And notice how different it sounds to the version you might get from the random person on the street:

Computer science is the study of computers.

If I had to preach the gospel of computer-science-as-computation, I'd probably riff off three things:

• The above mentioned CACM article. Message: Computer science is the study of algorithms and abstractions.
• Bernard Chazelle's IPod essay. Message: Algorithms are the language of modern science
  
• Scott Aaronson's 'Logicians on Safari' article. Message: Computer science is quantitative epistemology.
  

'Nuff said.

p.s Chazelle is quickly becoming the poet-laureate for 21st century computer science: check out the table of contents for his course titled, "What do your DNA and your iPod have in common ?"

Three thoughts on Anatoly Vershik's article...

Via Peter Woit and Luca Trevisan comes a pointer to an article by Anatoly Vershik in the new Notices of the AMS, lamenting the role of money prizes in mathematics. Three thoughts:

• "the newspapers, especially in Russia, are presently “discussing” a completely different question: Is mathematical education, and mathematics itself, really necessary in contemporary society ". At the risk of sounding patronizing, I find it terribly worrisome that the place that spawns such amazing mathematicians, and has such a legendary training program for scientists, should even indulge in such a discussion. Especially now, with all the handwringing in the US about the lack of mathematical training at school level, it seems a particularly bad time to abdicate what is a clearly a competitive advantage.
  
  
• He talks about not understanding "the American way of life" as regards how money is viewed. There's a juxtapositon of images that I've always been struck by, and that tennis lovers will recognize: At Wimbledon, the winner is crowned with a fanfare, royalty, and a trophy (or plate); the prize money is never really discussed. At the US Open on the other hand, along with the fanfare comes the huge check handed out by some corporate sponsor while the PA blares out the amount. The trophy presentation, although making for good photo-ops, seems almost anticlimactic.
  
  I am a little skeptical though whether offering prizes like the Clay prize convinces people that mathematics is a lucrative profession. After all, this hasn't happened for the Nobel prizes.
  


• On the false-duality: I've heard a variation of this argument many times. It goes basically like this: "Either you're interested in subject X and don't need motivation, or you aren't, in which case no amount of motivation is going to help". This is possibly true for identifying students likely to make the transition to being professionals in subject X. In fact, I've heard an anecdote from the world of music, about a maestro who would tell all his students that they would fail professionally at being musicians. His argument was that only the ones who cared enough to prove him wrong had what it took to survive.
  
  One has to realize though that the teaching of a subject is not about creating Mini-Mes: only a small fraction of the students we come in contact with will become professional computer scientists/mathematicians/whatever. But a large fraction of these students will vote, many of them will go onto position of influence either in industry or government, and they will all contribute to a general awareness of the discipline. So it's a mistake to give up on motivating students; even if they never end up proving theorems for a living, a better appreciation for those who do will help all of us.
  

Categories:

• outreach