Things a Complexity Theorist Should Do At Least Once

A few weeks ago, Suresh wrote a post Things a TCSer should have done at least once with the caveat

This list is necessarily algorithms-biased. I doubt you'll need many of these if you're doing (say) structural complexity. 

Basically begging a response. So here is what every structural complexity theorists should have done.

• Define a new complexity class that has some reason for being.
• To keep balance in the world, you should also collapse two other complexity classes. 
• While you are at it, separate two complexity classes that weren't separable before. 
• Create a new relativized world. Extra points if in this work you collapse two complexity classes while separating two others. 
• Use Kolmogorov complexity, information theory or the probabilistic method as a proof technique. They are really all the same technique in disguise.
• Use the sunflower lemma, or the Local Lovasz lemma, or some other weird probabilistic or combinatorial lemma just for the fun of it.
• Invoke VC dimension to solve a problem. I should have at least one in common with Suresh and Sauer's lemma is sometimes useful in complexity. 
• Have a theorem that starts "Assuming the extended Riemann hypothesis..."
• Give a "simpler" proof of a nasty theorem. 
• [Advice given by Noam Nisan many moons ago] Try to settle P v NP. In both ways. Only by really trying and failing can you understand why the easy stuff doesn't work. 

A new kind of Spam

(In this post I quote attempted posts to the blog.
I transcribe them as they are, so if you see a missing period
or awkward language, its not me (this time) its them.)

We moderate comments but do so very lightly.
There is no hard and fast rules but roughly speaking
we block comments that are BOTH offensive AND off-topic.
There may be exceptions- like if its on topic but REALLY REALLY offensive
and adds nothing to the discussion.
There may more benign exceptions- like if I post a question and will block the
answers so that when I reveal the answer the next day its more dramatic.
Of if someone posts information that is not public yet.
In these case we hope they try to post non-anonymously so we can email them
and tell them why they were blocked. There are other isolated cases as well.
All of these are very rare.

Recent attempted comments do not fall into these rules and we had to
decide on them. The following was an attempted comment on my post
about
STOC 2012-Workshops and honored talks

Hi there STOC 2012- workshop and honors talks Loved every second! Great views on that!
That actually breaks the mold! Great thinking!

This comment is NEITHER offensive NOR off-topic.Its a bit odd- I can't tell if
the Great view is of my post or of the talks I was writing about.
It does sound awkward. Why is that? IT WAS GENERATED BY A SPAMBOT!!!
How do I know this? Because if you click on the author you are directed to a site thatsells you paints for your living room.Hence we block such posts.

So, they think the readers of our blog are into interior decorating.
I am sure that some are, I don't think our readers are a particularly good market for this. Technology is good enough to find our blogs and try to use spambots on them,but not good enough (or there is no incentive) to figure out which blogs are worthtargeting.This is part of a bigger problem I blogged about
herewhere I noted that technology is good enough to know that I am a book review editor for SIGACT NEWS but notgood enough (or there is no incentive) to figure out that I only review comp sci and math books, and not
books on (say) politics.

A borderline case: an attempted comment on the blog
A natural function with very odd properties was

Awesome logic. You truly have some expert skills and enhanced my knowledge on Cantor Set Construction Agreements.

This one did not link to any product so it might be legit, except thatit is awkward sounding and the same person tried to submit,as a comment to Six Questions a about natural and unnatural mathematical objects

This truly enhanced my skills. very helpful Job Proposal.

Clearly spam, though I'm not sure why since there is no link to a product.

These posts are trying to pass a Turing Test- but so far they are not succeeding.

Sometimes they only positive comments I get are from spambots. Oh well.

Poset Games are PSPACE-complete

Consider the following game on a poset, each player takes turns picking an element x of a finite poset and removes all y ≥ x. First one to empty the poset wins. I posted last March about a high school student, Adam Kalinich, who showed how to flip the winner of a poset game.

Finding the winner of a poset game is in PSPACE by searching the game tree. A corollary of Adam's work showed that poset games were hard for Boolean formula leaving a huge gap in the complexity of finding the winner.

Daniel Grier, an undergrad at the University of South Carolina, has settled the problem and shows that determining the winner of a poset game is PSPACE-complete. His reduction is ridiculously simple (though not obvious) and the proof is not that complicated either.

Grier starts from Node Kayles which is a game on an undirected graph where each player takes turns removing a vertex and all its neighbors. Whomever empties the graph first wins. Thomas Schaefer showed the PSPACE-completeness of Node Kayles back in 1978.

Grier's reduction from Node Kayles to posets is very simple: Let G be the graph. Have one element in the poset for each vertex of G, all incomparable. For each edge e=(u,v) we add two more elements, one above the vertex elements corresponding to u and v, and one below every vertex element other than u and v. That's the whole construction.

Grier shows that if G has an odd number of edges and no immediate win for the first player then the first player wins the Node Kayles game if and only if the first player wins the corresponding poset game.

