Lune

Profiles2020-2026

Sanjeev Khanna

University of Pennsylvania

22Papers
5Last author
20Unique co-authors
7First author
0Solo

First and last author come from byline position, which some venues assign alphabetically.

Recent papers22

  1. Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and HardnessAuthor 1 of 3SODA 2026
  2. Efficient Algorithms and New Characterizations for CSP SparsificationAuthor 1 of 3STOC 2025 · 12 citations
  3. On the Parallel Complexity of Finding a Matroid BasisAuthor 1 of 3FOCS 2025 · 6 citations
  4. A Polynomial Space Lower Bound for Diameter Estimation in Dynamic StreamsAuthor 1 of 4FOCS 2025 · 3 citations
  5. Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical AlgorithmsAuthor 2 of 3STOC 2025 · 3 citations
  6. Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemerédi GraphsAuthor 2 of 3SODA 2025 · 2 citations
  7. Near-Optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral SparsificationAuthor 1 of 3STOC 2025
  8. Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic DepthAuthor 2 of 7SODA 2024 · 7 citations
  9. A Faster Combinatorial Algorithm for Maximum Bipartite MatchingAuthor 2 of 2SODA 2024 · 6 citations
  10. Code Sparsification and its ApplicationsAuthor 1 of 3SODA 2024 · 4 citations
  11. Maximum Bipartite Matching in n2+o(1) Time via a Combinatorial AlgorithmAuthor 2 of 2STOC 2024 · 2 citations
  12. Near-Optimal Size Linear Sketches for Hypergraph Cut SparsifiersAuthor 1 of 3FOCS 2024 · 2 citations
  13. On Regularity Lemma and Barriers in Streaming and Dynamic MatchingAuthor 3 of 4STOC 2023 · 13 citations
  14. Query Complexity of the Metric Steiner Tree ProblemAuthor 2 of 3SODA 2023
  15. Sublinear Algorithms for Hierarchical ClusteringAuthor 2 of 4NeurIPS 2022 · 12 citations
  16. New Trade-Offs for Fully Dynamic Matching via Hierarchical EDCSAuthor 2 of 2SODA 2022 · 11 citations
  17. On Weighted Graph Sparsification by Linear SketchingAuthor 2 of 3FOCS 2022 · 6 citations
  18. A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function MinimizationAuthor 3 of 3FOCS 2021 · 3 citations
  19. Approximate optimization of convex functions with outlier noiseAuthor 2 of 4NeurIPS 2021 · 3 citations
  20. Hardness of Approximation for Orienteering with Multiple Time WindowsAuthor 2 of 3SODA 2021 · 1 citation
  21. Near-linear Size Hypergraph Cut SparsifiersAuthor 2 of 3FOCS 2020 · 15 citations
  22. Near-Perfect Recovery in the One-Dimensional Latent Space ModelAuthor 3 of 3WWW 2020 · 3 citations
Dusk over the sea between two cliffs drawn in fine vertical lines