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.

A natural function with very odd properties

Last time I posted some questions. Today I post the answer that I know.

1. Is there a subset of [0,1] that is uncountable and has measure 0?  YES- take the Cantor Set.  Many readers knew this.
2. Is there such a set that is natural? Some comments thought the Cantor Set was natural. I disagree, however
   this is a matter of opinion and taste.
3. Is there a function that is continuous everywhere and differential nowhere?  YES- take the Weierstrass Function.  Many readers knew this.
4. Is there such a function that is natural? Some think the Weierstrass Function is natural. I disagree because it was constructed for the sole reason to be continuous everywhere and differential nowhere.  But again, there are those who think it is natural and this is a matter of opinion.
5. Is there a function that has derivative 0 at almost every points of [0,1] even though it is strictly increasing?
   YES- take Cantor Functions,
   also known as the Devil's staircase. Some readers knew this.
6. Is there a natural such function? YES- and this was the motivation for the post. (I also didn't want to have the example I read about mentioned in the comments of the last post which is why I wanted all posts to be non-anonymous- so if I blocked one I could email the author WHY I blocked it.)

The function I will talk about came about because of a real problem having nothing to do with finding weird functions. Hence I think it is unambiguously natural.

I base my exposition on the exposition in
How to Gamble if you Must
by Kyle Siegrist. The original source is from the classic book Inequalities for Stochastic Processes: How to Gamble
if you must by Dubbins and Savage. Classic or not, unless that book is free online the future
will credit Siegrist with the result (even though Siegrist references Dubbins and Savage.)


Consider the following game: Let 0 < p < 0.5.
Let 0 ≤ x ≤ 1. We will view p as a probability and x as how
much money you start with.
You place a bet (which has to be ≤ what you have).
A coin is flipped with prob of WIN being p and of LOSS being 1-p.
If you win you double your bet. If you lose you lose your bet.
You repeat until you have 0 or you have 1.

You could play TIMIDLY: bet a fixed small amount every time.
This is analyzed. In the paper and is interesting.


You could play BOLDLY: if you have < 1/2 then bet all you have,
and if you have ≥ 1/2 then bet so that if you win you'll have 1
and can stop.


If you play BOLDLY then
what is the probability that you will end with 1?
We will fix p and let F(x) be the prob if you begin with x.
(We assume 0 ≤ x ≤ 1.)
F satisfies the following recurrence:

F(x) = pF(2x) if x ∈ [0,0.5]

F(x) = p + (1-p)F(2x-1) if x  ∈ [0.5,1].

F(0)=0, F(1)=1

This is enough to define F on all rationals between 0 and 1 (use the expansion in base 2).
Then use continuity to define F on all the rationals between 0 and 1.

The paper claims that F has derivative 0 at almost every point of [0,1]
even though its strictly increasing.
I leave this for the readers (translation into English: I don't know the proof).
However, I emailed the author who emailed me the following:

There are proofs in the book Probability and Measure by Patrick
Billingsley. In the third edition, it's Example 31.1 on page 407.  The fact
that F is continuous and strictly increasing on [0, 1] is fairly easy to
see, based on the definition of the underlying random variable.  The fact
that F has derivative 0 is not as easy to see intuitively--the proof is
more of a hard analysis type proof.

The paper assumes that money is continuous and out lives are indefinitely long.
Ekhad, Georgiadis, Zeilberger have written a paper
How to Gamble if you're in a Hurry
that looks at these problems from (to quote their abstract) a purely discrete, finistic, and computational viewpoint.

Six Questions about unnatrual and natural mathematical objects

Today (Monday) I pose some questions. In my next post (Tuesday) I will post the answers
that I know (some I do not). Some questions are a matter of opinion
in terms of what you consider natural.

1. Is there a subset of [0,1] that is uncountable and has measure 0?
2. Is there such a set that is natural?
3. Is there a function that is continuous everywhere and differential nowhere?
4. Is there such a function that is natural?
5. Is there a function that has derivative 0 at almost every points of [0,1] even though it is strictly increasing?
6. Is there a natural such function?

I request that all comments be NON-anonymous.  (I'll tell you why when I post the answers I know on Tuesday.)

The Combinatorics of Batman

(I wrote this post about a year ago but waited until the new Batman
movie came out to post it. I haven't seen the movie yet so
there may more possibilities to add to this.)

There have been many versions of the BATMAN story:
comic books (and within that there are several versions),
many movies, and a TV series.
This may lead to a COMBINATORICS question you can ask your class.

So how many ways can the BATMAN story go?
This is NOT A QUIZ- all of the answers are correct
for some version of BATMAN.

1) As a child Bruce Wayne saw his parents gunned down.  What were they doing before this happened?

 a) Watching the movie Zorro.
 b) Watching the movie The Lone Ranger.
 c) )Watching an Opera.

