## Halloween Math Style

*The top scariest possible results*

Head chopped from source |

Washington Irving was a famous writer of the early 1800’s who is best known for his short stories. *The Legend of Sleepy Hollow* was based on the folklore that each Halloween a decapitated Hessian soldier, killed in the American Revolution, rises as a ghost, a nasty ghost, who searches for his lost head.

Today is Halloween and while Ken and I are not searching for any lost heads, we do believe it is a good day to think about scary stories.

Read more…

## Absolute Firsts

*An initiative for women in computing*

AIA source |

Louise Bethune was the first female professional architect in the United States, and possibly the world. She worked in Buffalo in the late 1800s through the early part of the 20th century.

Today we roll out ideas for an initiative on attracting women to computer science.

Read more…

## Going For Two

*Some football wisdom from Dick Karp*

Cropped from S.I. Kids source |

John Urschel is a PhD student in the Applied Mathematics program at MIT. He has co-authored two papers with his Penn State Master’s advisor, Ludmil Zikatanov, on spectra-based approximation algorithms for the -complete graph bisection problem. A followup paper with Zikatanov and two others exploited the earlier work to give new fast solvers for minimal eigenvectors of graph Laplacians. He also plays offensive guard for the NFL Baltimore Ravens.

Today Ken and I wish to talk about a new result by the front linesman of -completeness, Dick Karp, about football.

## 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…