A Tighter Grip on Circuit Depth
The polynomial hierarchy is infinite for a random oracle
Benjamin Rossman, Rocco Servedio, and LiYang Tan have made a breakthrough in proving lower bounds on constantdepth circuits. It came from a bicoastal collaboration of Rossman visiting the Berkeley Simons Institute from Japan and Tan visiting from Berkeley to Servedio at Columbia University in New York. Their new paper solves several 20 and 30year old open problems.
Today we congratulate them on their achievement and describe part of how their new result works.
Read more…
Transcomputational Problems
Problems beyond brute force search
Cropped from Wikipedia source 
HansJoachim Bremermann was a mathematician and biophysicist. He is famous for a limit on computation, Bremermann’s limit, which is the maximum computational speed of a selfcontained system in the material universe.
Today Ken and I wish to talk about the limit and why it is not a limit.
Read more…
The AntiPigeonhole Conjecture
A conjecture about faculty behavior
“Dr. Kibzwang” source 
Colin Potts is Vice Provost for Undergraduate Education at Georgia Tech. His job includes being a member of the President’s Cabinet—our president, not the real one—and he is charged with academic policies and changes to such policies. He is also a College of Computing colleague and fellow chess fan.
Today I want to state a conjecture about the behavior of faculty that arose when Tech tried to change a policy.
Read more…
Case Against Cases
How to avoid too many cases at least some of the time
Theon of Alexandria was history’s main editor of Euclid’s Elements.
Today I want to talk about case analysis proofs.
Read more…
Kinds of Continuity
Congratulations to John Nash and Louis Nirenberg on the 2015 Abel Prize
Combined from src1, src2. 
John Nash and Louis Nirenberg have jointly won the 2015 Abel Prize for their work on partial differential equations (PDEs). They did not write any joint papers, but Nirenberg evidently got Nash excited about David Hilbert’s 19th problem during Nash’s frequent visits to New York University’s Courant Institute in the mid1950s. Nash in return stimulated Nirenberg by his verbal approach of barraging a problem with offkilter ideas. The Norwegian Academy of Sciences and Letters recognized their ‘great influence on each other’ in its prize announcement.
Today we congratulate both men on their joint achievement.
Read more…
A Quantum TwoFinger Exercise
More mileage than expected from a little example
Cropped from World Science Festival source 
Sean Carroll is a cosmologist in the Department of Physics at Caltech. He also maintains a blog, “Preposterous Universe,” and writes books promoting the public understanding of science. I have recently been enjoying his 2010 book From Eternity to Here: The Quest for the Ultimate Theory of Time.
Today—yes, Carroll would agree that there is a today—I would like to share an interpretation of a little quantum computing example that occurred to me while reading his book.
Read more…
April Fool
Nonjokes on April Fool’s Day

Nun’s Priest’s Tale source 
Faadosly Polir is the older brother of Lofa Polir. You may recall he invented new ways to apply powerful mathematical techniques to prove trivial theorems, and she once claimed a great result on integer factoring. We have heard from both since, but they haven’t given us any new April Fool’s Day material, mainly because they weren’t fooling to begin with.
Today Ken and I wished to help you enjoy April Fool’s day.
Read more…