2) Who shot Bruce Wayne's parents?

 a) Joe Chill- a low level mugger.
 b) Joe Chill- hired by the mob since Thomas Wayne (Bruce Wayne's father) had once foiled a crime. The orders were to leave the boy alive so it would look like a low level mugging.
 c) The gangster who would later become the Joker.

3) Who was the Joker before he became the Joker?

 a) A completely innocent chemist-turned-comedian.  He was a good man but a bad comedian. He was just going to do one theft to make ends meet. Things went wrong and he fell into a batch of chemicals and became The Joker.  He is now a bad man but a good comedian.
 b) A gangster who was sleeping with his bosses girlfriend.  The boss arranged for him to be killed ,but nstead the gangster falls into a batch of chemicals and becomes The Joker.
 c) Hey, its just makeup. But he has scars which may have come from his father, himself, or who knows?
 d) There are surely other versions I do not know.  One could probably write a bad PhD on this topic.

NOTE: I don't think the Jokers name is known in any of the versions.
(Contrast: The Riddler's name is Edward Nigma.)

4) Where is the Joker now?

 a) In Arkam Asylum.
 b) Dead.
 c) Gee, he really seemed to die but we just know he'll turn up again.

5) Who is Two-face?

 a) Harvey Dent, the DA, who was a good man. During a court trial a criminal throws  acid on his face. Now half of his face is scared. This drove him insane and he is now a criminal.
 b) Harvey Dent, the DA, who was a good man. Dent and his girlfriend Rachel Dawes are kidnapped.Batman and Commissioner Gordan save him but (1) Rachel dies, and (2) Dent has his face half disfigured.This drives him mad.
 c) There are about 5 other people who took on this role. One of them was named Harvey Kent.   No relation to Clark Kent

6) Who else lives in Wayne Manor?

 a) Robin, Alfred the Butler, and Aunt Hariet.
 b) Robin and Alfred the Butler.
 c) Just Alfred the Butler.

7) How well do Batman and Superman get along?

 a) Superman is never mentioned.
 b) They get along.
 c) They don't get along.
 d) They REALLY don't get along!


This leads to a combinatorics question and a Batman question.
COMBINATORICS: Assuming that all of these options are independent, how many versions of the
Batman Legend could there be? This should be easy.
BATMAN: Of all of these, how many have actually been realized?
This might take a Batman scholar to figure out.
And I haven't even talked about Robin (nor will I).

There are also variants of the COMBINATORICS question if you disallow certain
combinations. For example, If Aunt Hariet exists then Superman does not.

I'm sure there are more options I don't know about.
If you know any, comment!

CCC12- post 4 of 4- Misc Info.

CCC 12 post 4 of 4.
The business meeting and other observations.

1. Programming committee info:
   
   1. There were 119 submissions of which 18 were junk (more on that later). This is pretty large- Paris 2009 had 113 submissions. The junk papers were not so much papers that claim they proved P=NP or P\ne NP; they were papers where it is hard to know what they are claiming. (Hmmm- there are valid papers that, after you go through all the definitions, its not clear what they are claiming.)
      
   2. 34 papers accepted. Second highest to Paris having 37. (In both Paris and this year there was no Rump Session- that could be why, no time for one.)
      
   3. Andrew Drucker won Best Student Paper award for Limitations of Lower-Bound Methods for the
      wire complexity of Boolean Operators.
      
   4. See Prog Comm Chair Slides for more information.
      
