Professor, Department of Computer
Science and Engineering, University of Washington, since 1998.
Associate Professor, Department of Computer
Science and Engineering, University of Washington, since 1991-1998.
Assistant Professor, Department of Computer Science and Engineering, University of Washington, 1986-1991.
Ph.D., Computer Science, Stanford University, January, 1986.
Advisor: Prof. Ernst Mayr. Thesis title: The Complexity of Parallel
Algorithms .
B.A., Mathematics, Reed College, Portland, Oregon, June, 1981.
Visiting Professor of Computer Science, Department of Computer
Science and Automation, Indian Institute of Science, Bangalore, India,
1993-1994.
Mathematical Sciences Research Institute, Berkeley, California.
Postdoctoral research fellow, 1985-1986.
Stanford University. Research assistant, 1983-1985. Teaching
assistant 1982-1985.
University of California at Berkeley. Research assistant, summer
1983.
IBM Watson Research Center, Yorktown Heights, New York. Research
assistant, summer 1982.
Control-C Software, Portland, Oregon. Systems programmer, 1981.
Best Paper Award,
1996 ACM Symposium on User Interface Software and Technology.
Indo-American Fellowship, Indo-US Subcommission on Education and
Culture, Award to support sabbatical visit to the Indian Institute of
Science, Bangalore, India, 1993-1994.
Fulbright Senior Scholar Award (declined), 1993-1994.
NSF Presidential Young Investigator Award, 1987-1992.
NSF Graduate
Fellowship, Stanford University, 1981-1984.
Phi Beta Kappa, Reed College, 1981.
NSF KDI Grant ``A Framework for Particle Simulation from
Proteins to Planetesimals'', with G. Lake and T. Quinn, $1,000,000
over 3 years, September, 1999.
NSF Grant ``Applications of Algorithmic Techniques,''
$118,000 over 2 years, August 1997.
NSF ESS Planning Grant,
``Applying Model Checking to Large Software System
Specifications,'' with D. Notkin and P. Beame,
$70,000 over one year, August 1997.
Indo-US Subcommission on Education and Culture: Indo-American
Fellowship to support a sabbatical visit to the Indian Institute of
Science, 1993-1994.
Fulbright Senior Scholar Award (declined), 1993-1994.
NSF Grant ``An Experimental Study of Parallel and
Distributed Algorithms,'' $150,000 over 2 years, September 1992.
NSF Institutional Infrastructure Award, ``High Performance
Parallel/Distributed Computing,'' with
A. Borning, T. DeRose, H. Levy, D. Notkin, E. Lazowska, L. Snyder,
S. Tanimoto, and J. Zahorjan, $1,600,377 over 4 years, July 1992.
NSF Research Experiences for Undergraduates (REU) Supplement,
$4,000, March 1991.
NSF Grant to support regional conference (WOBCATS),
with R. Ladner, P. Beame, L. Ruzzo, and M. Tompa, $10,000
over 2 years, April, 1990.
NSF/DARPA Parallel Computing Award,
with P. Beame and L. Ruzzo, $200,000 over 3 years, May, 1989.
DEC Equipment Award, $37,500 per year over 3 years, February, 1988.
DEC Equipment Award, $37,500, April, 1987.
NSF Presidential Young Investigator Award, $62,500 per year over 5
years, January, 1987.
UW Graduate School Research Fund, $5,000, November, 1986.
1997 ACM Symposium on the Theory of Computing.
1997 ACM-SIAM Symposium on Discrete Algorithms.
1996 International Parallel Processing Symposium.
1995 ACM Symposium on Parallel Algorithms and Architectures.
1993 IEEE Symposium on the Foundations of Computer Science.
1993 ACM Symposium on Parallel Algorithms and Architectures.
1992 ACM Symposium on Principles of Distributed Computing.
1991 ACM Symposium on Parallel Algorithms and Architectures.
Omid Madani, June 2000, ``Markov Decision
Processes''. Employment: Fizzy Labs.
William Chan, Ph.D., December 1999, ``Symbolic Model Checking
for Large Software Specifications,'' (co-advised with Paul Beame and
David Notkin). Deceased.
Joao Setubal, Ph.D., September, 1992, ``Implementation
of Parallel Network Flow Algorithms.'' Employment: University of Campinas,
Brazil.
Simon Kahan, Ph.D., October, 1991, ``Real-Time Processing of
Moving Data.'' (Co-advised with Paul Beame.) Employment: Tera Computer
Company.
Erik Brisson, Ph.D., August, 1990, ``Representation of $d$-Dimensional Geometric Objects.''
Design Intelligence, Algorithm Design, 1997, 1998.
Object Technology International, Constraint Solving, 1996.
2000-2001 Associate Chair (introductory courses and outreach),
Executive Committee, 142/143 Stewardship (ch), Introductory Placement
Exams, Teaching Assignments, Faculty Recruiting
1999-2000 Department Executive Committee, Professional
Master's Program Coordinator,
Masters Admissions Committee (Chair), Tutored Video Instruction
Coordinator, Faculty Recruiting Committee.
1998-1999 Professional Master's Program Coordinator,
Masters Admissions Committee (Chair), Educational Technology and
Distance Learning
1997-1998 Professional Masters Program Coordinator, Masters
Admissions (ch), Extension Liaison
1996-1997 Graduate Admissions (Chair), Department Executive Committee, Professional Masters Program Coordinator.
2000-2001 CSE 142, Introductory Programming, CSE 521, Design and
Analysis of Algorithms (G).
1999-2000 CSE 598, Complexity Theory (G), CSE 521, Design and
Analysis of Algorithms (G), CSE 142/143 TVI, Introductory Programming.
1998-1999 CSE 143, Introductory Programming II (U), CSE 321,
Discrete Structures (U), CSE 522, Advanced Algorithms (G).
1997-1998 CSE 341, Programming
Languages (U), CSE 321, Discrete Structures (U), CSE 521, Design and
Analysis of Algorithms (G)
1996-1997 CSE 326, Data Structures (U), CSE 341, Programming Languages (U).
Anderson, R. J., "Tree data structures for N-body simulation,"
SIAM Journal on Computing, 28(6):1923--1940, 1999.
Chan, W., Anderson, R. J., Beame, P., Burns, S., Modugno, F.,
Notkin, D., Reese, J., "Model checking large software specifications,"
IEEE Transactions on Software Engineering, 24(7):498-520, July 1998.
Anderson, R. J., Woll, H., ``Algorithms for the certified write all
problem,'' SIAM Journal on Computing, 26, 5, October
1997, pp. 1277-1283.
Anderson, R. J., Beame, P., Brisson, E.,
``Parallel algorithms for arrangements,''
Algorithmica, 15 (2), 1996, pp. 104-125.
(Preliminary version in Proceedings of the
2nd Annual ACM Symposium on
Parallel Algorithms and Architectures, July, 1990, pp. 298-306.)
Anderson, R. J., Setubal, J. C., ``A parallel implementation
of the push-relabel algorithm for the maximum flow problem,''
Journal of Parallel and Distributed Computing, 29 (1), 1995,
pp. 17-26.
(Preliminary version in Proceedings of the
4th Annual ACM Symposium on Parallel Algorithms
and Architectures, July 1992, pp. 168-177.)
Anderson, R. J., Simons, B., ``A fast heuristic for loop parallelization,''
Parallel Processing Letters, 4 (3), 1994, pp. 281-299.
(Preliminary Version:
Anderson, R. J., Munshi, A. A., Simons, B., ``A scheduling problem
arising from loop parallelization on MIMD machines,''
Proceedings of the 3rd Aegean Workshop
on Computing, July 1988, Springer-Verlag, pp. 124-133.)
Anderson, R. J.,
``Primitives for asynchronous list compression,''
Mathematical Systems Theory, 27, 1994, pp. 453-470.
(Preliminary version in Proceedings of the
4th Annual ACM Symposium on Parallel Algorithms
and Architectures, July 1992, pp. 199-208.)
Anderson, R. J., Setubal, J. C., ``Parallel and sequential
implementations of maximum-flow algorithms'' Network Flows and
Matching, Johnson and McGeoch editors, AMS, 1993, pp. 1-18.
Anderson, R. J., Kahan, S., and Schlag, M.,
``Single-layer cylindrical compaction,'' Algorithmica, 9,
1993, pp. 293-312. (Preliminary version: ``An $O(n\log n)$
algorithm for 1-D tile compaction,''
Proceedings of the International Conference on
Computer-Aided Design, Santa Clara, California, November 1989, pp 144-148.)
Anderson, R. J., Miller, G. L., ``Deterministic parallel list
ranking,'' Algorithmica, 6, 1991, pp. 859-868.
(Preliminary version in Proceedings of the
3rd Aegean Workshop on Computing, July 1988, Springer-Verlag,
pp. 81-90.)
Anderson, R. J., Snyder, L., ``A comparison of shared and
nonshared memory models of parallel computation,'' Proceedings
of the IEEE, 79,
4, April 1991, pp. 480-487.
Aggarwal, A., Anderson, R. J., Kao, M-Y., ``Parallel depth-first
search in general directed graphs,''
SIAM Journal on Computing, 19, 2, April, 1990, pp. 397-409.
(Preliminary version in Proceedings
of the Twenty First Annual ACM Symposium on the Theory of Computing, 1989,
pp. 297-308.)
Anderson, R. J., Miller, G. L., ``A simple randomized parallel
algorithm for list-ranking,'' Information Processing
Letters, 33, 10 January 1990, pp. 269-273.
Anderson, R. J., Mayr, E. W., Warmuth, M. K., ``Parallel approximation
algorithms for bin packing,'' Information and Computing,
82, 3, September, 1989, pp. 262-277.
Anderson, R. J., Lovasz, L., Shor, P., Spencer, J., Tardos, E.,
Winograd, S., ``Disks, balls, and walls: an analysis of a combinatorial
game,'' American Mathematical Monthly, 96, 6, June-July
1989, pp. 481-493.
Aggarwal, A., Anderson, R. J., ``A random NC algorithm for depth
first search,'' \break Combinatorica, 8, 1, 1988, pp. 1-12.
(Preliminary version
in Proceedings of the Nineteenth Annual ACM Symposium on the Theory of
Computing, 1987, pp. 325-334.)
Anderson, R. J., ``A parallel algorithm for the maximal path
problem,'' Combinatorica, 7, 3, 1987,
pp. 315-326. (Preliminary
version in Proceedings of the Seventeenth Annual
ACM Symposium on the Theory of Computing, 1985, pp. 33-37.)
Anderson, R. J., Mayr, E., ``Parallelism and greedy algorithms,''
Advances in Computing Research, JAI Press, 4, 1987, pp. 17-38.
Anderson, R. J., Mayr, E., ``Parallelism and the maximal path problem,'' Information Processing Letters, 24, 2, 1987, pp. 121-126.
Anderson, R. J., Chan, W., Beame, P., Notkin, D.
"Experiences with the Application of Symbolic Model Checking to the Analysis
of Software Specifications," Proceedings of the
Andrei Ershov Third International Conference on
Perspectives of System Informatics, Novosibirsk, Russia, pp. 355-361,
July, 1999.
Anderson, R. J., Sobti, S.,
"The table layout problem,"
COMPGEOM '99. Proceedings of the 15th ACM Symposium on
Computational Geometry, pp.115-123, 1999.
Chan, W., Anderson, R. J., Beame, P., Jones, D. H., Notkin,
D., and Warner, W. E.,
"Decoupling synchronization from local control for efficient symbolic
model checking of statecharts," Proceedings of the
1999 International Conference on Software Engineering, pp.142-151,
May, 1999.
Chan, W., Anderson, R. J., Beame, P., Notkin, D.,
"Improving efficiency of symbolic model checking for state-based system
requirements,'' 1998 ACM SIGSOFT Symposium on Software
Testing and Analysis, March, 1998.
Chan, W., Anderson, R. J., Beame, P., Notkin, D.,
``Combining constraint solving and symbolic
model checking for a class of systems with non-linear constraints,''
Computer Aided Verification, 9th International Conference,
CAV'97, June, 1997, pp. 316-327.
Borning, A., Anderson, R. J., and Freeman-Benson, B., ``Indigo: a
local propagation algorithm for inequality constraints,''
Proceedings of the
1996 ACM Symposium on User Interface Software and Technology,
November 1996, pages 129-136. Best Paper Award.
(Expanded version: University of
Washington Technical Report UW-CSE-96-05-01.)
Anderson, R. J., Beame, P., Burns, S., Chan, W., Modugno, F.,
Notkin, D., Reese, J., ``Model checking large software specifications,''
Proceedings of the
Fourth ACM SIGSOFT Symposium on the Foundations of Software
Engineering, October, 1996,
pp. 156-166. Invited to a special issue of IEEE Transactions on Software
Engineering. Submitted for journal publication.
Anderson, R. J., ``Tree data structures for N-body simulation,''
Proceedings of the 37th Annual Symposium on Foundations of
Computer Science, October, 1996,
pp. 224-233. Submitted for journal publication.
Anderson, R. J., ``Computer science problems in astrophysical
simulation,'' Proceedings
of the Silver Jubilee Workshop on Computing and
Intelligent Systems,
December, 1993, Indian Institute of Science. Tata McGraw-Hill Publishing
Company Limited, New Delhi, pp. 48-61.
Anderson, R. J., Setubal, J. C., ``A parallel implementation
of the push-relabel algorithm for the maximum flow problem,''
Proceedings of the 4th Annual ACM Symposium on Parallel Algorithms
and Architectures, July 1992, pp. 168-177.
(Journal version appeared in Journal of Parallel and Distributed
Computing.)
Anderson, R. J.,
``Primitives for asynchronous list compression,''
Proceedings of the 4th Annual ACM Symposium on Parallel Algorithms
and Architectures, July 1992, pp. 199-208.
(Journal version appeared in Mathematical Systems Theory.)
Anderson, R. J., Woll, H., ``Wait-free parallel algorithms for the
union-find problem,'' {Proceedings of the Twenty Third
Annual ACM Symposium on the Theory of
Computing, May, 1991, pp. 370-380.
Anderson, R. J., ``Parallel algorithms for generating random
permutations on a shared memory machine,''
Proceedings of the 2nd Annual ACM Symposium on
Parallel Algorithms and Architectures, July, 1990, pp. 95-102.
Anderson, R. J., Beame, P., Brisson, E.,
``Parallel algorithms for arrangements,''
Proceedings of the 2nd Annual ACM Symposium on
Parallel Algorithms and Architectures, July, 1990, pp. 298-306.
(Journal version appeared in Algorithmica.)
Anderson, R. J., Beame, P., Ruzzo, W. L., ``Low overhead
parallel schedules for task graphs,'' Proceedings of the
2nd Annual ACM Symposium on
Parallel Algorithms and Architectures, July, 1990, pp. 66-75.
Anderson, R. J., Kahan, S., and Schlag, M.,
``An $O(n\log n)$
algorithm for 1-D tile compaction,''
Proceedings of the International Conference on
Computer-Aided Design, Santa Clara, California, November 1989, pp 144-148.
(Journal version appeared in Algorithmica.)
Almquist, K., Anderson, R. J., Lazowska, E., ``The measured
performance of parallel dynamic programming implementations,''
Proceedings of the 1989 International Conference on Parallel
Processing, Volume 3, pp. 76-79.
Anderson, R. J., Miller, G. L., ``Deterministic parallel list
ranking,''
Proceedings of the 3rd Aegean Workshop on Computing,
July 1988, Springer-Verlag,
pp. 81-90. (Journal version appeared in
Algorithmica.)
Anderson, R. J., Munshi, A. A., Simons, B.,
``A scheduling problem
arising from loop parallelization on MIMD machines,''
Proceedings of the 3rd Aegean Workshop
on Computing, July 1988, Springer-Verlag, pp. 124-133.
(Journal version appeared in
Parallel Processing Letters.)
Aggarwal, A., Anderson, R. J., Kao, M-Y., ``Parallel depth-first
search in general directed graphs.''
Proceedings
of the Twenty First Annual ACM Symposium on the Theory of Computing, 1989,
pp. 297-308. (Journal version appeared in
SIAM Journal on Computing.)
Aggarwal, A., Anderson, R. J., ``A random NC algorithm for depth
first search,''
Proceedings of the Nineteenth Annual ACM Symposium on the Theory of
Computing, 1987, pp. 325-334. (Journal version appeared in
Combinatorica.)
Anderson, R. J., ``A parallel algorithm for the maximal path problem,'' Proceedings of the Seventeenth Annual ACM Symposium on the Theory of Computing, 1985, pp. 33-37. (Journal version appeared in Combinatorica.)
anderson@cs.washington.edu