New results on computing with modular gates

Shiteng Chen and Periklis Papakonstaninou have just written an interesting paper on modular computation. Its title, “Depth Reduction for Composites,” means converting a depth-${d}$, size-${s}$ ${\mathsf{ACC^0}}$ circuit into a depth-2 circuit that is not too much larger in terms of ${d}$ as well as ${s}$.

Today Ken and I wish to talk about their paper on the power of modular computation.

A way to recover and enforce privacy

 McNealy bio source

Scott McNealy, when he was the CEO of Sun Microsystems, famously said nearly 15 years ago, “You have zero privacy anyway. Get over it.”

Today I want to talk about how to enforce privacy by changing what we mean by “privacy.”

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 ${n \times n}$ boards.

Today we consider ways for chess pieces to tour not 64 but up to ${2^{64}}$ configurations on a chessboard.

A great presentation on thermoelectrics

Akram Boukai is a researcher in material science, and an expert on converting heat to electric energy: 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…