Computational Complexity and Local Algorithms: On the Interplay Between Randomness and Computation

This volume contains a collection of studies in the areas of complexity theory and Local Algorithms.

Oded Goldreich (oded.goldreich@weizmann.ac.il) is a Meyer W. WeisgalProfessor at the Faculty of Mathematics and Computer Science of the WeizmannInstitute of Science, Israel. Oded was born in 1957, and completed his graduatestudies in 1983 under the supervision of Shimon Even. He was a post-doctoralfellow at MIT (1983-86), a faculty member at the Technion (1986-94), a vis-iting scientist at MIT (1995-98), and a Radcliffe fellow at Harvard (2003/04).Since 1995, he is a member of the Computer Science and Applied MathematicsDepartment of the Weizmann Institute. He is the author of ＂Modern Cryptog-raphy, Probabilistic Proofs and Pseudorandomness＂ (Springer, 1998), the two-volume work ＂Foundations of Cryptography＂ (Cambridge University Press, 2001and 2004), ＂Computational Complexity: A Conceptual Perspective＂ (CambridgeUniversity Press, 2008), and ＂Introduction to Property Testing＂ (CambridgeUniversity Press, 2017).

Nader H. Bshouty (bshouty@cs.technion.ac.il) is a Professor of ComputerScience at the Technion - Israel Institute of Technology, Haifa, Israel. Born in1960, he completed his doctoral studies in Computer Science in 1989 at theTechnion under the supervision of Michael Kaminski. From 1989 to 1998, heheld academic positions at the University of Calgary, Canada. Since 1999, hehas been a Professor at the Technion. His research focuses on ComputationalLearning Theory, Property Testing, Models of Computation, and the Complexityof Algebraic Computations.

Dana Ron (danar@eng.tau.ac.il) is the Lazarus Brothers Chair of ComputerEngineering at the School of Electrical Engineering of Tel Aviv University, Israel.Dana was born in 1964, and completed her graduate studies in 1995 under thesupervision of Naftali Tishby. She was an NSF post-doctoral fellow at MIT(1995-97), a science scholar at the Bunting Institute, Radcliffe (1997-98), and aRadcliffe fellow at Harvard (2003/04). Since 1998 she is a faculty member in TelAviv University. She is a fellow of the EATCS and ACM.

Laliv Tauber (lalivta@gmail.com) completed her master thesis at the Weiz-mann Institute of Science in 2024.