Position:  PhD Candidate

Current Institution:  Tel Aviv University

Abstract:  Sublinear-Time Algorithms

The amount of recorded information in the world grows by the split-second. Each minute, more than $200$ million emails move across the Internet; $350 000$ tweets are sent worldwide; and $3.6$ million web searches are being performed. This rise in information is not limited to the Internet alone. Scientists too have more information than ever before. Biologists collect enormous numbers of measurement; astronomers fill banks of hard drives with observations of stars and galaxies; and earth scientists assemble detailed snapshots of the weather. While this abundance of information posses many opportunities, the problem of analyzing the data is becoming more and more difficult. How do we run efficient algorithms on this massive amount of ever-growing and constantly-changing data? What does “efficient” in these very large scales even mean? Classical algorithms are considered to be efficient if they run in time that is polynomial in the input size. However, in these massive data sets, even a single pass on the input could take too long. My research field tackles this exact problem. Sublinear-time algorithms are only allowed to read a small fraction of the input at the cost of providing an approximate answer. Typically, these algorithms rely on randomization and guarantee to return a highly accurate answer with high probability. My research focus is on devising sublinear time algorithms for estimating graph parameters and for property testing of graphs and Boolean functions.

Bio:
My name is Talya Eden and I am a PhD candidate in the Electrical Engineering School of Tel Aviv University under the advisement of Prof. Dana Ron. My research focus is on sublinear time algorithms and property testing and in particular sublinear time estimation of graph parameters. I received my BSc in Medical Sciences and Computer Science from Tel Aviv University and an MSc in Computer Science (graduated Magna Cum Laude). My research is supported by the Weinstein Award for Graduate Studies Sephora Berrebi Scholarship for Women in Advanced Computer Science and Azrieli Fellows Scholarship. During my studies I was a teacher assistant in the courses Computational Learning Theory (2018) for graduates Design and Analysis of Algorithms (2015-2017) for graduates Computational Models (2015) for undergraduates and Data structures and Algorithms (2016-2018) for undergraduates.