## Why Is Being Truthful A Good Thing?

*In the context of stable matching problems*

Jamie Morgenstern is a researcher into machine learning, economics, and especially mechanism design.

Today Ken and I would like to discuss a joint paper of hers on the classic problem of matching schools and students.

Read more…

## Congratulations, Noam

!–more–>

*The winner of the 2016 ACM-IEEE Knuth Prize*

Coursera source |

Noam Nisan has been one of the leaders in computational complexity and algorithms for many years. He has just been named the winner of the 2016 Donald E. Knuth Prize.

Today we congratulate Noam and highlight some of his recent contributions to algorithmic economics and complexity.

Read more…

## A Creeping Model Of Computation

*Local rules can achieve global behavior*

Sarah Cannon is a current PhD student in our Algorithms, Combinatorics, and Optimization program working with Dana Randall. Sarah has a newly-updated paper with Dana and Joshua Daymude and Andrea Richa entitled, “A Markov Chain Algorithm for Compression in Self-Organizing Particle Systems.” An earlier version was presented at PODC 2016.

Today Ken and I would like to discuss the paper, and relate it to some recent results on soft robots.

Read more…

## A Proof Of The Halting Theorem

*Toward teaching computability and complexity simultaneously*

Large Numbers in Computing source |

Wilhelm Ackermann was a mathematician best known for work in constructive aspects of logic. The Ackermann function is named after him. It is used both in complexity theory and in data structure theory. That is a pretty neat combination.

I would like today to talk about a proof of the famous Halting Problem.

Read more…

## How Hard, Really, is SAT?

*A new longest computer proof makes us wonder about things from security to the Exponential Time Hypothesis*

Marijn Heule, Oliver Kullmann, and Victor Marek are experts in practical SAT solvers. They recently used this ability to solve a longstanding problem popularized by Ron Graham.

Today Ken and I want to discuss their work and ask a question about its ramifications.

Read more…

## Descending Proofs Into Algorithms

*A way to make indirect reasoning more palpable*

Wikimedia Commons source |

Nicholas Saunderson was the fourth Lucasian Professor at Cambridge, two after Isaac Newton. He promoted Newton’s *Principia Mathematica* in the Cambridge curriculum but channeled his original work into lecture notes and treatises rather than published papers. After his death, most of his work was collected into one book, *The Elements of Algebra in Ten Books*, whose title recalls Euclid’s *Elements*. It includes what is often credited as the first “extended” version of Euclid’s algorithm.

Today we raise the idea of using algorithms such as this as the basis for proofs.

Read more…

## A Surprise For Big-Data Analytics

*A simple but interesting issue with analyzing high-dimensional data *

Peter Landweber, Emanuel Lazar, and Neel Patel are mathematicians. I have never worked with Peter Landweber, but have written papers with Larry and Laura Landweber. Perhaps I can add Peter one day.

Today I want to report on a recent result on the fiber structure of continuous maps.