- Parallel Sorting in Two dimensional
VLSI models of Computation, with I.D. Scherson,
**IEEE Transaction on Computers**, February 1989, pp. 238-249. - 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. - Finding an approximate-median with high probability in constant
parallel time,
**Information Processing Letters**, 34, 1990, pp. 77-80. - 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. - Optimal randomized parallel algorithms for
computational geometry, with J. Reif,
**Algorithmica**, 1992:7, pp. 91--117. - 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. - Dynamic point-location in arrangements of
hyperplanes, with K. Mulmuley,
**Discrete and Computational Geometry**(Special issue), 8, 1992, pp. 335--360. - On Parallel Integer Sorting, with S. Rajasekaran,
**Acta Informatica**, 29, Jan 1992 pp. 1--15. - Some Observations on Skip-Lists,
**Information Processing Letters**, 39, August 1991, pp. 173--176. - 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. - Fractional Cascading Revisited,
**Journal of Algorithms**, 19, Sept 1995, pp. 161--172. - An efficient output-sensitive hidden-surface removal
algorithm for polyhedral terrains, with J. Reif,
**Mathematical and Computer Modelling**, 21:5, 1995, pp. 89--104. - Selection in Monotone Matrices and computing k-th Nearest
Neighbours, with P. Agarwal,
**Journal of Algorithms**, 20, June 1996, pp. 581--601. - Lower bounds for parallel algebraic decision trees, parallel
complexity of convex hulls and related problems,
**Theoretical Computer Science**, 188, 1997, pp. 59--78. - Parallel searching in generalized Monge arrays with
applications ,
with A. Aggarwal, D. Kravets, J. Park,
**Algorithmica**, 19:3, 1997, pp. 291 -- 317. - Optimal output-sensitive algorithms for constructing planar hulls in
parallel, with N. Gupta,
**Computational Geometry: Theory and Applications**, 8, 1997, pp. 151-166. - On a simple, practical optimal output-sensitive randomized
planar convex-hull algorithm, with B. Bhattacharya,
**Journal of Algorithms**25, Oct 1997, pp. 177-- 193. - Distribution sensitive algorithms, with N. Gupta,
**Nordic Journal on Computing**(special issue), 6, 1999, pp. 194 -- 211. - An efficient output-size sensitive parallel algorithm for
hidden-surface removal for terrains, with N. Gupta,
**Algorithmica**, 31, 2001, pp. 179 -- 207. - 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. - Improved Algorithms for Uniform Partitions of
Points,
with P. Agarwal and B. Bhattacharya,
**Algorithmica**, 32(4), 2002, pp. 521 -- 539. - Planar Graph Blocking for External Searching,
with S. Baswana,
**Algorithmica**, 34(3), 2002, pp 298--308. - Towards a theory of cache-efficient algorithms
with S. Chatterjee, N. Dumeer,
**Journal of the ACM**, 49(6), Nov 2002, pp 828 --858. - 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. - 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. - A generalization of the 0-1 principle for
sorting, with S. Rajasekaran,
**Information Processing Letters**94(1), 2005, pp.43 -- 47. - 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. - A linear time algorithm for approximate 2-means
clustering
with Y. Sabharwal,
**Computational Geometry: Theory and Applications**, 32(2), 2005, pp. 159 -- 173. - 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. - 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. - 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. - 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.* - Optimal and practical algorithms for sorting on
the PDM, with S. Rajasekaran,
**IEEE Transactions on Computers**, Vol 57(4), April 2008, Pages 547 - 561. - Combating I-O
bottleneck using prefetching: Model, Algorithms and Ramifications, with
A. Verma,
**Journal of Supercomputing**45( 2): 205-235 2008. - All-Pairs Nearly 2-Approximate Shortest-Paths in O( n
^{2}polylog n) Time, with Surender Baswana, and Vishrut Goyal,**Theoretical Computer Science**410(1): 84-93 2009. - 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 . - 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. - A Simple
D
^{2}-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. - 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. - The
Robust Knapsack Problem with Queries with M. Goerigk, M. Gupta, Jonas Ide
and A. Schoebel,
**Computers and Operations Research**. - Fully dynamic maximal matching in O(log n) update time, with S. Baswana
and M. Gupta,
**SIAM Jnl on Computing**, 44(1) pp 88 --113. - The update complexity of selection and related problems
with M. Gupta, Y. Sabharwal,
*to appear*,**Theory of Computing Systems**.

- 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.
- Random Sampling Techniques and Parallel Algorithms
Design,
with S. Rajasekaran,
**Synthesis of Parallel Algorithms**, J. Reif ed., Morgan Kauffman, 1993. - Parallel Computational Geometry: An
approach using randomization
with
J. Reif,
**Handbook of Computational Geometry**, J. Sacks and J. Urrutia eds., Elsevier Science Publishing. - Concentration of measure for randomized algorithms: techniques
and applications, with D. Dubhashi, invited chapter for
**Handbook on Randomized Algorithms**. - Randomized Algorithms for Geometric
Optimization,
with P. Agarwal,
**Handbook on Randomized Algorithms**. - Randomized graph data structures for
approximate shortest paths,
with S. Baswana,
**Handbook of Data Structures and Applications**, Chapman \& Hall/CRC pub. - A simple and efficient algorithm for
spanners in weighted graphs,
with S. Baswana,
**Encyclopedia of Algorithms**, Springer. - Matching in dynamic graphs
,
with S. Baswana and M. Gupta
**Encyclopedia of Algorithms**, Springer. - Randomized graph algorithms: techniques and
analysis ,
with S. Baswana
**Handbook of Graph Theory, Combinatorial optimization and algorithms**, Chapman \& Hall/CRC. - The hardness of speeding up Knapsack,
**BRICS Tech Report 1998**.

