First my older daughter's fourth grade friends gave her a Tomagotchi and soon after my younger first grader also wanted one and we relented. She then convinced several of her first grade friends that they needed them which caused some parents to call us mostly because they got these Tomagotchis and nobody could figure out how to work them. My first grader is giving out lessons tomorrow.

These devices beep when they need attention—food or playing or needing cleanup after an "accident". Don't attend to them and they will die. My kids pay constant attention to the Tomagotchi and it is sometimes hard to bring them back to reality. My youngest, a couple of days ago, got all excited when her Tomagotchi learned to go to the bathroom by himself. It didn't seem like all that long ago that I got excited about the same thing for her.

Luckily young kids are fickle and the Tomagotchi craze will soon pass. But move over Godzilla, the scariest monster from Japan is a friendly looking creature in a plastic case.

--
Posted by Lance to Computational Complexity at 3/11/2005 08:02:00 AM

• Strength—A good collaborator should of course be a strong researcher in my area of interest and Harry certainly fits that bill. But there are many great complexity theorists I have hardly or never worked with.
• Compatibility of Strengths—The strengths should complement each other nicely. Good collaborators know their areas well and can quickly focus the inherently difficult parts of a problem and have different tools and approaches they can bring to the table.
• Respect—Good collaborators need to trust and respect each others ability and judgment.
• Philosophy—Long-Term collaborators need to share beliefs on what problems are important and worth working on.
• Personality—You need to have a friendly relationship outside of work. It helps immensely if your respective families get along.
• Luck—Finding the right problems to work on together at the right time. You need a good first collaboration before you start making time for further collaborations.
• Distance—This seems counterintuitive but two people in the same geographical area rarely have a long history of collaboration. It's hard to make time for working together when you are in close proximity. Also two people who see each other constantly get tired of working with each other no matter how compatible they are. Better to keep in email contact and have several short and long visits where one can allocate time for the other.

Why does the Netherlands have such a strong biking culture? Most of the country is flat, the cities are compact (at least by Chicago standards) and the weather never gets too hot or too cold to bike. One can reliably commute by bike nearly every day of the year. The country has many dedicated bike paths and marked bike lanes on many major roads. Traffic laws greatly favor bikes over cars. This all gives positive reinforcement to bicycling in this country.

Bicycles here for the most part do not have hand brakes or multiple gears but are otherwise rather sturdy. Bicycle lights are required at night; a visiting complexity theorist got a ticket for not using his. Virtually no one wears a helmet. When we lived here on sabbatical we would put our one-year old daughter on a bike seat on the handlebars without a helmet—the norm for Holland but might have gotten us arrested back in the states.

Bicycle theft is a big problem especially in the cities. The general rule is to spend as much on the lock as you did on the bike. Locking up your bike requires knowing your topology; Get it wrong and you might lose a wheel or worse yet keep your wheel and lose the rest of the bike.

Most people in Holland don't bike for health or environmental reasons. Bicycling is often simply the easiest way to get from point A to point B.

--
Posted by Lance to Computational Complexity at 3/16/2005 10:55:00 AM

Why do I travel? I don't enjoy at all the act of traveling despite the advantage of non-stop flights to nearly everywhere from Chicago. The tourism bit has long lost its allure. After a while all the cities and universities start to look the same.

I don't need to travel. I could hole up in Chicago, just work with the students and visitors and have a moderate research career. I have tenure so my job is safe in any case. So why travel?

1. People: Working with people, talking with people, drinking with people. Traveling to visit different people keeps my research and academic life from getting stale.
2. Getting Away: Like most people, I have considerable work and family responsibilities and travel allows me to escape and have time to focus on research. When I visit someone for a short time they will usually make time to work with me as well. The internet has prevented me from completely escaping but I can usually tell people I'm away and I will deal with the problem when I get back. I do try to keep to a goal of not leaving the family for more than a week at a time.
3. Being Involved: If you want to be an active member of the community people need to know who you are. Don't travel and people will forget you. Email is not a good substitute for meeting face to face.

