Move the Cheese
Report on the recent Coding, Complexity, and Sparsity Workshop
Martin Strauss and Anna Gilbert and Atri Rudra are the organizers of the just-held Coding, Complexity, and Sparsity Workshop. The theme of sparsity is working with objects that in their “vanilla” representation have many parts that are zero, redundant, or otherwise trivial. For instance, you might have an 
Today Ken and I want to thank them for having us attend this fun meeting. Read more…
Crypto Aspects of The Jacobian Conjecture
Crypto concepts promise partial progress via partial inversion
|
|
cropped from source. |
Shafi Goldwasser and Silvio Micali recently won the prestigious Turing Award. Our congratulations again to both of them. Shafi asked that we help announce the upcoming 8/22 deadline for the 5th Innovations in Theoretical Computer Science (ITCS) conference. We never do this kind of thing, so we will discuss something else.
Today I wish to talk about the Jacobian Conjecture, one of my favorite problems. Ken wanted to talk about it also, and he’s posting this during our travel to the kind of workshop we never announce, but he’s been enmeshed all week in the second story here. Read more…
Making Choices
The Axiom Of Choice, some history, some ideas
Gregory Moore is a historian of mathematical logic. One connection he has to things dear to us is that he edited the first two volumes of Kurt Gödel’s Collected Works, as well as some of the work of Bertrand Russell.
Today I want to talk about making choices and in particular the axiom of choice.
Read more…
Thirteen Sigma
Monitoring fabrication in industry and chess
|
|
“Hall of Fame” source. |
Bill Smith joined Motorola as a quality control engineer in 1986. He coined the term Six Sigma to formulate a goal for vastly reducing the fault rate of manufactured components. This needed improving not only the monitoring of quality but also the resolution of testing devices and statistical tools so they could make reliable projections in units of faults per million rather than per thousand. The resulting empowerment of Motorola’s engineers gave such great and verifiable results that Motorola received the Malcolm Baldridge National Quality Award in 1988.
Today I want to talk about the meaning of high-sigma confidence in areas where the results may not be verifiable. Read more…
Ghostbusting Old Factoring Ideas
Can ‘Shades’ of Carmichael Numbers be busted?
 |
| MAA source |
Robert Carmichael was an American mathematician who worked and published in various areas of mathematics, but is best known for numbers that were named after him. It’s a rare treat to have your own numbers; our famous Manuel Blum has his:
A Carmichael number is a product 
Today Ken and I want to talk about Carmichael numbers and their relationship to the factoring of integers.
Surely You Are Joking?
A new way to write mathematics
Vladimir Voevodsky won the Fields Medal in 2002 for his work on homotopy theory of algebraic varieties. Using his pioneering methods he proved, among many other things, a deep conjecture of John Milnor, that had been open for decades.
Today I want to talk about, no, rant about, a recent “breakthrough” that was just announced on the ACM Tech news service.
Rough Problems
Some problems on which we cannot even get in the zone
|
|
Rough on Ruff source |
Lindy Ruff was recently named coach of the Dallas Stars in the National Hockey League. He was the coach of the Buffalo Sabres against the Stars in the 1999 Stanley Cup Finals, which ended with the infamous “No Goal” overtime game. That series and controversy made Dallas the most hated team in the Buffalo area for a long time, even more than the Boston Bruins. Ruff’s 16 years coaching one team were far and away the longest active tenure in the NHL, until he was fired this past February. He also played 10 seasons for the Sabres in 1979–89 as a scrappy defenseman, living up to his name by averaging one penalty per game.
Today Dick and I want to talk about some complexity-relevant problems that are so rough we don’t even know whether they are decidable. Read more…
Independence Day
Will logical independence have its day?
John Adams was the second president of the United States. He predicted that July 2nd would be always remembered: “The second day of July, 1776, will be the most memorable epoch in the history of America.” He based this on the day that the Second Continental Congress voted to affirm a resolution of independence from Great Britain. He was off because the text of the explanation for that decision was not finalized and adopted until the 4th, whereupon it was immediately sent to printers for publication that evening. That is to say, the publication date of the paper is what counts.
Today Ken and I wish to talk about independence, not the day, not the holiday, but the notion of logical independence.
Approximating Boolean Functions
You can fool all the functions some of the time, and some of the functions all the time, but you cannot fool all the functions all the time, or even most of the time.
Eric Blais and Li-Yang Tan are both complexity theorists. Eric just finished his PhD and is currently a Simons Postdoctoral Fellow at MIT, while Li-Yang is about to finish his doctorate at Columbia.
Today Ken and I wish to talk about their recent paper on approximations to Boolean functions.
It Takes Guts To Do Research
Or rather to find bold paths when opportunity gives only part of a map
Robert Oppenheimer was one of the great physicists of the last century. He is most famous, of course, for his leadership of the Manhattan Project—the project that created the first atomic bomb.
Today I want to talk about research and why it requires a certain amount of courage, a certain amount of nerve, or just plain “guts.”
