The Problems of LaTeX

By request a post that may create the biggest backlash since I declared myself Unix free.

\begin{rant}
LaTeX is a great system for mathematical documents...for the 1980s. But the computing world changed dramatically and LaTeX didn't keep up. Unlike Unix I can't give it up. I write papers with other computer scientists and mathematicians and since they use LaTeX so do I. LaTeX still has the best mathematics formulas but in almost every other aspect it lags behind modern document systems.

WSYWIG: I love seeing the final document as I write it. There are front ends to LaTeX that approximate this but they produce LaTeX code that make it near impossible to collaborate unless everyone uses the same editor and we don't. "Code" is the right word, I have to compile a LaTeX document then start a separate program to see it.

Collaboration: The very reason I'm stuck with LaTeX is its greatest weakness. We all have different macros, style files and bibtex formats (and some don't use bibtex at all). We all have to agree in the beginning which of our homegrown stuff we want to use and merging already written documents is a bear. How often does some one send you a LaTeX document and you have to email back that they forgot some style file?

LaTeX documents are saved as text files which have different formats on different machines. I hate seeing ^M at the end of every line. Some people to break up LaTeX lines at reasonable places, other people don't messing up my editor and trying to figure out what my co-author has changed.. At least email attachments avoid the old ¿From problem.

Microsoft Word has a great system for tracking revisions. Google Docs lets people edit at the same time. Nothing close to either for LaTeX.

User Friendly: LaTeX is not user friendly. Try opening a text editor and (without looking at an old LaTeX document) write a LaTeX document to say "Hello World!" that will compile on the first try. Now go to Google Docs, create a new document and type "Hello World!". See the difference. Don't even get me started on creating a table.

Backward Compatibility: In the early 90's, LaTeX went through a major upgrade. There was a compatibility mode that claimed to be fully backward compatible. Not even close. Then they changed the font system, rendering my old documents unreadable. Luckily LaTeX hasn't changed significantly since then.

It's not difficult to convert between Word, Docs and most other document systems but nearly impossible to move to/from LaTeX.

I don't use LaTeX when I don't need to. I usually use Word or Docs for recommendation letters and other documents without much formulas and references including my upcoming P/NP book.

What we need is a way out of LaTeX, add-ons to Google Doc that make it as nice for math as LaTeX, and the ability to import old LaTeX documents, style files and bibtex files. Not holding my breath.
\end{rant}

Why did 1+1=2 take Russell and Whitehead 300 pages?

In my post about the myth that Logicians are crazy I mentioned in passing that Whitehead and Russell spend 300 pages proving 1+1=2 (but were both sane). Two people privately emailed me:

Are you sure Russell and Whitehead weren't a few axioms short of a complete set? How could they take 300 pages to prove 1+1=2. Isn't it... to obvious to be worth proving?

I responded by saying that they had to define 1, +, =, and 2 rigorously. One of them responded Are you a few limit points short of Banach space? That aside, there are some questions the 1+1=2 proof brings up:

1. How did they spend 300 pages proving 1+1=2?
2. Is it easier in ZFC?
3. How important is or was Principia Mathematica? Wikipedia says PM is widely considered by specialists in the subject to be one of the most important and seminal works in mathematical logic and philosophy since Aristotle's Organon. The Modern Library places it 23rd in a list of the top 100 English-Language nonfiction books of the twentieth century. Here is the list they are referring to. The other books look... readable.
4. I had thought that nobody reads PM anymore; however, its entry on amazon says it has a rank of roughly 294,000. This is far better than a book that truly nobody reads. For example this book has an Amazon rank roughly 5,300,000.
5. While more people are buying it than I thought, are people actually reading it? Did they ever? My guess is no and no, but I really don't know.
6. Can a book be influential if few people read it? Yes if they are the right people. Godel read it and I think it inspired him. (Its mentioned in the title of his Incompleteness paper.)
7. PM was an early attempt to formalize all of math from the ground up. This may be one of those tasks that you are almost destined to do in a clunky way before doing it smoothly.
8. I am talking in a vacuum here, having never read it. If any of my readers have actually read it and want to comment on what it was really like, you are more than invited to do so.

Delay for a Postdoc

Suppose you have a tenure track offer at the University of Southern North Dakota and a postdoc offer at MIT. Tenure track jobs are hard to get so you want to accept the USND position but before you spend your life in Hoople you'd like some more time in a top research place.

So you ask the CS chair at USND if you can spend the next year as a MIT postdoc before going to USND. The chair needs you to teach algorithms that spring. Also if you don't take the job, he may lose the position to the music department. What are his choices?

1. Say no, that you have to start this fall or not come at all. This runs the risk that you will not accept the USND position.
2. Say yes and find someone else to cover algorithms. This has a different risk, that you might find some other job and not come to USND at all.

Is it ethical for you to say you are coming to USND in a year and send out new applications in the fall? What if you don't go outright looking for a job but Michigan asks you to apply? Is it ethical for Michigan to pursue you if it knows about your promise to USND? What if you fall in love with someone in Ann Arbor?

Someone I know (not CS) turned down an academic job she had promised to take. The school sent her a bill for $12,000 to cover the expenses of finding someone else to cover the classes. She didn't pay.

One economic solution: The chair agrees to the postdoc but requires you to pony up $12,000 now which you will get with interest when you start at USND. Trouble is most grad students don't have $12,000 to pony up and probably would walk away from a school making this offer.

This would be much easier if universities worked like baseball teams. In order to get you, Michigan could offer USND Seth Pettie and a grad student to be named later.

Looking for people to review books for my column

I am looking for reviewers for the following books for my SIGACT NEWS book review column. I will try to edit this post to keep the list up to date; however, if you are reading this past July 28 then you should look at the this list which I am constantly updating.

1. Look here for advice for reviewers.
2. Look here the LaTeX template.
3. Look here for past columns.