You can read more details in Grier's short paper. It's really neat seeing high school students and undergrads solving interesting open problems. We need more problems like poset games.

Theory Conferences Galore

Early registration for the FOCS conference in New Jersey is September 27th. There is some travel support available for students and postdocs, deadline is this Friday the 21st.

STOC and Complexity will be co-located in Palo Alto in early June. STOC CFP (deadline November 2), Complexity CFP (deadline November 30).

SODA comes back to the US and New Orleans January 6-8. Accepted Papers.

Imagining Imaginary Probabilities

In the year 4000BC my great-great-...-great grandmother tried to solve (in today's terms) the equation

x² + 2x + 2 = 0

She discovered that if it had a solution then there would be a number a such that a²=-1. Since there clearly was no such number, the equation had not solution. She missed her chance to (depending on your viewpoint) discover or invent complex numbers.

Fast Forward 6012 years.

In the year 2012 I wondered: is there a probability p such that if you flip a coin that has prob(H)=p twice the prob that you get HT is 1/2? This leads to

p(1-p)=1/2

If you solve this you get p=(1+i)/2. Hence there is no such coin. WAIT A MINUTE! I don't want to miss the chance that my great...great grandmother missed! In the real world you can't have a coin with prob(H) = (1+i)/2. But is there some meaning to this?

More generally, for any 0 ≤ d ≤ 1 there is a p ∈ C (the complex numbers) such that ``prob(HT)=d.'' The oddest case (IMHO) was to take d=1. You then get that if a coin has prob(H)=(1+\sqrt(-3))/2 then prob(HT)=1. Does that mean it always happens? No since prob(TH)=1. Do the probs of HH, HT, TH, TT add up to 1? Yes they do since some are negative.

Is there an interpretation or use for this? I know that quantum mechanics uses stuff like this. Could examples like this be good for education? Are there non-quantum examples of the uses of this thatcould be taught in a discrete math course?

Max Flow

A couple of weeks ago Suresh tweeted the following result of James Orlin

Max flows in O(nm) time or better. jorlin.scripts.mit.edu/Max_flows_in_O…
— Suresh Venkat (@geomblog) August 31, 2012

I'm thinking, wow, max flow is one of the major standard algorithms problems, and O(nm)  time (n = number of vertices, m = number of edges) seems like a great clean bound. But there hasn't been much chatter about this result beyond Suresh's tweet.

Reading Orlin's paper gives some clues. The previous best bound due to King, Rao and Tarjan has a running time of O(nm log_{m/(n log n)}n) = O(nm log n) just a logarithm off from O(nm). Orlin doesn't directly give an O(nm) algorithm, his takes time O(nm+m^31/16log²n). It's the minimum of the running times of King-Rao-Tarjan and Orlin's algorithms that yields O(nm). Nor is O(nm) tight, Orlin also gives an algorithm with a running time of O(n²/log n) when m=O(n).

I don't mean to knock Orlin's work, he makes real progress on a classical algorithmic problem. But somehow I think of O(nm) as a magical bound when it is really just another bound. I'm just fooled by simplicity.

Some quantum Stuff

Two quantum announcements (emailed to me by Umesh Vazirani, and producedhere almost exactly) and then some thoughts of mine quantum computing.

Announcement one: The NSF has a new initiative to try to address the lack of tenured faculty (particularly in computer science departments) involved in quantum computation research.  CISE-MPS Interdisciplinary Faculty Program in Quantum Information

The initiative provides a paid sabbatical year to interested tenured faculty to visit a strong quantum computing group, so that can reposition their research interests. The rationale behind the solicitation is to increase the number of tenured researchers in quantum computation, but also to break through the "quantum skepticism" in faculty hiring decisions in those departments where there are no faculty actively involved in quantum computing research.

Announcement two: In support of this program, Carl Williams (a physicist working in Quantum Information who put together the US Vision for Quantum Information Science for the Office of the President) and Umesh have put together a workshop where interested individuals can learn about the initiative, the field and make contacts with people from the major quantum computing centers: see here.

The initiative comes at a particularly opportune moment for researchers in complexity theory, given the increasing relevance of quantum techniques in complexity theory --- the 2-4 norm paper of Barak, et al (SDPs, Lasserre), exponential lower bounds for TSP polytope via quantum communication complexity arguments (See Drucker and de Wolf  paper Quantum proofs for classical theorems for several apps of Q to Complexity, and see
here for the TSP polytope result)
quantum Hamiltonian complexity as a generalization of CSPs, lattice-based cryptography whose security is based on quantum arguments, etc.

MY COMMENTS: Umesh gives as a reason quantum is important its uses in other parts of complexity theory. While that is certainly good there are other intellectual reasons why Quantum is worth studying.

1. Factoring is in Quantum P! There are MANY problems (maybe 10) where Quantum seemsto be faster than classical.  I wouldn't really want to push this point sincequantum computer aren't build yet. More generally, if one claims a field is validfor real practical value, those arguments may become less believable over time.
   
2. Quantum computing can be used to simulate quantum systems- I think this was one of the original motivations.
   
3. Quantum computing is valuable for a better understanding of Physics.
   This was first told to be my Fred Green (A Physics PhD who went into computer science)and I made it the subject ofthis blog entry.
   I like his quote so much that I will quote it here
   

   
   Learning quantum computing helped me understand quantum mechanicsbetter. As a physicist I never thought about measurement theoryor entanglement, which were foundational issues, irrelevantto what was doing. In quantum computing, we reason about thesethings all the time.

   
   Over the years others have told me similar things.

Side note: The word Quantum is mostly misused in popular culture. Quantum Leap meant a big leapwhen actually quantum means small. The James Bond movie Quantum of Solace used it correctlybut was an awful movie. Oh well.

The Time of Research

Among the many conference/journal discussions, one systems person said the reason they don't publish in journals is that their work is very dependent on current technology. A few years in the future the technology will change and this research is no long relevant. The best systems research develop ideas that transcends technology, but much research in systems have a limited lifespan of relevancy.

In theory, if you prove a theorem that theorem will be true forever. In fact that theorem was always true, we just didn't know it. So it is important to have refereed long-term archival write ups of these results. A theorem could be supplanted by another result or get less interesting over time but it always remains true.  Theory results transcend technology, though most theory result have a zero lifespan of relevancy.

Theory Day at UMCP Oct 24

The University of Maryland at College park is having a Theory Day on Wed Oct 24! Come hear

1. Distinguished talks by Julia Chuzhoy and Venkataesan Guruswami!
   
2. Short talks (is that code for NOT distinguished?) by Bill Gasarch, MohammadTaghi Hajiaghayi, Jonathan Katz, Samir Khuller, David Mount, Elaine (Runting) Shi, and Aravind Srinivsan.  (I never realized I was first alphabetically until now.)
   
3. Discussions in hallways for those that learn more that way!

For more info see the link above, but note one thing: Its FREE!

I like theory days in general and often go to the NY theory days.  They are free and only one day.  I recommend going to any theory day that is an Amtrak Ride away.  (Might depend on how long the trip is- There is a 13-hour Amtrak from Atlanta Georgia to Maryland, though I doubt I'll see Lance there.) I get a lot out of theory day as noted in this post about NY theory day

(ADDED LATER AT THE REQUEST OF THE ORGANIZER:
Theory day at UMCP is intentionally after the NJ Focs and is an easy amtrak
away from NJ. The stop is New Carolton)

Should we learn from the Masters or from the Pupils?

The following is a paraphrase of a comment at the end of the Suggested Readings section of Spivak's calculus book:

Abel remarked that he attributed his profound knowledge of mathematics to the fact that he read the masters, rather than the pupils.

Are you better off reading the Masters or the pupils?  This of course depends on the masters and the pupil and other factors.

1. I have heard that Godel's original papers (even when translated) are well written and show a profound understanding of the subject and why its important.
   
2. However, we now have a better understanding of what Godel did and better ways to express it.
   
3. The Masters may include the motivation which may be lost in later papers.
   
4. Often the first proof of anything is ugly or odd and later proofs really clean it up.
   
5. Often the first proof of anything uses only basic concept- later abstractions may hide the heart of the proof.
   
6. As a practical matter sometimes the early papers are not available (thanks to paywalls or obscurity) or in a language you do not read.
   
7. If Lance and I ever do a book-of-blog-posts I will clean up some of the spelling, make some of the arguments more clear (perhaps indicate where I am being sarcastic in cases where it was not understood), improve the writing. This will make it better than the blog but less authentic.

Here are examples where the Masters papers may not be worth reading:

1. Recursion theory in the early 1960's had several infinite injury arguments. I have heard that they were known to work only because the lemmas and proofs worked out.  Only after Bob Soare's excellent article on the topic were they really understood. For 0''' priority arguments it is also true that the early papers are not the ones to read.
   
2. Example (and the real motivation for this post). I have tried to read Ramsey's original article. I knew that his goal was a problem in logic, and I wanted to know what that problem was. I had a hard time reading the paper.  (I did  my own writeup.) Why was his version so hard to read?  (1) He never uses the words coloring or graph or hypergraph. He doesn't mention that if you have six people at a party either three of them know each other or three of them don't know each other. Perhaps he didn't go to many parties.  (2) He uses odd terms at time.  (3) His paper is rather abstract. If he had just proven a simple case then it would be obvious how to proceed to his abstract case.  This is true for both his combinatorial theorem--- he only proves (what we would call) the hypergraph version, and also the Logic theorem.
   
3. The Cliff notes for Atlas Shrugged are far better than the book. Shorter too.  They are online for free here which makes sense since Ayn Rand was known for her altruism.

SO- what do you think? Examples of cases where the Master is better to read?
Examples of cases where the Pupil (or more generally later summaries, surveys, expositions) is better to read?

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.