## Remembering Ann Yasuhara

* Ann will be missed *

Ann Yasuhara was a mathematician and a complexity theorist, who passed away this June 11th. She lived over half of her 82 years in Princeton, and was a member of the faculty of computer science at Rutgers since 1972.

Today Ken and I send our thoughts and condolences to Ann’s husband Mitsuru Yasuhara, her family, and her many friends—Ann will be missed—she was special.

Read more…

## A Pretty Identity

* Or rather two beautiful identities *

src |

Joseph Lagrange was a mathematician and astronomer who made significant contributions to just about everything. Yet like all of us he could make mistakes: he once thought he had proved Euclid’s parallel postulate. He wrote a paper, took it to the Institute, and as they did in those days, he began to read it. But almost immediately he saw a problem. He said quietly:

Il faut que j’y songe encore.

“I need to think on it some more.” He put his paper away and stopped talking.

Today Ken and I thought we would talk about a beautiful identity of Lagrange, not about the parallel axiom. Read more…

## Counting Edge Colorings Is Hard

* Another dichotomy theorem *

Jin-Yi Cai is one of the world’s experts on hardness of counting problems, especially those related to methods based on complex—pun intended—gadgets. He and his students have built a great theory of **dichotomy**, which we covered two years ago. This means giving conditions under which a counting problem in must either be in or be -complete, with no possibility in-between. The theory is built around a combinatorial algebraic quantity called the *holant*, which arose in Leslie Valiant’s theory of holographic algorithms.

Today Ken and I wish to discuss a recent paper on the hardness of counting the number of edge colorings, even for planar graphs.

Read more…

## The Problem of Catching Chess Cheaters

* 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

* 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 to 4 decimal places, and interestingly, hinted by his choice of words that could only be “approached.” He introduced the concept of versine, that is , 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

* 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?

* 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…