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.
Caltech Welcomes Professor Chandrasekaran
Venkat Chandrasekaran, Assistant Professor of Computing and Mathematical Sciences, arrived at Caltech in early September 2012. His area of research is mathematical optimization. He describes, "Almost anything we wish to do in engineering design is about maximizing objectives subject to certain constraints—trading off different aspects of a system to optimize a few others. For instance, if you work in jet-engine design, you have certain constraints in the amount of material you can use, the weight of these materials, aerodynamic issues, etc. But then you want to be able to design your wings and so on in such a way that you maximize, for example, how fast you are able to go. My specific focus deals with trying to look at optimization problems that (a) are tractable to solve—not all optimization problems are ones that can be efficiently solved on a computer—and (b) arise in the information sciences." [Caltech Release]
Erik Winfree, Professor of Computer Science, Computation and Neural Systems, and Bioengineering, and colleagues including Caltech alumnae Rebecca Schulman, have created a new system to copy sequence information. In their approach, tiny DNA tile crystals consisting of many copies of a piece of information are first grown, then broken into a few pieces by mechanically-induced scission, or force. The new crystal bits contain all the information needed to keep copying the sequence. Each piece then begins to replicate its information and grow until broken apart again—without the help of enzymes, an essential ingredient in biological sequence replication. [Caltech Press Release]
Auctions, Traffic, Selfishness, and Data Privacy
Problems where a conflict or tension exists between individual incentives and more global objective are one of the foci of Professor Katrina Ligett's research. "I'm interested in new algorithms, in understanding how difficult it is to solve problems," Ligett, Assistant Professor of Computer Science and Economics, says. "There aren't that many places where computer scientists and economists actually talk to each other. At Caltech, people are really interested in and committed to investigating at this intersection, and that's very appealing." [Caltech Feature]