2. There were roughly 60 people at the conference. Here is a list of all attendance figures up through 2008 (if you know of the attendance in the later years let me know and I will add them).
   
3. Steering committee:
   
   1. Johan Hastad and Manindra Agrawal have been on the committee but their term has expired so they are now off of it.
      
   2. The steering committee put Madhu Sudan on.
      
   3. An election by people at the meeting put Venkat Guruswami on.
      
   4. Peter Bro Miltersen is stepping down as chair (his term expired) and Dieter is the new chair. Peter will stay on one more year (I think).
      
4. Future Conferences:
   
   1. 2013: the conference will be in Palo alto, ca, co-located with STOC June 1-4 STOC, June 4-7 CCC. I WILL BE THERE!
      
   2. 2014: the conference will be in Vancouver. Local arrangements chair Valentine Kabanets. There were no competing bids (are there ever?) I WILL BE THERE!
      
   3. 2015: Depends on if there is an FCRC and if we join it. In any case I WILL BE THERE! The Steering committee will decide these things later.
      
5. This year there were electronic proceedings (I think for the second time.) That's good, and I'm glad we don't have paper, but I would prefer if the proceedings were available on a public website before the conference (SODA has done that) or at least after (if it IS available and I missed that- leave an intelligent comment about it). On the other hand this might not matter much since most of the papers are available on line anyway.
   
6. My posts on the content of the conference didn't get many comments, nor did I think they would. I hope they were useful to you. Forcing myself to do it was very useful to me, and for that I thank you, the readers. (For abstracts of ALL of the papers without my opinions, see here and press on abstracts (not on the left column).
   
7. On my Honeymoon in 1991 I went on a cruise and we were cut off from ALL news. When we got back the first thing I heard was The crisis is over, the tanks are leaving Moscow. This was somewhat alarming. They were referring to the 1991 Soviet Coup d'etat attempt. By contrast, in 2012 in Portugal, I heard about the Supreme Court Decision on Health Care within an hour of when it happened. I missed the earlier incorrect accounts. Is it a good or bad that its harder to get away from news coverage? Lance posted on a related topic a while back
   
8. I was gone for a total of 20 days and did not check email once. (i had a vacation problem on.) I came home to 474 emails of which 20 needed to be responded to. None of them were crucial.
   

CCC 2012- Post 3 of probably 4

Post 3 of n on CCC 2012. I still don't know what n is.
I summarize the third and fourth day of the conference.
(The fourth day was only a half-day).

Thursday June 27 Morning Session:

1. Matrix Lie Algebra Isomorphism by Grochow. This paper was called (and the link above still uses the old name) Lie Algebra conjugacy. Some Isom problems for Lie Algebras are equivalent to Graph Isomorphism. In general Harder Math does not mean Harder Computationally.
   
2. On Sunflowers and Matrix Multiplication by Alon, Shpilka, Umans. Erdos-Rado made a conjectures about sunflowers. Coppersmith and Winograd made a conjecture in combinatorics which would, if true, yield a better Matrix Mult Alg. This paper shows (roughly) that if the ER-conj is true then the CW-conj is false. Neither conj sounds that intuitive to me so I don't know what to make of this.
   
3. Algebras of minimal multiplicative complexity by Blaser and Chokaev. I couldn't find a link- if you know one email it to me.
   
4. Invited Talk Prospects for Geometric Complexity Theory by Peter Burgisser. So what are the prospects? Mixed. I was happy to hear that there are people working on this, but the talk was not that optimistic.
   

Thursday June 27 Afternoon Session:

1. A Strong Direct Product Theorem for Quantum Query Complexity by Lee and Roland. Direct Product Conjectures say (roughly) that if a problem takes T blahs to do then doing k of them given to you all at once takes kT blahs to do. There are many of these depending on your interest. This paper shows shows something stronger: If you want to computer just the XOR of the k instances it will take roughly kT quantum queries. (That is not quite right- there are a lot of details I left out.)
   
