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.