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

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.

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

(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.)

--
Posted By GASARCH to Computational Complexity at 6/24/2009 12:33:00 PM

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!

--
Posted By Lance to Computational Complexity at 6/25/2009 06:12:00 AM

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.

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.

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.

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.

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).

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.

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.

--
Posted By GASARCH to Computational Complexity at 7/08/2009 10:00:00 AM

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.

--
Posted By GASARCH to Computational Complexity at 7/10/2009 12:33:00 PM

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.

More from Noam Nisan.

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

--
Posted By Lance to Computational Complexity at 7/13/2009 07:05:00 AM

--
Posted By Lance to Computational Complexity at 7/16/2009 05:17:00 AM

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.

--
Posted By Lance to Computational Complexity at 7/20/2009 05:21:00 AM

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. 

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.

1. To find out about papers that might spark my interest and lead to the following:
   1. Papers. Most recent example: Moser's paper in STOC 2009 has lead to a paper that is now in progress.
   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 honors projects and homeworks.
2. To find out random stuff in the hallways. Most recent example: Scott Aaronson told me about a proof that PP is closed under intersection that uses Quantum stuff. Oldest example: I found out Fixed Pareamter Tractability from Mike Fellows very early on at a conference.
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 I don't understand I sometimes take a 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. Not that many since 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 relevent.

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.

• The new and improved ECCC 
• Just told that for recent stimulus-based 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).

Be the first on your block to have NAME OF PRODUCT!

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!

1. 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.)
2. 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.
3. 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.
4. 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 on-demand, newer ones and DVD recorders have a problem with this.
5. 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.