One-Way Functions

What is a one-way function, intuitively a function that is easy to compute and hard to invert? Taking this intuitive idea to a formal definition has yield two quite different meanings, sometimes causing confusion.

The first directly tries to translate the intuition. A function f is one-way if

1. f is 1-1 (so an inverse is unique),
2. f is length increasing (so the output of the inverse function is not too large),
3. f is computable in polynomial time, and
4. there is no polynomial-time computable g such that for all x, g(f(x))=x.

This is a nice clean definition that fulfills the intuition but is not that useful for cryptography, since f could be easily invertible on all but a small number of inputs, or with stronger adversaries. To handle these issues we have a different looking definition.

A function f is r(n)-secure one-way if

1. There is a function l(n)≥n such that f maps strings of length n to strings of length l(n),
2. f is computable in polynomial time, and
3. for all probabilistic polynomial-time algorithms A, the probability that f(A(f(x)))=f(x) is at most r(n) where the probability is taken over x chosen uniformly from the strings of length n and the random coins used by A.

There are many variations on both definitions and a considerable amount of theory devoted to each. Grollmann and Selman show that one-way functions of the first kind exist if and only if P ≠ UP. On the other hand Håstad, Impagliazzo, Levin and Luby show that from any one-way function of the second kind, one can create a pseudorandom generator.

At one point I tried using complexity-theoretic one-way functions and cryptographic one-way functions to distinguish the two, but this only caused confusion. So we have to live with the fact that we have these two definitions with the same name and we'll have to just use context to figure out which definition is appropriate. If you give a talk or write a paper about one-way functions, it never hurts to distinguish which version you are talking about.

A Speech and A Weblog

UCLA Professor Andrew Kahng gave this wonderful speech to the incoming computer science graduate students. While designed for UCLA, with minor changes it applies to every research institution. Every graduate student or anyone interested in graduate school should read it.

Michael Nielsen, coauthor of my favorite book on quantum computing, has his own weblog. Worth checking out.

Proof, The Movie

We just got email that Proof, a movie adapted from the play, will be filmed in and around the University of Chicago campus over the next few weeks. I saw the play a couple of years ago in New York, a powerful story about an aging mathematician and his daughter. Given the cast, director and source material I would expect great things from the film version as well, and it certainly should best out the last movie I remember them filming here.

Turing, The Novel

Christos Papadimitriou has been exercising his creative talents. He has a new book Turing (A Novel about Computation) building a love story around some of Turing's lectures. He is now working on Logicomix, computer science in comic book form. I can imagine it now, our hero NP-Man and his trusty sidekick P-Girl battle the evil Execution Time.

The Buzz

There has been some buzz about the paper Resource Bounded Unprovability of Computational Lower Bounds by Tatsuaki Okamoto and Ryo Kashima. They claim to show that no polynomial-time machine can produce a proof of a super-polynomial-time lower bound for NP and as a consequence there is no proof that P≠NP in any reasonable proof system such as Peano Arithmetic. The first part I don't really understand but the latter would be a major breakthrough.

But don't get too excited. I have heard from multiple sources that Razborov has found serious problems in their paper, in particular that Theorem 22 is just false. So as one complexity theorist put it, "This is probably not the most important paper on your stack."

Creative Commons

In a conversation I had last week, a professor planned to use slides from lecture notes he found on the web in his own slides. He planned to give attribution to the original producers of the slides but did he need to contact them beforehand for permission. Technically yes, material put on the web is copyrighted by default. But if he sent them email most responses would be of the form, "Please don't waste my time!"

To deal with this issue, Creative Commons has a nice service giving an easy way to release some rights for online material. So I've added a link on the left column of the web log that basically allows you to modify and distribute the material in this weblog for noncommercial use with attribution. No need to ask me, not that anyone has.

On another note, I'm on vacation next week and off the internet. Back after that.

Balanced NP Sets

Last week I posed the following question:

(1) Exhibit an NP-complete language L, such that for all lengths n≥1, L contains exactly half (2^n-1) of the strings of length n.

