Alumnus Receives 2012 Simons Graduate Fellowships in Theoretical Computer Science

Christopher Beck (BS '09 Computer Science and Mathematics) is a recipient of a 2012 Simons Graduate Fellowship. The fellowships are given to graduate students in theoretical computer science with outstanding track records of research accomplishments. Beck’s work seeks to establish the limits of how efficiently we can solve computational problems. One of his papers studies a popular class of algorithms known as SAT solvers and shows that if their memory is restricted, then they can require exponential running time. Another result concerns how well we can approximately sample from certain distributions when our computation must be small depth, that is, highly parallelizable. Beck and his co-authors showed that even exponentially large bounded depth circuits cannot sample with even exponentially small success from a certain simple distribution.