Skip to content

A Polynomial Growth Puzzle

September 12, 2015

Correcting an erratum in our quantum algorithms textbook

Cropped from source

Paul Bachmann was the first person to use {O}-notation. This was on page 401 of volume 2 of his mammoth four-part text Analytic Number Theory, which was published in Germany in 1894. We are unsure, however, whether he defined it correctly.

Today we admit that we got something wrong about {O}-notation in an exercise in our recent textbook, and we ask: what is the best way to fix it?
Read more…

Open Problems That Might Be Easy

September 3, 2015

A speculation on the length of proofs of open problems

Broad Institute source

Nick Patterson is one of the smartest people I have ever known.

Today I would like to talk about something he once said to me and how it relates to solving open problems.
Read more…

How Joe Traub Beat the Street

August 31, 2015

An insight into the computation of financial information

Columbia memorial source

Joseph Traub passed away just a week ago, on August 24th. He is best known for his computer science leadership positions at CMU, Columbia, CSTB, the Journal of Complexity—they all start with “C.” CSTB is the Computer Science and Telecommunications Board of the National Academies of Science, Engineering, and Medicine. At each of these he was the head and for all except Carnegie-Mellon he was the first head—the founder.

Today Ken and I wish to highlight one technical result by Traub and his co-workers that you may not know about.
Read more…

Cancellation is a Pain

August 27, 2015

How to avoid the pain of estimating tough sums

Cricketing source

Andrew Granville is a number theorist, who has written—besides his own terrific research—some beautiful expository papers, especially on analytic number theory.

Today Ken and I wish to talk about his survey paper earlier this year on the size of gaps between consecutive primes.
Read more…

Cryptography And Quicksand

August 14, 2015

A basic question about cryptography that we pretend is not there.


Victor Shoup is one of the top experts in cryptography. He is well known for many things including a soon to be released book that is joint with Dan Boneh on, what else, cryptography; and the implementation of many of the basic functions of cryptography.

Today I want to talk about my recent visit to the Simons Institute in Berkeley where I heard Victor give a special lecture.
Read more…

Changing Definitions

August 10, 2015

How important is “backward compatibility” in math and CS?

David Darling source

Henri Lebesgue came the closest of anyone we know to changing the value of a mathematical quantity. Of course he did not do this—it was not like defining π to be 3. What he did was change the accepted definition of integral so that the integral from {a} to {b} of the characteristic function of the rational numbers became a definite {0}. It remains {0} even when integrating over all of {\mathbb{R}}.

Today we talk about changing definitions in mathematics and computer programming and ask when it is important to give up continuity with past practice. Read more…

Four Weddings And A Puzzle

August 2, 2015

An unusual voting problem?

“Four Weddings” is a reality based TV show that appears in America on the cable channel TLC. Yes a TV show: not a researcher, not someone who has recently solved a long-standing open problem. Just a TV show.

Today I want to discuss a curious math puzzle that underlines this show.

The show raises an interesting puzzle about voting schemes:
Read more…


Get every new post delivered to your Inbox.

Join 2,590 other followers