This question was posed by Ryan O'Donnell and solved by Boaz Barak. Here is a proof sketch.

By using standard padding and encoding tools, (1) is equivalent to

(2) There is an NP-complete language L and a polynomial-time computable function f such that for every n, there are exactly f(n) strings in L of length n.

First we show how to achieve (2) if we replace "strings" with "total witnesses." Consider pair of formulas φ and ¬φ. The total number of satisfying assignments between them total 2ⁿ if the have n variables. We just create an encoding that puts φ and ¬φ at the same length. The total number of witnesses at that length is equal to 2ⁿ times the number of formula pairs encoded at that length.

We now prove (2) by creating a language L that encodes the following at the same length for each φ

1. φ, where φ is satisfiable.
2. (φ,w) where w is a satisfying assignment for φ and there is another satisfying assignment u<w for φ.

You can check that the language is NP-complete and the total number of strings in L for each φ is just the number of satisfying assignments of φ.

Is P versus NP formally independent?

As promised back in March, the October 2003 BEATCS Complexity Column is on whether we can truly settle the P versus NP question. Scott Aaronson gives quite an interesting survey on this topic.

STOC 2004

I have received some requests for the call for papers for STOC 2004 which will be held in Chicago. Maybe it is because I gave the presentation for STOC 2004 at the 2003 business meeting, or because if you google 'STOC 2004' this weblog comes up in the list, or just because I'm in Chicago now, but I am not officially connected to STOC 2004.

Having said that, here is the tentative call for papers.

Institute of Advanced Study

The Institute will be quite a complexity powerhouse this year. In addition to IAS fixtures Wigderson and Razborov, visiting are Russell Impagliazzo, Manindra Agrawal (with his students Kayal and Saxena at Princeton) and postdocs Boaz Barak, Subhash Khot, Ryan O'Donnell and Nate Segerland. These are just the ones I met yesterday during a short visit several weeks before their semester officially begins. We'll expect great things from them.

Here is a question we thought about yesterday, posed by Ryan O'Donnell and ultimately settled by Boaz Barak:

Exhibit an NP-complete language L, such that for all lengths n≥1, L contains exactly half (2^n-1) of the strings of length n.

Think about it. I'll post the proof next week.

Scheduling Research

A colleague of mine, who shall remain nameless, likes to schedule time for research, a certain set block of time during the day where he puts off all his todo's and concentrates on science. Sounds good but often his chair will stop by for some discussion or an impromptu meeting. The colleague will say, "Sorry, but I reserved this time for research", but that argument didn't fly, the chair said he could do research anytime. One day he said instead, "Sorry I have a squash game" and the chair replied that they would talk at a future time. Welcome to the academic world, where research gets trumped by a meeting that itself can be trumped by a squash game.

Is scheduling time for research a good idea? It depends on your personality and your research style. If you find yourself with no time to think about an interesting problem because too much else is happening then yes, best to schedule a few hours where you promise yourself you will do nothing else but research during those times. This means more than not preparing for class but also ignoring your computer. Checking email and surfing the web are themselves great time sinks.

In my case, I find it difficult to just start thinking about research at a given time. So I use the rule that research trumps all and when inspiration hits me, or someone comes to my office with a research question, I drop everything I can to work on the problem. Okay, I can't skip a class for research but email, weblog posts, referee reports, etc., should never stand in the way of science.

Electronic Commerce

The call for papers for the 2004 ACM Conference on Electronic Commerce is now available. I'm posting this note as my duty as a program committee member to spread the word of the conference.

Why would an electronic commerce conference want me, a complexity theorist, as a PC member? Electronic commerce has many surprising connections to computational complexity. Consider complex auction situations where different buyers wish to purchase different items with varying needs for combinations of these auctions. One needs to design such auctions which decisions made by the buyers, as well as determining the winner must be computationally efficient. This in addition to the usual needs of auctions to be revenue generating, robust against players trying to cheat the system and other notions of "fairness."

