Bala KALYANASUNDARAM

Department of Computer Science
Georgetown University
Washington, DC20057
(202)687-2709
pal.georgetown.edu

EDUCATION

B.Sc., Applied Sciences, India, 1979.

B.E., Electronics and Communication, Indian Institute of Science, 1982.

M.S., Computer Science, Indian Institute of Technology, 1987.

Ph. D., Computer Science, Pennsylvania State University, 1988.

RESEARCH INTERESTS:

Computational Complexity

On-line, Probabilistic and Parallel Algorithms

Computational Biology and Geometry

Next Generation Network

UNIVERSITY POSITIONS

Georgetown University : (2001-)

Professor in Computer Science Department

Georgetown University : (2000-2001)

Associate Professor in Computer Science Department

University of Pittsburgh: (1994-2000)

Associate Professor in Computer Science Department

University of Pittsburgh: (1988-1994)

Assistant Professor in Computer Science Department

FUNDING

1. National Science Foundation. Topics in Space-Bounded Computations, CCR-9009318; $ 31,483; Aug 1990- Jul 1993.

2. National Science Foundation (with R. Daley). Research in Multi-Agent Learning Algorithms, CCR-9202158; $ 90,117; Aug 1992- Feb 1995.

3. National Science Foundation (with K. Pruhs). Scheduling Protocols for Networked Multi-Media Applications, CCR-9734927; $ 201,141; Jun 1998- Jan 2001.

4. Air Force Office of Scientific Research (with K. Pruhs). Dynamic Spectrum Allocation Algorithms, AFOSR; $ 199,996; Dec 1999- Nov 2001.

5. National Science Foundation (with K. Pruhs). Research Experience for Undergraduates, $ 5,000; Sep 1999- Aug 2000.

6. National Science Foundation Collaborative Research: Algorithmic Problems in Next Generation Networks, $ 143,000; Jul 2001- Jun 2004.

PATENTS:

Optimal Dynamic Bandwidth Management for Mobile Stations, (with Mahe Velauthapillai and John Waclawsky), US patent application is being processed at Cisco.

Browser and User Based Burst Bandwidth Management, (with Mahe Velauthapillai and John Waclawsky), US patent application is being processed at Cisco.

JOURNAL PUBLICATIONS

$\star$ indicates that the paper has been invited for normal refereeing process for journal publication.

