Skip to content

TEDx Time In Buffalo

October 13, 2014

Our own Ken joins the team for TEDx


Adrienne Bermingham is the manager of this year’s TEDx Buffalo event, which will be held this Tuesday at the Montante Center of Canisius College in downtown Buffalo.

Today I wish to proudly announce that our own Ken Regan is one of the presenters at this year’s event.
Read more…

More on Testing Dyson’s Conjecture

October 11, 2014

Applying deep number theory to algorithms

FullWiki source

Alan Baker won the Fields Medal in 1970 for his work on algebraic and transcendental numbers. He greatly extended a theorem of Aleksandr Gelfond and Theodor Schneider which had solved the seventh problem on David Hilbert’s famous list. Baker’s extension says that if {\alpha_1,\dots,\alpha_k} are algebraic numbers other than {0} or {1}, and if {\beta_1,\dots,\beta_k} are irrational algebraic numbers that together with {1} are linearly independent over the rationals, then the product of {\alpha_i^{\beta_i}} for {i = 1} to {k} is transcendental. Hilbert had stated the {k=1} case, which Gelfond and Schneider solved, and believed it would be harder than the Riemann Hypothesis.

Today Ken and I want to talk about computing numbers to high precision and their relationship to our recent discussion of Freeman Dyson’s challenge. Read more…

How To Add Numbers

October 5, 2014

It’s harder than you think


William Kahan is a numerical analyst and an expert on all things about floating point numbers. He won the 1989 Turing award for his pioneering work on how to implement floating point computations correctly. He has also been a tireless advocate for the care needed to avoid insidious numerical bugs, and his strong feelings come out in a 1997 interview for Dr. Dobbs’ Journal.

Today I want to talk about one of his results on how to sum a series of numbers.
Read more…

The Busy Beaver Problem

October 1, 2014

Can the impossible become practical?

Complex analysts gallery source

Tibor Radó was a mathematician who was the PhD advisor to a number of computer scientists. They include Shen Lin, Paul Young, and several others. All were his students while he was at Ohio State University. He is not the Rado of the Erdős-Ko-Rado theorem—that is Richard Rado, without an accent. Tibor Radó had an Erdős Number of 3, through Lin and then Ron Graham.

Today we want to continue to talk about the famous “Busy Beaver” problem which we mentioned in our discussion on the Microsoft SVC lab closing. Read more…

Microsoft Closes SVC

September 27, 2014

Some additional thoughts

Microsoft Research source

Omer Reingold is a brilliant researcher, and now all can see that he is also a very classy and thoughtful person. As you all know by now, he and many others have suddenly lost their jobs with the closing of Microsoft’s Silicon Valley Campus (SVC) Research Lab. The lab closed this week: it has been removed from Microsoft’s “Research labs worldwide” page. The closing affects about 50 jobs directly, and is part of an overall reduction of about 18,000 staff worldwide.

Today, Ken and I wish to express some of our feelings about this. At first we thought we could not add to what others have already said about the closing, but we realized we could still express support and add to the wider conversation.
Read more…

Evolution: A Complexity View

September 22, 2014

The role of sex?

Cropped from source

Christos Papadimitriou has a joint paper with Adi Livnat, Aviad Rubinstein, Gregory Valiant, and Andrew Wan that will appear soon at FOCS 2014. The conference is October 19–21 in Philadelphia, with workshops and tutorials on the 18th. Here are the accepted papers, several others of which interest me a lot. The last parallel session on Monday afternoon before my own award lecture has three of them in one room, including a paper co-authored by my recent student Danupon Nangonkai, and three on quantum—it would be nice to be in a quantum superposition and attend both sessions.

Today Ken and I want to discuss their paper, which is on complexity-theoretic aspects of evolution.
Read more…

Let’s Mention Foundations

September 18, 2014

Congratulating Dick on the 2014 Knuth Prize

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…


Get every new post delivered to your Inbox.

Join 2,135 other followers