Why go to conferences?

1. To find out about papers that might spark my interest and lead to the following:
   1. Papers. I saw Moser's paper in STOC 2009 and I already have a paper in preparation based on it. By contrast I saw Chandra-Furst-Lipton paper on Multiparty Communication Complexity at STOC83 and wrote a paper based on it in 2005 (its in MFCS-2005).
   2. Surveys. I saw a talk on PIR's at STOC 2000 which lead to my interest in them, my survey, and my website on them.
   3. Topics that I want to read up on. In CCC09 the paper on pointer-jumping pointed me to material I want to read up on.
   4. Ideas for Projects for students, ides for homeworks.
2. To find out random stuff in the hallways. At CCC2009 Scott Aaronson told me about a quantum proof that PP is closed under intersection.
3. To ask about stuff in the hallways. E.g., At CCC2009 I had some questions on derandomization that I asked around about.
4. During talks I don't understand I sometimes get other work done.
5. During talks where its too warm I get to take a nice nap.
6. I do not log on when I am at conferences. Really! I'm always curious how many emails I will get. This time I was gone for 12 days and came back to 289 emails. Why so few? Because lots of email is in resopnse to email that you send out, so the less you send out the less you get. Of the 289 about 20 were stll relevent. I did miss a chance to get $1,000,000,000 from some British Bank. Oh well.

Some say that you learn MORE from the hallways than the talks. And it is true that you can just read the talk later. But there is still something about seeing someone give a good inspiring talk that makes you want to follow up and give the paper a more careful read. The key is to maintain this feeling once you are home.

Time for Computer Science to Grow Up

The August CACM has my viewpoint article Time for Computer Science to Grow Up about the urgent need for conference reform.

Our conference system forces researchers to focus too heavily on quick, technical, and safe papers instead of considering broader and newer ideas. Meanwhile, we have devoted much of our time and money to conferences where we can present our research that we can rarely attend conferences and workshops to work and socialize with our colleagues.  

Computer science has grown to become a mature field where no major university can survive without a strong CS department. It is time for computer science to grow up and publish in a way that represents the major discipline it has become.

I argue that computer science uses conferences to play the role of reputation that journals play in other fields for reputation but then conferences no longer focus on the more important role of bringing out community together.

You can also download the pre-publication PDF.

Update 8/3: The editors of CACM have made the full text of the CACM article publicly accessible. 

8/7: Collection of related blog posts and other links. Feel free to send me others.

Patenting P=NP

The book Patent Failure by James Bessen and Michael J. Meurer notes that considerable more money is spent on litigation defense for technology patent infringement than on royalties collected and discusses various issues and potential solutions. 

From Chapter 9 (PDF) on Software Patents

Patent law assumes that once the words are mapped to a specific set of technologies, one can readily determine which technologies are equivalent and which are distinct. However, for software, this assumption is not always true. Computer algorithms may be equivalent, but computer scientists may not know that they are equivalent. In any cases, it has taken years for them to discover that different techniques are equivalent. For example, it has been shown that the “traveling salesman” problem, which is used for routing delivery trucks among other things, is more or less equivalent to the “map coloring” problem and a whole range of other problems. This means that an algorithm for solving the traveling salesman problem is also, if worded broadly enough, an algorithm for doing map coloring. In other cases, computer scientists suspect that algorithms are equivalent, but they are unable to prove the equivalence.

More than suspect, we can actually construct two equivalent algorithms where one cannot prove their equivalence in a given mathematical theory (assuming the consistency of that theory). In other words, it is theoretically impossible to determine whether one has software patent infringement in general. So if you are writing some code, it is impossible to determine whether you are infringing on an early patent. A theoretical justification for "Patent Failure".

What about the other part of this paragraph? Lipton might disagree, but we aren't in any danger of someone having a legitimate efficient algorithm for TSP or Coloring to patent. But suppose that someone managed to have such an algorithm and patented it as solving all NP-complete problems. For 17 years, only that person and his/her licensees could efficiently solve all sorts of problems while the rest of us toil away in exponential time. Which of Russell's worlds does this correspond to, Algorithmica Hell?

California Nightmare

I received a tiny raise for the next academic year but at least it is positive. Many of my academic colleagues have salary freezes or small cuts and many public institutions are having unpaid "furloughs" which for professors means the same amount of work for less pay. But nothing compares to how the best state university system in the country is being hit by the California budget crisis. The UC professors are taking salary cuts of 8% or more and are being told their retirement accounts are not fully funded, hiring is being curtailed. In the middle of a new analysis piece today in the New York Times on the California budget:

Classroom sizes are about to explode, and state universities are furloughing professors, cutting class offerings and reassessing, in the case of the University of California, whether the system can remain one of excellence for residents. 

Luca calls it The end of UC Berkeley as we know it and the many other strong campuses in the UC system will not fare well either.

I've seen vultures across disciplines lining up just getting ready to pounce on the best and brightest of the UC system. Just giving a UC faculty member what they previously had is a big advantage. Maybe the University of California can weather the storm, but we could see a drop from excellence. And that hurts all of us.

ECCC

One of the main topics of discussion at CCC last week centered around the problems with the Electronic Colloquium on Computational Complexity now 15 years old and showing its age.

In 1994, ECCC truly innovated the way we discover research. ECCC has a large board of editors that in theory quickly accept submissions that reach a minimum quality level in computational complexity. Once ECCC hit critical mass it became the must check place to see the latest results in complexity. I first heard about Omer Reingold's L=SL result from its ECCC post. 

Roughly here is how ECCC works: Once submitted, anyone on the ECCC scientific board can look at the paper and either accept or reject through a clunky email interface. Once accepted the paper appears nearly immediately. Papers by board members are automatically accepted. Papers not acted upon after two months are automatically rejected. A weekly email goes out to the board listing new and about-to-expire papers. 

Most papers are either accepted immediately if an editor is interested in it, or right before it expires. But often papers fall through the cracks, or the email doesn't get sent and papers time out. Recently many reasonable papers did time out which led to the discussions at the Complexity Conference. Also the site hasn't been updated much and is sometimes down or not working properly.

The main alternative to ECCC is the Computational Complexity section of the Computing Research Repository, now part of the ArXiv maintained by the Cornell University libraries and thus usually more more reliable than ECCC.

I subscribe to the RSS feeds for complexity papers on both ECCC and the CoRR. CoRR has a policy of accepting all papers in scope, including various P v NP "proofs", and most active complexity theorists self-select ECCC so only a few CoRR papers are interesting to me.

Scott Aaronson led a discussion at the CCC business meeting on suggestions on what to do with ECCC, not that the Complexity conference has any active role in ECCC. There were many thoughts including changing some of the policies by perhaps assigning papers to editors or have acceptance instead of rejection as a default, or have ECCC as just an overlay over CoRR to increase reliability. Maybe we just need to find a way to make sure more submissions get processed.

As the number of researchers and papers in complexity has increased, we have come to rely on systems like ECCC to let us learn the latest important results without having to wade through the chaff. When these systems fail us, even in little ways, we feel lost. But we can't fault the people who run ECCC, they have served us well for a decade and a half with little remuneration. But we need something or we will have to go back to the old ways of learning about good papers from conferences and journals.

Update 7/27: ECCC has relaunched with a new and improved website.

The Moon and a Legend

It is my first memory of a major event. Forty years ago today, my brother and a not-quite six-year old me were in my grandmother's apartment in New York watching a small TV and seeing Neil Armstrong stepping out on the moon. At the time I couldn't appreciate the fulfillment of JFK's 1960 challenge and the technological achievements that made it happen.

Years later I read Jules Verne's "From the Earth to the Moon" from the prospective of a dream already happened. I once read in a Sci-Fi magazine that hundreds of stories were written about a future moon landing, but none of them had it televised live.

I vaguely remember that day so long ago but in 1989 I watched the the CBS rebroadcast of those day's events with Walter Cronkite. I had watched Cronkite report from the Ford and Carter years through that strange day that combined the inauguration of Ronald Reagan and the release of the Iran hostages. In the fall of 1980 I was asked in an interview by an MIT alum whom I wanted as president, not limited to the current candidates, and I proposed Cronkite, generally regarded then as the most trusted man in America. Choosing Cronkite possibly cost me admission to MIT but I still believe him a better choice than Carter, Reagan or John Anderson. My daughters would later know Cronkite as Benjamin Franklin in the show Liberty Kids that Cronkite helped develop to educate youngster about early American history.

