Publications

    Journal Publications

  1. Parallel Sorting in Two dimensional VLSI models of Computation, with I.D. Scherson, IEEE Transaction on Computers, February 1989, pp. 238-249.

    The original shearsort Tech-report - my first paper !,

  2. Two Optimal algorithms for mesh using shear sort, with I.D. Scherson and Y. Ma, Journal of Parallel and Distributed Computing, Feb 1989, pp. 151-165.
  3. Finding an approximate-median with high probability in constant parallel time, Information Processing Letters, 34, 1990, pp. 77-80.
  4. Optimal parallel randomized algorithms for three-dimensional convex hulls and related problems, with J. Reif, SIAM Journal on Computing, 21:3, June 1992 pp. 466--485.
  5. Optimal randomized parallel algorithms for computational geometry, with J. Reif, Algorithmica, 1992:7, pp. 91--117.
  6. Random Sampling techniques for binary search on fixed connection networks with applications to geometric algorithms, with J. Reif, SIAM Journal on Computing, June 1994, pp. 633-651.
  7. Dynamic point-location in arrangements of hyperplanes, with K. Mulmuley, Discrete and Computational Geometry (Special issue), 8, 1992, pp. 335--360.
  8. On Parallel Integer Sorting, with S. Rajasekaran, Acta Informatica, 29, Jan 1992 pp. 1--15.
  9. Some Observations on Skip-Lists, Information Processing Letters, 39, August 1991, pp. 173--176.
  10. Improved Selection in Totally Monotone Arrays, with Y. Mansour, J. Park and B. Scheiber, Int'l Journal on Computational Geometry and Applications, 3, 1993, pp. 115-132.
  11. Fractional Cascading Revisited, Journal of Algorithms, 19, Sept 1995, pp. 161--172.
  12. An efficient output-sensitive hidden-surface removal algorithm for polyhedral terrains, with J. Reif, Mathematical and Computer Modelling, 21:5, 1995, pp. 89--104.
  13. Selection in Monotone Matrices and computing k-th Nearest Neighbours, with P. Agarwal, Journal of Algorithms, 20, June 1996, pp. 581--601.
  14. Lower bounds for parallel algebraic decision trees, parallel complexity of convex hulls and related problems, Theoretical Computer Science, 188, 1997, pp. 59--78.
  15. Parallel searching in generalized Monge arrays with applications , with A. Aggarwal, D. Kravets, J. Park, Algorithmica, 19:3, 1997, pp. 291 -- 317.
  16. Optimal output-sensitive algorithms for constructing planar hulls in parallel, with N. Gupta, Computational Geometry: Theory and Applications, 8, 1997, pp. 151-166.
  17. On a simple, practical optimal output-sensitive randomized planar convex-hull algorithm, with B. Bhattacharya, Journal of Algorithms 25, Oct 1997, pp. 177-- 193.
  18. Distribution sensitive algorithms, with N. Gupta, Nordic Journal on Computing (special issue), 6, 1999, pp. 194 -- 211.
  19. An efficient output-size sensitive parallel algorithm for hidden-surface removal for terrains, with N. Gupta, Algorithmica, 31, 2001, pp. 179 -- 207.
  20. Fast and optimal parallel multidimensional search in PRAMs with applications to linear-programming and related problems, with Martin Dyer, SIAM Journal on Computing, 30 (5), 2001.
  21. Improved Algorithms for Uniform Partitions of Points, with P. Agarwal and B. Bhattacharya, Algorithmica, 32(4), 2002, pp. 521 -- 539.
  22. Planar Graph Blocking for External Searching, with S. Baswana, Algorithmica, 34(3), 2002, pp 298--308.
  23. Towards a theory of cache-efficient algorithms with S. Chatterjee, N. Dumeer, Journal of the ACM, 49(6), Nov 2002, pp 828 --858.
  24. Faster output-sensitive algorithms for three dimensional convex hull and maximal vector problem, with N. Gupta, Journal of Parallel and Distributed Computing 63(4), 2003, pp. 488 -- 500.
  25. Fair adaptive bandwidth allocation: a rate control based active queue management discipline with Abhinav Kamra, Huzur Saran and Rajeev Shorey, Computer Networks, Vol. 44, No. 2, 2004, pp. 135 -- 152.
  26. A generalization of the 0-1 principle for sorting, with S. Rajasekaran, Information Processing Letters 94(1), 2005, pp.43 -- 47.
  27. Improved Decremental Algorithms for Maintaining Transitive Closure and All-Pairs Shortest Paths, with S. Baswana and R. Hariharan, Journal of Algorithms, Volume 62(2) April 2007, pp. 74--92.
  28. A linear time algorithm for approximate 2-means clustering with Y. Sabharwal, Computational Geometry: Theory and Applications, 32(2), 2005, pp. 159 -- 173.
  29. Nearest Neighbors Search using Point Location in Balls with applications to approximate Voronoi Decompositions with N. Sharma and Y. Sabharwal, Journal of Computer and System Sciences, Volume 72(6) , September 2006, Pages 955-977.
  30. A Simple Linear Time Algorithm for Computing a $(2k-1)$-Spanner of $O(n^{1+1/k)}$ Size in Weighted Graphs, with S. Baswana, Random Structures and Algorithms, Vol 30, 2007, Pages 532 -- 563.
  31. Approximate distance oracles for unweighted graphs in $O(n^2)$ time , with S. Baswana, ACM Transactions on Algorithms (Special issue SODA 2004), Vol 2(4), Oct 2006, Pages 557 - 577.
  32. A linear time deterministic algorithm to find a small subset that approximates the centroid , with P. Worah, Information Processing Letters Vol. 105(1), Dec 2007, Pages 17 -- 19.
  33. Optimal and practical algorithms for sorting on the PDM, with S. Rajasekaran, IEEE Transactions on Computers, Vol 57(4), April 2008, Pages 547 - 561.
  34. Combating I-O bottleneck using prefetching: Model, Algorithms and Ramifications, with A. Verma, Journal of Supercomputing 45( 2): 205-235 2008.
  35. All-Pairs Nearly 2-Approximate Shortest-Paths in O( n2 polylog n) Time, with Surender Baswana, and Vishrut Goyal, Theoretical Computer Science 410(1): 84-93 2009.
  36. Improvements on the Johnson bound for Reed Solomon Codes, with Muralidhara V.N., Discrete Applied Mathematics Volume 157, Issue 4, 28 February 2009, Pages 812-818 .
  37. Linear-Time Approximation Schemes for Clustering Problems in any Dimensions, with A. Kumar and Y.Sabharwal, Journal of the ACM, Vol. 57(2), Jan 2010, pp. 1 -- 32.
  38. A Simple D2-Sampling Based PTAS for k-Means and Other Clustering Problems with R. Jaiswal and A. Kumar, Algorithmica (Special Issue), 70(1), 2014, pp. 22 -- 46.
  39. The covert set cover problem with applications to network discovery with Muralidhara V., Proc of Indian National Science Academy, 80 (3), Sept 2014, pp. 609-619.
  40. The Robust Knapsack Problem with Queries with M. Goerigk, M. Gupta, Jonas Ide and A. Schoebel, Computers and Operations Research, 55, 2015, pp 12 -- 22.
  41. Fully dynamic maximal matching in O(log n) update time, with S. Baswana and M. Gupta, SIAM Jnl on Computing , 44(1), 2015, pp 88 --113.
  42. The update complexity of selection and related problems with M. Gupta, Y. Sabharwal , Theory of Computing Systems , 59(1), 2016, pp 112 --132.
  43. Fully Dynamic Maximal Matching in O(log n) Update Time (Corrected Version), SIAM Journal on Comput , 47 (3), 2018, pp 617 --650.

    Invited Chapters / Unpublished tech reports

  1. A case for randomized parallel algorithms, with J. Reif, NSF-ARC Workshop on `Opportunities and Constraints of Parallel Computing', IBM Almaden, San Jose, Dec 1988, J.L. Sanz ed., Springer Verlag.
  2. Random Sampling Techniques and Parallel Algorithms Design, with S. Rajasekaran, Synthesis of Parallel Algorithms, J. Reif ed., Morgan Kauffman, 1993.
  3. Parallel Computational Geometry: An approach using randomization with J. Reif, Handbook of Computational Geometry, J. Sacks and J. Urrutia eds., Elsevier Science Publishing.
  4. Concentration of measure for randomized algorithms: techniques and applications, with D. Dubhashi, invited chapter for Handbook on Randomized Algorithms.
  5. Randomized Algorithms for Geometric Optimization, with P. Agarwal, Handbook on Randomized Algorithms.
  6. Randomized graph data structures for approximate shortest paths, with S. Baswana, Handbook of Data Structures and Applications, Chapman \& Hall/CRC pub.
  7. A simple and efficient algorithm for spanners in weighted graphs, with S. Baswana, Encyclopedia of Algorithms , Springer.
  8. Matching in dynamic graphs , with S. Baswana and M. Gupta Encyclopedia of Algorithms , Springer.
  9. Randomized graph algorithms: techniques and analysis , with S. Baswana Handbook of Graph Theory, Combinatorial optimization and algorithms , Chapman \& Hall/CRC.
  10. The hardness of speeding up Knapsack, BRICS Tech Report 1998.

    Conference Publications

  1. Shear-sort: a true two-dimensional sorting technique for VLSI networks, with I.D. Scherson and Adi Shamir, Intl Conf on Parallel Processing, Aug 1986.
  2. The distance bound for sorting on two- dimensional mesh connected processor arrays is tight, with Y. Ma and I.D. Scherson, Proceedings of the 25th Annual IEEE Symposium on foundations of Computer Science (FOCS), 1986.
  3. Optimal randomized parallel algorithms for computational geometry, with J. Reif, International Conference on Parallel Processing, St. Charles, Illinois, 1987.
  4. An efficient output-sensitive hidden surface elimination algorithm and its parallelization, with J. Reif, 4th ACM Annual Symp on Computational Geometry, 1988.
  5. Polling: A new randomized sampling method for computational geometry, with J. Reif, Proc. of the 21st ACM Annual Symposium on the Theory of Computing (STOC), Seattle, Washington 1989.
  6. Random Sampling techniques for binary search on fixed connection networks with applications to geometric algorithms, with J. Reif, A.C.M. Symposium on Parallel Architectures and Algorithms, Greece, 1990.
  7. Parallel searching in generalized Monge arrays with applications, with A. Aggarwal, D. Kravets, J. Park, A.C.M. Symposium on Parallel Architectures and Algorithms, Greece, 1990.
  8. Improved Selection in Totally Monotone Arrays, with Y. Mansour, J. Park and B. Scheiber, Proc. of the Foundations of Software Technology and Theoretical Computer Science, 1991.
  9. Dynamic point-location in arrangements of hyperplanes, with K. Mulmuley, A.C.M. Symposium on Computational Geometry, 1991.
  10. Fractional Cascading Simplified, Proceedings of the 2nd Scandinavian Workshop on Algorithmic Theory, 1992, pp. 212-220.
  11. Selection in Monotone Matrices and computing k-th Nearest Neighbours, with P. Agarwal, Proc. of the Scandinavian Workshop on Algorithmic Theory, 1994.
  12. Lower bounds for parallel algebraic decision trees, complexity of convex hulls and related problems , Proc. of the FST\&TCS Foundations of Software Technology and Theoretical Computer Science, 1994, Madras, India.
  13. Faster Output-Sensitive Parallel Convex Hulls for $d \leq 3$: Optimal Sublogarithmic Algorithms for Small Outputs, with N. Gupta, A.C.M. Symposium on Computational Geometry, Philadelphia, 1996.
  14. Parallel multidimensional searching using approximation algorithms with applications to linear programming and related problems, ACM symposium on Parallel Algorithms and Architectures, Italy, 1996.
  15. An improved output-sensitive parallel algorithm for hidden-surface removal for terrains, with N. Gupta, {\em Proc. of, ACM Int'l Parallel Processing Symp., 1998.
  16. Distribution sensitive algorithms, with N. Gupta, Scandinavian Workshop on Algorithmic Theory, 1998.
  17. Output-Sensitive Algorithms for Uniform Partitions of Points, with P. Agarwal and B. Bhattacharya, ISAAC 99, Madras, India.
  18. Towards a theory of cache-efficient algorithms with S. Chatterjee, Proc. of the SODA, SanFrancisco, 2000.
  19. Cache-Efficient Matrix Transposition with S. Chatterjee, Proc. of HPCA, France, 2000.
  20. Planar Graph Blocking for External Searching, with S. Baswana, Proc. of FSTTCS 2000, LNCS 1974, pp. 252 -- 263.
  21. Optimal, Output-Sensitive Algorithms for Constructing Upper Envelope of Line Segments in Parallel, with N. Gupta and S. Chopra, Proc. of FSTTCS 2001, LNCS 2245, pp. 183--194.
  22. Improved online algorithms for transitive-closure and all-pairs shortest paths in digraphs for edge deletions, with S. Baswana, R. Hariharan, STOC 2002, pp. (34) 117 -123.
  23. Fair adaptive Bandwidth Allocation:a rate control based active queue management, with A. Kamra, H. Saran, R. Shorey, Networking 2002, Pisa Italy, pp. 838 -- 849.
  24. Maintaining Approximate All-Pair-Shortest-Paths under deletion , with S. Baswana and R. Hariharan , SODA 2003, pp. 394--403.
  25. Nearest Neighbor Searching using Point Location in Balls: with applications to approximate Voronoi Decompositions, with Y. Sabharwal and N.Sharma Proc of 22nd FSTTCS 2002, LNCS 2556, pp 311--323.
  26. A Simple Linear Time Algorithm for Computing a $(2k-1)$-Spanner of $O(n^{1+1/k})$ Size in Weighted Graphs, with S. Baswana, ICALP 2003, pp. 384--396.
  27. Approximate distance oracles for unweighted graphs in $O( n^2)$ time, with S. Baswana, SODA 2004, pp. 271 -- 280.
  28. A simple linear time approximation algorithm for geometric k-means problem in any dimension, with A. Kumar and Y. Sabharwal, FOCS 2004, pp. 454--462.
  29. PDM Sorting Algorithms that Take a Small Number of Passes, with S. Rajasekaran, International Parallel and Distributed Processing Symposium 2005.
  30. All-Pairs Nearly 2-Approximate Shortest-Paths in O( n2 polylog n) Time Symposium on Theoretical Aspects of Computer Science 2005, pp. 666--679.
  31. Linear Time Algorithms for Clustering Problems in any dimensions with A. Kumar and Y. Sabharwal, ICALP 2005, pp. 1374 -- 1385.
  32. A Simple Optimal Randomized Algorithm for Sorting on the PDM, with S. Rajasekaran, Proc of ISAAC 2005, pp. 543-552.
  33. Algorithmic ramifications of Prefetching in Memory Hierarchy, with Akshat Verma, High Performance Computing 2006.
  34. A Result on the Distribution of Quadratic Residues with Applications to Elliptic Curve Cryptography , with V.N. Muralidhara, Indocrypt 2007 .
  35. Distance Oracle for unweighted graphs: breaking the quadratic barrier with constant additive error with S. Baswana, A. Gaur and J. Upadhyaya, ICALP 2008.
  36. The covert set cover problem with application to Network Discovery with V. Muralidhara , WALCOM 2010, pp. 228 -- 239.
  37. Fully dynamic maximal matching in O(log n) update time, with Surender Baswana and Manoj Gupta, FOCS 2011 pp. 383 -- 392.
    Full version.
  38. The update complexity of selection and related problems} with Manoj Gupta and Yogish Sabharwal , FSTTCS 2011, 325 -- 338.
  39. Efficient cache oblivious algorithms for randomized divide-and-conquer on the multicore model with Neeraj Sharma, short paper ACM SPAA 2012 detailed version.
  40. A simple D2 -sampling based PTAS for k-means and other Clustering Problems, to appear COCOON 2012.
  41. Maintaining Approximate Maximum Weighted Matching in Fully Dynamic Graph (arxiv version) with Abhash Anand, Surender Baswana and Manoj Gupta, FSTTCS 2012, 257 -- 266.
  42. Approximation Algorithms for the Weight-Reducible Knapsack Problem, with M. Goerigk, Y. Sabharwal and A. Schoebel, TAMC 2014, 2013 --215.
  43. On Density, Threshold and Emptiness Queries for Intervals in the Streaming Model, with Arijit Bishnu Amit Chakrabarti and Subhas C. Nandy, FSTTCS 2015, 336 -- 349.
  44. Faster Coreset Construction for Projective Clustering via Low-Rank Approximation, with Rameshwar Pratap, IWOCA 2018, pp 336 -- 348.
  45. A Unified Approach to Tail Estimates for Randomized Incremental Construction, STACS 2019 58:1 -- 58:16.
  46. Efficient algorithms for decode efficient prefix codes, with Shashwat Banchhor, Rishikesh R. Gajjala, Yogish Sabharwal, 31st Data Compression Conference 2021 : 338
  47. Generalizations of Length Limited Huffman Coding for Hierarchical Memory Settings, with Shashwat Banchhor, Rishikesh R. Gajjala, Yogish Sabharwal, FSTTCS 2021, 8:1 -- 8:23