I have annotated each paper with a partial list of keywords using the following key:

ApA = Approximation Algorithms; CoL = Computational Learning;
DiA = Distributed Algorithms;
ElN = Admission Control and Routing in Deregulated Electric Power Networks;
ErC = Error-Correcting Codes; ExA = Experimental Analysis of Algorithms;
GrC = Graph/Hypergraph Coloring; InW = Internet/WWW-related technologies;
NeD = Network Design; PaA = Parallel Algorithms; RaC = Randomness and Computation;
ReS = Resource Allocation and Scheduling; RoA = Routing Algorithms;
RWA = Routing and Wavelength Assignment in Optical Networking;
Oth = Other topics not covered above.

Please email me if you would like copies of some of these papers.

Journal Publications

  1. New Algorithmic Aspects of the Local Lemma with Applications to Routing and Partitioning, with F. T. Leighton, C.-J. Lu and S. B. Rao. Accepted for publication in SIAM Journal on Computing. [ApA, InW, RaC, RoA, RWA]

  2. Improved Bounds on the Sample Complexity of Learning, with Y. Li and P. M. Long. Journal of Computer and System Sciences, Vol. 62, 516-527, 2001. [CoL]

  3. A Constant-Factor Approximation Algorithm for Packet Routing and Balancing Local vs. Global Criteria, with C. P. Teo. SIAM Journal on Computing, Vol. 30, 2051-2068, 2001. [ApA, InW, RoA]

  4. The One-Inclusion Graph Algorithm is Near-Optimal for the Prediction Model of Learning, with Y. Li and P. M. Long. IEEE Transactions on Information Theory, Vol. 47, 1257-1261, 2001. [CoL]

  5. Better Approximation Guarantees for Job-Shop Scheduling, with L. A. Goldberg, M. S. Paterson and E. Sweedyk. SIAM Journal on Discrete Mathematics, Vol. 14, 67-92, 2001. [ApA, RaC, ReS]

  6. Contention Resolution with Constant Expected Delay, with L. A. Goldberg, P. D. MacKenzie, and M. S. Paterson. Journal of the ACM, Vol. 47, 1048-1096, 2000. [DiA, InW, RaC, ReS]

  7. Improved Algorithms via Approximations of Probability Distributions, with S. Chari and P. Rohatgi. Journal of Computer and System Sciences, Vol. 61, 81-107, 2000. [PaA, RaC]

  8. Approximation Algorithms for Disjoint Paths and Related Routing and Packing Problems, with A. Baveja. Mathematics of Operations Research, Vol. 25, 255-280, 2000. [ApA, InW, RaC, ReS, RoA, RWA]

  9. Retrieval Scheduling For Collaborative Multimedia Presentations, with Ping Bai and B. Prabhakaran. ACM/Springer-Verlag Multimedia Systems Journal, Vol. 8, 146-155, 2000. [InW, ReS]

  10. Low Discrepancy Sets Yield Approximate Min-Wise Independent Permutation Families, with M. Saks, S. Zhou and D. Zuckerman, Information Processing Letters, Vol. 73, 29-32, 2000. [InW, RaC]

  11. Improved Bounds and Algorithms for Hypergraph 2-coloring, with J. Radhakrishnan, Random Structures & Algorithms, Vol. 16, 4-32, 2000. [GrC, RaC]

  12. Approximating Low-Congestion Routing and Column-Restricted Packing Problems, with A. Baveja, Information Processing Letters, Vol. 74, 19-25, 2000. [ApA, InW, RaC, RoA]

  13. Improved Approximation Guarantees for Packing and Covering Integer Programs, SIAM Journal on Computing, Vol. 29, 648-670, 1999. [ApA, RaC]

  14. Computing with Very Weak Random Sources, with D. Zuckerman, SIAM Journal on Computing, Vol. 28, 1433-1459, 1999. [RaC]

  15. Explicit OR-Dispersers with Polylogarithmic Degree, with M. Saks and S. Zhou, Journal of the ACM, Vol. 45, 123-154, 1998. [RaC]

  16. Approximating Hyper-Rectangles: Learning and Pseudo-Random Sets, with P. Auer and P. M. Long, Journal of Computer and System Sciences, Vol. 57, 376-388, 1998. [CoL, RaC]

  17. Improved Parallel Approximation of a Class of Integer Programming Problems, with N. Alon, Algorithmica, Vol. 17, 449-462, 1997. [PaA, RaC]

  18. Randomized Distributed Edge Coloring via an Extension of the Chernoff-Hoeffding Bounds, with A. Panconesi, SIAM Journal on Computing, Vol. 26, 350-368, 1997. [DiA, GrC, RaC, ReS]

  19. On the Complexity of Distributed Network Decomposition, with A. Panconesi, Journal of Algorithms, Vol. 20, 356-374, 1996. [DiA, ReS]

  20. Randomness-Optimal Unique Element Isolation with Applications to Perfect Matching and Related Problems, with S. Chari and P. Rohatgi, SIAM Journal on Computing, Vol. 24, 1036-1050, 1995. [PaA, RaC]

  21. Chernoff-Hoeffding Bounds for Applications with Limited Independence, with J. P. Schmidt and A. Siegel, SIAM Journal on Discrete Mathematics, Vol. 8, 223-250, 1995. [RaC, ReS]

  22. The Local Nature of Delta-Coloring and its Algorithmic Applications, with A. Panconesi, Combinatorica, Vol. 15, 255-280, 1995. [DiA, GrC]

  23. On Finding the Minimum Bandwidth of Interval Graphs, with R. Mahesh and C. Pandu Rangan, Information and Computation, Vol. 95, 218-224, 1991. [Oth]

  24. Efficient Algorithms for the Minimum Weighted Dominating Clique Problem on Permutation Graphs, with C. Pandu Rangan, Theoretical Computer Science, Vol. 91, 1-21, 1991. [Oth]

