The Net or the Jet

I spent the first half of my life in the jet age but not in the Internet age. I could fly anywhere in the world but the fastest way to get a research paper to another scientist was to bring the paper on the plane with me.

One could imagine technological innovation going the other way around where we had a functioning Internet but no air travel. Maybe we would have done a much better job creating virtual meetings and conferences.

Suppose you had to choose a world to live in:

1. Jets but no 'net. We know what this world looked like.
2. Net but no jets. We can only imagine.

Which one would you choose?

[This question came from a discussion with Paul Royal, a Georgia Tech research scientist in Information Security. We chose different answers.]

Neil Armstrong, Ray Bradbury: The future is not what we thought it would be

Neil Armstrong died on August 25, 2012.  He was the first man to walk on the moon.  (Since they always say this I wonder if Women walked on the moon earlier.) Ray Bradbury  died on June 5, 2012, though on this (and perhaps other) blogs with was overshadowed by death of Mihai Patrascu on the same day.

When man landed on the moon I thought that this would be a common thing- that we'd goto the moon about once a year. In the end only 12 people walked on the moon and we stopped going in 1972.  See here for details.

Why didn't we go more often? Maybe there wasn't much to see- you see one moonrock you've seen them all. Are unmanned flights much better in terms of science-for-the-money? I suspect yes.  Also, one reason America put men on the moon was to beat the Russians to it.  Once we already did that, the point was made, so no reason to go again.

If we went now it would cost much less. So perhaps we should have waited for the technology to catch up and go later for much cheaper.  That's not quite right- one reason we have some of the technology is that we went then. But in some areas- computers in particular- certainly we would have still made progress without going to the moon.  On the other hand going to the moon when we did was quite inspiring to some people.  (Are you one of those people?)

Ray Bradbury's classic Farenheit 451  was about censorship- the government had firemen who burned books. Books made of paper. I suspect that within 10 years e-books will be the standard (some exceptions- Art books, maybe some Math books).  Will that make censorship easier or harder? The Arab Spring was caused partially because the government could not control social media. However, in China the government is pretty good at blocking access to the Web. But still, some gets through.  So to rephrase the question- does current technology make censorship easier or harder?  I don't have an answer to this question- but I invite your intelligent commentary.

Ray Bradbury himself has said that the book was also about people choosing a shallow culture (e.g., TV over books). Modern technology has been a mixed bag for this.  Some TV shows will one day (or even now) be seen as classics (e.g., The Simpsons) while others are of course going to be seen as vapid, shallow, and not worth much (e.g., Madmen).

Knuth Prize

Leonid Levin will receive the Knuth Prize, and give the corresponding lecture, at FOCS this year. The Knuth Prize is jointly given by ACM SIGACT and the IEEE TC-MFCS for outstanding contributions to theoretical computer science.

Levin easily deserves the award alone for his amazing two-page 1971 paper, actually two major research lines

• An independent discovery of NP-completeness and
• Universal search

Today we call the seminal NP-completeness result for Satisfiability the Cook-Levin theorem.

Levin did so much more, from the "right" definition for average-case hardness to (with Hastad, Impagliazzo and Luby) producing pseudorandom generators from any one-way function.

Congrats to Leonid!

Ten Years of the Complexity Blog

On August 22, 2002 I wrote the following immortal words to start this blog

This is my complexity web log. I'll be giving random thoughts about computational complexity and about mathematics and computer science in general.

Ten years and over two thousand posts later this blog keeps going.

Computational Complexity has come a long way since 2002. In post two I talked about the then new result showing that Primes are in P. Since then we've seen Reingold's log-space algorithm for undirected connectivity, Dinur's "simpler" proof of the PCP theorems, new circuit lower bounds and great new algorithms. Alas the P versus NP problem is still open.

Thanks to all of you for reading and commenting on the blog. It's your support that has keeps us going for the the last ten years and many more years to come.

Fellow blogger Abie Flaxman named Top Innovator!

