From knight’s tours to complexity
|Von Warnsdorf’s Rule source|
Christian von Warnsdorf did more and less than solve the Knight’s Tour puzzle. In 1823 he published a short book whose title translates to, The Leaping Knight’s Simplest and Most General Solution. The ‘more’ is that his simple algorithm works for boards of any size. The ‘less’ is that its correctness remains yet unproven even for square boards.
Today we consider ways for chess pieces to tour not 64 but up to configurations on a chessboard.
A great presentation on thermoelectrics
Today I wish to talk about a beautiful presentation he just gave at TTI/Vanguard in San Francisco.
Some fun rejection comments
Joshua Gans and George Shepherd were doctoral students in economics at Stanford University back in the 1990s. They wrote an interesting paper that I just came across titled, “How Are the Mighty Fallen: Rejected Classic Articles by Leading Economists.” It grew into a 1995 book edited by Shepherd: Rejected: Leading Economists Ponder the Publication Process.
Today I want to discuss the same issue in our area of theory. Read more…
Doo wop, doo wop
Richard Lewis, Bill Horton, Earl Beal, Raymond Edwards, and John Wilson—the Silhouettes—were a doo wop/R&B group whose single Get A Job was a number 1 hit on the Billboard R&B singles chart and pop singles chart in 1958. Even back then it sold over one million records, and was later used in ads and movies.
Today I want to talk about hiring faculty, as we are getting near the end of the usual job hiring cycle.
An AMS article by Gil Kalai updates his skeptical position on quantum computers
|Cropped from Rothschild Prize source|
Gil Kalai is a popularizer of mathematics as well as a great researcher. His blog has some entries on Polymath projects going back to the start of this year. He has just contributed an article to the May AMS Notices titled, “The Quantum Computer Puzzle.”
Today we are happy to call attention to it and give some extra remarks. Read more…
A preview of the talks for this coming ARC Day
ARC is our Algorithms & Randomness Center at Tech. It was created by Santosh Vempala, and this Monday ARC is holding a special theory day. The organizers are Santosh with Richard Peng and Dana Randall.
Tomorrow, Monday April 11th, is the day for the talks, and I only have time to highlight just two of them.
Can we have overlooked short solutions to major problems?
Efim Geller was a Soviet chess grandmaster, author, and teacher. Between 1953 and 1973 he reached the late stages of contention for the world championship many times but was stopped short of a match for the title. The Italian-American grandmaster Fabiano Caruana was similarly stopped last week in the World Chess Federation Candidates Tournament in Moscow. He was beaten in the last round by Sergey Karjakin of Russia, who will challenge world champion Magnus Carlsen of Norway in a title match that is scheduled for November 11–30 in New York City.
Today we salute a famous move by Geller that was missed by an entire team of analysts preparing for the world championship in 1955, and ask how often similar things happen in mathematics and theory.