• Once you win an argument, stop arguing.
• Always play to win. He would always take a handicap and play his hardest rather than dumb down his play particularly in chess, his favorite game.
• When he went to college, the engineers measured their prowess in the number of digits of precision they could get from their slide rules. I guess he didn't get enough digits as he gave up engineering and eventually went into marketing.
• The extra character in a movie that seems to serve no purpose is the one that committed the murder.
• He said "When you grow up and drive you can choose the radio station." Like my daughters let me get away with that.
• Nixon really was a crook.
• Given enough money, there is nothing anyone won't do.
• He meticulously taught me how to keep score in baseball as this is a skill every American should know. He then told me never to keep score as it distracts from the game.
• The two course he regretted not taking in college were art and music appreciation. So I took art appreciation in my first year. Big mistake. For the record the two courses I wish I took were economics and mathematical logic.

For space we have an easy result: Every k-tape s(n)-space bounded Turing machine can be simulated by a 1-tape machine in O(s(n)) space. Create a single supertape with separate "tracks" for each of the original tapes and add markers for the locations of the heads on each of these tapes.

For deterministic and nondeterministic time, this constructions yields a t²(n)-time 1-tape simulation of a k-tape t(n)-time machine and this is the best you can do (consider { x#x | x∈Σ^*}). We can do much better if we reduce k tapes to 2 tapes.

We can simulate any nondeterministic t(n)-time k-tape machine in nondeterministic O(t(n)) time on a 2-tape machine. Roughly the simulation guesses every step of the transition function on one tape and uses the other tape to verify the transition function on each tape of the original machine one tape at a time.

For deterministic time we can only achieve a weaker result: Every t(n)-time k-tape machine has a 2-tape simulation using O(t(n)log t(n)) time. The proof (due to Hennie and Stearns) is quite involved and I won't give it here. The proof has a nice side effect: The construction creates an oblivious machine where the head movements depend only on the input length. One can use this fact to show that we can simulate any t(n)-time Turing machines with O(t(n)log t(n))-size bounded fan-in circuits and reduce any t(n)-time nondeterministic computation to satisfiability questions of size O(t(n)log t(n)).

--
Posted by Lance to Computational Complexity at 3/22/2005 03:05:00 PM

But suppose NP-complete problems do have very efficient algorithms. Can we use them to create art, perhaps, as someone recently suggested to me, create a new Mozart opera, Shakespeare play or finish Schubert's symphony?

Perhaps we could use P=NP to find a small circuit that outputs "Shakespeare" plays. But these plays will only extrapolate from his known works. The program cannot add the new creative ideas Shakespeare puts in his works. It cannot create art just generate similar pieces.

Of course this whole exercise is moot since we strongly believe that NP-complete problems are hard. Even so a P=NP fantasyland might put some mathematicians and computer scientists out of work but true artists will still create in ways computers can never match.

--
Posted by Lance to Computational Complexity at 3/24/2005 05:43:00 AM

I have but one brother. Happy Fortieth Matt. Thanks for making my life seem so ordinary.

--
Posted by Lance to Computational Complexity at 3/26/2005 08:34:00 AM

What about in academics? Supposedly some mathematicians have used amphetamines to get an edge or keep up with younger mathematicians. If we discover that a mathematician used such a performance-enhancing drug to prove a theorem would we take away his credit for that result? No, we wouldn't.

I don't have any direct evidence that any mathematicians or computer scientists actually use any performance-enhancing drugs, other than caffeine of course. Even so I doubt many of us would agree to random drug testing of academics. But then why should professional athletes be held to a different standard than professional academics?

--
Posted by Lance to Computational Complexity at 3/28/2005 09:10:00 AM

Suppose we could prove P≠NP in the theory of arithmetic. I can create a machine M that solve SAT on standard formula φ using |φ|^k time if k is nonstandard: Since k and thus |φ|^k is greater than every standard integer, we have time to do exhaustive search. However there will be some nonstandard φ that M will fail to solve satisfiability in time |φ|^k time, for whatever the satisfiability question for nonstandard φ means.

Now suppose P=NP in the standard model but P≠NP in some non-standard model (and thus the P versus NP question is independent of the theory of arithmetic). We have a standard machine M and a standard integer k such that M(φ) correct computes whether a standard φ is in SAT in |φ|^k steps. But for some non-standard φ, M(&phi); would fail even though it gets to run in time n^k for the nonstandard n=|φ|. Even if we allow M and k to be non-standard there will be some φ that M will fail to determine satsifiability.

You can keep playing this game and never get into trouble assuming the theory of arithmetic is consistent. But I get a headache when I try to think what non-standard Turing maching, non-standard polynomial running time and satisfiability of non-standard formula really mean.

--
Posted by Lance to Computational Complexity at 3/29/2005 08:37:00 PM

I wanted to ask you something about the Savitch and Immerman-Szelepcsényi theorems that I saw you have in your weblog. In both thorems we have that s(n)≥logn. Why is that?

Still many researchers have studied sublogarithmic space classes but these results tend to be dependent on the exact machine model and it's tricky to understand what they tell us about general computation.

--
Posted by Lance to Computational Complexity at 3/30/2005 07:02:00 PM

You can find a copy of their paper here.

--
Posted by Lance to Computational Complexity at 4/1/2005 05:44:00 AM

Today we think of the class NC in terms of circuits: NC contains the problems solvable in polynomial-size and polylogarithmic-depth circuits. But Nick Pippenger originally defined the class to capture parallel computation: problems solvable on a PRAM with a polynomial number of processors and polylogarithmic time. The PRAM model had several processors that shared a polynomial amount of random-access memory. There were three main variations:

• EREW–Exclusive Read/Exclusive Write: Every memory cell can be read or written only by one processor at a time.
• CREW–Concurrent Read/Exclusive Write: Multiple processors could read a memory cell but only one could write at a time.
• CRCW–Concurrent Read/Concurrent Write: Multiple processors could read and write memory cells. This variation had several subvariations depending on how one handled conflicting writes.

So why don't we think PRAM anymore when we look at NC? Moore's Law. Processors got faster. Much much faster. The ideas of having many many processors each doing a tiny bit of work seems wasteful these days when we can just as cheaply have each processor do a lot of work.

We still see active research in parallel computing and one can speed up many computations using a large number of machines sometimes far away from each other just connected via the internet. But the best one could hope for is perhaps a quadratic improvement, not the exponential improvement that comes from PRAMs.

--
Posted by Lance to Computational Complexity at 4/3/2005 05:28:00 PM

What is the longest song?

"ℵ₀ bottles of beer on the wall."

Happy Mathematics Awareness Month!

Submit your new original poem on a mathematics or theoretical computer science theme in the comments section of this post with your name and/or email. One entry per person. Entries due by 11:59 PM CDT on Monday April 18. A panel of celebrity judges will choose the winning poem based on whatever criteria they deem fit. The decision of the judges are final.

--
Posted by Lance to Computational Complexity at 4/4/2005 06:14:00 PM

Luis was sure he would be bored. We got awesome seats behind home plate and I introduced him to the full baseball experience with Polish sausages for lunch and Take me out to the ballgame during the seventh-inning stretch. Luis knew little about baseball but pretty soon he concentrated on every pitch counting balls and strikes. During the game he even said "baseball is not quite as boring as I had feared." The experience became complete when the Sox scored four runs in the bottom of the ninth to win the game.

Yes, baseball is back and all is good in the world.

--
Posted by Lance to Computational Complexity at 4/6/2005 05:10:00 PM

Student: I couldn't find the paper online.
Me: So walk over to the library and get the paper there.
Student: But you can't take those books out and I don't want to spend hours at the library reading the paper.
Me: So make a copy and take it home.
Student: The library has copy machines?

The next generation gets even worse. From a discussion in an undergrad class.

Student: I searched really hard for this topic and didn't find much. Are you sure it even exists outside of class?
Me: Really, I'm sure the math library [right down the hall] has several books on the topic.
Student: Oh, I just used Google.

• Declarative first sentences of the introduction, like "Analyzing Left-Handed 12-SAT is a key approach to solving the P versus NP question." Just because you say it doesn't make it true.
• "We use novel techniques that might be of independent interest." A double faux pas. You don't get to call your own techniques novel. "Might be of independent interest" is such a meaningless statement.
• Footnotes (and parenthetical statements) which interrupt the flow of the paper. If it's not worth mentioning in the text then don't mention it.
• Using citations as nouns like "[13] using techniques of [6] showed the main result of [4] follows easily from [18]." I hate having to keep flipping to and from the references to read these papers.
• Using the cliché "larger than the number of atoms in the known universe." It's big. We get it.
• Using the word "respectively" which says "I'm going to give you something hard to parse because I'm too lazy to write two sentences."
• Titles with symbols or complexity classes: If you can't describe your research with words you might consider becoming a mathematician.

Lance nicely invited me to expand on my views on the format for conference submissions. Currently, I am on a PC using the standard theory call:

A submission for a regular presentation must be no longer than 10 pages on letter-size paper using at least 11-point font…additional details may be included in a clearly marked appendix, which will be read at the discretion of the program committee.

The problem is that many, including myself, think that this formatting rule is silly, and so it has been widely ignored or at least painfully abused for many years. I would like to propose a simple and logical alternative: conference submissions should be in the same format (or as near an equivalent as possible) as the final conference version. Many other conferences (such as AAAI and Sigmetrics) use this approach with great success.

The advantages of this approach include:

1. It reduces the work of the authors. Right now, authors have to create entirely distinct submission versions and final versions of conference papers using various formats. Most authors find this a hassle, and this is my main reason for the proposal. I hate writing the same conference paper multiple times just to cope with formatting issues.
2. It gives the reviewer a more accurate picture of the conference paper. Reviewers will have a very good idea of what the paper will look like in the conference proceedings, making it easier to judge. When you're staring at 20+ pages of appendices, it is hard to tell what the final paper will look like.
3. It enhances fairness. Because this is a standard with a clear reasoning behind it -- you cannot have a longer submission than conference paper -- people are more likely both to follow and enforce the rule, avoiding potential unfairness.

1. The format is too hard for the reviewers to read.

   My response: If this is the case, then perhaps the conference paper format itself should be changed -- after all, don't we expect many people to actually read the conference version? If the conference paper is packed tight for other reasons (the publishers charge by the page), then for submissions design as near an equivalent format as possible. If we find 10 double-column 10 point pages with style file A essentially equals 20 single-column 11 point pages with style file B, then clearly state that in the call and ask for the latter. (Luca Trevisan pointed out this is done for the Complexity Conference already.)

2. Appendices are necessary when there are long proofs that won't fit in the paper.

   My response: If the proofs won't fit in the final conference paper, this is something a reviewer should see and know. The PC can either allow appendices, with the knowledge they won't have room to appear, or allow pointers to more complete versions (TRs, arXiv preprints) that the reviewers can examine if they desire.

3. By having different formats, we force authors to revisit and hopefully improve their paper.

   My response: Nice intentions, but don't people already want to make their published work as good as possible? This seems unnecessary, and not worth the price.

Translation Lemma: Let f(n), g(n), h(n) be reasonable (time-constructible) functions with h(n)>n. Then

The proof uses a technique known as padding. Let L be in NTIME(f(h(n))) via a machine M. Define A by

As an immediate consequence we get that if P=NP then E=NE (where E=DTIME(2^O(n))) by letting h(n)=2ⁿ.

The translation lemma works in only one direction. You need h(n)>n, you can't unpad an arbitrary x. It's open whether E=NE implies P=NP for instance.

The lemma has many applications. Here is one example.
Theorem: If P=NP then some language in E does not have subexponential-size circuits.

Proof: In the Σ₄ level of the E-time hierarchy we can compute the lexicographically-first language A that cannot be simulated by any 2^n/2-size circuits. If P=NP then the polynomial-time hierarchy collapse to P. By a version of the translation lemma with h(n)=2ⁿ the polynomial-time hiearchy collapsing to P implies the E-time hierarchy collapses to E. Thus A is in E but A does not have subexponential-size circuits.

--
Posted by Lance to Computational Complexity at 4/15/2005 08:41:00 AM

• You've been working hard on a research problem and someone else solves it. Does that make you feel happy or sad?
• Three people in an office. Two of them bounce ideas back and forth to prove a new theorem while the third just tries to keep up. Should the third person be a co-author?
• You are reviewing a paper and see an easy but major improvement to the paper's main result. What do you do?
• Your friend is applying to your university and you see that one of his recommenders wrote a weak letter. Do you tell your friend?
• Your advisor of the opposite sex has two tickets to a concert you really want to see and invites you to join him/her. Would you go?
• You discover a student wrote something strongly negative about a colleague on their weblog. What would you do, if anything?
• Would you still be a scientist if you could do research but all your work had to be published anonymously?

The previous proofs used considerable algebraic techniques. Dinur takes a more combinatorial approach using a powering and composition technique (inspired by Reingold and the zig-zag product) to separate the gap in 3SAT without increasing the number of variables.

An upcoming STOC paper by Ben-Sasson and Sudan gives a PCP for SAT of only quasilinear size but requiring polylogarithmic queries to verify the proof. Dinur, by applying her construction to those PCPs, can now create quasilinear-size proofs which only need a constant number of queries for verification.

--
Posted by Lance to Computational Complexity at 4/19/2005 06:52:00 AM

When a P-man loves an NP-woman

Been a happy deterministic man
With a simple polynomial brain
I contented myself with P problems,
And always looked at NP with disdain.

Fell in love with a polynomial woman,
But with a non-deterministic wit,
She said she would marry me,
Only if I could show her that P=NP.

I rushed to the library and studied,
Asked Garey Johnson for a hint to the truth,
They said "this is quite a hard question",
But none of them had a hint or a clue.

Went to church and prayed to The Almighty,
"Please Oh Lord, give me a lead the truth",
"Don't waste your time son", a voice said laughing,
For I myself on this wasted my youth.

First oracle says you will marry
Second one tells you you'll split
Time moves, paths branch, results may vary
Accept the state that finally fits

If you finally marry this girl,
And P=NP was true,
What a Chaos: E-banking unsafe, Salesmen traveling cheaply!
And mathematicians with nothing to do!

If I grant your happiness,
The precondition must be no witness,
Even you both did nothing completely wrong,
The punishments will be exponentially long.

If you really want to marry this woman,
Then randomness might be the only key,
But please stop praying for an answer to me,
For I could not decide on this P=NP!

--
Posted by Lance to Computational Complexity at 4/20/2005 01:50:00 PM

I'm no big fan of the SCI conference but virtually none of the conferences in computer science fully referee their submissions. A clever student could write a paper with a bogus proof and have a chance of that paper being accepted at a major conference like STOC. I would consider someone who intentionally submits a bogus paper to STOC guilty of academic fraud. Why are these MIT students any different?

Students make mistakes and we should tell them what they did was wrong instead of just glorifying such activities.

--
Posted by Lance to Computational Complexity at 4/21/2005 09:10:00 PM

This month we honor the papers that gave us the first NP-complete problems and marked the official beginning of the P versus NP question. The P and NP notation did not originate with these papers but I will use them anyway for clarity.

Steve Cook, The Complexity of Theorem-Proving Procedures, STOC 1971.

Suppose a nondeterministic Turing machine M accepts a set S of strings within time Q(n), where Q(n) is a polynomial. Given an input w for M, we will construct a propositional formula A(w) in conjunctive normal form such that A(w) is satisfiable iff M accepts.

The theorems suggest that it is fruitless to search for a polynomial decision procedure for the subgraph problem, since success would bring polynomial decision procedures to many other apparently intractable problems…The theorems suggest that Tautology is a good candidate for a set not in P, and I feel it is worth spending considerable effort trying to prove this conjecture. Such a proof would be a major breakthrough in complexity theory.

Leonid Levin, Universal'nyie Perebornyie Zadachi (Universal Search Problems), Problemy Peredachi Informatsii 1973. Translation in appendix of the Trakhtenbrot survey.

If we assume that there exists some (even if artificially formulated) problem of the search type that is unsolvable by simple (in terms of volume of computation) algorithms, then it can be shown that many "classical" search problems have the same property.

All of these problems are solved by trivial algorithms entailing the sequential scanning of all possibilities. The operating time of the algorithms, however, is exponential, and mathematicians nurture the conviction that it is impossible to find simpler algorithms…but not one has yet succeeded in proving it.

I have nothing against "follow your dream" movies and Ice Princess does put science and computers in a good light, at least in the early part of the movie. But just once can't we have a movie where a young woman whose parents want her to be a great figure skater, gymnast or tennis player and instead follows her dream of becoming a scientist.

--
Posted by Lance to Computational Complexity at 4/25/2005 03:08:00 PM

We talked with a computer magazine writer who said we could legally sell a game based on an arcade game as long as we changed the name and slightly changed the user interface. We focused on the game Frogger which was not yet available for the Apple and created Ribbit written mostly over winter break. That spring we sold the program through a local computer store before we got a cease-and-desist order from Sierra Online, who had bought the personal computer rights to Frogger. So we ceased and desisted but not before 1200 copies of the program got sold. I made about $2000 from the program, not bad for a college freshman in 1982. Also a computer magazine review of Frogger liked our program better!

"Sierra Online's Frogger is even worse than the game named after the sound a frog makes."

On the web page I set up for Ribbit I posted a pirated version of the game I found on the web. To get the original version I would have to find the disks buried somewhere in my mother's house and then find a machine that can read floppy disks from a time when disks were floppy.

--
Posted by Lance to Computational Complexity at 4/26/2005 08:05:00 PM

This is a Dell Computer. It has 3 different parts. The first part is the screen. The screen is were you see what you are typing. The next part is the keyboard. The keyboard is the place were you type. The last part is the mouse. It is my favorite part because it helps me to click on the things that I want to click on.

There are many other parts of a Dell Computer. Those are the parts that I recognize the most. But the mouse is my favorite part. The mouse comes in many different shapes and sizes. On a laptop the mouse is either a circle in the middle, a square at the end, or both. On a regular computer the mouse is either an oval, a trackball, or looking like a mouse.

The mouse is a really important part of the computer. I will always keep mine in handy.

--
Posted by Lance to Computational Complexity at 4/28/2005 01:04:00 PM

There is no serious upper page limit on a thesis and you can truly spend the extra time to make your thesis stand out.

1. Put the results of your earlier papers together in a common framework and add some new results you never bothered writing up. (Harry Buhrman's 1993 thesis has a large collection of results on exponential-time computations that I still often consult.)
2. Take the time to expand the proof of complicated results to the right amount of intuition and depth. (For many years Madhu Sudan's 1992 thesis had the best write-up of the proof of the PCP theorem.)
3. The initial chapters of your thesis can serve as an introduction to a relatively new research area, (Michael Kearns's 1989 thesis gave an early broad overview of computational learning theory.)
4. Or give your own impressions of a more established field (Scott Aaronson's thesis expounds on his views of quantum computing.)

What we have feared during the last weeks and months came true yesterday morning: Clemens Lautemann died at the age of 53 from cancer.