IF you want to review a book then FIRST goto the advice for reviewers and see if you really want to review a book. If so then email me your name and postal address to send the book (if you are out of the country I will have the publisher send it to you). Your reward for doing the book review: a free copy of the book! I would like to get requests before July 28 since that is when the next column goes to press and I would like to have an updated books list there; however, if you ask me past that date, and the book is still available, you can still review it. (ADDED LATER- DEADLINE IS MID-OCT OR MID-NOV, BUT CAN BE NEGOIATED IF THERE IS A REASON FOR LATER.)

Bio Comp

1. Introduction to Bio-ontologies by Robinson and Bauer.

Math

1. The Dots and Boxes Game: Sophisticated Child's play by Berlekamp.
2. New Mathematical Diversions by Martin Gardner.
3. The Magic Numbers of the Professor by O'Shea and Dudley.

Books on Misc-Comp Sci

1. Random walks and diffusion on graphs and database by Blanchard and Volcanic.

Disproving the Myth that many early logicians were a few axioms short of a complete set

While I was working on this post another blogger posted on the same topic here and I found a book review of Logicomix that touched on some of the same issues here. (For MY review of Logicomix see here.) They are very good sources and I will refer to them in this post.

There is a notion that logicians who work in foundations early on in the field were crazy. I give examples of where this is said and then I look at the real evidence.

1. In Rudy Rucker's post about Turing he writes

   ... it really does seem possible that Turing killed himself. Like the other logicians Godel and Cantor, he seems to have been somewhat nuts. Funny how many logicians are crazy and irrational. A paradox.

2. In Logicomix, a great comic book about the foundations of logic, there is an allusion to Logicians being crazy.
3. In Gian-Carlo Rota Indiscrete Thoughts he writes: it cannot be a complete coincidence that several outstanding logicians of the 20th century found shelter in asylums at some point in their lives: Cantor, Zermelo, Godel, and Post are some.

I've also seen an explanation for this alleged phenomena: Logicians were searching for absolute certainly and either it can drive you crazy or thinking you can find absolute certainly means you were crazy ahead of time.

So the people above, and others, give some examples of logicians being crazy and then claim that many logicians are crazy. I am reminded of people who say It was cold the other day, looks like Global warming is wrong.

Let us look at the actual record. I will look at all of the logicians in Wikipedia's list of logicians who

1. were born between 1845 and 1912. (1845 is when Cantor was born, 1912 is when Turing was born.)
2. I ruled out a few people who were really philosophers, and also Banach who I don't think would call himself a logician.

For each logician on the list who meets my criteria I say if I think they are sane or a few axioms short of a complete set. I am not a historian--- corrections are more than welcome. I also freely admit that crazy is not well defined.

You may well disagree with what years I pick and my opinions. The point is to get an intelligent discussion going.

