Sanjeev Khanna

ORCID

Publication Activity (10 Years)

Years Active: 1990-2024
Publications (10 Years): 95

Top Venues

Publications

Julia Chuzhoy, Sanjeev Khanna
Time via a Combinatorial Algorithm. CoRR (2024)
Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan
Code Sparsification and its Applications. SODA (2024)
Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan
Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers. CoRR (2024)
Sepehr Assadi, Sanjeev Khanna
Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemerédi Graphs. CoRR (2024)
Julia Chuzhoy, Sanjeev Khanna
A Faster Combinatorial Algorithm for Maximum Bipartite Matching. SODA (2024)
Arpit Agarwal, Sanjeev Khanna, Huan Li, Prathamesh Patil, Chen Wang, Nathan White, Peilin Zhong
Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth. SODA (2024)
Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan
Characterizations of Sparsifiability for Affine CSPs and Symmetric CSPs. CoRR (2024)
Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan
Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs. ICALP (2024)
Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan
Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs. CoRR (2024)
Julia Chuzhoy, Sanjeev Khanna
Time via a Combinatorial Algorithm. STOC (2024)
Arpit Agarwal, Sanjeev Khanna, Huan Li, Prathamesh Patil, Chen Wang, Nathan White, Peilin Zhong
Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth. CoRR (2024)
Sanjeev Khanna, Christian Konrad, Cezar-Mihail Alexandru
Set Cover in the One-pass Edge-arrival Streaming Model. PODS (2023)
Deeparnab Chakrabarty, Yu Chen, Sanjeev Khanna
A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization and Matroid Intersection. SIAM J. Comput. 52 (1) (2023)
Julia Chuzhoy, Sanjeev Khanna
A Faster Combinatorial Algorithm for Maximum Bipartite Matching. CoRR (2023)
Sanjeev Khanna, Aaron L. Putterman, Madhu Sudan
Code Sparsification and its Applications. CoRR (2023)
Yu Chen, Sanjeev Khanna, Zihan Tan
Query Complexity of the Metric Steiner Tree Problem. SODA (2023)
Yu Chen, Sanjeev Khanna, Zihan Tan
Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics. ICALP (2023)
Sepehr Assadi, Soheil Behnezhad, Sanjeev Khanna, Huan Li
On Regularity Lemma and Barriers in Streaming and Dynamic Matching. STOC (2023)
Arpit Agarwal, Sanjeev Khanna, Prathamesh Patil
A Sharp Memory-Regret Trade-off for Multi-Pass Streaming Bandits. COLT (2022)
Arpit Agarwal, Sanjeev Khanna, Huan Li, Prathamesh Patil
Sublinear Algorithms for Hierarchical Clustering. CoRR (2022)
Arpit Agarwal, Sanjeev Khanna, Huan Li, Prathamesh Patil
Sublinear Algorithms for Hierarchical Clustering. NeurIPS (2022)
Arpit Agarwal, Sanjeev Khanna, Prathamesh Patil
A Sharp Memory-Regret Trade-Off for Multi-Pass Streaming Bandits. CoRR (2022)
Yu Chen, Sanjeev Khanna, Huan Li
On Weighted Graph Sparsification by Linear Sketching. FOCS (2022)
Sanjeev Khanna, Christian Konrad
Optimal Bounds for Dominating Set in Graph Streams. ITCS (2022)
Arpit Agarwal, Sanjeev Khanna, Prathamesh Patil
PAC Top-k Identification under SST in Limited Rounds. AISTATS (2022)
Deeparnab Chakrabarty, Yu Chen, Sanjeev Khanna
A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization. FOCS (2022)
Anindya De, Sanjeev Khanna, Huan Li, Hesam Nikpey
Nearly Tight Bounds for Discrete Search under Outlier Noise. SOSA (2022)
Yu Chen, Sanjeev Khanna, Zihan Tan
Query Complexity of the Metric Steiner Tree Problem. CoRR (2022)
Soheil Behnezhad, Sanjeev Khanna
New Trade-Offs for Fully Dynamic Matching via Hierarchical EDCS. SODA (2022)
Soheil Behnezhad, Sanjeev Khanna
New Trade-Offs for Fully Dynamic Matching via Hierarchical EDCS. CoRR (2022)
Sepehr Assadi, Soheil Behnezhad, Sanjeev Khanna, Huan Li
On Regularity Lemma and Barriers in Streaming and Dynamic Matching. CoRR (2022)
Yu Chen, Sanjeev Khanna, Huan Li
On Weighted Graph Sparsification by Linear Sketching. CoRR (2022)
Yu Chen, Sanjeev Khanna, Zihan Tan
Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics. CoRR (2022)
Sepehr Assadi, Deeparnab Chakrabarty, Sanjeev Khanna
Graph Connectivity and Single Element Recovery via Linear and OR Queries. ESA (2021)
Naveen Garg, Sanjeev Khanna, Amit Kumar
Hardness of Approximation for Orienteering with Multiple Time Windows. SODA (2021)
Anindya De, Sanjeev Khanna, Huan Li, MohammadHesam NikpeySalekde
Approximate optimization of convex functions with outlier noise. NeurIPS (2021)
Deeparnab Chakrabarty, Sanjeev Khanna
Better and simpler error analysis of the Sinkhorn-Knopp algorithm for matrix scaling. Math. Program. 188 (1) (2021)
Yu Chen, Sanjeev Khanna, Ansh Nagda
Sublinear Time Hypergraph Sparsification via Cut and Edge Sampling Queries. CoRR (2021)
Sepehr Assadi, Sanjeev Khanna, Yang Li
Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem. SIAM J. Comput. 50 (3) (2021)
Deeparnab Chakrabarty, Yu Chen, Sanjeev Khanna
A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization. FOCS (2021)
Yu Chen, Sanjeev Khanna, Ansh Nagda
Sublinear Time Hypergraph Sparsification via Cut and Edge Sampling Queries. ICALP (2021)
Deeparnab Chakrabarty, Yu Chen, Sanjeev Khanna
A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization and Matroid Intersection. CoRR (2021)
Yu Chen, Sampath Kannan, Sanjeev Khanna
Near-Perfect Recovery in the One-Dimensional Latent Space Model. WWW (2020)
Yu Chen, Sampath Kannan, Sanjeev Khanna
Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation. ICALP (2020)
Yu Chen, Sanjeev Khanna, Ansh Nagda
Near-linear Size Hypergraph Cut Sparsifiers. FOCS (2020)
Mudabir Kabir Asathulla, Sanjeev Khanna, Nathaniel Lahn, Sharath Raghvendra
A Faster Algorithm for Minimum-cost Bipartite Perfect Matching in Planar Graphs. ACM Trans. Algorithms 16 (1) (2020)
Anindya De, Sanjeev Khanna, Huan Li, Hesam Nikpey
An Efficient PTAS for Stochastic Load Balancing with Poisson Jobs. ICALP (2020)
Anindya De, Sanjeev Khanna, Huan Li, Hesam Nikpey
An Efficient PTAS for Stochastic Load Balancing with Poisson Jobs. CoRR (2020)
Arpit Agarwal, Shivani Agarwal, Sanjeev Khanna, Prathamesh Patil
Rank Aggregation from Pairwise Comparisons in the Presence of Adversarial Corruptions. ICML (2020)
Sepehr Assadi, Deeparnab Chakrabarty, Sanjeev Khanna
Graph Connectivity and Single Element Recovery via Linear and OR Queries. CoRR (2020)
Yu Chen, Sampath Kannan, Sanjeev Khanna
Near-Perfect Recovery in the One-Dimensional Latent Space Model. CoRR (2020)
Rajeev Alur, Yu Chen, Kishor Jothimurugan, Sanjeev Khanna
Space-efficient Query Evaluation over Probabilistic Event Streams. LICS (2020)
Yu Chen, Sanjeev Khanna, Ansh Nagda
Near-linear Size Hypergraph Cut Sparsifiers. CoRR (2020)
Yu Chen, Sampath Kannan, Sanjeev Khanna
Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation. CoRR (2020)
Yu Chen, Shahin Jabbari, Michael J. Kearns, Sanjeev Khanna, Jamie Morgenstern
Network Formation under Random Attack and Probabilistic Spread. IJCAI (2019)
Arpit Agarwal, Sepehr Assadi, Sanjeev Khanna
Stochastic Submodular Cover with Limited Adaptivity. SODA (2019)
Sepehr Assadi, Yu Chen, Sanjeev Khanna
Sublinear Algorithms for (Δ + 1) Vertex Coloring. SODA (2019)
Julia Chuzhoy, Sanjeev Khanna
A New Algorithm for Decremental Single-Source Shortest Paths with Applications to Vertex-Capacitated Flow and Cut Problems. CoRR (2019)
Julia Chuzhoy, Sanjeev Khanna
A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems. STOC (2019)
Yu Chen, Shahin Jabbari, Michael J. Kearns, Sanjeev Khanna, Jamie Morgenstern
Network Formation under Random Attack and Probabilistic Spread. CoRR (2019)
Ashish Goel, Michael Kapralov, Sanjeev Khanna
Perfect Matchings in Õ (n 1.5) Time in Regular Bipartite Graphs. Comb. 39 (2) (2019)
Sepehr Assadi, Sanjeev Khanna, Yang Li
The Stochastic Matching Problem with (Very) Few Queries. ACM Trans. Economics and Comput. 7 (3) (2019)
Sepehr Assadi, Yu Chen, Sanjeev Khanna
Polynomial Pass Lower Bounds for Graph Streaming Algorithms. CoRR (2019)
Sepehr Assadi, Michael Kapralov, Sanjeev Khanna
A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling. ITCS (2019)
Sepehr Assadi, Yu Chen, Sanjeev Khanna
Polynomial pass lower bounds for graph streaming algorithms. STOC (2019)
Sepehr Assadi, Michael Kapralov, Sanjeev Khanna
A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling. CoRR (2018)
Sepehr Assadi, Sanjeev Khanna
Tight Bounds on the Round Complexity of the Distributed Maximum Coverage Problem. SODA (2018)
Deeparnab Chakrabarty, Sanjeev Khanna
Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling. SOSA (2018)
Ashish Chiplunkar, Michael Kapralov, Sanjeev Khanna, Aida Mousavifar, Yuval Peres
Testing Graph Clusterability: Algorithms and Lower Bounds. CoRR (2018)
Ashish Chiplunkar, Michael Kapralov, Sanjeev Khanna, Aida Mousavifar, Yuval Peres
Testing Graph Clusterability: Algorithms and Lower Bounds. FOCS (2018)
Mudabir Kabir Asathulla, Sanjeev Khanna, Nathaniel Lahn, Sharath Raghvendra
A Faster Algorithm for Minimum-Cost Bipartite Perfect Matching in Planar Graphs. SODA (2018)
Sepehr Assadi, Sanjeev Khanna
Tight Bounds on the Round Complexity of the Distributed Maximum Coverage Problem. CoRR (2018)
Sepehr Assadi, Yu Chen, Sanjeev Khanna
Sublinear Algorithms for (Δ+ 1) Vertex Coloring. CoRR (2018)
Deeparnab Chakrabarty, Sanjeev Khanna
Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling. CoRR (2018)
Arpit Agarwal, Sepehr Assadi, Sanjeev Khanna
Stochastic Submodular Cover with Limited Adaptivity. CoRR (2018)
Michael Kapralov, Sanjeev Khanna, Madhu Sudan, Ameya Velingker
(1 + Ω(1))-Αpproximation to MAX-CUT Requires Linear Space. SODA (2017)
Sepehr Assadi, Sanjeev Khanna
Randomized Composable Coresets for Matching and Vertex Cover. CoRR (2017)
Marek Chrobak, Uriel Feige, Mohammad Taghi Hajiaghayi, Sanjeev Khanna, Fei Li, Seffi Naor
A greedy approximation algorithm for minimum-gap scheduling. J. Sched. 20 (3) (2017)
Arpit Agarwal, Shivani Agarwal, Sepehr Assadi, Sanjeev Khanna
Learning with Limited Rounds of Adaptivity: Coin Tossing, Multi-Armed Bandits, and Ranking from Pairwise Comparisons. COLT (2017)
Sepehr Assadi, Sanjeev Khanna
Randomized Composable Coresets for Matching and Vertex Cover. SPAA (2017)
Konstantinos Mamouras, Mukund Raghothaman, Rajeev Alur, Zachary G. Ives, Sanjeev Khanna
StreamQRE: modular specification and efficient evaluation of quantitative queries over streaming data. PLDI (2017)
Sepehr Assadi, Sanjeev Khanna, Yang Li
On Estimating Maximum Matching Size in Graph Streams. CoRR (2017)
Sepehr Assadi, Sanjeev Khanna, Yang Li
The Stochastic Matching Problem: Beating Half with a Non-Adaptive Algorithm. EC (2017)
Sepehr Assadi, Sanjeev Khanna, Yang Li
On Estimating Maximum Matching Size in Graph Streams. SODA (2017)
Sepehr Assadi, Sanjeev Khanna, Yang Li
The Stochastic Matching Problem: Beating Half with a Non-Adaptive Algorithm. CoRR (2017)
Sepehr Assadi, Sanjeev Khanna, Yang Li, Rakesh Vohra
Fast Convergence in the Double Oral Auction. ACM Trans. Economics and Comput. 5 (4) (2017)
Sepehr Assadi, Sanjeev Khanna, Yang Li
The Stochastic Matching Problem with (Very) Few Queries. EC (2016)
Sepehr Assadi, Sanjeev Khanna, Yang Li
Tight bounds for single-pass streaming complexity of the set cover problem. STOC (2016)
Sepehr Assadi, Sanjeev Khanna, Yang Li, Grigory Yaroslavtsev
Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model. SODA (2016)
Sepehr Assadi, Sanjeev Khanna, Yang Li, Val Tannen
Algorithms for Provisioning Queries and Analytics. ICDT (2016)
Brett Hemenway, Sanjeev Khanna
Sensitivity and computational complexity in financial networks. Algorithmic Finance 5 (3-4) (2016)
Johannes Starlinger, Sarah Cohen Boulakia, Sanjeev Khanna, Susan B. Davidson, Ulf Leser
Effective and efficient similarity search in scientific workflow repositories. Future Gener. Comput. Syst. 56 (2016)
Sepehr Assadi, Sanjeev Khanna, Yang Li
Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem. CoRR (2016)
Alexander J. T. Gurney, Sanjeev Khanna, Yang Li
Rapid convergence versus policy expressiveness in interdomain routing. INFOCOM (2016)
Sanjeev Goyal, Shahin Jabbari, Michael J. Kearns, Sanjeev Khanna, Jamie Morgenstern
Strategic Network Formation with Attack and Immunization. WINE (2016)
Sepehr Assadi, Sanjeev Khanna, Yang Li, Rakesh Vohra
Fast Convergence in the Double Oral Auction. CoRR (2015)
Yannis Mantzouratos, Tarik Tosun, Sanjeev Khanna, Mark Yim
On embeddability of modular robot designs. ICRA (2015)
Sepehr Assadi, Sanjeev Khanna, Yang Li, Val Tannen
Dynamic Sketching for Graph Optimization Problems with Applications to Cut-Preserving Sketches. FSTTCS (2015)
Michael Brautbar, Moez Draief, Sanjeev Khanna
On the Power of Planned Infections in Networks. Internet Math. 11 (4-5) (2015)
Sepehr Assadi, Sanjeev Khanna, Yang Li, Grigory Yaroslavtsev
Tight Bounds for Linear Sketches of Approximate Matchings. CoRR (2015)

Sanjeev Khanna.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Sanjeev Khanna