 Operational Sentience: We can easily converse with computers.
 The AI Chain Reaction: A computer that boot straps itself to a better self. Repeat.
Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch
Friday, July 31, 2009
The Singularity
Thursday, July 30, 2009
Are you a firstblocker or a lastblocker?
Be the first on your block to have NAME OF PRODUCT!It might be more honest to say
Be the first on your block to have NAME OF PRODUCT! Be our beta testers! A year from now you can have a better version at a cheaper price!What are the PROS and CONS of being a a firstblocker (candidate for wordoftheyear) as opposed to being a lastblocker (another candidate)?
 Advantages of being a lastblocker: you get a cheaper better version of the product. Or in some cases you realize that you don't want the product (e.g., Betamax, which were actually called that.)
 Disadvantage of being a lastblocker: when do you finally buy the product? When I was a kid the first Polaroid Cameras came out. The innovation then was that they gave you the picture right away. It was in black and white, poor quality, and you had to shake it while it was developing. At the time I said I will wait until this is in Color. Once that happened I said I will wait until it is better quality. Once that happened I said I will wait until you don't have to shake it.. Once that happened I said I will wait until the price goes down. Once that happened I said I will wait until you can preview your shots before printing them out. Once that happened I said I will wait until you can do all of this on the computer. This has happened. Now I am waiting for the price to go down. Or the next innovation. Meanwhile, I have never owned a camera.
 Advantage of being a firstblocker: you get to tell your friends about it and advice them. Lance has done that with Kindle, KindleDX, and the ultimate wallet. This is what the advertisement had in mind.
 Advantage of being a firstblocker: There are times when the first model has some feature (or bug according to the manufacturer) that you want. One example: An older VCR can tape off ondemand, newer ones and DVD recorders have a problem with this.
 Some of this applies to seeing movies their first weekend you get to tell your friends about it, but you may see some really bad movies. I'm a lastlastblocker: I tape movies off TV, watch the the first 15 minutes, and then decide if I want to finish it. (Ebert's Rule for Comedies: If you don't laugh in the first 15 minutes, you're not going to laugh in the last hour and 45 minutes.) If not I might go to Wikipedia to see how it ends.
Wednesday, July 29, 2009
QIP = PSPACE
 QIP can be simulated by 3round quantum interactive proofs.
 3round quantum interactive proofs can be simulated in exponential time.
In an upcoming FOCS paper, Jain, Upadhyay and Watrous show that tworound quantum interactive proof systems can be simulated in PSPACE. QIP in PSPACE uses techniques from all these papers.
Still open: The power of multiprover quantum interactive proofs where the provers share prior entanglement but otherwise can't communicate. Classically we have MIP=NEXP (nondeterministic exponential time). Does QMIP=MIP? Neither containment is known.
The proof that QIP is in PSPACE is in three distinct parts:
 Reduce a given QIP protocol P to an equivalent semidefinite programming problem S. In other words, find a semidefinite programming problem S where the Verifier's optimal acceptance probability is the optimal solution to S.
 Describe a highlevel decision procedure for P based on computing a solution to S that is close to optimal.
 Show that this numerical solution can be approximated to sufficient accuracy in PSPACE.
The proof relies in a crucial way on an earlier result of Marriott and Watrous (building on Kitaev and Watrous) that any QIP protocol can be simulated by a much simpler QMAM (quantum MerlinArthurMerlin) protocol. In this protocol, which is a threeround quantum version of a standard ArthurMerlin protocol, Merlin is an allpowerful quantum process and Arthur is a polynomialsize quantum circuit. It runs as follows:
 Merlin gives Arthur some quantum state r.
 Arthur flips a *single* coin and sends the result to Merlin.
 Merlin gives Arther another quantum state s in a different register.
 Arthur performs one of two possible measurements, based on the value of his previous coin flip. He accepts if the result of the measurement is 1 and rejects otherwise.
The proof actually starts with this equivalent QMAM protocol and turns it into a semidefinite programming problem in Part 1, above.
Every semidefinite program has a primal and a dual formulation. The primal is a maximization problem, and the dual is a minimization problem. In Part 2, the authors give an iterative process that finds better and better feasible solutions to both formulations simultaneously. Each solution approaches the optimal one, the primal from below and the dual from above, giving better and better bounds in both directions. The optimal value is Arthur's maximum acceptance probability over all possible behaviors of Merlin. They show that after a certain bounded number of iterations, the solutions are close enough to the optimal to correctly determine the outcome of the QMAM protocol.
Finally, in Part 3, the authors argue that the iterative process in Part 2 can be implemented efficiently to reasonable accuracy in parallel, using polynomial space. This follows from the fact that basic matrix operations (especially exponentiation and spectral decomposition) can be done in the class NC of polynomialsize logdepth circuits. Here the circuits work on exponentialsize data (in the number of qubits), yet everything can still be executed using polynomial space.
One last comment: The proof improves upon and uses some techniques from a recent result of Jain, Upadhyay, and Watrous that twomessage quantum interactive proofs are in PSPACE (to appear in FOCS 2009). The same basic technique was also used in a paper by Jain and Watrous in the most recent CCC conference, showing that another quantum class is contained in PSPACE.
Tuesday, July 28, 2009
Whither to Post, Tweet or Facebook?
 The new and improved ECCC
 Just told that for recent stimulusbased grants: If it is determined that you are not spending quickly enough the funds can be revoked.
 Scan (11MB PDF) of shirt design from old Complexity conference (then Structures). Don't ask about the dog.
 Netflix contest over but no winner for a few weeks. Exciting conclusion (via:@ipeirotis)
 RT @statpumpkin: Bellkor's Pragmatic Chaos first place in Netflix Prize  contacted by Netflix and in validation phase. (thx @piggymurph)
 Tron returns and NYT worries about computers taking over. Coincidence?
 Iran has stopped issuing visas for US citizens including academics. The world got a little smaller.
 Rare CS article in Science Times: Destroying data with cryptography.
 Faded lines on Beamer slides only draw attention to themselves (e.g. pg 2 of this)
 Congrats to Rafael Pass and Nothwestern's Nicole Immorlica new Microsoft Research Faculty Fellows.
 Comic Sans: Yes it looks handwritten. Cute the first 100 times I've seen it. Now go use a grown up font. (See also bancomicsans.com)
 Awesome EC Keynote by Michael Moritz on innovation. "Companies whither when scientists and engineers move further away from the helm"
 Moritz: Many best and brightest mathematicians and scientists waste their lives working for private equity houses.
 And from June 3rd: Taught Moser's proof in my intro theory course today! (A comment worthy to be my first twitter post).
 Academics
 Friends and Family
 People I haven't seen in 25 years.
