Three Theorems About Growth
Is a key to polynomial versus exponential complexity lurking here?
|
|
Cropped from Abel Prize source |
Mikhail Gromov is a French-Russian mathematician who has made and continues to make fundamental contributions to many areas of mathematics. In 2009 he was awarded the Abel Prize for his seminal work on geometry. Here “geometry” is not high-school geometry of points and lines, but is all about things like: geometric group theory, hyperbolic groups, symplectic topology, and Riemannian geometry.
Today I (Dick) wish to talk about a great theorem of Gromov and its relationship to a theorem of our own Ken Regan, with a theorem by Rostislav Grigorchuk setting some goals.
Read more…
Happy Father’s Day
And the mother who gave it to us
Sonora Dodd is widely credited with the creation of Father’s Day. The first one was organized by her in Spokane, Washington in 1910. The history of her struggle to make it an annual holiday is told on the website fathersdaybirthplace.com maintained in Spokane, and on a HistoryLink page. Although the holiday was being observed all around the country by the mid-1920’s, it took until 1966 for President Lyndon Johnson’s proclamation setting it to be the third Sunday in June, and 1970 for a joint House-Senate resolution making it a national holiday, which President Richard Nixon signed into law in 1972.
Today Ken and I wish all fathers a happy day.
The Mathematics Of Dieting
Yes there are math issues in this activity
William Banting may have created the first very popular diet. In 1863 he published the Letter on Corpulence, Addressed to the Public, which outlined the details of a particular low-carbohydrate, low-calorie diet that had led to his own dramatic weight loss. The diet industry was born—see here for more on “banting”.
Today I want to have some fun with a major hard problem: how can we lose weight? Read more…
Triads and Dyads
Not dryads and naiads…
|
|
src |
Charles Peirce, who is regarded among the greatest logicians and philosophers, wrote a paper in 1897 titled “The Logic of Relatives.” Now we might want a guide to the logic of our own relatives, and in fact the word “brother” furnished Peirce’s first example. But what Peirce meant by “relative” is a term that attains its meaning only in conjunction with another noun as object, plus a word or other sign giving the relation. Examples, the first two his, are “brother of Napoleon,” “slayer of giants,” and “among the greatest logicians and philosophers.” The last has a wordless sign after “among” where the others have “of,” but then the rest may seem to make it a four-way relation. However, Peirce gave a general calculus of how all four and higher-way relations in semiotics could be decomposed into twos and threes. Such “relatives” and some other three-way relations, however, he proved to be irreducible within his system.
Today we consider an open problem about decomposing 3-ary finite automata. Read more…
Psst—It’s The Definition
Definitions are extremely important
|
|
src |
Shafi Goldwasser and Silvio Micali won the 2012 ACM Turing Award last March for their seminal work in cryptography. We are not a year late saying this—that is how the award is dated. By contrast, the official Academy Awards website says that the 2012 Oscars mean the ones for films in 2011, so February’s ceremony was the 2013 Oscars. The Turing Award is not like an Oscar anyway, as it is for lifetime achievement. The ACM-EATCS Gödel Prize, whose just-announced winners we intend to recognize soon, is more like an Oscar in that it honors specific performances (papers) within a limited timespan. Like the Oscar, some have won it more than once, including Shafi, while we cannot tell from the definition whether the Turing Award can be won twice.
Today Ken and I wish to talk about how great definitions transmit advances in math and theory, and how to make them greater.
Why Is There Something?
And is there everything?
|
|
not the src |
Jim Holt is the author of the modestly titled book, Why Does The World Exist? He has—as his book’s back cover says—written on string theory, time, infinity, numbers, truth, and even stercus taurinum, to use a learned translation of what the back cover actually says.
Today Ken and I thought it would be fun to ponder the main question he raises in his book.
Kenneth and Laurel Appel, In Memoriam
Mapping out the landscape of a proof
|
|
composite of src1, src2 |
Kenneth and Laurel Appel, our friend Andrew Appel’s father and sister, passed away in the past two months. Kenneth Appel partnered with Wolfgang Haken and some helpers to prove the Four-Color Map Theorem in 1976. One of those helpers was Laurel, then 13. Laurel became an adjunct associate professor of biology at Wesleyan University, where her husband Michael Weir is a professor, and directed the Ronald McNair Research Scholars program at Wesleyan. Her father was chair of mathematics at the University of New Hampshire, where he hired Yitang Zhang and is remembered for mentoring many junior faculty.
Today we remember both of them, and celebrate the nature of their work on the four-color proof.
Twin Primes Are Useful
Why the recent breakthrough is important
|
|
photo sources: UNH and Simons article |
Yitang Zhang, of the University of New Hampshire, has apparently proved a finite approximation to the famous Twin Prime Conjecture. This is a result of the first order. After ten days of progressively more detailed news, including today’s article in the New York Times, Zhang’s 56-page preprint has just been released on the Annals of Mathematics journal website. This is the final accepted version of the original submission, which was said in a story in Nature last week to have needed only “a few minor tweaks.”
Today Ken and I want to explain important aspects of the Twin Prime Conjecture.
Read more…
Graduate Student Traps
Can we help avoid parallel repetition of mistakes?
Irit Dinur has recently again shown a wonderful skill at re-conceptualizing an area that had seemingly been well worked out. A notable previous instance was her re-casting the proof of the PCP Theorem as a progressive amplification. Now she and David Steurer have posted a new paper whose title, “Analytical Approach to Parallel Repetition,” introduces a new framework. The subject of parallel repetition, which they call “a basic product operation for one-round two-player games,” is distinctive in having its genesis in a mistake made in a paper—a trap of automatic thinking. Lance Fortnow and Mike Sipser thought that executing multiple instances of a randomized protocol in parallel would have the same power-law reduction in the probability of overall failure as executing them independently in sequence, overlooking how the strategies in the parallel cases could be dependent and exploit this.
Today we talk about similar traps that people can fall into even at advanced graduate level. How might they be avoided?
Read more…
Advances on Group Isomorphism
Finally progress on this annoying problem
David Rosenbaum is right now the world expert on one of my favorite problems, group isomorphism. He is a third-year PhD student at the University of Washington in Seattle under Paul Beame, and has been visiting MIT this year to work with his other advisor, our familiar friend Aram Harrow. He presented a paper on this at SODA 2013, and recently posted a successor paper to the ArXiv. He grew up in the Portland area where he won prizes in scholastic chess tournaments.
Today I want to talk about his work, which not only advances our understanding of this problem, but also makes progress on other ones.