1. $\parbox{5.8in}{Rounds versus Time for the Two Person Pebble Game, (w... ...Symposium on Theoretical Aspects of Computer Science} (STACS), 517-529, 1989. }$
2. $\star$ $\parbox{5.8in}{On the Power of White Pebbles, (with G. Schnitger), {... ...red in the {\em Symposium of the Theory of Computing} (STOC), 258-266, 1988. }$
3. $\parbox{5.8in}{The Probabilistic Communication Complexity of Set-Int... ...eared in the {\em Conference on Structure in Complexity Theory}, 41-49, 1987.}$
4. $\parbox{5.8in}{On-line Weighted Matching, (with K. Pruhs), {\bf Jour... ...appeared in the {\em Symposium on Discrete Algorithms} (SODA), 234-240, 1991. }$
5. $\parbox{5.8in}{A Competitive Analysis of Algorithms for Searching Un... ...Algorithms}, 157-162, 1991, under the title \lq\lq Visual Searching and Mapping''. }$
6. $\parbox{5.8in}{Not All Insertion Methods Yield Constant Approximate ... ... Pruhs and V. Bafna), {\bf Theoretical Computer Science, 125, 345-353, 1994}. }$
7. $\star$ $\parbox{5.8in}{Constructing Competitive Tours from Local Information... ...al Colloquium on Automata, Languages and Programming} (ICALP), 102-113, 1993. }$
8. $\star$ $\parbox{5.8in}{Probabilistic PFIN-type learning, (with R. Daley and ... ...in the {Workshop on Analogical and Inductive Inference} (AII), 151-169, 1992. }$
9. $\star$ $\parbox{5.8in}{Breaking the probability $\frac{1}{2}$ barrier in FI... ...r has appeared in {\em Computational Learning Theory} (COLT), 203-217, 1992. }$
10. $\parbox{5.8in}{On-line Load Balancing of Temporary Tasks, (with Y. A... ...n the {\em Workshop on Algorithms and Data Structures} (WADS), 119-130, 1993. }$
11. $\parbox{5.8in}{ The Online Transportation Problem, (with K. Pruhs), ... ...appeared in the {\it European Symposium on Algorithms} (ESA), 484-493, 1995. }$
12. $\parbox{5.8in}{ An Optimal Deterministic Algorithm for Online b-Matc... ...ons of Software Technology and Theoretical Computer Science}, 193-199, 1996. }$
13. $\star$ $\parbox{5.8in}{ Fault-Tolerant Real-Time Scheduling, (with K. Pruhs)... ...appeared in the {\em European Symposium on Algorithms} (ESA), 296-307, 1997. }$
14. $\parbox{5.8in}{ Speed is as Powerful as Clairvoyance, (with K. Pruhs... ... Annual Symposium on Foundations of Computer Science} (FOCS), 214-221, 1995. }$
15. $\star$ $\parbox{5.8in}{ Maximizing Job Completions Online, (with K. Pruhs), ... ... appeared in the {\it European Symposium on Algorithms} (ESA), 235-246, 1998. }$
16. $\star$ $\parbox{5.8in}{ Eliminating Migration in Multi-Processor Scheduling,... ...ppeared in the {\it Symposium on Discrete Algorithms} (SODA), 499-506, 1999. }$
17. $\star$ $\parbox{5.8in}{ The Communication Complexity of Enumeration, Elimina... ...ry version of the paper has appeared in the conference {\it Structures 2000.} }$
18. $\parbox{5.8in}{ Caching for Web Searching (with J. Noga, K. Pruhs, a... ...on has appeared in {\it 7th Scandinavian Workshop on Algorithm Theory, 2000.} }$
19. $\star$ $\parbox{5.8in}{ Scheduling Broadcasts in Wireless Network (with Kirk... ...iminary version has appeared in {\it European Symposium on Algorithms, 2000.} }$
20. $\parbox{5.8in}{ Dynamic Spectrum Allocation (with K. Pruhs), accep... ... Foundations of Software Technology and Theoretical Computer Science}, 2000. }$
21. $\parbox{5.8in}{ Errata: A New Algorithm for Scheduling Periodic, Rea... .... Torng), appeared in {\bf Algorithmica, Vol. 28, No. 3, pp. 269-270, 2000.} }$

BOOK CHAPTERS

1. Communication Complexity and Lower Bounds in Sequential Computation (with G. Schnitger), invited technical paper, Teubner-Texte zur Informatik, Band 1, Edited by J. Buchmann, H. Ganzinger and W.J. Paul, 1992. A preliminary version of this paper has appeared in the Annual Allerton Conference on Communication, Control and Computation, 749-757, 1986, under the title ``On the Power of One-Tape Turing Machines''.
2. Algorithms, Handbook of Statistics Volume 9: Computational Statistics, 1-16, 1993.
3. Towards Reduction Arguments for FINite Learning, (with R. Daley), GOSLER final report: Algorithmic Learning for Knowledge Based Systems, Lecture Notes in Artificial Intelligence 961, 63-75, 1995.
4. Online Network Optimization Problems, (with K. Pruhs), Online Algorithms, The State of the Art, Lecture Notes in Computer Science 1442, 268-280, 1998.

CONFERENCE PROCEEDINGS (REFEREED)

These are additional conference publications. The journal version is being reviewed or under preparation.

1. Probabilistic vs. Pluralistic Learning with Mind Change (with R. Daley), Mathematical Foundations of Computer Science (MFCS), 218-226, 1992.
2. Capabilities of Probabilistic Learners with Bounded Mind Changes, (with R. Daley), Computational Learning Theory (COLT), 182-191, 1993.
3. Capabilities of Fallible FINite Learning, (with R. Daley and M. Velauthapillai), Computational Learning Theory (COLT), 199-208, 1993.
4. Use of Reduction Arguments in Determining Popperian FIN-Type Learning Capabilities, (with R. Daley), Algorithmic Learning Theory (ALT), 173-186, 1993.
5. Fault-Tolerant Scheduling, (with K. Pruhs), Symposium on the Theory of Computing (STOC), 115-124, 1994. Journal version is under review for SIAM Journal of Computing.
6. Simulating Teams with Many Conjectures, (with M. Velauthapillai), Algorithmic Learning Theory (ALT), 1995.
7. FINite Learning Capabilities and Their Limits, (with R. Daley), Computational Learning Theory (COLT) 1997.
8. Minimizing Flow-Time Nonclairvoyantly, (with K. Pruhs), 38th Annual Symposium on Foundations of Computer Science (FOCS), 345-352, 1997. Journal version under review in Journal of the ACM.

INVITED TALKS

1. Dynamic Pricing and Renegotiation for Network Management, Capital Area Theory Seminar, University of Maryland, 2000.

2. Computational Clairvoyance, Capital Area Theory Seminar, University of Maryland, 1999.

3. Computational Clairvoyance, Georgetown University, 1999.

4. Caching for Web Searching, Georgetown University, 1999.

5. Online Network Optimization Problems, Workshop on On-line Algorithms, Dagstuhl, Germany, 1996.

6. Constructing Competitive Tours from Local Information (or Learning/Exploring an Unknown Weighted Planar Graph), Capital Area Theory Seminar, Georgetown University, 1992.

7. Visual Searching and Mapping, DIMACS Workshop on On-line Algorithms, 1991.

8. On-line Algorithms, Pennsylvania State University, 1991.

OTHER TECHNICAL PUBLICATIONS

1. Detection of Bi-Symmetric Functions, (with R. Owens), TR-CS-86-05, Penn. State University.

2. On the Separation of Various Complexity Classes in Communication Complexity, TR-CS-87-16, Penn. State University.

3. Dynamic Pricing and Renegotiation for Network Management, (with Mahe Velauthapillai, and John Waclawsky), to be submitted for publication.

4. Wireless Resource Optimality Through Dynamic Service Selection, (with Mahe Velauthapillai, and John Waclawsky), submitted to MOBICOM 2001.

Teaching

COURSES TAUGHT: ($\star$) indicates a new course designed and introduced by me.

1. COSC071 Computer Science I.
2. COSC385 Theoretical Computer Science.
3. ($\star$) COSC393 Wireless Networks.
4. Data Structures, Discrete Structures, Algorithms, Theory and Cryptography are some of the courses taught at University of Pittsburgh.

UNDERGRADUATE RESEARCH EXPERIENCE

Adrien Treuille (Georgetown), Online Algorithm, 2000-2001.

Eric W Wiewiora (Univ. of Pittsburgh), Dynamic Spectrum Allocation, 2000-2001.

MASTER'S PROJECT

Sushma Banthia, Project, Efficient On-line Range Searching in Computational Geometry, University of Pittsburgh, April 1991.

THESIS COMMITTEE MEMBER

1. Hakan Aydin (Computer Science, Ph. D candidate), Enhancing Performance and Fault Tolerance in Reward-based Scheduling.
2. Claude-Nicolas Fiechter (Computer Science, Ph. D., 1997), Design and Analysis of Efficient Reinforcement Learning Algorithms.
3. Shaocen Han (Mathematics, Ph. D., 1995), Toughness of Graphs.
4. Hans Ros (Computer Science, Ph. D., 1992), Learning Boolean Functions with Genetic Algorithms.
5. Zhibo Chen (Mathematics, Ph. D., 1991), On Polynomial Representations of Functions over Integer Residue Class Rings and over Finite Fields.
6. Evelyn Duesterwald (Computer Science, M.S., 1990), Static Concurrency Analysis in the Presence of Procedures.

PROFESSIONAL ACTIVITIES

Guest Editor for:

Journal of Scheduling

Panelist for:

NSF proposals in Theoretical Computer Science

NSF Infrastructure proposals

Reviewer for:

Information Processing Letters

SIAM Journal on Computing

IEEE Transactions on Computers

Journal of Computer and System Sciences

Information and Computation

NSF proposals in Theoretical Computer Science

ESA, FOCS, FST&TCS, STOC, SODA conferences