Skip to content

The Problem of Catching Chess Cheaters

June 18, 2014

The detection game


Howard Goldowsky is the author of this month’s Chess Life cover story. Every month this magazine is mailed to about a quarter of a million players, but this cover story was deemed so important by Daniel Lucas, Chess Life’s editor, that he made it available online, free of charge.

Today I want to talk about this story because it is interesting, important, and it raises some novel theory questions.
Read more…

Honor Thy Fathers Correctly

June 15, 2014

Partly a rant from today’s New York Times

source—note the “\cdots”

Aryabhata is often called the father of Indian mathematics, and can be regarded as the progenitor of many modern features of mathematics. He completed his short great textbook, the Aryabhatiya, in 499 at age 23. Thus if there had been a “STOC 500,” he could have been the keynote speaker. The book has the first recorded algorithm for implementing the Chinese Remainder Theorem, which Sun Tzu had stated without proof or procedure. He computed {\pi} to 4 decimal places, and interestingly, hinted by his choice of words that {\pi} could only be “approached.” He introduced the concept of versine, that is {1 - cos(\theta)}, and computed trigonometric tables. He maintained that the Earth rotates on an axis, 1,000 years before Nicolaus Copernicus did, and while he described a geocentric system, he treated planetary periods in relation to the Sun.

Today Ken and I wish everyone a Happy Father’s Day, and talk about recognizing our scientific fathers correctly. This includes a short rant about a flawed piece in today’s New York Times. Read more…

Proof Envy

June 11, 2014

I wish I could have used Theorem X…

IISC centenary source

Vijaya Ramachandran is now the Blakemore Regents Professor of Computer Science at The University of Texas at Austin. Once upon a time she was my PhD student, at Princeton, working on the theory of VLSI chip design. Long ago she moved successfully into other areas of theory. She became a leader in cache oblivious algorithms, an area created by Charles Leiserson, whom I advised as an undergraduate many years ago. It’s a small world.

Today I want to talk about theorems, old theorems and new, that I wish I could have used in a paper.
Read more…

Is This a Proof?

June 6, 2014

Seeking the limits of mathematical proofs


Ivan Vinogradov was a famous mathematician who created a whole method, named after him, that allowed him to make major advances on many open number theoretic problems. These included his theorem on the Weak Goldbach Conjecture and many others.

Today Ken and I wish to talk about a new type of “mathematical proof,” illustrating it for the Weak Goldbach Conjecture.
Read more…

How To Avoid Leaving Clues

June 1, 2014

How to use memory without a trace


Harry Buhrman is a quantum complexity theorist. That is, if you take a measure of him, you will sometimes find that he is doing complexity theory, sometimes quantum computing, sometimes both, and sometimes neither. Whichever, he has been doing it great for a quarter century. He has a joint paper in STOC 2014, which begins today, that is part complexity and part—something else.

Today Ken and I want to talk about the beautiful new concept and results in that paper. They can be viewed as complexity theory results: this model of computation can compute such-and-such. They can also be viewed as security results: malware programs can do things to avoid detection.
Read more…

Avoiding Monsters and Non-Monsters

May 27, 2014

A new insight into the structure of some exotic mathematical objects


Karl Weierstrass is often credited with the creation of modern analysis. In his quest for rigor and precision, he also created a shock when he presented his “monster” to the Berlin Academy in 1872.

Today I want to talk about the existence of strange and wonderful math objects—other monsters.
Read more…

STOC 1500

May 23, 2014

What STOC might have been like in old times


Mikolaj Kopernik was a student of the professor mathematum Domenico Novara in 1500. They traveled from Bologna to Rome where Novara gave lectures on mathematics. We imagine that Novara might also have been asked to organize a symposium there on the practice of mathematics with mechanical aids, including the classical ruler-and-compass, abaci, astrolabes, and similar devices. Since the words “theory” and “theoretical” with their modern meanings trace only to the late 1500s, we suppose it might have been called the Symposium on Theology of Calculation (STOC).

Today Dick and I consider how STOC 1500 might have been similar to STOC 2014, which starts at the end of next week.
Read more…


Get every new post delivered to your Inbox.

Join 1,647 other followers