- 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. - 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. - Optimal randomized parallel algorithms for
computational geometry, with J. Reif,
**International Conference on Parallel Processing**, St. Charles, Illinois, 1987. - An efficient output-sensitive hidden surface
elimination algorithm and its parallelization, with J. Reif,
**4th ACM Annual Symp on Computational Geometry**, 1988. - 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. - 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. - 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. - 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. - Dynamic point-location in arrangements of
hyperplanes, with K. Mulmuley,
**A.C.M. Symposium on Computational Geometry**, 1991. - Fractional Cascading Simplified,
**Proceedings of the 2nd Scandinavian Workshop on Algorithmic Theory**, 1992, pp. 212-220. - Selection in Monotone Matrices and computing k-th Nearest
Neighbours, with P. Agarwal,
**Proc. of the Scandinavian Workshop on Algorithmic Theory**, 1994. - 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. - 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. - Parallel multidimensional searching using approximation algorithms
with applications to linear programming and related problems,
**ACM symposium on Parallel Algorithms and Architectures**, Italy, 1996. - 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. - Distribution sensitive algorithms, with N. Gupta,
**Scandinavian Workshop on Algorithmic Theory**, 1998. - Output-Sensitive Algorithms for Uniform Partitions of Points,
with P. Agarwal and B. Bhattacharya,
**ISAAC 99**, Madras, India. - Towards a theory of cache-efficient algorithms
with S. Chatterjee,
**Proc. of the SODA**, SanFrancisco, 2000. - Cache-Efficient Matrix Transposition
with S. Chatterjee,
**Proc. of HPCA**, France, 2000. -
Planar Graph Blocking for External Searching, with S. Baswana,
**Proc. of FSTTCS 2000**, LNCS 1974, pp. 252 -- 263. - 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. - 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. - 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. - Maintaining Approximate
All-Pair-Shortest-Paths under deletion
, with S. Baswana and R. Hariharan ,
**SODA 2003**, pp. 394--403. - 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. - 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. - Approximate distance oracles for unweighted graphs
in $O( n^2)$
time, with S. Baswana,
**SODA 2004**, pp. 271 -- 280. - 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. - PDM Sorting Algorithms that
Take a Small Number of Passes, with S. Rajasekaran,
**International Parallel and Distributed Processing Symposium**2005. - All-Pairs Nearly 2-Approximate Shortest-Paths
in O( n
^{2}polylog n) Time**Symposium on Theoretical Aspects of Computer Science**2005, pp. 666--679. - Linear Time Algorithms for Clustering
Problems in any dimensions
with A. Kumar and Y. Sabharwal,
**ICALP 2005**, pp. 1374 -- 1385. - A Simple Optimal Randomized Algorithm for Sorting on the PDM, with
S. Rajasekaran,
**Proc of ISAAC**2005, pp. 543-552. -
Algorithmic ramifications of Prefetching in
Memory Hierarchy, with Akshat Verma,
**High Performance Computing**2006. -
A Result on the Distribution of Quadratic Residues
with Applications to Elliptic Curve Cryptography
, with V.N. Muralidhara,
**Indocrypt 2007**. -
Distance Oracle for unweighted graphs: breaking
the quadratic barrier with constant additive error with S. Baswana, A. Gaur
and J. Upadhyaya,
**ICALP 2008**. -
The covert set cover problem with application to Network Discovery
with V. Muralidhara
,
**WALCOM 2010**, pp. 228 -- 239. - Fully dynamic maximal matching in O(log n) update time,
with Surender
Baswana and Manoj Gupta,
**FOCS 2011**pp. 383 -- 392.

Full version. - The update complexity of selection and related
problems}
with Manoj Gupta and Yogish Sabharwal ,
**FSTTCS 2011**, 325 -- 338. - Efficient cache oblivious algorithms for randomized
divide-and-conquer on the multicore model with Neeraj Sharma,
*short paper***ACM SPAA**2012 detailed version. -
A simple D
^{2}-sampling based PTAS for k-means and other Clustering Problems, to appear**COCOON**2012. -
Maintaining Approximate Maximum Weighted Matching in Fully Dynamic Graph
(arxiv version)
with Abhash Anand, Surender Baswana and Manoj Gupta,
**FSTTCS 2012**, 257 -- 266. - Approximation Algorithms for the Weight-Reducible Knapsack Problem,
with M. Goerigk, Y. Sabharwal and A. Schoebel,
**TAMC 2014**, 2013 --215. - 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.