In Praise Of Chalk Talks
Chalking up a terrific talk on bit compression
Winsor McCay was a cartoonist and animator in the early part of the twentieth century, and authored the comic strip Little Nemo. He may not have invented the chalk talk—that could have been Frank Beard—but McCay made them popular with his vaudeville act, in which he drew faces and then progressively aged them. While these were over a hundred years ago, it appears from the history that blackboards were used in schools in India a thousand years ago.
Today I want to talk about content and delivery, about a great chalk talk and a great result.
A Really Scary Thought
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…
Pretending In Number Theory
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…
A Request That We Passed On
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…
Teaching Helps Research
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.
Read more…
512
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…
Proving Cook’s Theorem
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 
Rating FOCS 1973
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.
Read more…
Stealing Strategies
How constructive are strategy stealing proofs?
David Gale was a famous mathematician and economist, who passed away just over five years ago. I had the honor of meeting him while I was on the faculty at Berkeley years ago; Gale spent most of his career at Berkeley, ending it as a professor emeritus.
Today I want to talk about his famous proof that there is a winning strategy for the game Chomp. Read more…
Two Bits About FOCS 2013
How to save money and attend the upcoming FOCS
John Cherniavsky is a theorist who published a paper in FOCS 1973, forty years ago. He has done much great work at NSF, and is currently the senior science advisor for research in the education directorate at NSF. The full name of his directorate is the Division of Research on Learning in Formal and Informal Settings. More on his paper and his work in a moment, but first a public announcement about one of our formal settings that also promotes informal research contact.
Today Ken and I want to remind you about the upcoming FOCS 2013, and look back at FOCS 1973. Read more…