Refereed Conference Publications

  1. Distributions on Level-Sets with Applications to Approximation Algorithms. To appear, IEEE Symposium on Foundations of Computer Science (FOCS), 2001. [ApA, RaC, RoA]

  2. Finding Large Independent Sets of Hypergraphs in Parallel, with H. Shachnai. ACM Symposium on Parallel Algorithms and Architectures (SPAA), 2001. [PaA, RaC]

  3. Experimental Analysis of Algorithms for Bilateral-Contract Clearing Mechanisms Arising in Deregulated Power Industry, with C. Barrett, D. Cook, V. Faber, G. Hicks, A. Marathe, M. Marathe, Y. J. Sussmann, and H. Thornquist. To appear, Workshop on Algorithm Engineering (WAE), 2001. [ElN, ExA, RaC]

  4. Approximation Algorithms for Partial Covering Problems, with R. Gandhi and S. Khuller. International Colloquium on Automata, Languages, and Programming (ICALP), 2001. [ApA, RaC]

  5. New Approaches to Covering and Packing Problems. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 567-576, 2001. [ApA, PaA, RaC]

  6. Domatic Partitions and the Lova'sz Local Lemma. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 922-923, 2001. [ApA, RaC]

  7. Wavelength Rerouting in Optical Networks, or the Venetian Routing Problem, with A. Caprara, G. Italiano, G. Mohan, and A. Panconesi. Third International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 72-83, 2000. [ApA, InW, RWA]

  8. The Value of Strong Inapproximability Results for Clique. ACM Symposium on Theory of Computing (STOC), pages 144-152, 2000. [ApA, RaC]

  9. Optimal Design of Signaling Networks for Internet Telephony, with K. G. Ramakrishnan, K. Kumaran, M. Aravamudan, and S. Naqvi. IEEE Conference on Computer Communications (INFOCOM), pages 707-716, 2000. [InW, NeD, RaC]

  10. Improved Bounds on the Sample Complexity of Learning, with Y. Li and P. M. Long. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 309-318, 2000. [CoL]

  11. Application-layer Broker for Scalable Internet Services with Resource Reservation, with P. Bai and B. Prabhakaran. Seventh ACM Multimedia Conference (MM '99), pages 103-106, 1999. (Poster paper.) [InW, ReS]

  12. Low Discrepancy Sets Yield Approximate Min-Wise Independent Permutation Families, with M. Saks, S. Zhou and D. Zuckerman, Third International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), pages 11-15, 1999. [InW, RaC]

  13. New Algorithmic Aspects of the Local Lemma with Applications to Routing and Partitioning, with F. T. Leighton and S. B. Rao, ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 643-652, 1999. [ApA, InW, RaC, RoA, RWA]

  14. Improved Bounds and Algorithms for Hypergraph Two-coloring, with J. Radhakrishnan, IEEE Symposium on Foundations of Computer Science (FOCS), pages 684-693, 1998.[GrC, RaC]

  15. Low-bandwidth Routing and Electrical Power Networks, with D. Cook, V. Faber, M. Marathe, and Y. J. Sussmann, International Colloquium on Automata, Languages, and Programming (ICALP), pages 604-615, 1998. [ApA, ElN, RaC]

  16. Multicommodity Flow and Circuit Switching, with F. T. Leighton and S. B. Rao, Hawaii International Conference on System Sciences (HICSS), pages 459-465, 1998. [ApA, InW, RaC, RWA]

  17. Improved Approximations for Edge-disjoint Paths, Unsplittable Flow, and Related Routing Problems, IEEE Symposium on Foundations of Computer Science (FOCS), pages 416-425, 1997. [ApA, InW, RaC, ReS, RoA, RWA]

  18. Mechanism Design for Intellectual Property Rights Protection, with P. S. Giridharan, International Conference on Information Systems (ICIS), 1997. [Oth]

  19. Approximating Hyper-Rectangles: Learning and Pseudo-Random Sets, with P. Auer and P. M. Long, ACM Symposium on Theory of Computing (STOC), pages 314-323, 1997. [CoL, RaC]

  20. A Constant-Factor Approximation Algorithm for Packet Routing, and Balancing Local vs. Global Criteria, with C. P. Teo, ACM Symposium on Theory of Computing (STOC), pages 636-643, 1997. [ApA, InW, RoA]

  21. Better Approximation Guarantees for Job-Shop Scheduling, with L. A. Goldberg, M. S. Paterson and E. Sweedyk, ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 599-608, 1997. [ApA, RaC, ReS]

  22. Improving the Discrepancy Bound for Sparse Matrices: Better Approximations for Sparse Lattice Approximation Problems, ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 692-701, 1997. [ApA, GrC, RaC]

  23. Improved Parallel Approximation of a Class of Integer Programming Problems, with N. Alon, International Colloquium on Automata, Languages, and Programming (ICALP), pages 562-573, 1996. [PaA, RaC]

  24. An Extension of the Lova'sz Local Lemma, and its Applications to Integer Programming, ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 6-15, 1996. [ApA, GrC, RaC]

  25. Splitters and Near-optimal Derandomization, with M. Naor and L. J. Schulman, IEEE Symposium on Foundations of Computer Science (FOCS), pages 182-191, 1995. [RaC]

  26. Contention Resolution with Bounded Delay, with M. S. Paterson, IEEE Symposium on Foundations of Computer Science (FOCS), pages 104-113, 1995. [DiA, RaC, ReS]

  27. Explicit Dispersers with Polylog Degree, with M. Saks and S. Zhou, ACM Symposium on Theory of Computing (STOC), pages 479-488, 1995. [RaC]

  28. Improved Approximations of Packing and Covering Problems, ACM Symposium on Theory of Computing (STOC), pages 268-276, 1995. [ApA, RaC]

  29. Computing with Very Weak Random Sources, with D. Zuckerman, IEEE Symposium on Foundations of Computer Science (FOCS), pages 264-275, 1994. [RaC]

  30. Improved Algorithms via Approximations of Probability Distributions, with S. Chari and P. Rohatgi, ACM Symposium on Theory of Computing (STOC), pages 584-592, 1994. [PaA, RaC]

  31. Randomness-Optimal Unique Element Isolation, with Applications to Perfect Matching and Related Problems, with S. Chari and P. Rohatgi, ACM Symposium on Theory of Computing (STOC), pages 458-467, 1993. [PaA, RaC]

  32. Chernoff-Hoeffding Bounds for Applications with Limited Independence, with J. P. Schmidt and A. Siegel, ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 331-340, 1993. [RaC, ReS]

  33. Fast Randomized Algorithms for Distributed Edge Coloring, with A. Panconesi, ACM Symposium on Principles of Distributed Computing (PODC), pages 251-262, 1992. [DiA, GrC, RaC, ReS]

  34. Improved Distributed Algorithms for Coloring and Network Decomposition Problems, with A. Panconesi, ACM Symposium on Theory of Computing (STOC), pages 581-592, 1992. [DiA, GrC]

