Avi Wigderson's Students

Thesis Supervision

• Prabhakar Ragde, U. C. Berkeley, co-advisor with R. Karp, 1983--1986. Ph.D Thesis: Lower bounds for parallel computation
• Mauricio Karchmer, Hebrew University, 1986--1988. Ph.D Thesis: Complexity of computation and restricted machines. Winner of the ACM Best Doctoral Thesis in Computer Science Award.
• Moti Reif, Ben-Gurion University, co-advisor with M. Rubin, 1987--1988. Ph.D Thesis: Parallel algorithms for convex sets in R^2 and R^3.
• Joseph Gil, Hebrew University, 1986--1990. Ph.D. Thesis: Lower bounds and algorithms for hashing and parallel processing.
• Aviad Cohen, Hebrew University, 1986-1991. Ph.D. Thesis: Disperser graphs, deterministic amplification and imperfect random sources.
• Ilan Newman, Hebrew University, 1987-1991. Ph.D. Thesis: On the formula complexity of simple boolean functions.
• Rafi Heiman, Weizmann Institute, co-advisor with D. Harel, 1987-1991. Ph.D. Thesis: Randomized decision tree complexity of read-once Boolean functions.
• Ran Raz, Hebrew University, co-advisor with M. Ben-Or, 1988-1992. Ph.D. Thesis: Communication complexity and circuit lower bounds. Summary in English
• Yuri Rabinovich, Hebrew University, co-advisor with N. Linial, 1988-1992. Ph.D. Thesis: Monlinear Mixing and evolution of Combinatorial Systems.
• Roy Armoni, Hebrew University, co-advisor with M. Ben-Or, 1994--1998. Ph.D. Thesis: On the random resources needed by space-bounded computational models
• Dorit Aharonov , Hebrew University, co-advisor with M. Ben-Or, 1994--1998. Ph.D. Thesis: Noisy quantum computation.
• Ronen Shaltiel , Hebrew University, 1997--2001. Ph.D. Thesis: Explicit constructions of pseudo-random generators and extractors .
• Amir Shpilka , Hebrew University, 1997--2001. Ph.D. Thesis: Lower bounds for small depth arithmetic and Boolean circuits.
• Eli Ben-Sasson, Hebrew University, 1997--2001. Ph.D. Thesis: Expansion in Proof Complexity.

M.Sc Students

• Ron Ben-Nathan, Hebrew University, 1987--1990. MSc Thesis: Transforming Probabalistic to Deterministic Algorithms.
• Shlomo Hoory, Hebrew University, 1987--1990. MSc Thesis: Universal sequences for expander graphs and contracting sequences on graphs.
• Michal Parnas, Hebrew University, 1987--1990. MSc Thesis: Approximate Counting, Almost Uniform Generation and Random Walks.
• Roded Sharan, Hebrew University, 1994--1995. MSc Thesis: Perfect Matching in Parallel Computation.
• Dana Pe'er, Hebrew University, 1997--1999. MSc Thesis: On Minimum Spanning Trees.
• Ziv Bar-Yossef, Hebrew University, 1997--1998. MSc Thesis: Deterministic amplification of space-bounded randomized algorithms.