In a more philosophical sense, what is a large financial market but some sort of massive parallel computation device that takes pieces of information and produces prices for securities. How can we model and analyze this process? Computational complexity should play a major role in understanding this model of computing and allow us to develop more efficient financial markets.

Hello Chicago

Here I am, my first day back on the campus of the University of Chicago. It's quiet here, Chicago is on the quarter system and classes don't start here until September 29.

I was on the road during the August 22 anniversary of my first post on this weblog. I hope you have enjoyed reading it this year as much as I have had fun writing it.

Goodbye New Jersey

My office is all packed up and ready to be shipped. On Friday we move out of our house. I've moved my web pages to Chicago. Burned my files to CD's. It is disconcerting to see all my life's work (papers, talks, programs, grant proposals, editorial and conference stuff, course material, etc.) fit so easily on one CD-ROM. Uncompressed.

Moving is always sad. I've made many good friends at NEC, in and out of theory. But with change comes the excitement of the new chapter of my life ahead of me.

With being on the road and settling in, posting on this site will be quite sketchy over the next several weeks. But don't worry, as one California gubernatorial candidate would put it, I'll be back.

A New-To-Me Pumping Lemma for Regular Languages

I have a gap in my knowledge of work in theory done between 1979 (the publication of Hopcroft and Ullman) and 1985 (when I started graduate school). So every now and then I see a new result from this time that I should have known years ago. Here is an example from the Winter 1982 SIGACT News, a variation of the regular language pumping lemma due to Donald Stanat and Stephen Weiss.

Theorem: If L is regular then there is a positive integer n such that for every string x of length at least n, there are strings u, v and w with v nonempty such that x=uvw and for all strings r and t and integers k≥0, rut is in L if and only if ruv^kt is in L.

What surprises me about this result is that w does not appear in the conclusion and that the initial r could put the finite automaton in any state before it gets to u. Here is a sketch of the proof.

Let s be the number of states of a finite automaton accepting L. Let y_i be the first i bits of x. For any initial state a, y_i will map it to some state b. So one can consider y_i as a function mapping states to states. There are at most s^s such functions so if |x|≥s^s there is an i and a j, i<j such that y_i and y_j represent the same function. We let u=x₁...x_i-1 and v=x_i...x_j-1. The rest follows like the usual pumping lemma.

Using a result of Jaffe, Stanat and Weiss show that this condition is not only necessary but also sufficient to characterize the regular languages.

Splitting Sets

Can every infinite set in P be partitioned into two infinite subsets, each also in P? Uwe Schöning answers this question in the affirmative in the Winter 1982 SIGACT News.

Let's generalize the question by saying that a set A splits a set B if both A∩B and A∩B are infinite. Schöning really shows the more general result that any infinite recursive set can be split by a polynomial-time computable set.

Playing with this splitting notion yields lots of potential homework questions. Try these:

1. Show that every infinite regular language can be split by another regular language. Can every infinite context-free language be split by a regular language?
2. Show there is an infinite recursive set that cannot be split by any regular language.
3. Prove Schöning's result above: Every infinite recursive set can be split by a set in P.
4. For a real challenge, show that there is an infinite co-r.e. set that cannot be split by any r.e. set.

In recursion theory, sets that cannot be split by r.e. sets are called cohesive, and r.e. sets whose complements are cohesive are called maximal. For question 4 you are showing that maximal sets exist, a result first proven by Friedberg in 1958.

SIGACT News and The Cold War

Cleaning out my office I came across some old SIGACT News that Bill Gear had given me when he cleaned out his office after his retirement. The Winter 1982 edition is quite interesting. I was a freshman in college that year, well before I was part of the theory community.

There are some interesting technical articles that I will get to in future posts. But the first two pages were letters to the editor that are chilling reminders of the cold war during that time.

On page two was the following short note from Witold Lipski, Jr. and Antoni Mazurkiewicz from the Polish Academy of Sciences.

We are very sorry to inform you that due to the situation in Poland we do not see any chance to organize our 1982 Conference on Mathematical Foundations of Computer Science.