2. A Strong Parallel Repetition Theorem for Projection Games on Expanders by Raz and Rosen. A parallel repetition theorem usually says that if the prob of (say) winning one game is p, then the prob of winning n games is pⁿ (That can't be quite right but that's the idea). The real question is how fast does the prob go down. This paper adds to our knowledge on this.
   
3. Share Conversion and Private Information Retrieval by Beimel, Ishai, Kushilevitz. I couldn't find an online version. If you know of one email the link please. The paper claims to unify and simplify PIR protocols!
   
4. Nondeterministic Circuit Lower Bounds from Mildly Derandomizing Arthur-Merlin Game by Aydinlioglu and van Melkebeek. There have been theorems along the lines of Lower bounds imply Derand. There have also been some (and this is one of them) along the lines of Derand implies Lower Bounds. As the author points out, when you first hear the result you may think one of two things: (1) GOOD NEWS- to get lower bounds, all I have to do is Derandomize! (2) BAD NEWS- to derandomize I HAVE to prove lower bounds, which are hard to prove. He claims a third interpretation of his paper- if you can derandomize then you can do so in a nice way
   
5. Hitting Set Generators for Sparse Polynomials over any Finite Fields by Lu. I could not find a link- if you know one email it to me.
   
6. Pseudorandom Generators for Read-Once ACC0 by Gavinsky, Lovett, and Srinivasan. Or see the talk on video from IAS.
   

Friday June 28 Morning Session

1. Non-Malleable Extractors with Short Seeds and Applications to Privacy Amplification by Cohen, Raz, and Segev. An extractor (informally) takes two strings and outputs a string that looks random. Strong Extractors and non-malleable extractors are stronger notions. Non-malleable extractors produce strings that look random, even to an adversary who is trying to make trouble. Hence they are good for Privacy Amplification. This paper has unconditional constructions of them!
   
2. Better Condensers and new extractors from Paravaresh-Vardy Codes by Ta-Shma and Umans I lose track of condensers vs extractors vs expanders vs dispersers.
   
3. List Decoding Barnes-Wall Lattices by Grigorescu and Peikert List decoding is when, instead of finding what a string decodes to, you find a small set of candidates, one of which is correct. What is a Barnes-Wall lattice? The paper does a good job on this. I wonder if the original paper by Barnes and Wall does as good a job?
   
4. Space-efficient algorithms for reachability in surface-embedded graph by Stolee and Vinodchandran. One of the consequences of there results is log-space algorithms for some graph-reachability problems. Maybe L=NL!
   
5. Space Complexity in Polynomial Calculus by Filmus, Lauria, Nordstrom , Thapen, Zewi. Proof complexity. While lower bounds on Resolution are well understood, what about more powerful proof systems? This paper is a good start on that.
   
6. Combinatorial PCPs with Short Proofs by Or Meir.
   I wish the PCP theorem itself had a short proof. Perhaps you can prove that it does.
   

CCC 2012: Post 2 of n

CC 2012. I still don't know what n is.
I summarize the second day of the conference.

Wednesday June 27 Morning Session:

1. A Satisfiable Algorithm and Average Case Hardness for Formulas over Full binary Basis
   by Seto and Tamaki.
   
2. Approximating AC
   by Beame, Impagliazzo, Srinivasan.
   
3. DNF Sparsification and Faster Deterministic Counting by Goplan, Meka, Reingold.
   

All three of the above papers solve a hard problem in slightly-better-than the usual worst case. All three of them (I think) want to use this to obtain lower bounds. (Recall that this is ultimately how Ryan got his lower bound- via an algorithm. I want to see a SODA paper that gets an algorithm via a lower bound.) Something bothers me about this. If we are getting algorithms that beat (albeit, just barely) brute force search, perhaps we should be yelling MAYBE P = NP instead of LETS USE THIS TO SHOW THAT P ≠ NP. Just a thought.

1. Invited talk Communication Complexity and Information Cost: Foundation and New Directions by Toniann Pitassi.
   This was an excellent talk. I didn't realize it was an hour long invited survey talk instead of a 20 minute long normal talk.
   I kept waiting for
   (a) her results, and (b) the talk to end, even though I was enjoying it.
   ADDED LATER: Toni emailed me her slides.
   They are
   here
   

