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…

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…

What those phrases really mean ${\dots}$

Eduardo Tengan is a mathematician at the Institute for Mathematical Sciences and Computation in Sao Paulo, Brazil. He has written a delightful set of notes titled, “An Invitation to Local Fields.” He also has a great sense of humor. Go check his home page for a proof.

Today I thought I would quote some of his cool comments and add some of our own.

Mary Jean has passed away—she is already greatly missed

Mary Jean Harrold started like many of her generation, as a math major. She earned her BS and MA degrees in mathematics from Marshall University. Then she received her MS and PhD degrees in computer science from the University of Pittsburgh.

Today I will talk about Mary Jean. I talk with sadness because she passed away this week, but also with appreciation. Read more…

Why it may take a ‘miracle’ to catch some cheaters

 source, where he’s right after Charles Dickens

John Littlewood really existed. He appeared as second author on so many papers with Godfrey Hardy that some believed him to be a fictional appendage. He kept on writing papers for a quarter century after Hardy’s death in 1947 and lived into his 90′s, passing away in 1977. Read more…

How teaching helps you understand proofs

Stanislav Žák is a theorist who has made important contributions to complexity theory. He was at the Institute for Computation Techniques of the Technical University in Prague thirty years ago when he proved the theorem below. He is now affiliated with the Institute of Computer Science of the Czech Academy of Sciences, where he has just written a new paper on “A Turing Machine Distance Hierarchy” with his colleague Jirı Šıma. He should not be confused with Professor Stanislaw Żak of Purdue’s ECE Department.

Today I want to discuss a classic theorem of Žák that is in the textbooks, and why it is a bit tricky to understand.