Skip to content

Progress On Modular Computation

May 28, 2016

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.
Read more…

Making Public Information Secret

May 20, 2016

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.”
Read more…

Coins on a Chessboard III

May 14, 2016

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.
Read more…

Theory Meets Material Science

May 9, 2016

A great presentation on thermoelectrics

Akram Boukai is a researcher in material science, and an expert on converting heat to electric energy:

Today I wish to talk about a beautiful presentation he just gave at TTI/Vanguard in San Francisco.
Read more…


May 6, 2016

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…

Get A Job

April 27, 2016

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.

Read more…

Quantum Supremacy and Complexity

April 22, 2016

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…