Skip to content

Halloween Math Style

October 31, 2016


The top scariest possible results

washington_irving_duyckinick_portrait_cutoff_head
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

October 29, 2016


An initiative for women in computing

louisebethunegraphic
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

October 16, 2016


Some football wisdom from Dick Karp

john-urschel-ravens-july-header1
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 {\mathsf{NP}}-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 {\mathsf{NP}}-completeness, Dick Karp, about football.

Read more…

Why Is Being Truthful A Good Thing?

October 14, 2016


In the context of stable matching problems

jamie-morgenstern_0

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

October 5, 2016

!–more–>
The winner of the 2016 ACM-IEEE Knuth Prize

nisanphoto
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

September 25, 2016


Local rules can achieve global behavior

sarahcannonpicture

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

September 19, 2016


Toward teaching computability and complexity simultaneously

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