An approach to complexity lower bounds?
Kurt Gödel did it all, succinctly. His famous 1938 paper “The Consistency of the Axiom of Choice and of the Generalized Continuum-Hypothesis” was pages long. Since the Proceedings of the National Academy of Sciences was printed on single-column pages in fairy large type, it would have been under one page in FOCS or STOC format. Only Leonid Levin has famously been that succinct.
Today Ken and I wish to advance another approach on complexity questions based on succinctness and Gödel’s brilliant idea. We have covered succinctness before, but now our angle is more arithmetical.
Taking a conjecture about identities to college
Alex Wilkie is a Fellow of the Royal Society, and holds the Fielden Chair in Mathematics at the University of Manchester. Ken knew him at Oxford in 1981—1982 and again from 1986. In 1993 Wilkie won the Karp Prize of the Association of Symbolic Logic, equally with Ehud Hrushovski. This is named not after Dick Karp but rather Carol Karp, a mathematical logician in whose memory the prize was endowed.
Today I wish to talk about logical theories, motivated by some questions from Bill Gasarch and others.
Musings on gravity and quantum on the 4th of July
Cropped from Crumbel source
Amanda Gefter is the author of the book titled Trespassing on Einstein’s Lawn: A Father, a Daughter, the Meaning of Nothing, and the Beginning of Everything. As the title suggests—and as Peter Woit pointed out in his review—there are parallels with Jim Holt’s book Why Does the World Exist?, which we covered a year ago. Gefter’s essay for Edge last year lays out more briefly how Einstein regarded relativity and early quantum as structurally divergent theories.
Today her book has led me to think further about the relationship between gravity and quantum mechanics. Read more…
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.
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…
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.
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.