Monday, July 27, 2009
Why go to conferences?

To find out about papers that might spark my interest and
lead to the following:
 Papers. I saw Moser's paper in STOC 2009 and I already have a paper in preparation based on it. By contrast I saw ChandraFurstLipton paper on Multiparty Communication Complexity at STOC83 and wrote a paper based on it in 2005 (its in MFCS2005).
 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.
 Topics that I want to read up on. In CCC09 the paper on pointerjumping pointed me to material I want to read up on.
 Ideas for Projects for students, ides for homeworks.
 To find out random stuff in the hallways. At CCC2009 Scott Aaronson told me about a quantum proof that PP is closed under intersection.
 To ask about stuff in the hallways. E.g., At CCC2009 I had some questions on derandomization that I asked around about.
 During talks I don't understand I sometimes get other work done.
 During talks where its too warm I get to take a nice nap.
 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.
Friday, July 24, 2009
Time for Computer Science to Grow Up
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.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.
Thursday, July 23, 2009
Patenting P=NP
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.
Wednesday, July 22, 2009
California Nightmare
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.
Tuesday, July 21, 2009
ECCC
Monday, July 20, 2009
The Moon and a Legend
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 SciFi 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.
Friday, July 17, 2009
Complexity WrapUp
 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 logspace 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 912 after STOC and same as EC all in Cambridge. Dieter van Melkebeek PC chair. Salil Vadhan local.
 CCC 2011 at FCRC (June 411) 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.
Thursday, July 16, 2009
Our First Complexity Vidcast
Wednesday, July 15, 2009
Complexity Day 1
Tuesday, July 14, 2009
A Complexity Proposal
Monday, July 13, 2009
ICALP
ICALP has a pretty large number of papers, divided into three tracks. Track A is roughly algorithms and complexity ("Amerotheory"?). Track B is roughly Logic, Semantics, and PL Theory ("Eurotheory"?). 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 CojaOghlan's outstanding paper A better algorithm for random kSAT, 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 kSAT 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 complexitytheoretic aspects of Papadimitriou's research. Normally these events are good for getting amusing anecdotes about the fested 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 PhDstudent Yannakakis to switch from EEstyle information theory to TCS.
 Philip Bille and Mikkel Thorup's paper in which they made the first runningtime 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 namechecked SLOGN in his very nice talk.
More from Noam Nisan.
Pictures: view of hotel grounds; view of hotel beach; view of basketball players at the conference lunch.
Friday, July 10, 2009
Will the real Adam Smith please stand up, please stand up, please stand up
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.
Thursday, July 09, 2009
TARK vs. EC
Wednesday, July 08, 2009
Speedup for Natrual Problems (Guest Post)
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 coNPcomplete language has an infinitelyoften (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 coNPcomplete 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 NPcomplete 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 coNPcomplete 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.
Tuesday, July 07, 2009
Raking Up the Frequent Flyer Miles
This will be my first time tweeting conferences in case you want to follow at least some of what's going on.
Monday, July 06, 2009
Pairs of Celebrities died/born the same day
 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.)

If you are famous and want people to notice
your death there here are some tips:
 DO NOT die the same day as a someone more famous. Example: Farrah Fawcett overshadowed by Michael Jackson.
 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.)
 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.
 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).
Friday, July 03, 2009
FOCS Papers
 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)
Here are a few of the many interesting looking papers that caught my eye.
 David Doty. Randomized SelfAssembly for Exact Shapes
 You just don't see many STOC/FOCS papers on selfassembly 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. Twomessage 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.
Thursday, July 02, 2009
Learn PCPs at DIMACS
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.
Registration is free and limited travel support is available for nonlocal participants (with preference to students and postdocs). More info on the workshop web site.
Wednesday, July 01, 2009
2piday? Other holiday possibilities!
So whatshouldbepiday 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.
 Multicultural day. OR give every ethnic group a holiday. This may lead to the 4day work week.
 Midautumn day to give us a break.
 PiDay (March 14)
 Mole Day (Oct 23)
 Talk like a pirate day (Sept 19.) Did pirates really talk that way in the past? now?
 Election day. That way more people will vote.
 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 antisemitism in America.
 Peace Day. Could celebrate the end of some war. But there is always the next war. Oh well.
 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}.
 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 4day work week.
 Groundhog day. (Feb 2). The movie movie Groundhog day higher Google rank than the day does.
 Chocolate day.
 Moon day. They have Earth Day so why not Moon Day?
 Children's day. We have Mothers and Fathers day, so why not Children's day?
 St. Patrick's day. Or the day after to get rid of your hangover.
 Teacher's day. Would teachers get this day off?
 Weird Al's birthday (10/23). Since its the same as Mole Day we can combine them to get Weird Mole Day.
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 3day 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 Piday 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.