We lost Walter Cronkite on Friday, that great newsmen that I first remember seeing that moon landing day. And that's the way it was, July 20, 1969.

Complexity Wrap-Up

I twittered about some interesting papers, the business meeting and various other impressions. Since I don't have much time to write up this post I'll just list my conference related twitters here in chronological order.

• At CCC in Paris. Arrived half way through Ryan giving talk of our paper. Paris attracted impressive group of researchers.
• If a talk starts with a warning about simplifying, it won't be simple enough.
• Steve Cook: Not surprised P vs NP taking so long to solve.
• Manindra bring back the BH isomorphism conjecture to CCC. I had posted about it back in April.
• Bill during Manindra's talk. He claims the room is too warm.
  
  
  

• Prajakta Nimbhorkar gives last CCC talk of the day with log-space alg for planar graph iso. Nice application of L=SL.
• CCC banquet at Macéo easily beats EC banquet at Google but we got caught in a hail storm on way back to hotel.
• Scott talks quantum money with no intentional jokes or proofs.
• Live Tweeting the CCC business meeting. Promised 30 mins/35 if discussion. 100+ attendees with 36 students. USA 28, France 18, Israel 11
• Hastad PC report: 37 papers accepted out of 113 (32.7%). High because after STOC announcements. PC more fun in person maybe not crucial.
• CCC 2010 in Boston in Harvard, June 9-12 after STOC and same as EC all in Cambridge. Dieter van Melkebeek PC chair. Salil Vadhan local.
• CCC 2011 at FCRC (June 4-11) in San Jose. Again with STOC and EC as well as many others.
• Discussion on paper v. electronic proceedings. Straw vote: 28 electronic vs. 11 paper. Steering committee will decide.
• @geomblog replies: why do all theory confs have straw polls and let the steering committee decide ? let's be democractic or autocratic, not neither !
• Scott brings up problems with ECCC, server often down, papers get delayed or rejected. I'll post more next week.
• New steering committee chair: Peter Bro Miltersen. New members: Johan Hastad and Manindra Agrawal. Meeting over, lasted 50 minutes.

Our First Complexity Vidcast

Live from the 24th CCC conference in Paris, Bill, Lance and special guests talk about our firsts in our first vidcast. I apologize for the audio quality.

Complexity Day 1

I arrived at the Institut Henri Poincaré in time to catch the last half of Ryan Williams giving a talk on our paper with Rahul Santhanam. I missed the first set of talks including Mark Braverman's Poly-logarithmic independence fools AC0 circuits. To no one's surprise Braverman won the best paper award for this work. The Ronald V. Book Prize for Best Student Paper went to Akitoshi Kawamura for his paper Lipschitz Continuous Ordinary Differential Equations are Polynomial-Space Complete.

A good turn out, about a hundred for the conference including many notables such as Steve Cook, Manindra Agrawal and of course Bill Gasarch. Eric Allender is here so we are now both at 24 and counting for perfect attendance at complexity conferences. Great to see many friends, colleagues and former students including Sophie Laplante, the main local organizer. Something about Paris draws people to the conference.

With my jet lag I realized I would just snooze through any afternoon talk so I had a pleasant time talking research in the Jardins de Luxembourg (near the conference site). Now I'm off to bed and hopefully well rested for day 2.

A Complexity Proposal

Tonight I fly off to Paris for the 24th IEEE Conference on Computational Complexity, the namesake conference of the blog. If the plane arrives on time I should just make it for my paper's presentation (which will be given by Ryan Williams in any case).

I (along with Eric Allender) will have attended all 24 conferences. I have had several papers in the conference, served on the PC including once as chair and a six-year stint as conference chair. But my most important Complexity Conference event had little to do with any of the above. 

Twenty years ago, I attended the 1989 Structures Conference (as it was called back then) at the University of Oregon between grad school and my first job at the University of Chicago. The outing consisted of a rafting trip and I landed in a raft with Toda and Razborov. Glad we didn't capsize.

But the moment came when I found a florist in Eugene. I sent a dozen red roses to my then girlfriend Marcy's work place back in Boston with a card that said "Will you marry me?"

We've been married nearly nineteen years.

ICALP

Ryan O'Donnell, reporting from last week's ICALP in Rhodes.

ICALP has a pretty large number of papers, divided into three tracks. Track A is roughly algorithms and complexity ("Amero-theory"?). Track B is roughly Logic, Semantics, and PL Theory ("Euro-theory"?). Track C, formerly cryptography, is now Foundations of Networked Computation; this seems to appeal most to the Track A people, and sometimes there were mixed A/C tracks.

Three highlights for me were:

• Amin Coja-Oghlan's outstanding paper A better algorithm for random k-SAT, which quite deservedly won Best Paper in Track A. I was very sorry to miss the talk, the earliest in the schedule, as my hydrofoil from Bodrum did not get in till just after it finished. In this paper, Amin gives an O(n^3/2)-time algorithm for random k-SAT which finds satisfying assignments for clause densities up to (ln k / k) 2^k. Much work has gone into this problem, and the previous best algorithm only worked up to density (1.8 / k) 2^k. Although the threshold for satisfiability is (ln 2) 2^k, Amin's work may in fact be "tight": his FOCS 2008 result with Achlioptas gives significant theoretical evidence that (ln k / k) 2^k may be the "algorithmic barrier".
• The special session devoted to Papadimitriou. This proved to be a birthday Festschrift, although it was not advertised as such. Laci Lovasz gave it away (repeatedly) in his invited talk, and the rumour floating around afterwards was that Papadimitriou is indeed "nearly 60" (cf. this). The invited talks here were excellent: Karp, on algorithmic problems from biology; Lovasz, on graph limits; Nisan, on auctions; Roughgarden, on improved methods for analyzing the price of anarchy; and Yannakakis, on complexity-theoretic aspects of Papadimitriou's research. Normally these events are good for getting amusing anecdotes about the fest-ed person, but most stories were quite heartfelt ones about the influence of Papadimitriou on the speaker's work. Possibly the most interesting thing was learning that one of Papadimitriou's most notable contributions to TCS was convincing fellow PhD-student Yannakakis to switch from EE-style information theory to TCS.
• Philip Bille and Mikkel Thorup's paper in which they made the first running-time improvement in 17 years on the problem of regular expression matching; they got it down from nm/log(n) to nm/log^3/2(n) (modulo log log factors). Naturally, Philip name-checked SLOGN in his very nice talk.

We also saw the Greek and Turkish national youth basketball teams at the conference lunches; I believe they skipped all the talks, though.

More from Noam Nisan.

Pictures: view of hotel grounds; view of hotel beach; view of basketball players at the conference lunch.

Will the real Adam Smith please stand up, please stand up, please stand up

I thought about doing a post on ADVICE FOR GOING TO CCC 2009, but I recalled that my advice from a 2007 blog posting will suffice..

CONGRADS to Adam Smith and Sean Hallgren for being among the 100 people who won the Presidential Early Career Awards for Scientists and Engineers award (PECASE).

Adam Smith (the same one as above) recently began a blog focusing on CRYPTO issues. here it is

To quote Adam Smith:

It was started around the same time as Jon Katz's blog, also with the goal of providing the crypto community a place for online discussions. Here is my explanation of why it's needed: here

If you google Adam Smith you get around 4,700,000 hits. Most are, of course, to the ecomomist or things associated to him (e.g., Adam Smith Think Tank) However, the FIRST Google Page does include our Adam Smith.

TARK vs. EC

The 12th TARK and 10th EC conferences both are being held at Stanford this week, both look at questions relating economics and computer science and shared yesterday's Keynote by Susan Athey. But that's where the similarities end.

TARK is held every other year. Next time in 2011 likely in Holland. Krzysztof Apt is the sole PC chair.

