Publication
Mathematics
Video
Life without CONS
Can higher-order functional programs solve more problems than first-order programs? Answer: NO, since both program classes are Turing complete. The reason is that higher-order values can be simulated by first-order values: use function “closures” built…
Video
Streaming Lower Bounds for Approximating MAX-CUT
We consider the problem of estimating the value of MAX-CUT in a graph in the streaming model of computation. We show that there exists a constant $\e_* > 0$ such that any randomized streaming algorithm…
Video
Information-Performance Tradeoffs in Control
Consider a flying drone controlled from the ground by an observer who communicates with it via wireless. We are interested in how well the drone can be controlled via a channel that accepts r bits/sec.…
Publication
Local Max-Cut In Smoothed Polynomial Time
Microsoft Research Blog
New Microsoft Research Dissertation Grant provides support to under-represented groups in computing
By Dr. Meredith Ringel Morris, Principal Researcher, Microsoft Research I am pleased to announce that Microsoft Research is funding a new academic program, the Microsoft Research Dissertation Grant. This grant program offers selected doctoral students…
