A scary question, a really scary question

Vincent Price was just featured last Thursday night with a series of his movies, scary horror ones shown on Turner Classic Movies. Price was known for his distinctive voice and special smirk, which was perfect for these movies. The series was in honor of Halloween. October 31 is the day of trick-or-treating, wearing costumes, going door-to-door to get candy, telling scary stories, and watching horror films.

Today Ken and I want to raise a simple fundamental, and scary question. Read more…

A definition is often more important than a theorem

Andrew Granville is a British mathematician and a world expert in analytic number theory. He came to Canada for his PhD, and after a postdoc in Toronto and time at IAS in Princeton, joined the faculty of another Georgia university, Tech’s arch-rival in football, the “Bulldogs” of the University of Georgia. After serving as Chair of Mathematics there he went back to Canada in 2002 to join the Université de Montréal, where he is today. Interestingly his university also has a football team, where “football” does not mean soccer like in Britain, but does not quite mean football. It plays Canadian football, which uses a wider and longer field for teams of 12 not 11 but allows only 3 downs to advance 10 yards. Is that football? It depends on how you define “football.” Anyway, his new team is not a rival of ours.

Today I wish to discuss the role of the right definition in advancing mathematics and theory in general, and Granville’s relatively new brilliant definition in particular. Read more…

Peto de la Simons Instituto

Alistair Sinclair is a “British computer scientist and computational theorist”—to quote our friends at Wikipedia. I know him more as Berkeleyan than British, but Ken knew him long ago in Britain itself, so what do I know. Wherever he is, he is one of the leaders in the world on anything concerning randomized algorithms of all kinds. He has won the prestigious Gödel and Fulkerson Prizes. The latter was for his brilliant work on the permanent, in a long project that culminated in his famous breakthrough paper with Mark Jerrum and my Georgia Tech colleague Eric Vigoda.

Today I want to talk about a request we just got from Alistair that Ken and I decided to take a pass on, and give a reason why we did so. Read more…

How teaching interacts with research

Tim Budd is a computer scientist who works mostly in programming theory and practice. He once was a graduate student of mine, and did his thesis work on an APL compiler. Ken recalls that when he asked a certain undergraduate classmate in 1980 whether anyone had written a compiler for APL, the friend replied “A compiler for APL? That would be worth a Nobel Prize!” Well, we have gone another year of missing on our recurring prediction that a person we recognize as a computer scientist will win a Nobel Prize, though the prize in chemistry this year came close.

Today I want to talk about the relationship between teaching basic material and doing research.

This is our 512th post

Jim Carrey is an actor known best for his comedic roles, and is considered one of the top movie stars in Hollywood. He starred in the movie The Number 23, which is based on the the 23 enigma: a belief that all of life is directly connected to the number 23, often in an indirect manner.

Today Ken and I want to thank everyone who reads and supports GLL; thank you very much. Read more…

Another proof idea using finite automata

Steve Cook proved three landmark theorems with 1971 dates. The first has been called a “surprising theorem”: that any deterministic pushdown automaton with two-way input tape can be simulated in linear time by a random-access machine. This implies that string matching can be done in linear time, which inspired Donald Knuth and Vaughan Pratt to find a direct algorithm that removes a dependence on the input alphabet size. This was before they learned that James Morris had found it independently, later than but without knowledge of Cook, and their algorithm is now called KMP. Fast string matching has thousands of applications. Second was his characterization of polynomial time by log-space machines with auxiliary pushdowns, a fact which may yet help for proving lower bounds. Then there was his third result, which appeared at STOC 1971, and was given a “slif” (stronger, later, independent form) by Leonid Levin.

Today I want to present a proof of the famous Cook-Levin Theorem that ${\mathsf{SAT}}$ is ${\mathsf{NP}}$-complete, and also mention one used by Ken. Read more…

Can we rate the research topics from 1973?

Janos Simon is one of Juris Hartmanis’ illustrious students. He did not have a paper in FOCS 1973, but did have one with Juris at FOCS 1974, which went into his PhD thesis in 1975. He has been a mainstay of the University of Chicago Computer Science Department ever since. He posed a very interesting question as a comment in our recent discussion on FOCS 2013.

Today I am going out on a limb, taking a chance, potentially losing, all because of his question about FOCS 1973.