Euler’s back-door pass to Gauss sinks a bucket

ACC stands for the Atlantic Coast Conference, which is an athletic organization that contains Georgia Tech and fourteen other colleges. In basketball, the top several teams in the ACC qualified for the NCAA championship tournament, which started today. We call the NCAA tournament “March Madness” because the opening rounds have games being shown on national TV seemingly every hour of every day, and often some spectacular upsets happen. Indeed Harvard has just beaten a favored University of Cincinnati team.

Today I want talk about another ACC: our own complexity class. Read more…

A shocking story from our friendly Leprechaun

Neil L. is not a computer scientist—he is a Leprechaun. He has visited me every year since I started writing GLL, always visiting on St. Patrick’s day.

Today I want to report on what happened this year.

Evaluating mathematical beliefs

 Rutgers in memoriam source.

Leonid Khachiyan in 1979 caused arguably the most sudden surprise to the West’s popular scientific understanding since the successful launch of Sputnik in 1957. His ellipsoid method gave the first algorithm for linear programming whose polynomial running time was verified. Thanks largely to Narendra Karmarkar it has been superseded by faster interior-point methods, while older algorithms have since been noted to run in polynomial time, but the breakthrough and inspiration came from Khachiyan. Could something like it happen again?

Today Ken and I want to ask whether recent argument over beliefs about ${\mathsf{P=NP}}$? can be evaluated in light of this shock.

Long proofs are not always the most important results

Michael Rabin is visiting Georgia Tech today and tomorrow to give a pair of distinguished lectures. Both of these will be on applications of cryptography. One is to help auctions avoid cheaters, while the other is to help elections avoid cheaters. I see a pattern. Ken sees another pattern— he is helping chess tournaments avoid cheaters.

Today I want to comment about Rabin’s fame and what makes a result important.

Results and problems about primes that make us think of coding theory

 Cropped from source.

Zhi-Wei Sun is a professor in Mathematics at Nanjing University in China. He is the Editor in Chief of the recently-founded Journal of Combinatorics and Number Theory. His homepage is unique in prominently featuring a long list of

• …not his awards,
• …not his papers,
• …not his theorems,
• …but rather his conjectures.

Indeed we count 432 total conjectures in his list, subtracting one that he seems last year to have proved. They do not seem to be easy conjectures—this one implies the Riemann Hypothesis in a nontrivial way. Some of them involve powers of 2, which lend them a coding-theory flavor.

Today Ken and I wish to share ideas of using coding theory to prove number-theoretic results. Read more…

The computational power of plants

Martin Howard and Alison Smith are research scientists at the John Innes Centre (JIC) in Norwich, England. JIC was founded as a horticultural institution by the philanthropist John Innes in 1910, and is today one of several independent institutes affiliated to the University of East Anglia. Howard and Smith are the senior scientists on a paper that claims to show that plants can perform arithmetic division. Their co-authors are Antonio Scialdone, Sam Mugford, Doreen Feike, Alastair Skeffington, Philippa Borrill, and Alexander Graf.

Today I thought we might look at their claim and see if theory can shed any light on it.