Wednesday June 27 Afternoon Session:

1. Gaussian Noise Sensitivity and Fourier Tails by Kindler and O'Donnel. They first define a new kind of sensitivity Rotation Sensitivity They then show that this type of sensitivity is subadditive. This is used to obtain simple (or at least simpler) proofs of the the Gaussian Isoperimetric inequality in certain cases and a lower bound on approx max-cut of .8787 (not the best known, but very close and a simpler proof).
   
2. Junto-Symmetric Functions, Hypergraph Isomorphism, and Crunching by Fischer, Garcia-Soriano, Matsliah. Two Boolean functions are Isomorphic if they are the same up to a relabelling of the variables. Given two Boolean functions, can we tell if they are isomorphic? One way is to obtain the truth table for both of them and then see if some permutation of the variables makes them the same. Even if all we care about is queries, this seems like a lot. Can we do this in less queries? That is, we are asking Property Testing questions. What if we restrict them. Then what? Read the paper to find out!
   
3. Complexity lower bounds through Balanced Graph Properties by Moshkovitz.
   This looks hard! They mention Tensors!
   
4. Limitations of Lower-Bound Methods for the Wire Complexity of Boolean Operators by Andrew Drucker. First there were pathetic lower bounds on wire complexity. Then after what seemed like half a century, there were (just recently) some slightly less pathetic lower bounds. Even so, that was promising. This paper shows NO, don't get too excited. The new technique will not get better results. Gee Andy Drucker, couldn't you have let us dream just a bit longer. The most depressing talk I have every seen. (It was a GREAT talk and a GREAT result, but still depressing.)
   
