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.
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
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.
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.
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.
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.
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.
Faster Coreset Construction for Projective Clustering via Low-Rank Approximation,
with Rameshwar Pratap, IWOCA 2018, pp 336 -- 348.
A Unified Approach to Tail Estimates for Randomized Incremental Construction,
STACS 2019 58:1 -- 58:16.
Efficient algorithms for decode efficient prefix codes, with
Shashwat Banchhor, Rishikesh R. Gajjala, Yogish Sabharwal,
31st Data Compression Conference 2021 : 338
Generalizations of Length Limited Huffman Coding for Hierarchical
Memory Settings, with Shashwat Banchhor, Rishikesh R.
Gajjala, Yogish Sabharwal, FSTTCS 2021, 8:1 -- 8:23