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