EC is held every year. In 2010 at Harvard, June 7-11 overlapping STOC and Complexity, both also in Cambridge. A mini-FCRC a year before all three are in San Jose for the real FCRC. Moshe Tennenholtz and Chris Dellarocas are PC chairs. Yiling Chen and Jenn Wortman are doing local arrangements. David Parkes is general chair.

TARK drew about 50 attendees, EC is drawing about 175.

TARK talks were held in a small classroom in the old GSB building. EC talks are being held in a large ballroom in the Alumni Center. The atmosphere encouraged questions after TARK talks and discouraged them at EC.

TARK has no industry support and few industry participants. EC gets money from several companies and has many people here from Google, Yahoo, Microsoft and others. Yahoo bought us lunch yesterday at EC, tonight's banquet is at the Googleplex.

EC has a new general chair every year. TARK has had one general chair: Joe Halpern.

TARK had traditional printed proceedings which are now available on the ACM DL though not an ACM sponsored conference. EC, sponsored by ACM SIGecom, has CD only proceedings not yet available on the DL.

TARK focuses on models, most papers give logical models of knowledge-related concepts and discuss theorems but rarely give proofs. EC has many new models and mechanisms too but more of an emphasis on proofs in the theoretical papers.

EC has a continual identity crisis on broadness and applicability. TARK did change its name a few years ago (from Theoretical Aspects of Reasoning about Knowledge to Theoretical Aspects of Rationality and Knowledge) but is quite happy with what it is.

Speedup for Natrual Problems (Guest Post)

Speedup for Natural Problems (Guest post by Hunter Monroe.)

Blum proved speedup for an artificially constructed problem; this paper (arXiv link), (ECCC link) presents two results on speedup for natural problems (not in the worst case). First, it identifies a condition apparently only slightly stronger than P ≠ NP which implies that accepting any coNP-complete language has an infinitely-often (i.o.) superpolynomial speedup, and furthermore NP≠coNP. We define terms and then state the condition:

BHP={<N,x,1^t >| there is at least one accepting path of nondeterministic TM N on input x with t or fewer steps};

HP={<N,x>| there is at least one accepting path of NTM N on input x (with no bound on the number of steps)};

T_M is the function that maps a string y to how many steps M(y) takes.

The condition states:

(*) For any deterministic Turing machine M accepting coBHP, there exists (N',x')∈coHP such that the function f(t)=T_M(N',x',1^t) is not bounded by any polynomial.

(*) implies that any coNP-complete language has i.o. speedup: Let M be a TM that decides BHP. By (*) there is an N',x' such that, for all t, (N',x',1^t) is NOT in BHP. Hence a TM that first checks if the input is of the form (N',x',1^t), outputs NO if it is, and runs M if its not, has a superpolynomial advantage over M on infinitely many inputs. (*) shows that NP ≠ coNP since Schnorr showed there is an optimal M accepting any NP-complete language.

Second, the paper shows that coBHP unconditionally has a weaker type of i.o. speedup. The intuition is that recognizing nonhalting N',x' is useful for an M accepting coBHP M can accept without reading the 1^t part of the input. However, no M can avoid reading the full input for all N',x' as M could accept coHP which is not computably enumerable.

In a similar spirit, the following conjectures suggest a nice linkage between the theories of complexity and computability: If there exists a poly time M accepting a coNP-complete language (for instance coBHP), then M can be modified to accept a language that is not c.e. (for instance coHP). If M can factor integers in polynomial time, then M can be modified to accept the set of true arithmetic statements.

Raking Up the Frequent Flyer Miles

This week I'm at Stanford for the TARK and EC conferences co-located for the first time. Next week in Paris for Complexity. Also a shout out to ICALP in Rhodes also being held this week including a special day "to honor the mature period of Christos Papadimitriou contribution to CS". Happy maturity Christos!

First up, TARK, Theoretical Aspects of Rationality and Knowledge. TARK draws from a broad range from theoretical computer science, AI, economics, linguistics, psychology and philosophy who try to model questions like what does it mean to know something, to be aware of it, to be rational about one's decisions and how do these models affect the outcome of various interactions.

Much of my recent research looks at finding the right ways to bring efficient computation (from a complexity theorists view) to economic models. My TARK papers, Program Equilibria and Discounted Computation Time and A Computational Theory of Awareness and Decision Making (with Nikhil Devanur) are two attempts in this direction.

This will be my first time tweeting conferences in case you want to follow at least some of what's going on.

Pairs of Celebrities died/born the same day

Farrah Fawcett and Michael Jackson died the same day (June 25, 2009).

1. Who is the most famous pair of people that died the same day? While its hard to measure fame objectively, there are two candidates that come to mind. (1) If you give a bonus for being in very different fields then the answer could be Orville Wright and Gandhi (Jan 30, 1948). (2) If you have an American bias then perhaps John Adams and Thomas Jefferson (July 4, 1826). Possible Bonus for July 4 being the day. (James Monroe also died on July 4, though in 1831. What is the probability that three of the US presidens died the same day? Prob=1 since they did.)
2. If you are famous and want people to notice your death there here are some tips:
   1. DO NOT die the same day as a someone more famous. Example: Farrah Fawcett overshadowed by Michael Jackson.
   2. DO NOT die close to the day someone more famous dies. Examples: (1) Ed McMahon died the day before Michael Jackson. (2) Mother Theresa died a few days after Princess Di (It is likely that Mother Theresa wanted to not have a big deal made of her death, so perhaps this was a win for her.)
   3. DO NOT die the last week of the year. James Brown and Gerald Ford both died the last week in 2006. By that time all the lists of famous people who died in 2006 were already made. So James Brown and Gerald Ford never made those lists.