5. Limits on Alternation-Trading Proofs for Time-Space Lower Bounds Fortnow, Lipton, van Melkebeek, Viglas showed that any algorithm for SAT that uses log space must take at least time n^1.61 (the golden ratio). Since the golden ratio is a natural number (not literally) it was plausible that current techniques could not improve that. But Ryan Williams got n^c where c is 2cos(π/7) which is roughly 1.801. This can't possible be the best we can do since its just such a funny looking number. Ryan Williams wrote a program to try to fine tune the constants and do better but he couldn't do better. So he said NOBODY can do better!!!!. His advisor Manuel Blum believed him, but nobody else did. NOW he has shown, with help from Sam Buss, that NO, nobody can do better. I am impressed that he and Sam Buss were able to formalize what the technique was in a way that really does pin down ALL prior proofs. Had this paper been written first, there would only be one paper. This talk was NOT depressing since, being a new problem, I can believe that Ryan or Sam or someone can look at what the old techniques were and come up with some new ones and break the (I can't believe I am writing this) 2cos(π/7) barrier! And then what? A paper showing that that bound can't be improved, and then improve it. How far can this go? I've heard that really, really, we won't be able to show quadratic lower bounds. We'll see.
   
6. The Hardness of Being Private Common problem in crypto: Alice has x, Bob has y, they want to computer f(x,y) but they can't know anything about the other ones input accept what they can learn from their input and f(x,y). Are there any functions that people really want to compute like this? YES- the functions involved in a Vickrey Auction. In a Vickrey auction Bob and Alice bid x and y privately. The winner pays the LOSING bid. So if Alice bids 1000 and Bob bids 100, Alice gets to buy it for 100. Formally f(x,y) contains both WHO won and what they paid. The winner does know what the loser bid. But the loser should not know what the winner bid. This paper is about computing this function approximately-private in both the worst case and the average case. The most practical paper at the conference which isn't saying much. (Can the winner use Quantum Money?)
   

CCC12: Post 1 of n

(Post 1 of n on CCC 2012. I don't know how large n is yet.)

I will discuss the papers in the order they were presented.

June 26, 2012. Morning

1. Amplifying Circuit Lower Bounds Against Polynomial Time with Applications by Richard Lipton and Ryan Williams. Of course, what we mean by Applications may differ from what other people call applications. Here is one of the two main results:
   
   

   Let c,d ≥ 1 and e < 1 such that c < (1-e+d)/d. Either QBF is not solvable in time n^c or the Circuit Eval problem cannot be solved with circuits of size n^d and depth n^c.
   

   
   This is one of those odd results where its and OR of two things that we think are both true. But there are two unconditional lower bounds that can be derived from it:
   
   
   1. QBF does not have O(n^1.618)-time uniform circuits of depth n^o(1).
      
   2. For all ε > 0, QBF does not have O(n^{2- ε})-time uniform circuits of depth n^o(1).
      
   In his talk Ryan said that he needed the kind of complexity that only people like Dick Lipton still remember. (ADDED LATER: This is a misquote, see Ryan Williams comment below.)
2. Is the Valiant-Vazirani Isolation Lemma Improvable? By Holger Dell, Valentine Kabanets, Dieter van Melkebeek. Probably not. Oh well.
   
   
3. Parallel Approximation of min-max problems with application to classical and quantum zero-sum games by Gus Gutoski and Xiado Wu. In this paper they developed a better solution to a classical problem and then applied it to a quantum problem. I don't think this is common-- do you know of any other examples?
   
   
4. On the complexity of the Separable Hamiltonian Problem by Andre Chailoux and Or Sattah. (The first name is Or.). This paper looks hard!
   
   
5. Quantum Money with Classical Verification by Dimitry Gavinsky. Quantum Money is a funny topic in that it may be feasible in 100 years, but by then we will all have e-money.
   
   

Afternoon:

1. The Usefulness of Predicates by Per Austrin and Johan Hastad. There is an hour-long version of the talk done on a blackboard here.
   
   li> Reductions between Expansion Problems by Prasad Raghavendra, David Steurer, and Madhur Tulsiani. The authors claim that the Small Set Expansion Hypothesis (SSEH) is a natural hypothesis. (It has been discussed in earlier papers.) This paper shows that SSEH is equivalent to a subcase of UGC. The authors claim that SSEH is is the combinatorial heart of the UGC. WOW!
   
   
2. On Problems as Hard as CNFSAT by Marek Cygan, Holger Dell, Daniel Lokshantov, Daniel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabi, Magnus Wahlstrom, The Strong Exponential Time Hypothesis (SETH) states that for every ε > 0 there exists k such that k-SAT cannot be solved in time 2 ^{ε n} This paper assumes SETH and proves from it lower bounds on HITTING SET, SET SPLITTING, and NAE-SAT.
   
   
   
3. Testing List H-Homomorphisms A List H-Homomorphism is (informally) a homomorphism that satisfies given constraints. Given the constraints and given oracle access to an alleged hist H-Homomorphism, we want to determine if it IS one or is FAR FROM being one (if its not one but close we don't care.) As usual in property testing we are concerned with O(1) queries and sublinear queries. Both are characterized.
   
   
4. A Dichotomy for Real Weighted Holant Problems. by Sangxia Huang and Pinyan Lu. Recall that in Valiant's paper Accidental Algorithms he showed that for monotone planer 3-CNF formulas where each var appears twice (1) finding the number of solutions mod 2 is parity-P complete, but (2) finding the number of solutions mod 7 is in P. Since then there has been a wave of research trying to classify which counting problems are hard (likely complete somewhere) and which are on P. The paper by Huang and Lu is a big jump in this field.
   

North Carolina tries to legislate science

(I will post on CCC 2012 next week. I am still recovering from Jet Lag and going
through 472 emails that piled up on 2.5 weeks, of which 22 were relevent.)


You may have heard the story about the state of Indiana Pi bill:
In 1897 the state of Indiana wanted to legislate a value of pi.  Before reading the true story
I had heard the following:

1. They wanted to legislate pi=3 since the bible says that pi=3.  (The Bible does have a passage that seems to say pi=3, though that may not be the right interpretation.
   See here.)This version of the story puts them in a bad light.
2. They wanted to legislate pi=3 since this makes calculations easier.  They didn't really say pi=3, just that when measuring wheat in silos (or some such) everyone uses pi=3 to make everyones calcuations uniform and easy. (This was in the 1880's- they didn't have Wolframs Alpha).  This version of the story puts them in a good light.

Neither version is true. Look up the link to see what really happened.  Could this happen in America today?
On two issues it certainly could: Evolution and on Climate Change.

The North Carolina House has passed a law saying HOW to predict sea level rise rates.
The method they require predict less sea level rise then... anyone else. And only the
Division of Coastal management is allowed to put out such numbers.  So Independent scientists are not allowed to use... the scientific method.  (Not sure how they will enforce that.) See here for details.

Who wins, who loses?

1. Colbert gets a nice bit about it (which is how I learned about it): here
2. I get a blog out of it.
3. Scientists have to publish less, thus less trees get cut down, so the environment wins.
4. North Carolina looks more ridiculous than Indiana did back in 1897. But there are two differences-
   (1) North Carolina understood what the bill was saying and still passed it, Indiana did not.
   (2) North Carolina's bill has actual policy consequences, Indiana's pi-bill wouldn't have.
   

Fortunately the North Carolina Senate did not pass the bill so its not law. Yet.

Why is it called the Turing Award?

The ACM Turing Award represents the highest honor in the computing research community, the closest we have to a Nobel prize in computer science. In this centenary celebration of Alan Turing, it seems obvious that the award should be named after him.

But back in 1966 when Alan Perlis won the first Turing award, Turing's influence on the field was far less obvious. Turing's model had only a few years earlier found its way into computer science literature, still dominated by automata, parsing and circuits. In 1966, what is now the Foundations of Computer Science conference was just renamed Switching and Automata Theory from Switching Circuit Theory and Logical Design.

So why name the award after Turing back then? This question came up during one of the panel sessions at the ACM Turing Celebration where there were some vague guesses. I asked around during the breaks and nobody seemed to know. I even put the question to Turing biographer Andrew Hodges in Cambridge and he similarly didn't know.

The Knuth prize aside, most awards are named after people who have passed away. Back in 1966 there weren't very many dead computer scientists. Even among Turing's generation, Church, Post, Kleene, even Gödel were alive and kicking. Turing would have only been 54 had circumstances been different. John von Neumann died young from cancer in 1957 but wasn't thought of primarily as a computer scientist. There were also Charles Babbage and Ada Lovelace but I'm not sure they were in people's minds back then.

I'm guessing that Turing was just the default choice for the name of the award and the ACM just got extraordinarily lucky for picking the right person in spite of themselves.

Instance Compression

Some announcements: FOCS Accepts, ITCS Call and ToC Special Issue for Rajeev Motwani

I'd like to highlight one of the new FOCS papers "New Limits to Classical and Quantum Instance Compression" by MIT student Andrew Drucker which solves a problem that has dogged me for a few years. Ignore the "Quantum" in the title, that's not the interesting part.

Consider the OR-SAT problem, given m formulas each of size n, is at least one of them satisfiable. In STOC 2008, Rahul Santhanam and I showed that if there is a reduction from OR-SAT to any language L with the property that the reduction reduces to instances of size polynomial in n (independent of m) then the polynomial-time hierarchy collapses. The question arose from parameterized complexity though it also has some applications to cryptography and PCPs.

Our techniques failed to get a similar result for AND-SAT, where we want to know if all of the formulas are satisfiable. Drucker settled the question, showing that a compression of AND-SAT (reducing to instances of size polynomial in n) also gives a similar collapse of the hierarchy. What impressed me the most was the ingenuity Drucker uses in his proof.

Drucker derives the following lemma about probability distributions based on a strong version of Fano's inequality. Let A be a set of strings, D a distribution over A and f any function that maps A^m to {0,1}^m-2. If you pick a y from D, with high probability there is an index i, such that the distributions f(D^m) and f(D^m) with the ith location replaced by y are statistically close.

Drucker combines this lemma with a minimax argument and a result of Sahai and Vadhan that characterizes Statistical Zero-Knowledge as determining whether two distributions are different from the circuits that generate them.

Sometimes people solve your open questions with a simple argument that makes you hit your head for not thinking of it yourself. Other times you just sit back amazed at the solution knowing there was no hope for you to find it. Drucker's paper definitely falls in that second category.