Professor Sofya Raskhodnikova Receives NSF CAREER award

Assistant Professor Sofya Raskhodnikova has received a five-year Faculty Early Career Development (CAREER) award from the National Science Foundation for her proposal "Sublinear Algorithms – Theory and Applications."  The funding period of the award begins this month, September 2009.

Sublinear algorithms perform quick approximate computations – in time sublinear in the length of the input – and are useful for processing massive datasets.  The project includes foundational theoretical work as well as designing sublinear algorithms for a variety of applications.

"The amount of existing and newly appearing data accumulated by scientific, governmental and business organizations around the world is daunting," says Raskhodnikova. "As data of all types gets easier to obtain and cheaper to store, data sets are becoming increasingly large. Consequently, there is a need to perform computational tasks on massive data sets: comparing genomes, compressing media files, searching through and clustering large sets of documents, studying the Internet graph, and compiling census data, to name just a few."  Raskhodnikova's research project has its roots in the following question, fundamental to several fields:

Can we still compute something useful about a data set when reading all of it is prohibitively expensive? In other words, what can we do in time sublinear in the length of the input?
     
Although Raskhodnikova's main area of interest is the design and analysis of sublinear-time algorithms for combinatorial problems, she also works on data privacy, and, more generally,  on randomized
algorithms and computational complexity.

After receiving her Ph.D. in Computer Sciences from MIT in 2003, Raskhodnikova was awarded a Lady Davis Fellowship for her postdoctoral research at the Hebrew University of Jerusalem. She was also a postdoctoral researcher at the Weizmann Institute of Science and a visiting scientist at the Institute for Pure and Applied Mathematics at UCLA. She joined the Computer Science and Engineering Department at Penn State in 2007.  The same year, she was awarded the Joel and Ruth Spira Award for Teaching Excellence.

According to the NSF website, CAREER Program offers the National Science Foundation's most prestigious awards for new faculty members. It recognizes and supports the early career-development activities of those teacher-scholars who are most likely to become the academic leaders of the 21st century. CAREER awardees are selected on the basis of creative, career-development plans that effectively integrate research and education within the context of the mission of their institution.

In addition to Raskhodnikova, five faculty members in the department hold active CAREER awards.