While still a graduate student, Balaji Prabhakar, in collaboration with
Tom Mountford, established the Reiman-Simon conjecture, a long-standing
open problem in queueing theory: They showed that a general stochastic
arrival process is eventually shaped into a Poisson process after passing
through an infinite series of exponential-service queues.  Like many good
conjectures, the conclusion seems very believable, almost obvious.  It is
natural to view the queue as an operator that maps arrival processes into
departure processes.  For an exponential server, Burke's output theorem
implies that the Poisson process is a fixed point of that operator.  Thus, 
conjecturing that the departure prcess from such a series of queues converges 
to a Piosson process amounts to conjecturing that the queue, viewed as an
operator, has a unique fixed point to which iterates of the operator 
converge regardless of the initial condition.  Verifying that conjecture
and establishing various extensions, however, proved to be quite 
difficult, requiring the reduction to an interacting particle system and
the application of coupling, large-deviation and entropy concepts.

Balaji has also initiated several exciting new directions of research. 
Together with Nick McKeown, Balaji has shown that a comibined-input-
output-queueing switch with an appropriate algorithm can achieve both
fast switching/routing infrastructure and guaranteed quality of service.
Balaji has developed new randomized algorithms to emualate effective
but computationally burdensome deterministic algorithms, producing
significant applications to load balancing and cache replacement.