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
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.
We really understand the complexity theory of space
Anil Ananthaswamy is the author of the book The Edge of Physics. He also consults for Britain’s New Scientist weekly magazine, and wrote an interesting article on space and time entitled, “Space vs time: One has to go—but which?” He started the article with this:
TO ISAAC NEWTON, space was the “sensorium of God,” the organ through which the deity surveyed His creation. It was absolute, unchanging, infinite. Flowing through it “equably without regard to anything external,” as Newton wrote in his great physical treatise, was another similarly absolute heavenly creation: time.
Today I wish to talk about what we know about space, not space as viewed by Newton, but space as used in complexity theory. For us complexity theorists, space is a measure of the cost of a computation of a Turing Machine (TM). It is the number of squares that a TM uses during a computation. It is not an “organ,” nor is it absolute and unchanging; it is simply the number of different cells written to by the computation. Meanwhile time is the number of steps that a TM takes during a computation. Read more…