3. Who were the most famous pair of people that were born the same day? While its hard to measure fame objectively a good candidate pair is Abe Lincoln and Charles Darwin (Feb 12, 1809). Others of interest (from this website): George W. Bush and Sylvester Stallone (July 6, 1946), (One is a pretend war hero, the other starred in the ROCKY movies.) Sigmund Freud and Robert Peary (May 6, 1856), Winston Churchill and Lucy Maud Montgomery (Nov 30, 1874), (I didn't know who Montgomery was. Either fame is fleeting or I am not up on my writers of books for young girls-- she wrote Anne of Green Gables.) Ariel Sharon and Fats Domino (Feb 26, 1928).

FOCS Papers

For this pre-Independence Day post Bill suggested I write about the math knowledge of our founding fathers or how "P=NP" will declare itself independent of ZFC. Luckily FOCS announced the accepted papers so I can talk about that instead. First the lists.

• Accepted Papers
• Accepted Papers with Abstracts
• Accepted Papers with available PDF links (Shiva Kintali)
• Algorithmic Game Theory (Noam Nisan)
• Geometry and Topology (Jeff Erickson)
• Streaming (Muthu Muthukrishnan)

PC Chair Dan Spielman discusses the review process though he doesn't talk about the usefulness of the 2-page addendum or the criteria used to choose the papers, which seems to have tended again towards the technical.

Here are a few of the many interesting looking papers that caught my eye.

• David Doty. Randomized Self-Assembly for Exact Shapes
• You just don't see many STOC/FOCS papers on self-assembly or from Iowa State.
• Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco Servedio and Emanuele Viola. Bounded Independence Fools Halfspaces
• I like results that just sound neat and can be fully stated in the title.
• Zeev Dvir, Swastik Kopparty, Shubhangi Saraf and Madhu Sudan. Extensions to the Method of Multiplicities, with applications to Kakeya sets and Mergers
• And better randomness extractors too.
• Or Meir. Combinatorial PCPs with efficient verifiers
• Sounds interesting and the only FOCS paper that cites one of my papers in the abstract.
• Rahul Jain, Sarvagya Upadhyay and John Watrous. Two-message quantum interactive proofs are in PSPACE
• QIP is known to sit in between PSPACE and EXP and it's an interesting open question which way it goes. This paper makes some progress in resolving that.
• Neeraj Kayal and Shubhangi Saraf. Blackbox Polynomial Identity Testing for Depth 3 Circuit
• Makes progress on deterministic polynomial identity testing, one of the few remaining probabilistic algorithms to derandomize.
• Ravindran Kannan. A new probability inequality using typical moments and concentration results
• Looks like something we will all need to add to our toolboxes. The accepted papers list dropped the word "inequality" which made the paper seem unreal.
• Alexander Sherstov. The Intersection of Two Halfspaces Has High Threshold Degree
• An exciting result in its own right. The Complexity class analogue goes the other way: Beigel, Reingold and Spielman showed the class PP is closed under intersections.

Learn PCPs at DIMACS

Prahladh Harsha asked me to post the following announcement on the blog. I don't usually post announcements but this seems like an excellent opportunity to learn about approximation and PCPs from the masters. You can find many more links and short announcements on my Twitter Feed where you would also learn the FOCS accepted papers list is out. My thoughts on the FOCS papers tomorrow.

  

---

DIMACS Tutorial on Limits of Approximation Algorithms: PCPs and Unique Games

When: July 20 - 21, 2009 
Where: DIMACS Center, CoRE Building, Rutgers University

I would like to advertise an upcoming tutorial on "Limits of Approximation Algorithms: PCPs and Unique Games", organized under the auspices of the DIMACS Special Focus on Hardness of Approximation. This tutorial is geared towards graduate students, postdocs and others who are theoretically oriented, but not necessarily familiar with the material.  The aim of the tutorial is to give participants a general overview of approximability, introduce them to important results in inapproximability, including some of the recent developments in the world of probabilistically checkable proofs (PCPs) and the unique games conjecture. 

The list of speakers includes: Matthew Andrews (Alcatel-Lucent Bell Laboratories), Sanjeev Arora (Princeton University), Moses Charikar (Princeton University), Prahladh Harsha (University of Texas, Austin), Subhash Khot (New York University) and Lisa Zhang (Alcatel-Lucent Bell Laboratories).

Registration is free and limited travel support is available for non-local participants (with preference to students and postdocs). More info on the workshop web site.

2pi-day? Other holiday possibilities!

May 28 should be Pi-day instead of March 14 since pi should be what we now call 2*pi (6.28...) since 2*pi comes up in more formulas than pi. (When I blogged about this here one of the commenter's suggested 2*pi*i.)

So what-should-be-pi-day was last Sunday. To honor this day I asked people what day or concept they would want to make a holiday. Here is what I got.

1. Multicultural day. OR give every ethnic group a holiday. This may lead to the 4-day work week.
2. Mid-autumn day to give us a break.
3. Pi-Day (March 14)
4. Mole Day (Oct 23)
5. Talk like a pirate day (Sept 19.) Did pirates really talk that way in the past? now?
6. Election day. That way more people will vote.
7. The day Louis Brandeis got appointed to the supreme court. He was the first Jewish member of the court. This could be a way to celebrate the decline of anti-semitism in America.
8. Peace Day. Could celebrate the end of some war. But there is always the next war. Oh well.
9. The day women got the vote. (Aug 26, 1920). To quote Hail to the Chiefs, with regard to the election of Warren G. Harding as president in 1920: {\it It was the first election women voted in. They needed more practice}.
10. The day the civil rights act passing. Actually there were many civil rights bills passed, so you'd have to pick which one to celebrate. Or celebrate all of them and get a 4-day work week.
11. Groundhog day. (Feb 2). The movie movie Groundhog day higher Google rank than the day does.
12. Chocolate day.
13. Moon day. They have Earth Day so why not Moon Day?
14. Children's day. We have Mothers and Fathers day, so why not Children's day?
15. St. Patrick's day. Or the day after to get rid of your hangover.
16. Teacher's day. Would teachers get this day off?
17. Weird Al's birthday (10/23). Since its the same as Mole Day we can combine them to get Weird Mole Day.

Lets say they made your choice a holiday. And then there was a movement to make it, instead of the actual day, the 2nd Monday of that month it was in. (or something like that). Would you mind? On the one hand, your holiday is getting made into just a day off. On the other hand, you get a 3-day weekend!

Veterans day would have been the 2nd Monday in November except that some veterans protested. Or did they? Maybe it was groups that claim to represent them. I wonder if veterans prefer 3-day weekends or prefer having their holiday be on the day WW I ended. What is more important: Efficiency or meaning?

Some days would be hard to move. July 4, Cinco do Mayo and Pi-day are rather tied to the day they are celebrated. Even so, the government (and others) gives July 3 off if July 4 is on a Saturday.

The NSF Annual Report

The NSF has been getting very strict about having PIs (primary investigators) fill out an annual report listing publications and activities related to their grants. The report is due 90 days before the anniversary of the start of the grant, so if you have a grant that started in the fall you are probably getting notices reminding you that your report is now overdue. 

There are few academic tasks more painful than filling out annual grant reports but best to just grit your teeth and do it or the NSF could cut off your money. Would you rather the alternative, not having to do a report because you don't have a grant?

Annual reports are used more for gathering information than for evaluation so you don't need to worry about the style as much as you might for a grant proposal. 

There is one confusing part of the reporting system on NSF Fastlane: There are separate sections for conferences and publications. Most of our conferences don't show up under conferences so best to just list your other conference papers as proceedings in the publications section, probably under "Books or Other One Time Publications".

Fastlane reporting is a one-size fits all system so it is not well designed for the way computer science handles conferences. But we computer scientists always know how to implement the Kludge.

Update 7/10: NSF Theory Program Director Richard Beigel makes available a Sample Report (Dan Spielman) and Sample Findings (Mihir Bellare).

Re-request/when to include a known proof in a paper?

In my post of June 24 I requested some help on a sum (among other things). In particular, we had a summation result that we were using in a paper and we wanted to know if it was new or not. We got three comments relevant to it

1. Method of differences due to Pascal
2. discrete calculus analog of the fact that the nth degree Taylor expansion of a polynomial is the polynomials.
3. The first lemma is a direct consequence of the method of finite differences; it says that the nth forward difference of a polynomial of degree n-1 is identically zero. The inner summation in the second identity is basically computing the coefficients of the Newton Form of the polynomial, although you seem to be using a slightly different basis. Nevertheless, these results are quite standard.

This raises a request and some question.

REQUEST:

Authors of those comments (and others who know stuff)--- please email me more exact references. I found some things on Google but it would be good to know what to read and what is a good source to reference. Preferable online.

QUESTION: In a paper if you are using a result that is known how much detail should you put in?

1. Clearly put in that it is known and provide a references. I would not want to frustrate my readers with This is easily derived from the method of differences. without providing a reference. In this day and age an online reference if you can mange it.
2. If the result is not quite written down anywhere but your readers could easily derive it using known techniques, then you do not need to supply a proof. But this is not as clear a statement as it sounds- it depends on how you define readers, easily, known, and technique.
3. If the result is known but you have a cute proof of it which seems new (hard to tell) then what do you do?
4. If the proof is short then I am more inclined to include it. If its an e-journal than length matters less. (This topic has been raised in a different form before---if Conferences proceedings are CD's then why have a page limit?)
5. If there are no online references then I am more inclined to include a proof.
6. My only real point here is that its a QUESTION- what is the cutoff for what is worth including? There is no one answer.

Tales of Two Theories

I finished reading two very different books about two theories in physics, The Age of Entanglement: When Quantum Physics Was Reborn by Louisa Gilder and “Gina Says,” Adventures in the Blogsphere String War "selected and edited" by Gil Kalai. While vastly different in style they both feature scientists happy to talk about and defend their own points of view in controversy theories but rarely willing to reconsider those views.

Louisa Gilder's book takes a detailed look at the early years of quantum theory using an interesting technique: Creating imagined conversations between the leading scientists of the time based on their writings. These conversations make the development of the theory an exciting story when greats like Einstein, Bohr and Heisenberg struggle over the right ways to handle the seemingly paradoxical nature of quantum effects. As Bohr gets quoted in the book during a Copenhagen trolley ride with Einstein and Sommerfeld, "I suppose that during a stage in science where everything is in ferment, it cannot be expected that everybody has the same view about everything". 

Gilder's book gives a detailed year by year development through the 1935 Einstein-Poldolsky-Rosen paper but then moves much quicker through David Bohm's theories from his exile in Brazil (due to McCarthyism), the Bell inequalities and related experiments, and the development of quantum cryptography and computing. The computer science aspects are particularily short with only a brief mention of "the reclusive Peter Shor and the witty Luv Grover". She doesn't ignore the political backdrops of the times but thankfully she doesn't overly emphasize it either.

You won't learn more than the broad strokes of quantum physics with this book but you get to relive the development of a discipline as brilliant minds argue the right way to model a new phenomenon. 

Gil Kalai's book is a quick read from the viewpoint of "Gina" a non-expert who comments on the blogs of mostly string theory skeptics. It certainly was a fun read but I finished not sure of the purpose of the book. Seemed to focus more on the role of bloggers and commentors than the philosophical questions of developing a complicated theory that seemingly can't be tested. Where's Occam's Razor when you need it? Kalai had some interesting digressions to areas like Godel's incompleteness theorem and Bayesian learning but those just added to the disjointness of the book. Kalai's book does have the big advantage of being a free download.

So I'd recommend Gilder's book if you want a detailed almost novel-like development of a field and Kalai's book if you want a quick fun free read on how some skeptics defend their skepticism. 

Both books remind us that theoretical research must go beyond just doing the math, in finding the simplest models that best capture the concepts we study. Lessons that hold as much in computer science as they do in physics.

Complexity Report from DNA 15

Guest post by Aaron Sterling

I attended DNA 15, the 15th International Meeting on DNA Computing and Molecular Programming, held June 8-11, 2009, at the University of Arkansas. The co-chairs of the organizing committee were Rusell Deaton and Jin-Woo Kim, who I thought did a great job. The research presented, and the backgrounds of the attendees, were diverse from experimental nanochemistry to theoretical computer science. I'll highlight a few elements of the program that had TCS and complexity flavor.

Jim Aspnes and Kenichi Morita gave TCS plenary talks. Aspnes introduced the audience to the computational theory of “population protocols” (see here for a survey) a theory of computation over a large network of agents who each possess very limited computational power. This theory can model ad hoc wireless networks, and (potentially) smart molecules interacting in solution. Morita surveyed results on reversible cellular automata and presented animations that showed the inner workings of several such devices. A reversible computation device is one in which each noninitial configuration has exactly one preceding configuration. Many models of natural computing are reversible models.

NP-completeness of the Direct Energy Barrier Problem Without Pseudoknots, due to Manuch et al., was presented by Anne Condon. The Energy Barrier Problem is decision problem about molecular folding. Given a structure in some initial configuration, does there exist a pathway through subsequent configurations to a final configuration, such that the step from each configuration to the next requires at most energy k, for some fixed k. The paper reduces a simplified version of the Energy Barrier Problem to 3-Partition, a known NP-complete problem.

Several papers discussed the theory and practice of building DNA-based circuits. I would like to focus on Signal Propagation and Propagation Delays in Molecular Circuits by Seelig and Soloveichik, as it puts forth the thesis that circuit depth is not the correct measure of time complexity for chemical circuits (in contrast to electronic circuits, or classical circuit complexity). They present a theoretical model to capture something that has been observed in the lab: when there are just a few molecules of a certain species in solution, the reactions that depend on them will be slow, because the species will interact with low probability, since contact with it is so rare. As a result, stepping through a circuit is not a linear process. Approach to completion of a circuit becomes increasingly slow the deeper the circuit is, because the later layers require the output of all the earlier layers. One possible fix for this is to catalyze the reactions in question, so the reactions occur quickly even if there is only a small amount of species present. The drawback to this is leakage: if a chemical species is not fully consumed at an earlier stage, its presence can build exponentially at later stages, leading to the circuit providing incorrect answers. All in all, an intriguing model that raises a lot of questions.

DNA 16 will take place in Hong Kong, and DNA 17 will be organized by Erik Winfree at CalTech. I'm looking forward to them both!

Two requets: A sum and a reference

I have two requests from my readers. Both are essentially help tracking things down.

First: We (Bill Gasarch, Clyde Kruskal, Justin Kruskal) have in a paper of ours a summation that we proved. Is it new? Here is the summation: (It uses a sum that I previously inquired about here and got useful information, including that it was originally proved by Euler.)

Let p(x) &isin Z[x] be a polynomial of degree n with constant term 0.

p(s) - &sum_k=1ⁿ(s+k-1 choose k)&sum_i=0^k-1(k-1 choose i)(-1)ⁱ (p(s+i+1) - p(s+i)) = 0

Our proof is here.

(Side Request: How do you do a choose-sign in html?)

Second: I am, as always, tracking down lower bounds on the VDW numbers. I need the article An application of the Lovasz Local Lemma, a new lower bound for the Van der Warden numbers by Zoltan Szabo, Random Structures and Algorithms, 1990. Electronic preferred, but will take what you got. SO, if someone has it please email me article or pointer or whatnot. (Pointer might not work if your library has access to this journal, since ours does not have it in electronic or hardcopy.)

Annoucing YATB (Yet Another Theory Blog)

Jon Katz has a blog Random Bits

We've put it on our blogroll.

What will it be about? To quote Jon himself:

The blog will cover random topics, but especially crypto. It was started because there are currently no (active) crypto blogs and I hope this will become, to paraphrase Lance, a meeting place for the crypto community where we would have some discussions, sometimes quite heated, over the issues of concern to our community

Some advice for Jon and any new blogger:

1. In your technical posts try to have the first paragraph so that if someone doesn't want to read the rest of it they still get something out of.
2. Spellcheck!
3. Will you post every day but almost never make comments on the blog (Bill and Lance model)? Will you post once a week but make lots of comments on your own blog (Scott Aaronson model)? Will you post class notes? (Luca does that. Scott sometimes.) Will you be controversial or stear clear of controversy? (I'll let you guess who does what, it varies at times.) Do you have guest posts? What is your policy on anonymous commenters? There are no right and wrong answers; however, you should have answers.
4. If you have an idea for a blog try to write it up as soon as possible while you still are enthused about it. If it doesn't work then put it aside--- it may combine well with another idea later.
5. Keep a backlog of blogs that are timless.
6. Don't get upset at lack of comments, stupid comments, comments that misinterpret your post, or off-topic comments. You will get all of these.
7. If you try to make each blog perfect you will have a hard time getting anything out.
8. Technical posts are harder to write then others and may get tiring (though Lipton's doing just fine with them). Pace yourself on those.

SIGACT

I'm honored to have been elected as the new chair of SIGACT, the ACM Special Interest Group on Algorithms and Computation Theory. The rest of the executive committee (as of July 1) will be Cynthia Dwork, Anna Lysyanskaya, Michael Mitzenmacher, Mike Saks and Richard Ladner as previous chair. I look forward to working with all of them. 

A fond goodbye and thanks to those leaving the committee: Richard Cole, Joan Feigenbaum, Éva Tardos and Hal Gabow. We will have a difficult act to follow.

SIGACT has a small number of formal responsibilities: Running the STOC conference, co-sponsoring and cooperating with several other conferences, handling prizes and awards, publishing SIGACT News and acting as the theory liaison to the ACM mostly in dealing with publications. But SIGACT plays a more important role, as the organization that addresses and protects the interests and needs of the theoretical computer science community, the whole community, not just those who come to our conferences regularly. 

So please let us know what issues you think are important to the theoretical computer science and how SIGACT can help address these needs. Feel free to contact me or any other member of the executive committee. SIGACT exists to serve you.

The Story of the Blog

Google is celebrating the 10th anniversary of Blogger by asking its users to write the stories of their blogs. I'll bite as this blog has become such a a large part of my life and I like to think a part for the theoretical computer science community and beyond.

In 2002 I read a Newsweek article on then new phenomenon on blogging. I decided to give it a try. I wanted to blog on a specific topic and so I started blogging on the topic I know best. On August 22, 2002 I started "My Computational Complexity Web Log", the first major blog devoted to theoretical computer science. The blog gained in readership after a sardonic mention in Jason Kottke's popular blog. All of a sudden I had thousands of readers interested in computational complexity. In that first year I wrote mostly technical posts. I did a set of posts entitled Foundations of Complexity giving an introduction to the field and a series Complexity Class of the Week where I would review results and questions about a specific complexity class. Later on I wrote a monthly series of my Favorite Theorems in the field.

But the technical posts take considerable effort to write and proofread so I started writing more opinion and academic-oriented posts. The blog became a meeting place for the theoretical computer science community where we would have some discussions, sometimes quite heated, over the issues of concern to our community. Most of the young people I would meet at conferences knew me more for the blog than for my research. For a while a Google search on my name led to the blog before it led to me.

Changes happen. I shortened the name of the blog and experimented with podcasting. In March of 2007 after a post on turtles, I realized I was just going through the motions and decided to retire from blogging. Bill Gasarch took over the blog and kept it going. But I had too much I wanted to say and rejoined the blog in January 2008. Since then Bill and I have co-written this blog trying to get out a post every working day.

Now we have many excellent blogs in theoretical computer science ranging from very technical to very amusing. We strive to be the blog of record, the weblog people turn to to learn about the issues and happenings in the community. Weblogs have become the places that brings our ever growing academic community together in a way our conferences no longer can. I'm glad this blog is able to play its part in that effort.

Nondeterministic Parallelism

A reader asks

Can we define a class NNC such that NC ⊆ RNC ⊆ NNC. Is NNC known by some other name? It is clear that NNC ⊆ NP, but the reverse is not obvious.

NC is Nick's Class (named after Nick Pippenger) and can be characterized by either a PRAM model with polynomial processors and poly-logarithmic time or by polylogarithmic-depth polynomial-sized circuits¹.

So what about nondeterministic NC or NNC? NNC is just the same as NP.

First let's consider randomized NC, RNC. Here each processors each had a limited number of random bits but they can share their random bits through memory, a technique used for example to find maximal matchings.

NNC, particularly if you want to have RNC ⊆ NNC, needs to have a similar definition. Suppose all the processors could act nondeterministically. Here is an NNC algorithm for 3SAT with n variables and m clauses.

1. Processor i (1 ≤ i ≤ n) guesses the ith bit of a potential satisfying assignment and writes it in memory location i.
2. Processor j (1 ≤ j ≤ m) checks whether this assignment makes clause j true.
3. If all processors in the second round accept than accept (which takes another log m rounds).

Since 3SAT is NP-complete under reductions computable easily in parallel, we have NNC = NP. The reverse direction is a simple simulation.

A simple observation but a very important point: Every nondeterministic computation has an easy nondeterministic parallelization. 

Alternately you can define RNC or NNC with an additional random or nondeterministic input (in either the circuit or parallel model) and get the same classes. 

RL and NL on the other hand handle randomness and nondeterministic differently. Here you have one processor using polynomial time and logarithmic space. While the processor can use a polynomial number of random/nondeterministic bits, the processor cannot remember them all. So RL and NL are considerably weaker, in particular both are contained in P.

Noam Nisan wrote paper On Read-once vs. Multiple Access to Randomness in Logspace that explores these definitions of randomness in more depth.

---

1. I'm ignoring uniformity issues in this post.

Do laypeople know what Prisoner's Dilemma is? Now they might

(Our blog has ALWAYS been green.)

This is a continuation of the topic in this blog entry.

In the June 17, 2009 issue of The New Republic, in an article called Plan of Attack, the term Prisoner's Dilemma was used and not explained. Does the public know what the term means? Are they supposed to learn what it means from context? I am asking these questions non-rhetorically. Here is the context and exact quote.

Context: Bob Woodward is going to do a book about the Obama White house. If you work in the White house, do you cooperate with him or not?

He (Bob Woodward) flashes a glimpse of what he knows, shaded in a largely negative light, with the hint of more to come, setting up a series of prisoner's dilemmas in which each prospective source faces a choice: Do you cooperate and elaborate in return for (you hope) learning more and earning a better portrayal-- for your boss and yourself? Or do you call his bluff by walking away in the hope that your reticence will make the final product less authoritative and therefore less damaging? If no one talks, there is no book. But if someone talks--- then everyone-- always talks.

1. Do people who are not involved with game theory on some level know what The Prisoner's Dilemma is? Some do, but I wonder how many.
2. Does it matter? Are writers freer to use terms the audience might not know since the writers know the readers can look it up easily. This is even more true if you are reading online and the writer provides links. However, in that case you may get distracted and not finish the article.
3. Will writers do this more often and will this educate the public?
4. I have also seen this on TV. If a show mentions some fact I didn't know, I might look it up. Sometimes its fictional, but sometimes its true. And sometimes you may get a skewed view of the issue: I once saw the 25th amendment used three times in one month of TV (West Wing, 24, and a repeat of 24) and always in a dramatic fashion. I looked it up and now know it; however, in real life, it has never been used in a dramatic fashion.
5. The article right after the Woodward one was about what to do with the detainees at Gitmo. The name of the article: Prisoner's Dilemma

Cond. Cvg Sequences in R^d AND real applications!

We present some PURE math that was APPLIED in a real way. I am more surprised by these things than I should be.

Recall that a summation &sum_i=0^&infin a_i Conditionally Cvgs if it cvg but &sum_i=0^&infin |a_i| does not cvg.

Recall the following theorem.

Cond Cvg Thm: Let &sum_i=0^&infin a_i be a cond. cvg sum. Let A &isin R. Then there exists a way to rearrange the summation such that it cvg to A.

What happens if instead of reals you have points in R^d? For this we need Steinitz's Lemma which we state below. For a nice proof and discussions of variants of it see Imre Barany's paper On the power of linear dependencies (Also available here in case it goes away from his website.)

Steinitz's Lemma Let d be a natural number, B be the unit ball in R^d, and V be a finite subset of B such that &sum_{v&isin V} v = 0. Then there is an ordering v₁, v₂, ..., v_n of the elements of V such that

v₁ &isin dB

v₁+v₂ &isin dB

v₁+v₂+v₃ &isin dB

etc.

v₁+...+v_n &isin dB

End of Statement of Steinitz's Lemma

This can be used to show the following:

d-dim version of Cond Cvg Theorem If a₁, a₂, a₃,... &isin R^d and &sum_i=0^&infin a_i conditionally cvgs then the set of points that this sum can be rearranged to converge to is an affine subspace of R^d.

This looks like a question and answer in pure math. But wait! there are applications of this sort of thing! And I don't mean applications to other parts of pure math! I don't even mean applications to complexity theory! There are applications to algorithms! Here are four references from Imre Barany's article. Only one was online (alas). If you find links to the other articles then send me link AND article and I will modify this post.

1. A vector sum theorem and its application to improving flow shop guarantees. By I. Barany. Math. Oper. Res. Volume 6, 1981, 445-452. downloadhere or if it goes away or does not work then here
2. Bibliography: Series of vectors and Riemann sums. By I. Halperin and T. Ando. Sapporo, Japan, 1989
3. On approximate solutions of a scheduling problem. by S.V. Sevastyanov. Metody Diskr. Analiza Volume 32, 1978, 66-75. (In Russian).
4. On some geometric methods in scheduling theory: a surey, Discrete Applied Math, Volume 55, 1994, 59-82.

Conference Proceedings should have final version in Journal! (Guest Post)

(Guest Post by Samir Khuller.)

I have noticed that even though in the 80's and 90's a large number of FOCS, STOC, and SODA papers eventually appeared in journals (David Johnson even kindly edited a book that gave pointers to the journal versions of FOCS and STOC papers), the percentage appears to have declined significantly (I have not done a systematic analysis, but when I look for papers I often find that no journal version appeared.)

Most conference papers (even the top conferences) are not reviewed extremely carefully for correctness. The PC has a limited amount of time, and a large volume of papers to review.

What is the reason for this decline?

Are we so desperate to publish papers that we do not want to do a thorough job writing up the proofs after "staking our claim"?

Its very frustrating when when you are reading a paper and details are omitted or missing. Worse still, sometimes claims are made with no proof, or even proofs that are incorrect. Are we not concerned about correctness of results any more? The reviewing process may not be perfect, but at least its one way to have the work scrutinized carefully.

Now that proceedings are on CD's do we still need a strict 10 page limit on the conference version? Is this limit there to simply encourage people to submit to journals? If so, I am not sure its working.

What can we as a community do to ensure that results get properly reviewed and published in full in journals after they are published at a conference?

Math on Kindle DX

My Kindle DX arrived yesterday. I loved my first Kindle which I used for reading books and the New York Times. But the Kindle couldn't handle mathematical papers. The DX has native PDF support. So how well does it do for our community's papers?

I tested the DX on PDF documents, postscript won't work. I chose papers from STOC, CACM, Springer and Elsevier journals, ECCC, my own PDFlatex generated papers and the open access Theory of Computing and the ACM Transactions on Computation Theory journals. 

The math looks great. The resolution (1200x824) looks fine, the formulas and diagrams show up as good as on regular paper. No color but that's not an issue for most of our papers.

The papers take a couple of seconds to load and usually (but not always) quick to change pages. I had the worst experience on a scanned paper (Valiant's permanent paper) which took a very long time to load and change pages and looks as lousy on the Kindle as it does printed.

There are two ways to view a paper: portrait and landscape. Let me discuss each separately.

Portrait: A page of the PDF is filled into the screen area. The screen is about 3/4 the height and 2/3 the width of the US standard 8.5x11 paper so some papers are slightly squished, particularly multicolumn STOC and CACM papers have this problem. The ToC and ToCT papers looked the best. The text, formulas and diagrams are also shrunk but still quit readable as long as I am using my reading glasses (yes I've gotten old).

Landscape: You get to landscape mode simply by turning the screen (or manually with the Aa button). The landscape mode keeps the original aspect ratio but you only see part of the page. The width of screen in landscape mode is about the same as the width of regular paper so the type size is about right. You can move through the rest of the page with the Next Page/Prev Page buttons but otherwise no scrolling. The 5-way button seems to have no effect on PDF documents.

Extras: You can do a basic text search within a PDF document but not between documents or in scanned documents. Unlike normal Kindle documents you can't change the type size, add notes, highlight text, convert text to speech or move to a word to get its definition. You can bookmark a page but otherwise the only way to navigate is via the next page/prev page buttons. No way to click on links within a PDF file.

You can move documents quickly through the USB cable. The Kindle has tons of memory and can hold lots of PDF files. You can move whole directories but the Kindle flattens them out listing every file (by file name) separately on the main home page. You can also email papers at $0.15/MB and most of our papers are well under a megabyte.

Many of the issues above could be fixed by software updates but no guarantees Amazon will do so. Also it shouldn't be hard to produce DX-friendly PDF documents, with the right aspect ratio and large font size. If the DX gets popular than publishers might start producing Kindle-friendly versions of their papers. The old Chicken v. Egg problem.

The Great Oracle Debate of 1993

In the STOC talk Russell Impagliazzo gave on his paper An Axiomatic Approach to Algebrization, Russell alluded to a controversy with his earlier still unpublished paper with Sanjeev Arora and Umesh Vazirani. Bill asked me if I knew about the controversy and I said I'd answer in a blog post.

The Arora-Impagliazzo-Vazirani paper was submitted to the 1993 Complexity conference (then called Structure in Complexity Theory) which was part of the first FCRC conference in San Diego. The AIV paper tried to explain why the then recent interactive proof results (IP=PSPACE, MIP=NEXP, PCP theorem) don't relativize. I somehow got hold of a copy of the paper and thought AIV completely missed the mark, focusing on local checkability instead of the algebraic transformation of formulas. Also the AIV paper seemed down on relativization, a common theme, and I thought a response necessary. So I quickly wrote up my own response paper The Role of Relativization in Complexity Theory. 

The PC didn't accept the AIV paper but they set up a debate between Russell and myself at the conference. Russell and I spent several wonderful hours before the debate overlooking the ocean and talking about our models.¹ We did find some common ground during the day which unfortunately led to a debate without much fireworks.

After the debate, Juris Hartmanis asked me to submit my paper to the Complexity Column he ran for the Bulletin of the EATCS and so it appeared there. AIV is still going through revisions and Russell said during the STOC talk (that's last week's STOC) that they still planned to publish it. 

To continue the debate: Russell gave his STOC talk explaining that limiting the types of relativization would lead to "worlds" closer to our own. But you get a trade-off: While a few more techniques relativize in this model, it becomes much harder to create oracles, most of the oracles we have in the traditional model don't go through for the restricted model. Since the 1993 debate there have been many oracles in the traditional model published. Local checkability, algebraic methods and every other technique has failed to crack any of those oracles after they've been published. So why restrict our worlds when we still get so much more mileage in the traditional model?

---

1. The beach resort where we had the first FCRC was so much nicer than the inland location of the last two San Diego FCRCs

Can we make this problem FUN?

Consider the following cute problem:

Alice, Bob, and Carol each have a number between 0 and 1,000,000,000,000 on their forehead. Everyone can see the numbers that are NOT on their own forehead. Call the three numbers x,y,z. They wish to determine if x+y+z is divisible by 1,000,000,000,000. There is an easy solution: Alice can just say Bob, your number is .... This would take 13 digits of communication. Can they do better?

Chandra, Furst, and Lipton showed that if instead of 1,000,000,000,000 was replaced by 2ⁿ, and if n is large, then do this in roughly \sqrt n bits. They were more interested in the k-party lower bound of &omega(1) since this leads to lower bounds on branching programs. (NOTE: They studied a variant of the the problem above, but everything they did applies hear also.) See their paper or my writeup for JUST the upper bound or my writeup of the upper and lower boundand its application to branching programs for more information.

The problem stated above with people having numbers on their foreheads sounds like it could be a fun problem for the layperson. BUT: The problem with this problem for the layperson is two fold: (1) The original problem involves 3-free sets. While our community might say Wow, an application of stuff coming out of van der Waerden's theorem (or at least I would say that), the layperson would not think of it or care. (2) Frankly, I don't know if 13 digits numbers are big enough for the asymptotics to kick in and give a better answer than 13.

SO- here is my challenge: Is there a solution to this problem (or perhaps one with larger numbers) where the solution is non-trivial--- that is, you do not communicate all of the numbers, but is also FUN! FUN means you can tell it to your non-mathematical-nephew, or perhaps your 10-years-old-great-niece-who-likes-math. Quite okay if its far worse than \sqrt(n).

Fifty Years of Mathmagic Land

I finally succumbed to Twitter. I plan to use my twitter account to supplement the blog with bite-sized items. I may sometimes expand those tweets into longer blog postings like today.

My 11-year old daughter talked about using straight lines and angles to improve her mini-golf game. That reminded me of the billiard ball scene in a Donald Duck math movie I saw many times over during my grade school years. Off to YouTube where we watched Donald in Mathmagic Land which coincidentally turns fifty years old this month.

Holds up pretty well after fifty years though the modern music, art, architecture and technology aren't so modern any more. Catch the Turing machine (reel-to-reel computer) near the end.

It was this movie and a Time-Life book on mathematics (which had a really cool chapter on probability) that got me excited by the fun of math which, of course, helped shape my future academic career.

The movie has a scene where Donald tries to open some locked doors that the narrator says represents knowledge yet to be discovered. Cool to think that I have now witnessed many of those door opened, some with my own hands.

Are there any longstanding conjectures that ended up being false?

Mathematics and TCS are full of conjectures. Some are proven true, some are still not known. Most that have been resolved have been true:

1. Fermat's last theorem should have been called a conjecture. It was proven. I don't think any serious mathematician ever thought it was false.
2. Baudet's' Conjecture is now VDW's Theorem.
3. The Modell Conjecture is now Faltings Theorem.
4. I could list more, so could you.

Are there any conjectures that ended up being false? Yes, though none listed below is really a clean story.

1. Hilbert's 10th problem asked for an algorithm that would, given a poly in many variables over Z, determine if it has a Diophantine solution. We now know this cannot be done. While this may have surprised Hilbert, he was aware of this sort of thing happening. See the preface to his problems, or better see his entire address here.
2. Same with the Ind of CH from ZFC. Hilbert thought it was true. More to the point, Hilbert certainly thought it had an answer. Now we know that it does not. Or at least that its ind of ZFC.
3. NL=coNL surprised alot of people.
4. In 1986 most people thought that P\ne BPP (hard to believe!). One notable exception was Mike Sipser. Now most people think that P=BPP. Of course, not resolved yet.

I have not been able to find a dramatic example of a long standing conjecture that a large community believed ending up being false. Do you know of any?

I doubt that any of the Clay problems will end up being false. I doubt that any serious mathematician thinks that any will end up being false. That might be self-correcting: if someone did we would label him (perhaps unfairly) non-serious.

Rajeev Motwani

Tragic news from Jennifer Widom via Paul Beame.

I am deeply saddened to inform the database community that Prof. Rajeev Motwani passed away Thursday night in a swimming pool accident at his home. He will be remembered by the large number of professional colleagues, faculty colleagues, and students whose education and lives have been enriched tremendously by his.

A tremendous loss for the theory community as well. Rajeev Motwani had an incredible publication record particularly in algorithms, wrote major textbooks, served our community well and was a true bridge between theory and practice. He received the Gödel prize in 2001 for the PCP paper. We lost one of the great ones.

Update: Suresh, one of Rajeev's former students, writes a very nice personal remembrance. 

Not about STOC/Funny Stuff people have send me

The other bloggers have done such a great job covering STOC that I won't add anything, except to say that I agree most of whats been said: Moser's talk and result were GREAT, the Innovations in Computer Science Conference has to be better defined, and Lance has both lost weight AND gotten a haircut

People often send me funny short math things and say this would be great for your blog!. Here is a collection of things people send me over the last year. XKCD comics:

1. RANDOM NUMBER
2. OPEN SOURCE
3. HAMILTONIAN
4. LABYRINTH PUZZLE
5. ONLINE COMMUNITIES
6. SECURITY
7. DUTY CALLS

A song about Mandelbrot Sets, although one of the comments on it claims that the song is actually about Julia sets. The person who send it was amused that there is a curse word in it. But he's young and easily amused--- he's 32.

A recursive music video.

A Failure of Social Networks?

One of Northwestern's professors made quite a splash a month ago with his group's predictions on the spread of the Swine Flu (now called H1N1). Dirk Brockmann claimed a worst-case scenario of 1700 flu cases by the end of May. Another group in Indiana made similar predictions. The research got picked up on a front page New York Times article. Brockmann's group used data from Where's George, a site that tracks movement of dollar bills, to understand interactions that would lead to the spreading of disease.

So how did these groups do? Not even in the right ballpark, off by two orders of magnitude. As a follow-up article in Tuesday's Science Times the CDC estimated there were well over 100,000 cases by the end of last month. What went wrong? In short Brockmann claims faulty initial data. Nevertheless I always worry that bad predictions from scientists make it harder to have the public trust us when we really need them to.

Might this be an instance where prediction markets greatly out-performed the experts? In short, no. There were relevant markets but two big problems: 

• No one thought to create a market for the number of flu cases over a couple of thousand. 
• Prediction markets require a verifiable outcome so they were based on CDC confirmed cases. But after the flu turned out not to be that dangerous, the CDC stopped confirming most cases and there were less than 7500 confirmed cases by the end of May.

Thoughts from STOC

I haven't been to STOC/FOCS since FCRC in San Diego two years ago. Since then I dropped thirty pounds and got a haircut last week. Amazing how many people thought something looked different about me and asked about the haircut.

I missed the Valiant celebration but it brought a large number of senior theorists who don't often attend STOC/FOCS. I enjoyed seeing and talking with them. Still, despite a relatively easy to reach location (say compared with last year's Victoria), STOC only attracted about 260 attendees, nearly half students. We just don't get draw many non-local attendees who don't have papers in the conference. Though David Johnson told me he's attended every STOC since the early 70's.

I don't attend many talks at STOC, I prefer to hang in the hallways chatting with people, about research, politics, gossip and baseball. The talks I did attend usually had about five or so good minutes of motivation and results followed by technical details for experts in that particular area. That's probably the right way to give those talks but I was rarely one of those experts.

And then I see a talk as amazing as Moser's and I realize: This is why I love theory.

A Kolmogorov Complexity Proof of the Lovász Local Lemma

Robin Moser gave one of the best STOC talks ever in his award-winning paper A Constructive Proof of the Lovász Local Lemma. Not only an amazing result but also an incredibly inventive simple proof that he came up with while preparing the talk.

Here is a sketch of Moser's proof written as a Kolmogorov complexity argument. This is not the full Lovász Local Lemma but captures the main principle.

Theorem: Suppose we have a k-CNF formula φ with n variables and m clauses and each clause shares a variable with at most r other clauses. Then there is a constant d such that if r < 2^k-d then φ is satisfiable. Moreover we can find that assignment in time polynomial in m and n.

Here's the algorithm:
Solve(φ)
Pick a random assignment of φ
While there is an unsatisfiable clause C
         Fix(C)
Fix(C)
Replace the variables of C with new random values
While there is clause D that shares a variable with C that is not satisfied
        Fix(D)

Assume Fix(C) always terminates. Every clause that was satisfied before we called Fix(C) will still remain satisfied and C will also now be satisfied. So Solve makes at most m calls to Fix.

We need to show all the Fix(C) terminate. Suppose the algorithm makes s Fix calls including all the recursive ones. We will show s is bounded and thus the algorithm terminates.

Fix a Kolmogorov random string x of length n+sk (random relative to φ, k, s, r, m and n) and assume the algorithm uses the first n bits as the initial assignment and k bits each to replace the variables in each Fix call.
If we know which clause is being fixed, we know the clause is violated so we know all the bits of this clause and thus we learn k bits of x. We then replace those bits with another part of x.

So we can describe x by the list of clauses we fix plus the remaining n bits of the final assignment. We can describe the C such that Fix(C) is called by Solve by m log m bits and the remaining fixed clauses by log r + O(1) bits because either it is one of r clauses that intersects the previous clause or we indicate the end of a recursive call (keeping track of the recursion stack).

So we must have m log m + s(log r+O(1))+n ≥ n+sk or s(k-log r-O(1)) ≤ m log m.

To show s is bounded, we need k-log r-O(1) to be positive or r<2^k-d for some constant d.

Note this in fact shows s = O(m log m) so the algorithm runs in polynomial time. We choose the x randomly which with high probability will be Kolmogorovly random. QED

In the talk, Moser gives the bound r<2 ^k-3 and in follow-up work with Gábor Tardos shows r<2 ^k/e (e = 2.71…) which is the best that comes out of the original Lovász Local Lemma.

STOC

Howdy from Bethesda. Lots of theory bloggers here and I don't want to spend too much time on the computer so today just some announcements from an uncontroversial business meeting. 

Sampath Kannan gave a long talk about the NSF. In short, they have money, you should apply.

Salil Vadhan gave us a preview of the research nuggets from the Visioning Workshop held right before STOC 2008.

Shafi Goldwasser gave the Athena Lecture. The Gödel Prize was awarded.

Mitzenmacher gave the PC report: 77 papers accepted out of 321 submissions. Best Paper award jointly to:

• Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem, Chris Peikert (SRI International)
• A Constructive Proof of the Lovász Local Lemma, Robin A. Moser (ETH Zürich)

Moser also won the Danny Lewin best student paper award.

Mitzenmacher mentioned a number of PC issues that he plans to discuss on his blog. Definitely worth following.

Aravind Srinivasan discussed local arrangements (which have been excellent). 255 attendees including 116 students. He suggested STOC could be held at universities in the future to keep costs down.

Richard Ladner gave the SIGACT report. About 1300 profession members and 160 student memberships down from 240 in 2004. To get the numbers up, student registrants at SIGACT sponsored conferences will get an automatic one-year membership.

You can still vote for me (or Madhu) in the SIGACT Elections until June 15.

Get your calendars ready:

• FOCS 2009 will be in Atlanta October 24-27.
• STOC 2010 will be in Cambridge, Massachusetts June 6-8. Complexity will also be held in Cambridge immediately afterwards.
• STOC 2011 will be part of FCRC June 4-11 which will also include Complexity, COLT, SPAA and EC.
• Silivio Micali announced a new conference, Innovations in Computer Science to be held January 4-7, 2010 in Beijing.
• Russell Impagliazzo publicly announced the Barriers Workshop, August 25-29, 2009.