Chapters in Books and Survey Articles

  1. Combinatorial Problems Arising in Deregulated Electrical Power Industry: Survey and Future Directions, with D. Cook, G. Hicks, V. Faber, M. Marathe, Y. J. Sussmann, and H. Thornquist, Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems (P. M. Pardalos, Editor), Kluwer Academic Publishers, pages 138-162, 2000. [ApA, ElN, RaC]

  2. Low-discrepancy Sets for High-dimensional Rectangles: A Survey, Bulletin of the European Association for Theoretical Computer Science, Number 70, pages 67-76, 2000. [ErC, RaC]

  3. A Survey of the Role of Multicommodity Flow and Randomization in Network Design and Routing, Randomization Methods in Algorithm Design (P. M. Pardalos, S. Rajasekaran and J. Rolim, editors), American Mathematical Society, Series in Discrete Mathematics and Theoretical Computer Science, Volume 43, pages 271-302, 1999. [ApA, InW, RaC, RoA]

  4. Approximation Algorithms via Randomized Rounding: a Survey. Lectures on Approximation and Randomized Algorithms (M. Karonski and H. J. Promel, editors), Series in Advanced Topics in Mathematics, Polish Scientific Publishers PWN, Warszawa, pages 9-71, 1999. [ApA, InW, RaC, RoA]

  5. Scheduling and Load-balancing via Randomization, Proc. Pre-Conference Workshop on Randomized Algorithms, Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 1997. [RaC, ReS]

  6. The Role of Randomness in Computation, BRICS Notes Series NS-95-6, Basic Research Institute in Computer Science, Denmark, 1995. [RaC]

Technical Reports and Theses

  1. Techniques for Probabilistic Analysis and Randomness-Efficient Computation, TR 93-1378, Department of Computer Science, Cornell University, 1993. [DiA, GrC, PaA, RaC, ReS]

  2. A Generalization of Brooks' Theorem, TR 92-1302, Department of Computer Science, Cornell University, 1992. [DiA, GrC]

  3. Fast Algorithms for Some Problems on Interval and Permutation Graphs, B. Tech. Thesis, Department of Computer Science and Engineering, Indian Institute of Technology, Chennai, 1989. [Oth]

Other Papers

  1. Fast and Efficient Bandwidth Reservation for Robust Routing, with L. Fleischer, A. Meyerson, I. Saniee, and B. Shepherd, DIMACS Mini-Workshop on Quality of Service Issues in the Internet, 2001. [ApA, InW, ReS, RoA]


Aravind Srinivasan / srin@research.bell-labs.com