MFCS started in 1972 as an annual conference rotating between Poland and Czechoslovakia, and now between Poland, Slovakia and the Czech Republic. There was no conferences in 1982 or 1983 and the conference did not return to Poland until 1989.

Talking about the Czechs, there was a much longer letter on page one from James Thatcher of IBM. Here are some excerpts.

On a recent trip to Europe, I visited Prague and had the pleasure of talking with Dr. Ivan M. Havel who is a friend and colleague of many years. Ivan Havel received his Ph.D. in CS from Berkeley in 1971. He joined the Institute for Applied Computer Technology in Prague in 1972 and then in 1974 became a member of the Czechoslovakian Academy of Sciences, in the Institute of Information Theory and Automation.

Ivan's brother, Vaclav Havel, an internationally known playwright, was imprisoned in 1979 for four and a half years for his activities in connection with the Charter 1977 movement.

In 1980, possibly related to his refusal to denounce his brother, Ivan Havel was removed from his position in the Academy of Sciences and was unemployed for several months. Last May, he and Vaclav's wife were arrested and charged with "subversion" for allegedly "collecting and distributing written material oriented against the socialist state and social establishment, with hostile intentions." After four days detention, they were released.

He is employed as a programmer-analyst by META, a home-worker program for the handicapped.

Ivan Havel remained a programmer until after the Velvet Revolution in 1989. After some political work in 1990, he became a docent (associate professor) at Charles University and director of the Center for Theoretical Study where he remains today.

His brother Vaclav went on to become president of the Czech Republic.

My Life in Email

When I move back to Chicago, I will go back to my old email address . I got to thinking about how my career can be described by my email addresses.

As an undergrad at Cornell, I spent several years working for computer services writing an email system in assembly language for the IBM 370. The system was scrapped shortly after I left for grad school at Berkeley. After a year at Berkeley, I followed by advisor, Michael Sipser, to MIT.

I had email addresses at Cornell and Berkeley but I have long since forgotten them. At MIT I wanted the userid "lance", but the name was taken by Lance Glasser, then an MIT professor. So my email became .

When I graduated and went to Chicago, I decided to stick with the userid "fortnow" for an email of . This bucked the trend at the time of having first names for email at Chicago so I had to have aliased to . When the university started system wide email I got though also works.

When I did a sabbatical in Amsterdam my email became or simply . When I moved to the NEC Research Institute my email because aliased to and when the NEC Research Institute became NEC Laboratories America I got my current email .

In addition to this, the ACM has created permanent email addresses, permanent as long as you are an ACM member and I did create an address though I never did give it out (until now). My brother and I now own the domain fortnow.com and I have what I do call my permanent address, . I also am the default receiver for fortnow.com mail, which means that addresses like , or even will all go to me.

All of the email addresses in this post still work and forward to me. But I will stick to using two main email addresses, for work related email and for non-work emails.

I used javascript to generate the emails in this post to avoid adding even more to my heavy spam load. We'll see if it works or whether I start getting spam sent to .

Information Markets for Fighting Terrorism

A few months ago I had a post describing information markets, a system of buying and selling securities that pay off if a given future event happens. Based on the price of a security, one can get an estimate of the probability that that event will occur. Studies have shown that information markets are better predictors than polls or experts.

Information markets have taken a blow in the past few days. The US Department of Defense has cancelled a program that would have set up limited futures markets on securities based on terroristic activities. They bowed to pressure from senators who consider it morally wrong to bet on events on future terrorist attacks. I understand their concerns but computer scientists and economists have produced what could have been a powerful tool in controlling terrorism and it is quite a shame to see it discarded so easily.

David Pennock sent me some links on a more positive point of view from CNN, Fortune and Wired and a fun CNN piece on the Tradesports Poindexter future.

Update (8/1): A well-written New York Times column A Good Idea with Bad Press and a nicely argued opinion piece by David Pennock.

The Tour

I know this is not a sports weblog and I don't even like bicycling but anytime an American named Lance wins a major championship I can't let it go unnoticed.