Amir Yehudayoff
Krill Prize 2014
Technion
Ass.Prof. Amir Yehudayoff (פרופ”מ אמיר יהודיוף)
Research Interests:
Combinatorics and theory of computing
Theoretical aspects of computing have deep and beautiful connections to many
areas of mathematics and science in general. I am interested in improving our
understanding of these connections and in finding and exploring new ones. Here
are several examples of research projects I am part of.
Computational complexity theory studies the amount of resources that are needed to
perform a given task. A simple example is the communication complexity model
defined by Yao, which has found numerous applications since its introduction. In this
model, there are two players usually called Alice and Bob. Alice gets an input x, Bob
gets an input y and their goal is to compute a common function f(x,y) while
communicating the minimal amount possible. We have been studying efficient
compression of communication protocols, and searching for more connections with
other known complexity measures.
Another goal of complexity theory is efficient constructions of useful combinatorial
objects. A good example of such objects are expander graphs, which are highly
connected graphs of constant degree. Expanders have many applications, for example,
in coding theory and derandomization. A basic question that I am interested in is
“how simple can expander graphs be?” We have showed that there are monotone
expanders (that are simple due to the monotonicity restriction), and we are studying
the question of whether expanders can be defined by simple maps (e.g., that are close
to one-dimensional affine).
We are also looking for clean mathematical frameworks that model scientific
endeavours. Two examples of such frameworks from my recent work are: (a) The
restriction access model that relates to learning theory and provides a clean
framework to study non-black-box access to computational processes. (b) The
population recovery model that concerns recovery of information from partial (noisy
or lossy) data. In both of these models, we have found new algorithms that will
hopefully be used in practice or influence the way similar tasks are approached in the
future.
Another related area that is fascinating to me is the behaviour of random processes
and objects. It is a well-known phenomenon that random objects exhibit a typical
Behavior. In complexity theory, e.g., a random function is typically difficult to
compute. We have been studying several random systems and helped to describe
some of the typical behaviors of these system. Two recent examples are the behavior
of random Lipschitz functions on expander graphs and trees, and the behavior of the
cover time of trees (which is a generalisation of the “coupon collector” problem).