Sharath Raghvendra
Department of Computer
Science
Virginia Tech
Email: sharathr at vt.edu
About Me
I am an Associate Professor
in the Department of Computer Science at Virginia Tech. Prior to joining
Virginia Tech, I spent two years as a postdoc in the Computer Science and Management Science
and Engineering departments at Stanford working with Prof. Leo Guibas
and Prof. Ashish Goel. I
completed my Ph.D. from the Department of
Computer Science at Duke University where
I worked with Prof. Pankaj Agarwal.
I received my B. Tech (Hons) (Computer Science) from IIIT, Hyderabad.
Research Interests
I’m generally interested in design of efficient algorithms and data structures for problems in computational geometry and graph theory. My research spans problems from geometric optimization, graph theory, computational topology and online algorithms. Check my publications for more information.
Rachita Sowle (Ph. D. candidate, Computer Science)
Students
Kaiyi Zhang (Ph. D. candidate, Computer Science)
Nathaniel Lahn (Ph.D., Computer Science), 2020 (Dissertation work published in SODA '18, SODA '19, SOCG '19, SODA '21)
Krati Nayyar (MS, Computer Science), 2017 (Thesis work published in FOCS '17)
Alexander Daniel Friedman (MS, Mathematics), 2017 (Thesis work published in WAOA '17)
Mariette Wessels (MS, Mathematics), 2017 (Thesis work published in SODA '18)
Mudabir Kabir Asathulla (MS, Computer Engineering), 2017 (Thesis work published in SODA '18)
Harsh Patel (M. Engg., Computer Engineering), 2017
Rutvij Mahajan (MS, Computer Engineering), 2018
Deepika Mulchandani (MS, Computer Science), 2019 (Thesis work published in NeurIPS '19)
Jiacheng Ye (MS, Computer Science), 2020
Grants
"The Geometry Behind Logistics ‐ Approximation Algorithms for Real‐Time Delivery" (NSF CRII), $175,000, Feb’15- Jan’18 "Algorithms for Fundamental Optimization Problems in Computational Geometry" (NSF), $450,000, Jul’19- Jun’22 CS4104: Data and
Algorithm Analysis (Fall’14, Fall'15, Fall'16, Fall'18) CS3114: Data Structures and Algorithms (Spring '18, 2 Sections)
CS5114: Theory of Algorithms (Spring '16, Fall '17, Fall '19)
CS6104: Online
Algorithms (Spring’15), Geometric Optimization (Spring '17), Combinatorial Algorithms for Network Flow problems (Spring, '19) A Graph Theoretic Additive Approximation of Optimal Transport A Weighted Approach to Maximum Cardinality Bipartite Matching Problem with Applications in Geometric Settings
A Faster Algorithm for Minimum-Cost Matching in Minor Free Graphs Improved Topological Approximations by Digitization Optimal Analysis of an Online Algorithm for the Bipartite Matching Problem on a Line A Grid-Based Approximation Algorithm for the Minimum Weight Triangulation Problem A Faster Algorithm for Minimum-Cost Bipartite Perfect Matching in Planar Graphs Improved Approximate Rips Filtration with Shifted Integer Lattices An Input Sensitive Online Algorithm for the Metric Bipartite Matching Problem A k-Median Based Online Algorithm for the Stochastic k-Server Problem Robust and Optimal Online Algorithm for the Minimum Metric Bipartite Matching Polynomial-Sized Topological Approximations Using the Permutahedron Approximation and Streaming Algorithms for Projective Clustering via Random Projections Connectivity
in Random Forests and Credit Networks
Teaching
Publications
Nathaniel Lahn, Deepika Mulchandani, Sharath Raghvendra
NeurIPS 2019.
Nathaniel Lahn, Sharath Raghvendra
SOCG 2019.
Nathaniel Lahn, Sharath Raghvendra
SODA 2019.
Aruni Choudhary, Michael Kerber, Sharath Raghvendra
SODA 2019.
Sharath Raghvendra
SOCG 2018.
Sharath Raghvendra, Mariette Wessels
SODA 2018.
Mudabir Kabir Asathulla, Sanjeev Khanna, Nathaniel Lahn, Sharath Raghvendra
SODA 2018.
Aruni Choudhary, Michael Kerber, Sharath Raghvendra
ESA 2017.
Krati Nayyar, Sharath Raghvendra
FOCS 2017.
Abhijin Adiga, Alexander D. Friedman, Sharath Raghvendra
WAOA 2017.
Sharath Raghvendra
APPROX 2016.
Aruni Choudhary, Michael Kerber, Sharath Raghvendra
SOCG 2016.
Michael Kerber, Sharath Raghvendra
CCCG 2015.
Ashish Goel, Sanjeev Khanna, Sharath Raghvendra, Hongyang Zhang
SODA 2015.
Approximation
Algorithms for Bipartite Matching with Metric and Geometric Costs
Pankaj K. Agarwal, R. Sharathkumar
STOC 2014.
Approximate
Cech Complex in Low and High Dimensions
Michael Kerber, R. Sharathkumar
ISAAC 2013.
A
Sub-Quadratic Algorithm For Bipartite Matching of Planar Points with Bounded
Integer Coordinates
R. Sharathkumar.
SOCG 2013
A
Near-Linear Time ε-Approximation Algorithm for Geometric Bipartite Matching
R. Sharathkumar, Pankaj K. Agarwal.
STOC 2012
Algorithms
for Transportation Problem in Geometric Settings
R. Sharathkumar, Pankaj K. Agarwal.
SODA 2012
Streaming
Algorithms for Extent Problems in High Dimensions
Pankaj K. Agarwal, R. Sharathkumar
SODA 2010 (Appears in Algorithmica)
Approximate
Euclidean Shortest-paths amid Convex Obstacles
Pankaj K. Agarwal, R. Sharathkumar, Hai Yu.
SODA 2009
On approximate geodesic-distance queries amid deforming
point clouds
Pankaj K. Agarwal, Alon Efrat,
R. Sharathkumar, Hai Yu.
WAFR 2008
Range
Aggregate Proximity Queries
R. Sharathkumar, Prosenjit
Gupta.
Technical Report, 2007.
Range
Aggregate Proximity Detection for Design Rule Checking in VLSI layouts
R. Sharathkumar, Prosenjit
Gupta.
CCCG, 2006.