Skip to content

Who Invented Pointers, Amortized Complexity, And More?

August 26, 2014

Some algorithmic tricks were first invented in complexity theory

Screen Shot 2014-08-26 at 4.00.14 PM

Andrey Kolmogorov, Fred Hennie, Richard Stearns, and Walter Savitch are all famous separately; but they have something in common. Read on, and see.

Read more…

Why Is 290 Special?

August 23, 2014

How exceptions in theorems may affect their complexity

Cropped from India Today source

Manjul Bhargava is a mathematician who just won one of the 2014 Fields Medals. We offer our congratulations on this achievement. He is an expert in number theory, which makes him special to us among Fields medalists. His Fields citation includes his doctoral work on a powerful reformulation and extension of Carl Gauss’s composition law for quadratic forms. He also proved a sense in which 290 is special to us among numbers, since we have been thinking recently about quadratic forms as tools in complexity theory.

Today we talk about his “290 Theorem” with Jonathan Hanke, which is quite accessible, and also raise complexity-related questions about this result. Read more…

The Derivative Of A Number

August 19, 2014

Are you kidding?


Edward Barbeau is now a professor emeritus of mathematics at the University of Toronto. Over the years he has been working to increase the interest in mathematics in general, and enhancing education in particular. He has published several books that are targeted to help both students and teachers see the joys of mathematics: one is called Power Play; another Fallacies, Flaws and Flimflam; and another After Math.

Today I want to discuss his definition of the derivative of a number, yes a number.
Read more…

The 3SUM Assumption Is Wrong?

August 16, 2014

A new result on our three body problem

Screen Shot 2014-08-16 at 11.16.19 AM

Allan Grønlund and Seth Pettie are leaders in algorithm design and related problems.

Today I want to give a quick follow up on our discussion of 3SUM based on a recent paper of theirs. Read more…

Our Three Body Problem

August 13, 2014

The three body problem, computer theory style


Ellis Horowitz is one of the founders of the theory of algorithms. His thesis with George Collins in 1969 had the word “algorithm” in the title: “Algorithms for Symbolic Integration of Rational Functions.” He is known for many things, including an algorithm that after forty years is still the best known.

Today I want to talk about this algorithm, and one of the most annoying open problems in complexity theory. Read more…

Laplace’s Demon

August 8, 2014

Demons and other curiosities


Pierre-Simon Laplace was a French scientist, perhaps one of the greatest ever, French or otherwise. His work affected the way we look at both mathematics and physics, among other areas of science. He may be least known for his discussion of what we now call Laplace’s demon.

Today I want to talk about his demon, and whether predicting the future is possible.

Can we predict the past? Can we predict the present? Can we predict the future? Predicting the past and predicting the present sound a bit silly. The usual question is: Can we predict the future? Although I think predicting the past—if taken to mean “what happened in the past?”—is not so easy.

Read more…

Diagonalization Without Sets

August 3, 2014

Avoiding actual infinities


Carl Gauss is of course beyond famous, but he had a view of infinity that was based on old ideas. He once wrote in a letter to Heinrich Schumacher in 1831:

so protestiere ich zuvörderst gegen den Gebrauch einer unendlichen Größe als einer vollendeten, welcher in der Mathematik niemals erlaubt ist. Das Unendliche ist nur eine façon de parler, indem man eigentlich von Grenzen spricht, denen gewisse Verhältnisse so nahe kommen als man will, während anderen ohne Einschränkung zu wachsen gestattet ist.

Today we want to show that the famous diagonal argument can be used without using infinite sets. Read more…


Get every new post delivered to your Inbox.

Join 1,806 other followers