(Guest post from William Heisel, Assistant Director for External Relations, Institute for Health Metrics and Evaluation, University of Washington, 2301 5th Avenue, Suite 600,Seattle, WA 98121)

Abraham (Abie) Flaxman who writes the Healthy Algorithms blog
(which is on Complexity Blogs' Blog Roll) has been named one of the world's top young innovator by MIT.  This is a sign that algorithms are finally getting a little respect in the global health and technology worlds.

In global health  the rock stars are the vaccines, new toilets, and bed nets. Health measurement is considered something for bean counters whose pasty skin never sees the blistering Sub-Saharan African sun. But what about the tech junkies? They must see the value in crunching all those numbers to do the world some good? Not so much. Techies get excited about apps and gadgets and new ways to monetize web hits.

Finally, Technology Review, MIT's tech industry Bible, is naming a health measurement pioneer (who happens to work at the Instutite for Health Metrics and Evaluation (IHME) IHME) to its list of the world's top young technology pioneers.  Here is the official press release:

For the first time, a prestigious technical innovation honor from the Massachusetts Institute of Technology (MIT) will go to an expert in health measurement: Abraham Flaxman, an Assistant Professor of Global Health at the Institute for Health Metrics and Evaluation (IHME) at the University of Washington (UW).

Since 1999, MIT's Technology Review has honored the world's top innovators under the age of 35 (TR35), in fields such as biotechnology, software, and energy. Until this year, the TR35 judges have not named an innovator in health measurement. Dr. Flaxman was selected from more than 250 nominations by a panel of expert judges and the editorial staff of Technology Review.  Past winners include Facebook founder Mark Zuckerberg and Google co-founders Sergey Brin and Larry Page.

Abie's technical innovations in the field of global health have been game changing in our ability to measure health and health interventions, IHME Director Dr. Christopher Murray said. He has - and continues to be - at the forefront of pioneering methods that improve our ability to measure health outcomes and the effectiveness of interventions that address the world's greatest health challenges.

Nowhere is this more important than in the upcoming Global Burden of Disease (GBD) 2010 Study. Dr. Flaxman is the youngest member of the core team for the ambitious study that aims to provide the most comprehensive assessment to date of the burden from death and disability for more than 300 diseases, risk factors and injuries. Dr. Flaxman advanced a new way of disease modeling that allows researchers to combine all of the world's data on prevalence incidence, remission, and mortality and produce consistent estimates of the way diseases progress through the population, as a function of age, time, sex, and geography. When the GBD study is published, it will give governments and health program funders the best picture yet of how the world has advanced or fallen behind in efforts to improve population health.  We are able to understand what is truly causing the greatest amount of mortality and disability in the world because of technical advancements that can be traced back to Abie scribbling on a white board in  his office, said Dr. Mohsen Naghavi, Associate Professor of Global Health at IHME and one of the lead researchers on the GBD project.

Dr. Flaxman also has made significant advancements in verbal autopsy methods for gathering health data in low-resource settings. His machine learning algorithm for computer-certified verbal autopsy takes the results of a health interview of relatives about a recently deceased person and automatically determines the cause of death. He also created a stock-and-flow model for tracking the distribution of insecticide-treated bed nets to prevent malaria. The results are updated annually and included in the World Health Organization's World Malaria Report.  The advancements Dr. Flaxman and colleagues have made in data-driven data quality audits (D3QA) were recently recognized at the Symposium on Computing for Development. Their publication on the development of the D3QA tool won on the best-paper award. The tool can be used to ensure that health data and other data gathered from household surveys are accurate. It is currently being used in research aimed at estimating mortality from war-related causes in Iraq.

Dr. Flaxman has accomplished all of this in just four years. He was on track to join the legions of computer scientists who staff technology giants such as Microsoft and Amazon. While working at Microsoft Research in 2008, he applied for an IHME Post-Graduate Fellowship. His extraordinary work as a Post-Graduate Fellow propelled him to being hired as a UW faculty member.

The world is not lacking in health data, and yet certain basic information has never been quantified, Dr. Flaxman said. I realized four years ago that I could use computational algorithms to solve some of these measurement challenges in global health. And I am incredibly honored to have been recognized by the TR35 judges for this work. Dr. Flaxman will discuss his work alongside other TR35 honorees at the EmTech MIT 2012 conference at the MIT Media Lab in Cambridge, October 24-26. All the TR35 winners for 2012 will be featured in the Sept/Oct issue of Technology Review

The Institute for Health Metrics and Evaluation (IHME) is an independent global health research center at the University of Washington that provides rigorous and comparable measurement of the world's most important health problems and evaluates the strategies used to address them. IHME makes this information freely available so that policymakers have the evidence they need to make informed decisions about how to allocate resources to best improve population health.

For more information about IHME, please visit: here.  Technology Review, Inc., is an independent media company owned by MIT It publishes Technology Review magazine, the world's longest-running technology magazine (established 1899).  Additional information about TR35 winners and judges is available here For more information about EmTech MIT 2012, please visit: here.

Is the Turing Test Still Interesting?

Besides the Turing machine, Alan Turing also developed what we now call the Turing Test in Turing's seminal 1950 AI paper "Computational Machinery and Intelligence". Turing describes his imitation game and says if a judge cannot distinguish between communicating with a computer versus a human than this is an indication of that a computer "thinks".

It's not clear exactly when a computer will pass the Turing Test but with systems like Watson and Siri we are getting very close. One can imagine that if we run the right machine learning algorithms on large data sets like Facebook chats or text messages, we can create a system that would fool most people. But would it really be intelligent?

Think about how Google translate works. There is no understanding of the meaning of the words in either language, just a statistical approach to develop a function that maps one language into another. Is this method really intelligence, are Google's computers "thinking"? Not really.

In a couple of years it will be clear that computers easily pass the Turing test. It will be another milestone, like beating humans at Chess and Jeopardy. The computers won't be any more intelligent by passing the test but they will be more useful. And I'll take useful over intelligent any day.

Book Review Column (a bit late)

I try to post my book review column when it comes out but I am behind on that. This is the one that came out a few months ago.  The column is here though I have removed the list of books I want reviewed since it is out of date. The current list of books I need reviewed is here.  Advice for reviewers is here.  The LaTeX template for reviews is here.

The books reviewed in the column are:

1. A Concise Introduction to Data Compression by David Salomon.  This book covers different aspects of data communications with a main focus on source coding, more commonly known as data compression.  We can view source coding as lossless compression, where the goal is to find a bijective function that when fed a bitstream, also known as a message, outputs a shorter bitstream.
   
2. Parallel Algorithms by  Henri Casanova, Arnaud Legrand, and Yves Robert.  This book provides the reader with an advanced introduction into the principles of Parallel computing.  The book is targeted at advanced readers -- graduate students and post-graduate researchers with a strong computational background -- and represents a good resource both in support of a graduate course in parallel algorithms, and for self-guided learning.
   
3. Polynomia And Related Realms by Dan Kalman.  This book is about polynomials. Topics include Horners rule, root finding (e.g., the cubic equation) and max-min problems. There is also some history in the book so you'll know where the ideas come from.  The MAA awarded this book a Beckenback Prize at the January meetings.  Details are posted here
   
4. Biscuits of Number Theory Edited by  Arthur T. Benjamin and Ezra Brown.  The authors themselves give the best description of the book: an assortment of articles and notes on number theory, where each item is not too big, easily digested, and makes you feel all warm and fuzzy when you're through.
   
5. Combinatorial Geometry and Its Algorithmic Applications: The Alcal\'a Lectures by Janos Pach and Micha Sharir.  Combinatorial Geometry is the study of points, lines, and planes.  This material often has algorithmic applications; however, unlike Computational Geometry, this is not the original motivation. This book explores the aspects of combinatorial geometry that have applications to algorithms.
   
6. Handbook of Large-Scale Random Networks Edited by Bela Bollobas, Robert Kozma and Deszo Miklos.  Networks can often be modeled as a random graph.  The research here is truly interdisciplinary.  This handbook is an outcome of a U.S.-Hungarian workshop on complex networks held at the R\'{e}nyi Istitute in Budapest in 2006.  According to its editors, its purpose  is to provide a significant update and extension beyond the materials presented in the ''Handbook of Graphs and Networks published in 2003 by Wiley
   
7. Algorithms and Theory of Computation Handbook Edited by : Mikhail J. Atallah and Marina Blanton.  This is a pair of volumes that cover many topics of interest to TCS research.  Volume I is mostly algorithms and Volume II has some real applications.
   
8. Primality testing and integer factorization in public key cryptography by Song Y. Yan.  This book covers number theory, some of which is quite advanced, and how it interacts with modern cryptography.
   
9. Process Algebra: Equational Theories of Communicating Processes by J. C. M. Baeten, T. Basten, and M. A. Reniers.  Process algebra is a method for specifying and verifying distributed and parallel systems that uses logic and universal algebra.  This book deals mostly with using Process Algebras for communicating processes.
   
10. Insider Threats in Cyber Security Edited by Probst, Hunker, Gollman, and Bishop.  This book seeks to educate the reader about the various aspects of insider threat and attempt to define/explain the problem (e.g., types of insiders, the nature of the problem and types of misuse), and ways in which end users and businesses can seek to mitigate some of these risks.  Other topics include fraud detection and insider threat mitigation technologies. Several challenges from both practitioner and research perspectives are discussed.

Another Algorithmic Market Failure

In 2009, Matt Cushman, Managing Director at Knight Equity Markets, gave a seminar at Northwestern on "High Frequency Trading". Here is the abstract:

High frequency trading has emerged over the past decade as a critical component of modern electronic financial markets. It provides liquidity, efficiency and stability to the global equities, foreign exchange, futures and other electronic marketplaces. By some accounts, two-thirds of US equity shares traded are done by high frequency systems. Yet, misconceptions abound in the popular media today concerning high frequency trading's impact and value to the broader economy.

We will discuss the value of high frequency trading, and some of the problems (both quantitative and technological) that must be solved to operate a successful high frequency system.

Much of the talk focused on how Knight put its servers close to those of the NYSE so it could be first in line for trades. I failed to see the societal value. Say at the airport if someone cuts in front of the security line, they get considerable extra value but it will be cancelled out by the lost time of everyone behind him.

The company, now called Knight Capital, tried out a new algorithm last Friday and lost $440 million buying when it should have sold.

I cry no tears for Knight but such losses can have a disastrous effect on the stability financial markets. One solution is to have the government or some other agency verify code before traders can use it on the markets. But code verification is practically difficult and theoretically impossible.

I would prefer a tiny transaction tax on every trade, negligible for all but high-frequency traders. Computation has made the market nearly frictionless, time to but some friction back in.

My take on the Olympics

Thoughts about the Olympics

1. If you are rooting for your country, would you rather they get (say) 18 medals: 6 Gold, 6 Silver, 6 Bronze, or 17 medals: 10 Gold, 4 Silver, 3 Bronze?  More generally, when is (g,s,b) better than (g',s',b') Some schemes:
   
   
   
   1. The commentators and the websites seem to use g+s+b. They say things like
      American is leading the Medal Count without breaking it down.  Given that the margins-of-victory are often rather small, and all of the athletes who finish in the top 3 (often even in the top 20) are quite good, I think that just g+s+b is good.
      
   2. If you want to value gold medals more than a scheme like 3a+2b+c makes sense.  One problem- the weights 3,2,1 are arbitrary. What would a criteria be for good weights?
      
   3. It may be a complicated function. For example (g,s,b) is better than (g',s',b') if g ≥ g'+4 OR (g ≥ g'-3 AND g+s+b ≥ g'+s'+b').
      
   4. You may want to allow for a partial order--- that is, some triples are incomparable.
   
   
2. Swimming or running: Often the top X people are 0.5 seconds apart and all close to or better than the world or Olympic record.  I would give them all medals. This is not some wimpy self-esteem crap--- if the athletes are that close together, and close to breaking records, they really are all excellent and you really can't say whose better. A possible scheme:
   
   
   
   1. If you tie or beat a world record you get a Gold Medal. (Might even allow if you are within X of a world record for some X.)
      
   2. If nobody has beaten or tied a world record and you tie or beat an Olympic record then you get a Gold Medal.  If someone else has beaten or tied a world record then you get a Silver Medal.  (I may allow some leeway in both cases.)
      
   3. The top person behind all of those people gets the bronze Medal.
   
   
3. Or we could give more medals: Gold, Silver, Bronze, Zinc, Aluminum, maybe more.
   
4. In Women's Gymnastics these women do spectacular things but if they land badly TAKE OFF X POINTS! Somehow that doesn't seem right.
   
5. In most events Women and Men compete separately.
   
   
   
   1. Track and Swimming: Since these are timed we can say without apology that the men are better, so its best if they don't compete head-to-head. However, if a women wanted to compete in the men's event she should be allowed to (Are they now? I doubt it.) I don't think this has come up. 
   2. Gymnastics. Here its NOT that either gender is better, its just that they do different things.  The very thought of a guy on the uneven parallel bars terrifies me.  The thought of anyone doing backflips on a 4-inch wide beam also terrifies me.
      
   3. Equestrian- from what I could tell from the Yahoo Schedule Website men and women compete equally here.
      
   4. Archery and Shooting are seperated by Gender. For Archery this might make sense- some strength is required.  For Shooting this makes no sense to me. I asked a guy who knows about shooting and he told me that many non-Olympic shooting sports are not seperated by gender.  So why are the Olympic Shooting contests seperated by gender? My guess is that its the same reason COLT allows PC members to submit and CCC does not: because that's how we've always done it.
   
   
6. Game theorist needed: The rules for Badminton were set up so that it was in China's interest to throw a game (see here).  In this case I think it should be fine for a team to forfeit rather than play badly on purpose. More important- the rules need changing.  The Blog Turing's invisible Hand discussed this here.
   
7. What sport do you most want to see in the Olympics? I would say Chess Boxing or Skeet Surfing. Both make more sense then the Olympic sport of Modern Pentathlon which combines pistol shooting, fencing, freestyle swimming, show jumping, and a 3 km cross country run.

MOOCs

I haven't posted in about a month. A combination of traveling, vacation, moving to Atlanta and getting started as chair. I appreciate why Michael Mitzenmacher stopped blogging as he became department head. I'll try to post once a week but no promises.

Last week I attended the CRA Snowbird meeting, a biennial meeting of CS chairs and other leaders in the field. The big topic this year: Massively Open Online Courses or MOOCs. Coursera just a couple weeks ago had their big announcement with their line-up of universities that will produce courses including Georgia Tech.

John Hennessey, president of Stanford, gave the CRA keynote address arguing that MOOCs will save universities. He puts the untenable costs of universities at personnel costs (faculty salaries) are making colleges unaffordable (not sure I fully agree). He argued that MOOCs will help teach courses more effectively. The hidden subtext: fewer professors and probably fewer universities, or as someone joked, we'll all be branch campuses of Stanford.


As pointed out by a few at the meeting there is nothing essentially computer science about MOOCs. But it's hard to ignore the CS influence: The Stanford courses that started the new MOOC era were in computer science, Coursera and Udacity are led by computer scientists, as are the MOOC centers at Stanford, MIT, Georgia Tech and many other schools. With great influence comes great responsibility so let's be sure to do it right.


About the only thing people could agree with is that the we are in the very early stage of MOOCs produced by major universities and nobody is sure where we are going. MOOCs may completely change higher education in America and around the world. Or they won't.