1. Wilhelm Ackerman (1896-1962): He defined the function that bares his name. He also worked on the epsilon-calculus which formed the basis for Bourbaki's logic. Reading Bourbaki might drive one crazy; however, forming the basis for it does not. He was quite sane (Ackerman that is-- Bourbaki had multiple personality disorder.)
2. Alice Ambrose (1906-2001): She had the longest lifespan of anyone on this list. She studied with Moore and Wittgenstein and got two PhD's. (In those days a women had to do twice as much as a man to get a job.) She was more on the philosophy side of logic, but certainly had math training. She wrote a textbook with her husband, known as Ambrose and Lazerowitz. Sane!
3. Paul Bernays (1888-1977): He worked with Hilbert on alternative set theories. Sane!
4. Evert Willem Beth (1908-1964): He helped to establish Logic as a discipline. Sane!
5. L.E.J. Brouwer (1881-1966): He thought that all math should be constructive. This point of view lost the battle if ideas; however, that does not make him crazy. The Wikipedia article quotes Martin Davis as saying: he felt more and more isolated, and spend his last years under the spell of totally unfounded financial worries and a paranoid fear of bankruptcy, persecution, and illness. However, Dirk van Dal en wrote a scholarly two-volume biography of Brouwer that indicates that Brouwer was not crazy. And I agree. Sane!
6. Georg Cantor (1845-1918): He had a new way of looking at infinity that was brilliant and is now accepted. That does not make him crazy. He was also convinced that Bacon wrote the plays of Shakespeare and that Joseph of Arimathea was the father of Jesus Christ. That does not make him crazy. However, he was obsessed with these views and was in and out of sanitariums. A few axioms short of a complete set.
7. Rudolph Carnap (1891-1970): I originally thought he was more of a philosopher; however, he published in thermodynamics and the foundations of probability. He fled Hitler's regime and later refused to sign a loyalty oath in America (during the McCarthy Era). His second wife committed suicide. He led an interesting life but was sane.
8. Alonzo Church (1903-1995): He invented (discovered?) The Lambda Calculus, proved that Peano Arithmetic was undecidable, and articulated what is now called the Church-Turing Thesis. These are all sane things to do. (Bob Soare distinguishes Church's Thesis from Turing's Thesis here.)
9. Haskell Curry (1900-1982): He worked in combinatory logic. There is a programming logic named after his first name! (see here). Sane!
10. Adolf Fraenkel (1891-1965): The F in ZF-set-theory. Provably Sane!
11. Gottlob Frege (1848-1925) He hated Jews, Catholics, and the French. That might make him unpleasant to hang around, especially if you are a French Jew who converts to Catholicism. However, that does not make him crazy. He is often given as an example of someone who was crazy, though the links ( here and here) argues for Frege being sane. I defer to the two links. Sane!
12. Gerhard Gentzen (1909-1945): He made the cut- Sane!
13. Kurt Godel (1906-1978): He stopped eating because he thought people were trying to poison his food. They weren't. A few axioms short of a complete set.
14. Jean Van Heijenoort (1912-1986): Best known in Logic for writing From Frege to Godel, a history of Logic from ... Frege to Godel (duh). Best known outside of logic for being Trotsky's secretary and later a historian of that movement. He was killed by his estranged fourth spouse. An interesting life, an interesting death, but he was sane.
15. Jacques Herbrand (1908-1931) Has the shortest lifespan (died at 23 in a mountaineering accident) of anyone on this list. He worked in proof theory. Sane!
16. Arend Heyting (1898-1980) He continued Brouwer's work on intuitionism. Sane!
17. David Hilbert (1862-1943): In Logiccomix they claim that Hilbert's son Franz had a mental illness and Hilbert cut off all contact with him. However, this refutes this and claims that Hilbert's son was only put away for 3 years and then re-joined his family. One may question if David Hilbert deserves a World's Greatest Father mug, but one cannot question his sanity.
18. Clarence Irving (1883-1964): He took exception to Principia's use of material implication. I'm impressed that he read and understood Principia enough to have objections. Sane!
19. Stanislaw Jaskowski (1906-1965): He worked in Intuitionistic Logics. Since I can't prove that he was crazy I assume he was sane.
20. William Ernest Johnson (1858-1931): He wrote three volumes on logic which showed technical expertise but was superseded by Principia Mathematica. This did NOT drive him crazy. Sane!
21. Philip Jourdain (1879-1919): He was interested in paradoxes and formed the card version of the liar's paradox. He also worked on algebraic logic. Quite sane. His sister Eleanor Jourdain claimed to have traveled through time and seen ghosts, but was not a logician.
22. Stephen Kleene (1909-1994): Kleene hierarchy, Kleene star, Kleene algebras are all named after him. He also proved the recursion theorem. Did this go to his head and make him insane? NO- he was totally sane.
23. Christine Ladd-Franklin (1847-1930): Her PhD was on Algebra and Logic. She faced problems being a women in a man's field but kept her sanity.
24. Stanislaw Lesniewski (1886-1939): He rejected axiomatic set theory (because of Russell's paradox) and tried to obtain other formal systems to replace it. A noble effort that failed. Still, he kept his sanity.
25. Adolf Lindenbaum (1904-1941): He proved Lindenbaum's Lemma- every consistent theory of predicate logic can be extended to a complete consistent theory. Like many major advances, profound at the time, easy to prove now. Certainly sane.
26. Leopold Lowenheim (1878-1957): The Lowenheim of Lowenheim-Skolem. See Skolem for more on that. A model of sanity.
27. Jan Lukasiewicz (1978-1956) Wikipedia says He thought innovatively about traditional propositional logic. Is innovatively a word? My spell checker does not think so but whoever wrote his Wikipedia entry thinks so. Sane.
28. Saunders Mac Lane (1909-2005) (He preferred the space between Mac and Lane.) His PhD thesis was on Logic and he also worked in Category theory. But he also did lots of Algebra. Sane.
29. Carew Arthur Meredith (1904-1976): He worked on obtaining short axiom basis for logic systems. Sane.
30. John von Neumann (1903-1957): Calling him a logician seems odd since he contributed to so many fields. Sane.
31. Jean Nicod (1893-1924): Co-discovered the Sheffer Stroke from which you can do everything in prop logic. Sane.
32. Pyotr Novikov (1901-1975): He proved the word problem for groups undecidable. His son Sergei Novikov won a Fields Medal in 1970 and, more importantly, is a professor at The University of Maryland! Sane.
33. Giuseppe Peano (1858-1932): His Wikipedia entry calls him the founder of Mathematical Logic and Set Theory. That seems over-the-top, but not by much. His axiom system is still the standard. Sane.
34. Emil Post (1897-1954) He introduced Turing Degrees. In the mid 1940's he posed Post's Problem which is to find a r.e. set (now called c.e.) that is neither decidable nor complete. This was solved in 1956 by Friedberg and Munhnik independently. He suffered from mental illness. A few axioms short of a complete set.
35. Mojzesz Presburger (1904-1943): Presburger proved Presburger Arithmetic was decidable. What are the odds of that!? Sane!
36. William Quine (1908-2000): He was more of a philosopher; however he did do some math. At Harvard he taught Symbolic Logic every fall for 50 years. That might drive some crazy; however, he was quite sane.
37. Frank Ramsey (1903-1930): The paper where he proved what is now known as Ramsey Theory was titled A Problem in Formal Logic and solved a case of the Decision Problem. He regarded himself as a logician so we shall too. Speculation: He would be surprised at where his work lead to (combinatorics) and then pleased that it lead back to logic again : The Large Ramsey Theorem (see also here) and much work in the reverse mathematics of Ramsey's theorem".
38. Raphael Robinson (1911-1995): He worked in Logic and Number Theory. He is probably best known for his work on tiling the plane. He married Julia Bowman (who changed her name to Julia Robinson) who was also a logician but born in 1919--- a little too late to be on this list. Having two academics in the same area get married might drive some crazy, but not them. Sane!
39. J. Barkley Rosser (1907-1989): He strengthened Godel's incompleteness theorem. Sane!
40. Bertrand Russell (1872-1970): He was obsessed with the quest for certainty; however, that does not make him crazy. He had several wives (not at the same time) and believed in open marriage. He was not crazy, just ahead of his time. Sane.
41. Moses Schonfinkel (1889-1942): He worked in Combinatory Logic. By 1927 he was in a sanitarium. The only non-famous logician on my list who was a few axioms short of a complete set.
42. Thoralf Skolem (1887-1963): He is best known for the Lowenheim-Skolem theorem: The notion that any consistent set of axioms has a countable model is very interesting--- One corollary: there is a countable model of the reals. Thinking about that might drive some crazy, but not him. Sane!
43. Alfred Tarski (1901-1983): The Banach-Tarski paradox is crazy; however, Tarski was not. Sane.
44. Alan Turing (1912-1954): He defined Turing Machines, though he didn't call them that. The story I had assumed was true is that the British Government made him take hormones (or something) to cure him of his homosexuality, and this drove him to suicide. But the story doesn't quite work with the timeline. He committed suicide a few years after he was forced to take drugs. Delayed reaction? Suicide for some other reason? Really was an accident? In any case, since his possible suicide is the only evidence that he was crazy I say Sane!
45. Nicolai Vasilev (1880-1940): The originator of non-Aristotelian logics. Sane.
46. Alfred North Whitehead (1861-1947): In Russell-Whitehead's Principia Mathematica they spend 300 pages proving that 1+1=2. This might drive some insane but not him. Whitehead was stark raving sane.
47. Ludwig Wittgenstein (1889-1951): He gave away all his money and seemed to be a self-hating Jew. Odd yes, but he was sane. (NOTE- Scott Aaronson left a comment that argues that Wittgenstein should be classified as a few axioms short of a complete set. I believe his arguments (they are backed up by facts) and may later redo the stats at the end of this post.)
48. Ernest Zermelo (1871-1953): The Z in ZF set theory. He disapproved of Hitler's Regime. Hardly crazy. Rota says that Zermelo was crazy but neither I nor this post have been able to find any evidence of this. Zermelo did spend time in a hospital for lung problems, which may have confused Rota.

So what to make of all of this?

1. Cantor, Godel, Post and Schonfinkel were crazy. So we have 4 out of 48 were crazy. That's around 8%. This website claims that 6% of all people are crazy. So 8 seems high, but the sample space is pretty small. Conclusion: Same as the posts on the same topic referenced at the beginning: the notion that people in logic are crazy is not well founded. In addition, this post argues that the problems Cantor, Godel, and Post had were unrelated to their study of logic. (There was no comment on Schonfinkel.)
2. AH- but Rota said that so many outstanding logicians were crazy. Since three of the four who I say were crazy were outstanding there may be a point here. One could look at who on my list was outstanding and see what percent of them logicians were crazy. However, determining who was outstanding is even harder than determining who was crazy, so I leave it to others to continue this work.
3. There were some on the list that in my opinion were sane but others think were crazy: Brouwer, Frege, Turing, Zermelo. Perhaps more. If enough of them turn out to be crazy then there may be something to this logicians are crazy theme; however, I doubt this will happen.
4. Was it crazy to spend so much time and effort on this one post? I am not on the logic list, nor was I born between 1845 and 1912 so the answer is not relevant to the study.
5. This blog posting has a crazy number of links: 71. That breaks the record for this blog which was held by this entry which had around 37.

Math, the Universe, and Everything: Max Tegmark's Interpretation of reality (guest post)

(This is a guest post by Nadia Jones who blogs at online college about education, college, student, teacher, money saving, movie related topics. You can reach her at nadia.jones5@gmail.com. Why is she doing a guest blog? She asked me, pointed me to some of her work, and suggested some topics that seemed reasoanble. You can do that too!.)

Math, the Universe, and Everything: Max Tegmark's Interpretation of Reality

Despite how much mathematicians like to think that their work is the end-all, be-all, it can be sometimes quite complicated to explain to friends and family who are not familiar with the pleasures and perils of doing high-level math exactly why it is so important. At the same time, however, devout followers of math still realize that there is an element of get-your-head-out-of-the-clouds, especially when dealing with abstract mathematics that do not directly apply to career paths that are lucrative or have potential for advancing research in an academic setting.

But what if someone were to tell you that everything that we know, everything that we feel, is all a complex series of mathematical structures? Of course, many have theorized that math and disciplines that are heavily math-based like physics, are very accurate ways to describe the world as it exists, but cosmologist Max Tegmark takes things one step further.

In an absolutely fascinating article published in Discover Magazine, here Tegmark explains his theories that were almost impossible to publish or even be taken seriously a few years ago. Taking a leaf out of string theory's book, Tegmark has endeavored to explain what is known in popular science as "alternative" or "parallel" universes. In more serious academic circles, these universes are known as "multiverses." Tegmark notes that others have posited three multiverses, but he has added a fourthâthe mathematical multiverse. (Another article about Tegmark is here.)

Tegmark describes this particular multiverse as such in the Discover interview:

Galileo and Wigner and lots of other scientists would argue that abstract mathematics describes reality. Plato would say that mathematics exists somewhere out there as an ideal reality. I am working in between. I have this sort of crazy-sounding idea that the reason why mathematics is so effective at describing reality is that it is reality. That is the mathematical universe hypothesis: Mathematical things actually exist, and they are actually physical reality.

Although Tegmark's work has not received as much critical attention as other mathematician's work, it his is melding of physics, pure math, and cosmology that has helped his research be more seriously considered. For more information on Tegmark's theories, check out his MIT hosted website, The Universes of Max Tegmark

A slightly diff take on Lipton's use of Ramsey's Theorem

This post takes an idea of Dick Lipton's in a slightly different direction.

ω(G) is the size of max clique in G.

Recall that, for all 0 < δ₁ < δ₂ < 1, the following problem is NP-hard: Given a graph G with the PROMISE that either ω(G) ≤ n^δ₁ OR ω(G) ≥ n^δ₂, determine which one it is. Output NO in the first case and YES in the second case. (Reference: David Zuckerman proved the result here by derandomizing a result of Johan Hastad that had as its conclusion ZPP=NP rather than P=NP. See here for Hastad paper.)

Note the following,

If ω(G) ≥ n^δ₂ then, by Ramsey's Theorem and the current bounds known on the Ramsey numbers, for ANY 2-coloring of the edges of G there will be a mono clique of size (0.5)*(δ₂)log n. (Slightly larger values can also be obtained.)

This gives rise to the following POSSIBLE RTIME(n^{O(log n)}) algorithm for the promise problem.

1. Input G
2. Do the following n^{Alog n} times Or until you get a NO. (A is a constant that we pick later.)
   1. Randomly 2-color the edges of G
   2. Look for a mono clique of size (0.5)*(δ₂)log n. (This takes n^{O(log n)} time.)
   3. If you DO NOT find one then output NO and stop. (In this case you KNOW the answer is NO.)
   4. Otherwise try again.
3. (If you got here then every coloring you tried had a mono clique of size (0.5)*(δ₂)log n.) Output YES. (You are NOT SURE that this is correct.)

The algorithm clearly runs in time n^{O(log n)}. But does it work? And what should A be?

1. IF ω(G) ≥ n^δ₂ then the algorithm will correctly say YES.
2. IF ω(G) ≤ n^δ₁ then will the algorithm find a coloring that shows this? Or more precisely, will this happen with high prob?

In order to get NP in RTIME(n^{O(log n)}) we need the algorithm to work for SOME 0 < δ₁ < δ₂ < 1. Hence we need the following CONJECTURE to be true:

There exists 0 < δ₁ < δ₂ < 1, A, and a function p(n) = n^{Alog n} such that the following is true: For almost all graphs G with ω(G) ≤ n^δ₁ the prob that a rand 2-coloring of the edges will have a mono clique of size (0.5)*(δ₂)log n is LESS THAN (1-p(n)). (ADDED LATER: Almost All Graphs means for all but a FINITE number of graphs.)

So, what to make of this?

1. One MAY think the following; Since we DO NOT think that NP is in RTIME(n^{O(log n)}) the conjecture is false. Perhaps it can be PROVEN false (unconditionally) using the techniques of Zuckerman or Hastad, or other techniques in the area.
2. Is our confidence that NP is not in RTIME(n^{O(log n)}) SO STRONG? We could at least TRY to prove the conjecture.
3. One could put the correct Ramsey Number, and a good set of coin flips, into an advice string. This would yield an algorithm in DTIME(n^{log n})/poly. A slighly weaker conjecture would suffice to prove this algorithm works.

FOCS Accepts

This list of FOCS accepts are out, with abstracts, with PDF links (via Kintali) and in Algorithmic Game Theory (Nisan) and Algorithms (Eppstein). The FOCS Conference will be held October 23-25 in Palm Springs.

Looks like a strong collection of papers. Lots of tight bounds. I'm a sucker for tight bounds because it means you have the right answer and less chance of follow-up papers.

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

Randomness buys depth for approximate counting by Emanuele Viola. Buys you exactly two layers of AND-OR gates. Viola has another nice paper Extractors for circuit sources.

A Small PRG for Polynomial Threshold Functions of Gaussians by Daniel Kane. I like Gaussians because you can look at them at any angle and the distribution doesn't change.

Optimal bounds for quantum bit commitment by André Chailloux and Iordanis Kerenidis. Perfect quantum bit commitment is impossible but you can do better than classical. This paper shows exactly how well you can do.

Information Equals Amortized Communication by Mark Braverman and Anup Rao. A nice connection between information theory and communication complexity. I wonder if this can be tied into Kolmogorov complexity.

Scooped by 400 years

This article claims that finding the area under a curve by dividing up the region into rectangles is helpful. Maybe they could take some sort of... limiting process where the rectangles get skinnier. Who knows- they may be able to get an EXACT formula for, say, the area under the curve y=x² from x=0 to a. (The Wikipedia entry on the article claims that it rediscovered the trapezoid rule. See here.)

I was going to begin an April fools day post with the above; however since the article (which is real) is already out there and being criticized here, here, here, here, and here, I decided to not go that direction. I have a different angle.

How often do you get a result and then find that someone else already had it? Is this MORE or LESS common in the internet age? There are several competing forces:

1. With Search tools its EASIER to find whats already out there.
2. With email or various websites like stack exchange it is EASIER to ASK if something is already known.
3. Some people are gathering up stuff and putting it on line making it EASIER to find- if you know where to look. (Examples: Website of all of Ronald Graham's papers, or Website of some number theory related to VDW stuff). I thought I found a website of secret sharing papers and when I tried to find it again I hit several sites about different kinds of secrets.) ADDED LATER: updated site for Ron Graham's papers: here, and list (but not links) of papers on secret sharing are here.)
4. Areas are getting more specialized and each use their own terminology making it HARDER to know if what you have done is original.
5. There is so much is out there that it is HARDER to see whats already been done.
6. NOT everything is online. The material that is not online might be HARDER to find then they used to be.

There are other issues. What if your proof is cleaner but essentially the same? What if it truly is independent? What if people come from completely different motivations? What if you read a result, forget that you read it, and later think its yours (its not). I've seen all of these things things happen and in all combinations.

The Quantum Tivo

Chuck Klosterman writes on watching sports on tape delay and Jeff Ely follows up. I take a quantum mechanics view: A sporting event saved on my Tivo is like Schrödinger's cat: Until I watch the game or otherwise learn the result, the outcome hasn't been determined. There are multiple worlds with different game outcomes and until observed we do not know which world we live in. There is no physical difference between watching an event live or delayed. If I get partial information on the outcome, like a half-time score, then the outcome is then just conditioned on this partial information.

We also have entanglement. Two people can be light-years apart watching the same gave on their Tivos. They will see the same outcome. The Tivo's are entangled. Even though in each person's view the outcome is random, they will be random in the same way.

That's where the analogy to quantum ends. Entangled Tivos can't explain Bell's inequalities.

Let me add a reason for watching on tape delay: The fast-forward button. If a game looks one-sided, I can speed up the game to see if it gets close again. And some sports (yes, soccer, I'm talking about you) are vastly improved with the entire game watched in double speed. 

The Sputnik Moment

Earlier this month the New York Times had a story Computer Studies Made Cool, on Film and Now on Campus followed-up on a series of short essays on Computer Science's 'Sputnik Moment'. No doubt computer science is a hot major again, the number of CS majors at Northwestern has doubled over the past few years and I hear similar stories elsewhere. My daughter's high school will offer computer science for the first time in years. Big companies are using real computer science ideas from IBM's Watson to Netflix's recommender systems to nearly everything Google does. Obama talks robots at Carnegie-Mellon.

Mehran Sahami called this Computer Science's Sputnik Moment, evoking the phrase used by the president in his State of the Union Speech.

 Half a century ago, when the Soviets beat us into space with the launch of a satellite called Sputnik, we had no idea how we would beat them to the moon.  The science wasn’t even there yet.  NASA didn’t exist.  But after investing in better research and education, we didn’t just surpass the Soviets; we unleashed a wave of innovation that created new industries and millions of new jobs.

This is our generation’s Sputnik moment.  Two years ago, I said that we needed to reach a level of research and development we haven’t seen since the height of the Space Race.  And in a few weeks, I will be sending a budget to Congress that helps us meet that goal.  We’ll invest in biomedical research, information technology, and especially clean energy technology -– (applause) -- an investment that will strengthen our security, protect our planet, and create countless new jobs for our people.

The fate of that budget remains unclear in the current congress.  But there's an excitement for CS and science in general that we haven't seen since the 60's.

Computer Science seems to run in cycles, we build up excitement (the spread of personal computers in the early 80's, the Internet in the 90's and social networks and machine learning today) and soon after people see these as commodities and the excitement wanes. We need to not squander the current good will, find a way to keep CS exciting. The computer science story has a long way to go. Computer science needs to be a front office profession leading the way and not just in the back office keeping it going.

Math on FUTURAMA and LAW AND ORDER:CI

MATH ON TV

FUTURAMA mentions the Banach-Tarski Paradox! In the June 23, 2011 episode Professor Farnsworth invents a Banach-Tarski-Dupla-Shrinker which takes a blueprint of an object (like a sweater or Bender) and some matter and then produces two smaller but otherwise identical copies of the original. The real Banach Tarski Paradox takes one object and produces two of the exact same type. The writers might have felt that was just a little too weird. See here for a full description of the episode. The episode aired on thursday, and today, Tuesday, a full description is on Wikipedia. This surprised me (so fast!) but did not surprise my great nieces and nephews.

LAW AND ORDER: CRIMINAL INTENT had its last episode Sunday June 26, 2011, thus ending a rather long running show which was part of a rather long running (and still running) franchise. Here is the whole list: Law and Order (1990-2010, 456 episodes), Law and Order: Criminal Intent (2001-2011, 195 episodes), Law and Order: LA (2010-2011, 22 episodes), Law and Order: SVU (1999-2011, 272 episodes, and still going), Law and Order: Trial by Jury (2005-2006, 13 episodes), Law and Order: UK (2009-2011, 26 episodes, and still going). 456 episodes is HUGE! Check out this list of long running TV shows. The list is only updated once a year This surprised my great nieces and nephews (so slow!) but did not surprise me.

I recall three episode of Law and Order:Criminal Intent that mentioned math. I am sure there are more.

In the episode Bright Boy there was a school for gifted children in math that tried to get 10 year olds to work on the Riemann Hypothesis. It was not clear if they wanted them to solve it as children (which seems absurd) or as adults later in life (not absurd but a real long shot). The reason I find it absurd that a 10 year old could solve RH is that cleverness and brilliance is not enough- you have to actually have learned a great deal of math, perhaps too much for a 10 years old to have learned. Problems that need lots of KNOWLEDGE really can't be solved by bright 10 years olds or amateurs, no matter how brilliant they are. (See here for a post of Lipton's about of when amateurs helped solve math problems.) Getting kids interested in math by having them work on RH is the opposite of using Math competitions. Lance and I discussed math competitions as a way to interest kids in math here. Which is better? Even if you get bright pre-high school students working on problems, having them work on RH would just lead to frustration. Are there math programs that have student work on real open problems? How about phony open problems (the mentor knows the answer ahead of time). Some REU's do this for College students, but is there anything like this for High School Students?

The episode Inert Dwarf involved a brilliant physicist who, for medical reasons, was in a wheelchair (modeled vaguely after Stephen Hawking). One point of interest: he had a password that was based on hard physics and hence uncrackable. Gee, I thought that you just need to make sure your password is (1) not a word in any language (2) long enough, and (3) used Upper Case (easy for ME), lower case, numbers, and punctuation symbols. Unless it was some sort of quantum system (the episode did not indicate this) I can't see how hard physics can make a password uncrackable.

In some episode this season (I forget which one) Goren (the detective) was given the following riddle by his psychologist: There are two doors and two guards. One of the doors leads to heave, the other to hell. One of the guards always tells the truth and one always lies. You get to ask one guard one question and then you must pick a door. Goren is supposed to some sort of genius who also knows a great deal of stuff so I'm surprised he didn't know it. In the last episode of the entire series, To the boy in the blue knit cap, he answers it correctly. I think that was supposed to be symbolic or meaningful or something, but I didn't see why. (Bad writing? I'm being dense?) (ADDED LATER- ACTUALLY GOREN ASKED THE PSYCHOLOGIST THE QUESTION WHICH MAKES MORE SENSE IN TERMS OF WHO-KNOWS-WHAT.)

