Avishay Tal 2013-2014

Institution of PhD:
Weizmann Institute of Science
Academic Discipline of PhD:
Computer Science
PhD Advisor/s:
Prof. Ran Raz
Dissertation Topic:
Analysis of Boolean Functions in Theoretical Computer Science
Year Awarded PhD:
Institution of Postdoc:
Institute for Advanced Study
Present Institution:
University of California, Berkeley
Present Academic Position:
Assistant Professor

Avishay was born and raised in Kibbutz Shefayim. After high school, he joined the ATUDA program and finished a BSc in Software Engineering and a BA in Mathematics at the Technion.  He then joined the army and served for 6 years as an algorithmic researcher and a team leader. This was his first encounter with mathematical and algorithmic research, which he found fascinating and enjoyable. In parallel to his service in the army Avishay completed his MSc studies at the Technion in the field of theoretical computer science, under the guidance of Prof. Amir Shpilka. In his MSc thesis, he analyzed properties of Boolean functions and applied it to the problem of learning from examples in the presence of irrelevant data.

After finishing his army service and MSc studies summa cum laude Avishay joined the Weizmann Institute of Science Department of Computer Science and Applied Mathematics under the guidance of Prof. Ran Raz. He is interested in various questions on the edge between combinatorics and computational complexity. The main driving force in computational complexity is the P vs NP problem, which asks whether there exist problems that are hard to compute, though easy to verify once a solution is given. This is a notoriously hard question, open for several decades now. One of the main efforts is to show that some problems are hard to compute in a more limited model of computation than the usual Turing machine. One such model is the decision tree model in which we are given access to a long input and want to compute some function on it by reading as few letters of it as possible. In this model it is easier to show that certain algorithms are optimal (i.e. that no better algorithm is possible) since this problem has more combinatorial nature. A work by Avishay about the relation between different variants of this model was presented in the Innovations in Theoretical Computer Science conference and won the best student paper award. His paper solves a 15 year-old mathematical, very basic, open problem.

Another concrete model of computation is the model of formulas which captures the power of parallelism. In this model we are asked whether there are problems which can be computed efficiently, but cannot be computed much faster using many cores. A work in which Avishay is a partner, shows that certain problems cannot be even approximated in this model, i.e. we cannot even find an algorithm which is correct on a significant fraction of the inputs.