Skip to content

Let’s Mention Foundations

September 18, 2014


Congratulating Dick on the 2014 Knuth Prize

LiptonSecondary
Cropped from source

Dick Lipton is of course the founder and driving writer of this weblog. He is also a computer scientist with a great record of pathbreaking research. The latter has just been recognized, I am delighted and proud to say, with the award of the 2014 Knuth Prize. The prize is awarded jointly by the ACM Special Interest Group on Algorithms and Computation Theory and the IEEE Technical Committee on the Mathematical Foundations of Computing, and was instituted in 1996, shortly after the formal retirement of the great—and very much active—Donald Knuth.

Today I am glad to give my congratulations in public, and also my thanks for a wonderful and long association.
Read more…

Some Strange Math Facts

September 14, 2014


Things we did not know

250px-STAN_ULAM_HOLDING_THE_FERMIAC
Ulam holding a strange device

Stanislaw Ulam was a Polish-American mathematician whose work spanned many areas of both continuous and discrete mathematics. He did pioneering research in chaos theory and Monte Carlo algorithms, and also invented the concept of a measurable cardinal in set theory. His essential modification of Edward Teller’s original H-bomb design is used by nearly all the world’s thermonuclear weapons, while he co-originated the Graph Reconstruction conjecture. His name is also associated with the equally notorious 3n+1 conjecture. Thus he was involved in some strange corners of math.

Today Ken and I want to talk about some strange facts observed by Ulam and others that we did not know or fully appreciate.
Read more…

A Challenge From Dyson

September 9, 2014


A reversal question

Unknown

Freeman Dyson celebrated his {\text{90}^{th}} birthday last December. He is world famous for his work in both physics and mathematics. Dyson has proved, in work that was joint with Andrew Lenard and independent of two others, that the main reason a stack of children’s blocks doesn’t coalesce into pulp is the exclusion principle of quantum mechanics opposing gravity. He shaved a factor of {\sqrt{2}} off the exponent for bounds on rational approximation of algebraic irrationals, before the result was given its best-known form by Klaus Roth. He has received many honors—recently, in 2012, he was awarded the Henri Poincaré Prize at the meeting of the International Mathematical Physics Congress.

Today Ken and I want to talk about one of his relatively recent ideas, which is more mathematics than physics. Perhaps even more theory than mathematics.
Read more…

Enriching the Frankl Conjecture

September 2, 2014


See a number, make a set

BruhnSchaudt

Henning Bruhn and Oliver Schaudt are mathematicians or computer scientists, or both. They are currently working in Germany, but wrote their survey on the Frankl Conjecture (FC) while working together in Paris. Schaudt is also known as an inventor of successful mathematical games.

Today Ken and I wish to talk about the Frankl conjecture and a principle of mathematics. Read more…

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
by


How exceptions in theorems may affect their complexity

BhargavaindiaToday
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?

Unknown

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…

Follow

Get every new post delivered to your Inbox.

Join 1,875 other followers