Skip to content

You Think We Have Problems

January 7, 2016

Some hard problems in philosophy

Wikimedia Commons source

Loki is a Jötunn or {{}^{\textstyle \text{\c{\'O}}}}ss in Norse mythology, who, legend has it, once made a bet with some dwarves. He bet his head, then lost the bet, and almost really lost his head—-more on that in a moment.

Today Ken and I wanted to look forward to the new year, and talk about what might happen in the future.
Read more…

Blasts From the Past

December 31, 2015

Is the “Forsch” awakening in complexity theory?

Composite of src1, src2, src3

Max von Sydow starred as the chess-playing knight in Ingmar Bergman’s iconic 1957 film The Seventh Seal. He has the first line of dialogue in this year’s Star Wars VII: The Force Awakens:

This will begin to make things right.

His character, Lor San Tekka, hands off part of a secret map before… well, that’s as much as we should say if you haven’t yet seen the movie. Highly recommended.

Today Dick and I marvel at how some of this past year’s best results hark back to the years when Star Wars first came out.

Read more…

Why Is Discrete Math Hard To Teach?

December 27, 2015

A new approach to teaching discrete math

René Descartes and François Viète are mathematicians who have something in common, besides being French. Let’s get back to that shortly. dv

I am about to teach our basic discrete math class to computer science majors, and need some advice.

At Tech this class has been taught for years by others such as Dana Randall. She is a master teacher, and her rankings from the students are always nearly perfect. Alas, she is on leave this spring term, and I have been selected to replace her.

Read more…

A Game On Infinite Trees

December 16, 2015

An independent principle in set theory

Cropped from Oberwolfach source

Ronald Jensen is a famous set theorist who was a past president of the Kurt Gödel Society. Dana Scott is the current president of this prestigious society.

Today I thought we would turn from graphs and their isomorphism problem to the study of simple trees. Well I wrote that last week, but Ken has filled out details. In the meantime we are happy to note that László Babai has released his 84-page graph-isomorphism paper, and we anticipate saying more about it in coming weeks.

Read more…

Permutation Problems With Strings

December 7, 2015

From “Parsons Puzzles” to Babai’s breakthrough, and more?

NZ silver fern source: Robin Ducker (CC)

Dale Parsons and Patricia Haden, of Otago Polytechnic in New Zealand, wrote a seminal paper on a genre of programming puzzles that Barbara Ericson at Georgia Tech is furthering in her doctoral work. The puzzles give lines of code in a scrambled order, sometimes with incorrect lines thrown in. The goal is to find the correct order of the correct lines.

Today Ken and I wish to discuss various string rearrangement problems in relation to the Graph Isomorphism problem.

Read more…

Thanks for Additivity

November 27, 2015

A mathematical metaphor for progress

Cropped from source

Nicole Oresme was a fourteenth-century polymath. He lived in France and became an advisor to King Charles V, who sponsored him to translate many works by Aristotle into French as well as Latin. He then became bishop of Liseux until his death in 1382. Oresme made original advances in physics, geography, and mathematics. He was evidently the first to prove that the harmonic series {\sum_N \frac{1}{N}} sums to infinity.

Today—yesterday was Thanksgiving Day in the US—we give thanks for mathematical advances and discuss what kind of cornucopia they are.

Read more…

A Little More on the Graph Isomorphism Algorithm

November 21, 2015

Looking at some of its components

From source, our congrats too

Laci Babai’s first talk a week ago Tuesday is now a webcast here. There is also a great detailed description of his talk by Jeremy Kun, including background on the problem and how the proof builds on Eugene Luks’s approach.

Today we talk some more about ingredients of Laci’s algorithm.

Read more…


Get every new post delivered to your Inbox.

Join 2,643 other followers