Emanuele Viola

Emanuele Viola
Name	Emanuele Viola
Nationality	Italian
Fields	Computer science, Theoretical computer science
Institutions	ETH Zurich, University of Amsterdam, Harvard University, Columbia University, Microsoft Research
Alma mater	University of Milano-Bicocca, École Normale Supérieure, University of California, Berkeley
Doctoral advisor	Salil Vadhan
Known for	Pseudorandomness, derandomization, complexity theory, randomness extractors

Emanuele Viola is an Italian theoretical computer scientist known for contributions to pseudorandomness, derandomization, and computational complexity. He has held faculty and research positions at major institutions and produced influential results on randomness extractors, lower bounds, and derandomization techniques. His work connects foundational topics in cryptography, probability theory, combinatorics, and computational complexity theory.

Early life and education

Viola was born in Italy and completed early studies in mathematics and computer science at the University of Milano-Bicocca. He pursued graduate work in theoretical computer science and spent formative time at the École Normale Supérieure and the University of California, Berkeley, where he engaged with research groups active in pseudorandomness and complexity theory. Viola completed a Ph.D. under the supervision of Salil Vadhan, integrating methods from number theory, Fourier analysis, and randomness extractors into the study of derandomization.

Academic career and positions

Viola's appointments have included positions at the University of Amsterdam, Harvard University, Columbia University, and a research fellowship at Microsoft Research. He has been affiliated with ETH Zurich and has collaborated with researchers at institutions such as the Institute for Advanced Study, the Simons Institute for the Theory of Computing, and the Royal Society. Viola has served on program committees for conferences including the ACM Symposium on Theory of Computing, the IEEE Symposium on Foundations of Computer Science, and the Conference on Computational Complexity. He has held visiting positions and given seminars at centers like Princeton University, Massachusetts Institute of Technology, Stanford University, and Carnegie Mellon University.

Research contributions and notable results

Viola's research spans pseudorandom generators, randomness extractors, hardness amplification, and lower bounds. He proved results on constructing explicit pseudorandom generators from hardness assumptions and on limitations of certain derandomization approaches. Notable contributions include advances in constructing extractors for independent sources, constructions related to the Nisan-Wigderson pseudorandom generator paradigm, and derandomization implications for complexity classes such as BPP, P/poly, and NP.

Viola produced new techniques for converting worst-case hardness into average-case hardness, engaging with frameworks developed by Impagliazzo and Wigderson. His work on pseudorandomness used tools from additive combinatorics, interacting with results of Ben Green and Tao on arithmetic progressions, and employed Fourier-analytic techniques reminiscent of methods from Harmonic analysis applied in theoretical computer science. He contributed to explicit constructions of extractors for two independent weak sources, building on prior work by Trevisan, Raz, and Srinivasan.

In derandomization, Viola explored connections between circuit lower bounds and randomness-efficient algorithms, relating to foundational results by Yao, Shannon, and Valiant. He examined the complexity of distinguishing structured distributions from uniform, with implications for property testing and learning theory in settings influenced by researchers like Goldreich and Vadhan. Viola also investigated pseudorandomness against classes of low-degree polynomials, engaging with lines of work by Razborov and Smolensky on circuit complexity.

His collaborative papers advanced understanding of randomness extractors in the presence of quantum side information, intersecting with research by Renner and Devetak on quantum information theory. Viola's results often balanced combinatorial constructions, probabilistic method innovations, and complexity-theoretic hardness assumptions, contributing tools utilized by subsequent researchers in derandomization, coding theory, and cryptographic primitives.

Awards and honors

Viola's work has been recognized by invitations to speak at major venues such as the International Colloquium on Automata, Languages and Programming, the International Congress of Mathematicians satellite events on discrete mathematics, and plenary or invited addresses at the Conference on Computational Complexity. He has received grants and fellowships from national and international agencies and has been named in lists highlighting young researchers in theoretical computer science by organizations including the European Research Council and various national science foundations.

Selected publications and lectures

Viola has authored and coauthored papers in proceedings of the ACM Symposium on Theory of Computing, the IEEE Symposium on Foundations of Computer Science, the Conference on Computational Complexity, and journals such as the Journal of the ACM and the SIAM Journal on Computing. Representative works include manuscripts on extractors for independent sources, derandomization via hardness amplification, and pseudorandomness against low-degree tests. He has delivered invited lectures at the Simons Institute for the Theory of Computing, the Institute for Advanced Study, Princeton University, and the Mathematical Sciences Research Institute.

Category:Italian computer scientists Category:Theoretical computer scientists Category:Complexity theorists