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.

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.

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…

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.

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.

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.