Skip to content

Remembering Ann Yasuhara

July 1, 2014

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

June 29, 2014

Or rather two beautiful identities


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

June 23, 2014

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 {\mathsf{\#P}} must either be in {\mathsf{P}} or be {\mathsf{\#P}}-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

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…


Get every new post delivered to your Inbox.

Join 1,690 other followers