Roei Tell
Education
BA (Tel-Aviv University and Open University)
MSc (Weizmann Institute of Science)
PhD (Weizmann Institute of Science)
Research interests
When saut茅ing onions, do you just randomly toss onion pieces around in the pan, hoping that in the end most pieces will be cooked more-or-less the same? Many algorithms work like that, making random choices about what to do instead of following carefully laid-out plans. In fact, sometimes making random choices is, provably, the only efficient way in which algorithms can solve the problem they're faced with.
My research lies in computational complexity theory, which is a field that delineates the capabilities of algorithms when their resources are limited: which tasks can be performed when we limit algorithms' time, memory, communication, randomness, and so on? I focus on the role of randomness in efficient computation, looking at computer science through the lens of pseudorandomness and derandomization. This perspective naturally leads to studying a broad array of theoretical areas, including circuit complexity, error-correcting codes, interactive proofs, cryptography, and more.