Bright Boy and Inert Dwarf had the same problem that many TV shows have: If the real world fact do not make the plot work, the writers change the real world facts. Numb3rs did this with Math quite a lot.

FCRC 2011. Part 2 of... probably 2.

(A workshop on Coding, Complexity and Sparsity will be held at Ann Arbor, August 1-4, 2011. See this website.)

More thoughts on FCRC.

1. Russell Impagliazzo is one of the Luddites (spellcheck made me use a capital L) in the field (I'm another, and I know of one more person in Complexity who could be called a Luddite) who famously uses transparencies at talks. BUT, he has entered the 1990's- he gave a talk on PowerPoint (or something like it). (Spellcheck made me use two capital P's). I asked him why he made the change. The ability to SCAN IN his old transparencies was one of the keys. (Of course, he probably could have done that 10 years ago...) The talk was on his world view. I don't mean how he feels about the debt ceiling or Libya or Global Warm ning or the problems in FILL IN ANY COUNTRY THAT HAS PROBLEMS. I mean his worlds:
   1. Algorithmica: P=NP
   2. Algorithmica: NP ⊆ BQP. This was in a talk he gave at a workshop. Its in a link below but was not in his CCC talk.
   3. Heristica: P ≠ NP but NP problems are tractable on average for any samplable distribution.
   4. Pessiland: There are NP problems hard an average AND there are no one-way functions.
   5. Minicrypt: P ≠ NP, one-way functions exist, but public key crypt is impossible.
   6. Cryptomania: P ≠ NP, public key crypto is possible.
   For the CONTENT of his talk see Lance's blog entry. Blogs on his world are here and here. There was a workshop in 2009 on the worlds. You can actually see Russell talk about it, with transparencies, as a link from this page Russell's paper on the worlds was hard for me to find since its title is A personal view of Average Case Complexity which you can find on his web page. A POLL on which of Russell's works we live in would be interesting, but I leave that for someone else to do.
2. Les Valiant made the cover of CACM! I hope that eases the pain of no longer being the best theorist who had not won a Turing award.
3. Alan Borodin was the only one at STOC who had been to the first STOC (1969). I asked him if, at the time, he thought there would be a STOC 2011. He said that as a grad student at his first conference he thought more of it as being HIS first conference than STOCs first conference.
4. Several of my lunches were with people NOT going to STOC or CCC. A bunch of PLDI grad students asked me what he hot area in Theory was. I told them (1) Quantum is still strong, which surprised me, and (2) Algorithmic Game Theory seems hot now. Any other candidates for a short answer to this question if asked? Be prepared with an answer before the next FCRC.
5. I heard that one of the logistic problems was that different conferences gave out different stuff (bags, pens, paperweights. Paperweights?). I also heard some sniping How come that conference got so much better pens than we got?.
6. Jin Yi Cai gave a great talk at CCC about dichotomy for #CSP. Certain counting problems are in P and other ones are #CSP complete. Cai has managed to classify exactly which are which. I asked him about the CSP problem- is there any hope of a dichotomy theorem there. He said This talk is on Counting CSP. I asked him How Narrow are you?. He challenged me to read a 300 page paper in the field before accusing him of being narrow. Over lunch he gave me a better answer: Counting problems are hard in general so they have to be rather special to be in P, so classifying is doable. By contrast, CSP problems can be easy so its much harder to tell which are which.
7. The only ones at CCC that were at the first CCC were probably Fortnow, Allender, Gasarch, Selman, Homer. The founders of the conference were Book, Hartmanis, Mahaney, Selman, and Young. Selman is the only one who is still doing theory. (Book and Mahaney are deceased, Hartmanis and Young are retired.)
8. I don't bring a laptop to conference (I don't have one); however, I borrowed Marius Zimand laptop to catch up on some websites during one of the breaks. Then a talk came that I wanted to see and I could not pull myself away from the laptop. It can be addictive. I will never do that again. Other distractions such as doing math on paper I can break away from, but web surfing was hard to break away from. What are your experiences with this?

Blog Redesign

We redesigned the blog to use the newest Blogger features. This lets me not have to maintain the 2002 html code we had before and lets us have some new features like adding comments directly on the post page.

We, of course, kept the signature background color.

Creating an Email System at Cornell

Email celebrates its fortieth anniversary so let me tell the story of my job for three summers, and part-time during the academic year, while an undergrad at Cornell University: Creating an email system from scratch.

In my sophomore year (1982) I took an computer structure course. I had a heavy set of final exams and papers so I did the final program for this course early and turned it in the last day of class to the instructor, Steve Worona. In that class you could scale assignments and tests from 0.75 to 1.5 to make them count more or less. When I turned it in, Worona asked me why, if I'm turning it in a week early, did I scale it at 0.75? "You never give me A+'s on the programs and I didn't want to lower my grade."

That was perhaps my most obnoxious moment but it got me noticed and Worona, who worked for computer services, offered me a programming job. We would create a new email system for Cornell. Cornell had an email system written in some scripting language, slow and clunky. We wouldn't use any fancy high-level language, we would code directly in IBM 370 assembly language. We would do it all ourselves, user interface, database for storing messages, interactions with SMTP servers, etc to maximize efficiency. No small task which is why it took me nearly three years.

IBM Assembly language was quite bloated with instructions. There was a command called "Edit and Mark" that went through a range data making modifications based on some other data. This was a single assembly language instruction. We used to joke that there was a single instruction to do your taxes.

Cornell at the time was a gateway between BITNET ("Because It's Time NETwork", connecting about 30 universities in US and Europe) and a fledgling ARPANET, the precursor to the Internet. BITNET worked with files, ARPANET one line at a time so there was a special file-based Batch SMTP to transmit email between the two. The fun I had working this all out.

As a test bed, my email system was used in only one building, Day Hall, which held the university administration: President, Provost etc. Great pressure to make sure there were no bugs.

One day a company that helps get people green cards sent an email to everyone on BITNET. My first piece of spam.

As a side project I helped write an ARPANET interface into CUINFO, an early electronic information system at Cornell. That was pretty simple, we just used the Telnet interface into a different port. This is basically what HTTP does now. I could have invented the Web!

In my senior year I told Steve Worona that I was planning to go to graduate school in theoretical computer science.

"You really want to spend your life shaving log n factors off algorithms?"

"Yes I do." (But I never did, since I went into computational complexity)

"Well the world just lost a great programmer."

As soon as I left Cornell my email system was scrapped for a commercial product. C'est la vie!

I am conducting a NEW POLL on P vs NP

In 2002 I did a poll that appeared as SIGACT News Complexity Theory Column 36 on what people thought of P vs NP. See here.

That article is now linked to on Wikipedia and (much to my surprise) has come to be the AUTHORITY on what people were thinking then.

TEN years have passed! It is time to take the pulse of the community again. Hence I will ONCE AGAIN (!) be conducting a poll to appear in a SIGACT News Complexity Column.

SO- I would like you to email gasarch@cs.umd.edu (in LaTeX or plaintext) the answers to the questions below. (Comments to the blog will not be counted as answering the poll.) I would like to get this poll written this summer, so I will give a deadline of October 31, 2011. (I may extend this if I do not have enough responses.)

1. Do you think P=NP or not? You may give other answers as well.
2. When do you think it will be resolved?
3. What kinds of techniques do you think will be used?
4. Will the problem still be relevant given advances in algorithms and in SAT Solvers?
5. Feel free to comment on anything else: Graph Isomorphism, Factoring, Derandomization, Quantum computers, and/or your own favorite problem.
6. Do I have your permission to print your response? I will do this for some people--- how many depends on how many answer the poll.
7. What is your highest degree in and where is it from? This information will be used for statistics only.

Theory Jobs 2011

The computer science job market never comes to a complete close. CI Fellows are still being decided, Oxford is just starting its search for an algorithms professor. But many jobs have settled so it is time for our annual list of who is going where. Many of the strong theory groups have hired this year, surely spurred on the by the competition for the new Simons Institute but still we have way too many theoretical computer scientists doing multiple postdocs or taking industrial or financial jobs.

For optimal crowdsourcing I created a Google spreadsheet that everyone can edit and for all to view. Do not add or modify the sheet unless you are sure a job has been offered and accepted. It may take some time for the embedded sheet below to update to the latest changes.

FCRC 2011. Part I of... maybe I, maybe more.

I do not log on at conferences so I came back to 400 emails. Exactly 400- not sure how I managed that. TODAY I am posting about a few things from FCRC, I may post more next week as I remember them.

1. CCC finally no longer has proceedings. Most conferences at FCRC did not have proceedings. ISCA, the International Symposiusm on Computer Architecture, still has proceedings. I asked someone from ISCA why they still have proceedings. They gave an answer which boils down to That's the way we've always done it. Also, ISCA has MONEY so they don't need to save money as well.
2. The best student paper award at STOC went to Analyzing Network Coding Gossip made Easy by Bernard Haeupler. Great Talk!
3. The best paper award went to Electrical Flows, Laplacian Systems, and Faster Approximation of Network Flows in Undirected Graphs Electrical Flows, Laplacian Systems, and Faster Approximation of Network Flows in Undirected Graphs by It also might be a contender for longest title. A better title might have been Electrical Flows and Networks Flows. Great talk. Looks like a paper I can actually read and understand. Network flows is a well studied problem- one slide had over 30 references on it. (ADDED LATER: A helpful commenter pointed out that The Best Paper award was actually shared by the FLOWS paper and also by Subexpontential lower bounds for randomized pivoting rules for the simplex algorithm by Friedmann, Dueholm, Hansen, and Zwick. This seems to be unknown to thiswebsite.) (ADDED EVEN LATER- The page I just pointed to now DOES know about the two awards and has been updated.)
4. I skipped the talk on The Computational Complexity of Linear Optics by Aaronson and Arkhipov since I saw some version of it a while back. My mistake- talks I see twice I actually understand, and I heard it was an excellent talk. Going to Scott's webpage to make this post I spotted a paper on using Linear optics to prove the PERM is #P complete. THATS the paper I really want to read! Serendipity is alive and well.
5. Proof Complexity means two different things: (1) proving that theorem X NEEDED to use Axioms Y or had to be nonconstructive of level Z, and (2) proving that certain formulas need exponential number of steps to prove they are not satisfiable. This talk tried to use a theorem (the Paris Harrington Ramsey Theory) that is not provable in Peano Arithmetic requires a long proof in some systems. They end up saying that if a version of Paris Harrington (that CAN be proven in PA) has a short proof then Pigeon hole principle has a short proof. This is rather odd- the only thing they can prove DIRECTLY requires long proofs is PHP, so everything reduces to it. The talk is here, the paper is here, for a writeup of the version of Large Ramsey they were talking about see here
6. Ryan Williams won the Best Paper award at CCC for this paper. Lance did an excellent blog on the result a while back here. (NOTE- the link to the paper seems to be down now. Hopefully it will come back up soon.)
   1. On his website it has next to the paper Will receive Best Paper award. Did he put that there when he submitted ASSUMING that he would win it? That doesn't sound right. Did he put it there when he found out he would win it? That doesn't sound right either-- being notified that you won it is the same as receiving it.
   2. I would like to think that he was inspired by my April Fools Day post of 2011 which said we should all go out and PROVE things instead of whining about barriers and oracles. Actually its the other way around- Ryan inspired the post when, at some DAGSTUHL, we were all saying what we can't prove and he said When do you think we will separate NL from PSPACE? I fell for it and said Not for a while at which point he reminded me that its already known. That inspired the post.
   3. Whenever a new result appears the question arises Did it use new techniques or a clever combination of old techniques. Or more egocentric Could I have proven that? For example, if Wiles proof of FLT is really the only way to do it then Gauss could not have done it. Ryan's proof looks like a really really clever combination of older results. This is NOT to downgrade it. And NO, I could not have done it. A better question: will it lead to MORE results? IS P vs NP just around the corner? No.
7. CCC 2012 is in Portugal. CCC 2013 is at Stanford co-located with STOC. CCC 2014 MIGHT be in Koyoto Japan. Is that a good idea? If there exists N people who CAN go if its in Japan and NOT otherwise but M people who normally go but now can't then if N and M are roughly the same or even if N is a bit bigger, than I think we should do it. Not sure what the real values of N and M are.
8. Some grad students I talked to think that CCC and/or FCRC should have an after-conference Survey Form to fill out about the conference so that they can improve things for next time. I agree!

New Complexity Vidcasts

The newly renamed Computational Complexity Channel features two new vidcasts Bill and I hosted last Thursday from San Jose.

Bill's Enigma

Interview with Ryan Williams

Talks I Missed

The Complexity conference comes to a close today and I head back to Chicago. I tend to go to few talks, preferring hallway conversations, but occasionally I hear about a few great talks that in retrospect I wish I attended.

The first STOC talk, The Power of Simple Tabulation Hashing by Pătraşcu and Thorup. Simple hashing scheme that takes a random function of pieces of an input and XORs them together. Surprisingly this simple scheme is close to looking like a fully random hash function for a variety of purposes.

The last of Thursday's Complexity talks, Property Testing Lower Bounds via Communication Complexity by Blais, Brody and Matulef. An easy reduction from communication complexity to property testing gives a large number of new lower bounds for property testing based on known bounds for communication complexity.

Another FCRC comes to an end. Next year in New York (STOC) and Porto (Complexity).