Sanjeev Khanna

333 papers A* 127A 17B 8C 8Journal 137Unranked 31

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	An n CoRR Sanjeev Khanna, Junkai Song
2026	J	`jnl`	Fault-Tolerant Distance Oracles Below the n · f Barrier. CoRR Sanjeev Khanna, Christian Konrad, Aaron Putterman
2026	A*	`conf`	Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness. SODA Sanjeev Khanna, Ashwin Padaki, Erik Waingarten
2025	A*	`conf`	A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams. FOCS Sanjeev Khanna, Ashwin Padaki, Krish Singal, Erik Waingarten
2025	J	`jnl`	A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams. CoRR Sanjeev Khanna, Ashwin Padaki, Krish Singal, Erik Waingarten
2025	A*	`conf`	A Theory of Spectral CSP Sparsification. ICALP Sanjeev Khanna, Aaron Putterman, Madhu Sudan
2025	J	`jnl`	A Theory of Spectral CSP Sparsification. CoRR Sanjeev Khanna, Aaron Putterman, Madhu Sudan
2025	A*	`conf`	Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms. STOC Sepehr Assadi, Sanjeev Khanna, Aaron Putterman
2025	J	`jnl`	Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms. CoRR Sepehr Assadi, Sanjeev Khanna, Aaron Putterman
2025	A*	`conf`	Efficient Algorithms and New Characterizations for CSP Sparsification. STOC Sanjeev Khanna, Aaron Putterman, Madhu Sudan
2025	A*	`conf`	Improved Approximation Algorithms for Capacitated Network Design and Flexible Graph Connectivity. ICALP Ishan Bansal, Joe Cheriyan, Sanjeev Khanna, Miles Simmons
2025	A*	`conf`	Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemerédi Graphs. SODA Sepehr Assadi, Sanjeev Khanna, Peter Kiss
2025	A*	`conf`	Near-Optimal Hypergraph Sparsification in Insertion-Only and Bounded-Deletion Streams. ICALP Sanjeev Khanna, Aaron Putterman, Madhu Sudan
2025	A*	`conf`	Near-Optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification. STOC Sanjeev Khanna, Huan Li, Aaron Putterman
2025	J	`jnl`	Near-optimal Hypergraph Sparsification in Insertion-only and Bounded-deletion Streams. CoRR Sanjeev Khanna, Aaron Putterman, Madhu Sudan
2025	J	`jnl`	Near-optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification. CoRR Sanjeev Khanna, Huan Li, Aaron Putterman
2025	A*	`conf`	On the Parallel Complexity of Finding a Matroid Basis. FOCS Sanjeev Khanna, Aaron Putterman, Junkai Song
2025	J	`jnl`	On the Parallel Complexity of Finding a Matroid Basis. CoRR Sanjeev Khanna, Aaron Putterman, Junkai Song
2025	J	`jnl`	Optimal Parallel Basis Finding in Graphic and Related Matroids. CoRR Sanjeev Khanna, Aaron Putterman, Junkai Song
2025	J	`jnl`	Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness. CoRR Sanjeev Khanna, Ashwin Padaki, Erik Waingarten
2025	A*	`conf`	Stochastic Knapsack without Relaxing the Capacity. FOCS Anindya De, Sanjeev Khanna, Nathan White
2025	A*	`conf`	Streaming Maximal Matching with Bounded Deletions. ICALP Sanjeev Khanna, Christian Konrad, Jacques Dark
2025	J	`jnl`	Streaming Maximal Matching with Bounded Deletions. CoRR Sanjeev Khanna, Christian Konrad, Jacques Dark
2024	A*	`conf`	A Faster Combinatorial Algorithm for Maximum Bipartite Matching. SODA Julia Chuzhoy, Sanjeev Khanna
2024	A*	`conf`	Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs. ICALP Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan
2024	J	`jnl`	Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs. CoRR Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan
2024	J	`jnl`	Characterizations of Sparsifiability for Affine CSPs and Symmetric CSPs. CoRR Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan
2024	A*	`conf`	Code Sparsification and its Applications. SODA Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan
2024	J	`jnl`	Improved Approximation Algorithms for Flexible Graph Connectivity and Capacitated Network Design. CoRR Ishan Bansal, Joseph Cheriyan, Sanjeev Khanna, Miles Simmons
2024	J	`jnl`	Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemerédi Graphs. CoRR Sepehr Assadi, Sanjeev Khanna
2024	A*	`conf`	Maximum Bipartite Matching in n STOC Julia Chuzhoy, Sanjeev Khanna
2024	J	`jnl`	Maximum Bipartite Matching in n CoRR Julia Chuzhoy, Sanjeev Khanna
2024	A*	`conf`	Near-Optimal Size Linear Sketches for Hypergraph Cut Sparsifiers. FOCS Sanjeev Khanna, Aaron Putterman, Madhu Sudan
2024	J	`jnl`	Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers. CoRR Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan
2024	A*	`conf`	Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth. SODA Arpit Agarwal, Sanjeev Khanna, Huan Li, Prathamesh Patil, Chen Wang, Nathan White, Peilin Zhong
2024	J	`jnl`	Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth. CoRR Arpit Agarwal, Sanjeev Khanna, Huan Li, Prathamesh Patil, Chen Wang, Nathan White, Peilin Zhong
2023	J	`jnl`	A Faster Combinatorial Algorithm for Maximum Bipartite Matching. CoRR Julia Chuzhoy, Sanjeev Khanna
2023	J	`jnl`	Code Sparsification and its Applications. CoRR Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan
2023	A*	`conf`	On Regularity Lemma and Barriers in Streaming and Dynamic Matching. STOC Sepehr Assadi, Soheil Behnezhad, Sanjeev Khanna, Huan Li
2023	A*	`conf`	Query Complexity of the Metric Steiner Tree Problem. SODA Yu Chen, Sanjeev Khanna, Zihan Tan
2023	A*	`conf`	Set Cover in the One-pass Edge-arrival Streaming Model. PODS Sanjeev Khanna, Christian Konrad, Cezar-Mihail Alexandru
2023	A*	`conf`	Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics. ICALP Yu Chen, Sanjeev Khanna, Zihan Tan
2022	J	`jnl`	A Sharp Memory-Regret Trade-Off for Multi-Pass Streaming Bandits. CoRR Arpit Agarwal, Sanjeev Khanna, Prathamesh Patil
2022	A*	`conf`	A Sharp Memory-Regret Trade-off for Multi-Pass Streaming Bandits. COLT Arpit Agarwal, Sanjeev Khanna, Prathamesh Patil
2022	—	`conf`	Nearly Tight Bounds for Discrete Search under Outlier Noise. SOSA Anindya De, Sanjeev Khanna, Huan Li, Hesam Nikpey
2022	A*	`conf`	New Trade-Offs for Fully Dynamic Matching via Hierarchical EDCS. SODA Soheil Behnezhad, Sanjeev Khanna
2022	J	`jnl`	New Trade-Offs for Fully Dynamic Matching via Hierarchical EDCS. CoRR Soheil Behnezhad, Sanjeev Khanna
2022	J	`jnl`	On Regularity Lemma and Barriers in Streaming and Dynamic Matching. CoRR Sepehr Assadi, Soheil Behnezhad, Sanjeev Khanna, Huan Li
2022	A*	`conf`	On Weighted Graph Sparsification by Linear Sketching. FOCS Yu Chen, Sanjeev Khanna, Huan Li
2022	J	`jnl`	On Weighted Graph Sparsification by Linear Sketching. CoRR Yu Chen, Sanjeev Khanna, Huan Li
2022	A	`conf`	Optimal Bounds for Dominating Set in Graph Streams. ITCS Sanjeev Khanna, Christian Konrad
2022	A	`conf`	PAC Top-k Identification under SST in Limited Rounds. AISTATS Arpit Agarwal, Sanjeev Khanna, Prathamesh Patil
2022	J	`jnl`	Query Complexity of the Metric Steiner Tree Problem. CoRR Yu Chen, Sanjeev Khanna, Zihan Tan
2022	J	`jnl`	Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics. CoRR Yu Chen, Sanjeev Khanna, Zihan Tan
2022	A*	`conf`	Sublinear Algorithms for Hierarchical Clustering. NeurIPS Arpit Agarwal, Sanjeev Khanna, Huan Li, Prathamesh Patil
2022	J	`jnl`	Sublinear Algorithms for Hierarchical Clustering. CoRR Arpit Agarwal, Sanjeev Khanna, Huan Li, Prathamesh Patil
2021	J	`jnl`	A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization and Matroid Intersection. CoRR Deeparnab Chakrabarty, Yu Chen, Sanjeev Khanna
2021	A*	`conf`	A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization. FOCS Deeparnab Chakrabarty, Yu Chen, Sanjeev Khanna
2021	A*	`conf`	Approximate optimization of convex functions with outlier noise. NeurIPS Anindya De, Sanjeev Khanna, Huan Li, MohammadHesam NikpeySalekde
2021	J	`jnl`	Better and simpler error analysis of the Sinkhorn-Knopp algorithm for matrix scaling. Math. Program. Deeparnab Chakrabarty, Sanjeev Khanna
2021	A	`conf`	Graph Connectivity and Single Element Recovery via Linear and OR Queries. ESA Sepehr Assadi, Deeparnab Chakrabarty, Sanjeev Khanna
2021	A*	`conf`	Hardness of Approximation for Orienteering with Multiple Time Windows. SODA Naveen Garg, Sanjeev Khanna, Amit Kumar
2021	A*	`conf`	Sublinear Time Hypergraph Sparsification via Cut and Edge Sampling Queries. ICALP Yu Chen, Sanjeev Khanna, Ansh Nagda
2021	J	`jnl`	Sublinear Time Hypergraph Sparsification via Cut and Edge Sampling Queries. CoRR Yu Chen, Sanjeev Khanna, Ansh Nagda
2021	J	`jnl`	Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem. SIAM J. Comput. Sepehr Assadi, Sanjeev Khanna, Yang Li
2020	J	`jnl`	A Faster Algorithm for Minimum-cost Bipartite Perfect Matching in Planar Graphs. ACM Trans. Algorithms Mudabir Kabir Asathulla, Sanjeev Khanna, Nathaniel Lahn, Sharath Raghvendra
2020	A*	`conf`	An Efficient PTAS for Stochastic Load Balancing with Poisson Jobs. ICALP Anindya De, Sanjeev Khanna, Huan Li, Hesam Nikpey
2020	J	`jnl`	An Efficient PTAS for Stochastic Load Balancing with Poisson Jobs. CoRR Anindya De, Sanjeev Khanna, Huan Li, Hesam Nikpey
2020	J	`jnl`	Graph Connectivity and Single Element Recovery via Linear and OR Queries. CoRR Sepehr Assadi, Deeparnab Chakrabarty, Sanjeev Khanna
2020	A*	`conf`	Near-Perfect Recovery in the One-Dimensional Latent Space Model. WWW Yu Chen, Sampath Kannan, Sanjeev Khanna
2020	J	`jnl`	Near-Perfect Recovery in the One-Dimensional Latent Space Model. CoRR Yu Chen, Sampath Kannan, Sanjeev Khanna
2020	A*	`conf`	Near-linear Size Hypergraph Cut Sparsifiers. FOCS Yu Chen, Sanjeev Khanna, Ansh Nagda
2020	J	`jnl`	Near-linear Size Hypergraph Cut Sparsifiers. CoRR Yu Chen, Sanjeev Khanna, Ansh Nagda
2020	A*	`conf`	Rank Aggregation from Pairwise Comparisons in the Presence of Adversarial Corruptions. ICML Arpit Agarwal, Shivani Agarwal, Sanjeev Khanna, Prathamesh Patil
2020	A*	`conf`	Space-efficient Query Evaluation over Probabilistic Event Streams. LICS Rajeev Alur, Yu Chen, Kishor Jothimurugan, Sanjeev Khanna
2020	A*	`conf`	Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation. ICALP Yu Chen, Sampath Kannan, Sanjeev Khanna
2020	J	`jnl`	Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation. CoRR Yu Chen, Sampath Kannan, Sanjeev Khanna
2019	J	`jnl`	A New Algorithm for Decremental Single-Source Shortest Paths with Applications to Vertex-Capacitated Flow and Cut Problems. CoRR Julia Chuzhoy, Sanjeev Khanna
2019	A	`conf`	A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling. ITCS Sepehr Assadi, Michael Kapralov, Sanjeev Khanna
2019	A*	`conf`	A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems. STOC Julia Chuzhoy, Sanjeev Khanna
2019	A*	`conf`	Network Formation under Random Attack and Probabilistic Spread. IJCAI Yu Chen, Shahin Jabbari, Michael J. Kearns, Sanjeev Khanna, Jamie Morgenstern
2019	J	`jnl`	Network Formation under Random Attack and Probabilistic Spread. CoRR Yu Chen, Shahin Jabbari, Michael J. Kearns, Sanjeev Khanna, Jamie Morgenstern
2019	J	`jnl`	Perfect Matchings in Õ (n 1.5) Time in Regular Bipartite Graphs. Comb. Ashish Goel, Michael Kapralov, Sanjeev Khanna
2019	J	`jnl`	Polynomial Pass Lower Bounds for Graph Streaming Algorithms. CoRR Sepehr Assadi, Yu Chen, Sanjeev Khanna
2019	A*	`conf`	Polynomial pass lower bounds for graph streaming algorithms. STOC Sepehr Assadi, Yu Chen, Sanjeev Khanna
2019	A*	`conf`	Stochastic Submodular Cover with Limited Adaptivity. SODA Arpit Agarwal, Sepehr Assadi, Sanjeev Khanna
2019	A*	`conf`	Sublinear Algorithms for (Δ + 1) Vertex Coloring. SODA Sepehr Assadi, Yu Chen, Sanjeev Khanna
2019	J	`jnl`	The Stochastic Matching Problem with (Very) Few Queries. ACM Trans. Economics and Comput. Sepehr Assadi, Sanjeev Khanna, Yang Li
2018	A*	`conf`	A Faster Algorithm for Minimum-Cost Bipartite Perfect Matching in Planar Graphs. SODA Mudabir Kabir Asathulla, Sanjeev Khanna, Nathaniel Lahn, Sharath Raghvendra
2018	J	`jnl`	A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling. CoRR Sepehr Assadi, Michael Kapralov, Sanjeev Khanna
2018	—	`conf`	Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling. SOSA Deeparnab Chakrabarty, Sanjeev Khanna
2018	J	`jnl`	Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling. CoRR Deeparnab Chakrabarty, Sanjeev Khanna
2018	J	`jnl`	Stochastic Submodular Cover with Limited Adaptivity. CoRR Arpit Agarwal, Sepehr Assadi, Sanjeev Khanna
2018	J	`jnl`	Sublinear Algorithms for (Δ+ 1) Vertex Coloring. CoRR Sepehr Assadi, Yu Chen, Sanjeev Khanna
2018	A*	`conf`	Testing Graph Clusterability: Algorithms and Lower Bounds. FOCS Ashish Chiplunkar, Michael Kapralov, Sanjeev Khanna, Aida Mousavifar, Yuval Peres
2018	J	`jnl`	Testing Graph Clusterability: Algorithms and Lower Bounds. CoRR Ashish Chiplunkar, Michael Kapralov, Sanjeev Khanna, Aida Mousavifar, Yuval Peres
2018	A*	`conf`	Tight Bounds on the Round Complexity of the Distributed Maximum Coverage Problem. SODA Sepehr Assadi, Sanjeev Khanna
2018	J	`jnl`	Tight Bounds on the Round Complexity of the Distributed Maximum Coverage Problem. CoRR Sepehr Assadi, Sanjeev Khanna
2017	A*	`conf`	(1 + Ω(1))-Αpproximation to MAX-CUT Requires Linear Space. SODA Michael Kapralov, Sanjeev Khanna, Madhu Sudan, Ameya Velingker
2017	J	`jnl`	A greedy approximation algorithm for minimum-gap scheduling. J. Sched. Marek Chrobak, Uriel Feige, Mohammad Taghi Hajiaghayi, Sanjeev Khanna, Fei Li, Seffi Naor
2017	J	`jnl`	Fast Convergence in the Double Oral Auction. ACM Trans. Economics and Comput. Sepehr Assadi, Sanjeev Khanna, Yang Li, Rakesh Vohra
2017	A*	`conf`	Learning with Limited Rounds of Adaptivity: Coin Tossing, Multi-Armed Bandits, and Ranking from Pairwise Comparisons. COLT Arpit Agarwal, Shivani Agarwal, Sepehr Assadi, Sanjeev Khanna
2017	A*	`conf`	On Estimating Maximum Matching Size in Graph Streams. SODA Sepehr Assadi, Sanjeev Khanna, Yang Li
2017	J	`jnl`	On Estimating Maximum Matching Size in Graph Streams. CoRR Sepehr Assadi, Sanjeev Khanna, Yang Li
2017	B	`conf`	Randomized Composable Coresets for Matching and Vertex Cover. SPAA Sepehr Assadi, Sanjeev Khanna
2017	J	`jnl`	Randomized Composable Coresets for Matching and Vertex Cover. CoRR Sepehr Assadi, Sanjeev Khanna
2017	A*	`conf`	StreamQRE: modular specification and efficient evaluation of quantitative queries over streaming data. PLDI Konstantinos Mamouras, Mukund Raghothaman, Rajeev Alur, Zachary G. Ives, Sanjeev Khanna
2017	A*	`conf`	The Stochastic Matching Problem: Beating Half with a Non-Adaptive Algorithm. EC Sepehr Assadi, Sanjeev Khanna, Yang Li
2017	J	`jnl`	The Stochastic Matching Problem: Beating Half with a Non-Adaptive Algorithm. CoRR Sepehr Assadi, Sanjeev Khanna, Yang Li
2016	A	`conf`	Algorithms for Provisioning Queries and Analytics. ICDT Sepehr Assadi, Sanjeev Khanna, Yang Li, Val Tannen
2016	J	`jnl`	Effective and efficient similarity search in scientific workflow repositories. Future Gener. Comput. Syst. Johannes Starlinger, Sarah Cohen Boulakia, Sanjeev Khanna, Susan B. Davidson, Ulf Leser
2016	A*	`conf`	Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model. SODA Sepehr Assadi, Sanjeev Khanna, Yang Li, Grigory Yaroslavtsev
2016	—	`ch.`	Quantiles and Equi-depth Histograms over Streams. Data Stream Management Michael B. Greenwald, Sanjeev Khanna
2016	A*	`conf`	Rapid convergence versus policy expressiveness in interdomain routing. INFOCOM Alexander J. T. Gurney, Sanjeev Khanna, Yang Li
2016	J	`jnl`	Sensitivity and computational complexity in financial networks. Algorithmic Finance Brett Hemenway, Sanjeev Khanna
2016	—	`conf`	Strategic Network Formation with Attack and Immunization. WINE Sanjeev Goyal, Shahin Jabbari, Michael J. Kearns, Sanjeev Khanna, Jamie Morgenstern
2016	A*	`conf`	The Stochastic Matching Problem with (Very) Few Queries. EC Sepehr Assadi, Sanjeev Khanna, Yang Li
2016	J	`jnl`	Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem. CoRR Sepehr Assadi, Sanjeev Khanna, Yang Li
2016	A*	`conf`	Tight bounds for single-pass streaming complexity of the set cover problem. STOC Sepehr Assadi, Sanjeev Khanna, Yang Li
2015	J	`jnl`	Algorithms for Provisioning Queries and Analytics. CoRR Sepehr Assadi, Sanjeev Khanna, Yang Li, Val Tannen
2015	J	`jnl`	Approximability of Capacitated Network Design. Algorithmica Deeparnab Chakrabarty, Chandra Chekuri, Sanjeev Khanna, Nitish Korula
2015	A*	`conf`	Connectivity in Random Forests and Credit Networks. SODA Ashish Goel, Sanjeev Khanna, Sharath Raghvendra, Hongyang Zhang
2015	—	`conf`	Dynamic Sketching for Graph Optimization Problems with Applications to Cut-Preserving Sketches. FSTTCS Sepehr Assadi, Sanjeev Khanna, Yang Li, Val Tannen
2015	J	`jnl`	Dynamic Sketching for Graph Optimization Problems with Applications to Cut-Preserving Sketches. CoRR Sepehr Assadi, Sanjeev Khanna, Yang Li, Val Tannen
2015	—	`conf`	Fast Convergence in the Double Oral Auction. WINE Sepehr Assadi, Sanjeev Khanna, Yang Li, Rakesh V. Vohra
2015	J	`jnl`	Fast Convergence in the Double Oral Auction. CoRR Sepehr Assadi, Sanjeev Khanna, Yang Li, Rakesh Vohra
2015	A*	`conf`	On (1, SODA Deeparnab Chakrabarty, Sanjeev Khanna, Shi Li
2015	A*	`conf`	On embeddability of modular robot designs. ICRA Yannis Mantzouratos, Tarik Tosun, Sanjeev Khanna, Mark Yim
2015	J	`jnl`	On the Power of Planned Infections in Networks. Internet Math. Michael Brautbar, Moez Draief, Sanjeev Khanna
2015	J	`jnl`	Strategic Network Formation with Attack and Immunization. CoRR Sanjeev Goyal, Shahin Jabbari, Michael J. Kearns, Sanjeev Khanna, Jamie Morgenstern
2015	A*	`conf`	Streaming Lower Bounds for Approximating MAX-CUT. SODA Michael Kapralov, Sanjeev Khanna, Madhu Sudan
2015	J	`jnl`	Tight Bounds for Linear Sketches of Approximate Matchings. CoRR Sepehr Assadi, Sanjeev Khanna, Yang Li, Grigory Yaroslavtsev
2014	B	`conf`	A Utility Equivalence Theorem for Concave Functions. IPCO Anand Bhalgat, Sanjeev Khanna
2014	A*	`conf`	Approximating matching size from random streams. SODA Michael Kapralov, Sanjeev Khanna, Madhu Sudan
2014	A	`conf`	Differential Privacy: An Economic Method for Choosing Epsilon. CSF Justin Hsu, Marco Gaboardi, Andreas Haeberlen, Sanjeev Khanna, Arjun Narayan, Benjamin C. Pierce, Aaron Roth
2014	J	`jnl`	Differential Privacy: An Economic Method for Choosing Epsilon. CoRR Justin Hsu, Marco Gaboardi, Andreas Haeberlen, Sanjeev Khanna, Arjun Narayan, Benjamin C. Pierce, Aaron Roth
2014	A*	`conf`	Disjoint Set Union with Randomized Linking. SODA Ashish Goel, Sanjeev Khanna, Daniel H. Larkin, Robert Endre Tarjan
2014	—	`conf`	Fast and Improved SLEX Analysis of High-Dimensional Time Series. MLINI@NIPS Ahmed Hefny, Robert E. Kass, Sanjeev Khanna, Matthew A. Smith, Geoffrey J. Gordon
2014	A*	`conf`	Influence Maximization in Undirected Networks. SODA Sanjeev Khanna, Brendan Lucier
2014	—	`conf`	Layer Decomposition: An Effective Structure-Based Approach for Scientific Workflow Similarity. eScience Johannes Starlinger, Sarah Cohen Boulakia, Sanjeev Khanna, Susan B. Davidson, Ulf Leser
2014	C	`conf`	Matchings, Random Walks, and Sampling. LATA Sanjeev Khanna
2014	J	`jnl`	On $(1, ε)$-Restricted Assignment Makespan Minimization. CoRR Deeparnab Chakrabarty, Sanjeev Khanna, Shi Li
2014	J	`jnl`	Streaming Lower Bounds for Approximating MAX-CUT. CoRR Michael Kapralov, Sanjeev Khanna, Madhu Sudan
2014	J	`jnl`	Top-k and Clustering with Noisy Comparisons. ACM Trans. Database Syst. Susan B. Davidson, Sanjeev Khanna, Tova Milo, Sudeepa Roy
2013	C	`conf`	A Greedy Approximation Algorithm for Minimum-Gap Scheduling. CIAC Marek Chrobak, Uriel Feige, Mohammad Taghi Hajiaghayi, Sanjeev Khanna, Fei Li, Seffi Naor
2013	J	`jnl`	Dynamic and Nonuniform Pricing Strategies for Revenue Maximization. SIAM J. Comput. Tanmoy Chakraborty, Zhiyi Huang, Sanjeev Khanna
2013	C	`conf`	On the Power of Adversarial Infections in Networks. WAW Michael Brautbar, Moez Draief, Sanjeev Khanna
2013	J	`jnl`	Perfect Matchings in O(nlog n) Time in Regular Bipartite Graphs. SIAM J. Comput. Ashish Goel, Michael Kapralov, Sanjeev Khanna
2013	A*	`ed.`	Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013 SODA Sanjeev Khanna
2013	J	`jnl`	The All-or-Nothing Multicommodity Flow Problem. SIAM J. Comput. Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd
2013	—	`conf`	To Show or Not to Show in Workflow Provenance. In Search of Elegance in the Theory and Practice of Computation Susan B. Davidson, Sanjeev Khanna, Tova Milo
2013	A	`conf`	Using the crowd for top-k and group-by queries. ICDT Susan B. Davidson, Sanjeev Khanna, Tova Milo, Sudeepa Roy
2012	J	`jnl`	Adaptive Selective Verification: An Efficient Adaptive Countermeasure to Thwart DoS Attacks. IEEE/ACM Trans. Netw. Sanjeev Khanna, Santosh S. Venkatesh, Omid Fatemieh, Fariba Khan, Carl A. Gunter
2012	J	`jnl`	An O(k Theory Comput. Julia Chuzhoy, Sanjeev Khanna
2012	J	`jnl`	Distributed Private Heavy Hitters CoRR Justin Hsu, Sanjeev Khanna, Aaron Roth
2012	—	`conf`	Distributed Private Heavy Hitters. ICALP (1) Justin Hsu, Sanjeev Khanna, Aaron Roth
2012	—	`conf`	Improved Hardness Results for Profit Maximization Pricing Problems with Unlimited Supply. APPROX-RANDOM Parinya Chalermsook, Julia Chuzhoy, Sampath Kannan, Sanjeev Khanna
2012	—	`conf`	Mechanism Design for a Risk Averse Seller. WINE Anand Bhalgat, Tanmoy Chakraborty, Sanjeev Khanna
2012	A*	`conf`	On the communication and streaming complexity of maximum bipartite matching. SODA Ashish Goel, Michael Kapralov, Sanjeev Khanna
2012	J	`jnl`	The Power of Local Information in Social Networks CoRR Christian Borgs, Michael Brautbar, Jennifer T. Chayes, Sanjeev Khanna, Brendan Lucier
2012	—	`conf`	The Power of Local Information in Social Networks. WINE Christian Borgs, Michael Brautbar, Jennifer T. Chayes, Sanjeev Khanna, Brendan Lucier
2011	A*	`conf`	Algorithms for the Generalized Sorting Problem. FOCS Zhiyi Huang, Sampath Kannan, Sanjeev Khanna
2011	B	`conf`	Approximability of Capacitated Network Design. IPCO Deeparnab Chakrabarty, Chandra Chekuri, Sanjeev Khanna, Nitish Korula
2011	A	`conf`	Compression without a common prior: an information-theoretic justification for ambiguity in language. ICS Brendan Juba, Adam Tauman Kalai, Sanjeev Khanna, Madhu Sudan
2011	A*	`conf`	Delays and the Capacity of Continuous-Time Channels. FOCS Sanjeev Khanna, Madhu Sudan
2011	J	`jnl`	Delays and the Capacity of Continuous-time Channels CoRR Sanjeev Khanna, Madhu Sudan
2011	A	`conf`	Enabling Privacy in Provenance-Aware Workflow Systems. CIDR Susan B. Davidson, Sanjeev Khanna, Val Tannen, Sudeepa Roy, Yi Chen, Tova Milo, Julia Stoyanovich
2011	A*	`conf`	Improved Approximation Results for Stochastic Knapsack Problems. SODA Anand Bhalgat, Ashish Goel, Sanjeev Khanna
2011	J	`jnl`	Mechanism Design with Risk Aversion CoRR Anand Bhalgat, Tanmoy Chakraborty, Sanjeev Khanna
2011	A	`conf`	On provenance and privacy. ICDT Susan B. Davidson, Sanjeev Khanna, Sudeepa Roy, Julia Stoyanovich, Val Tannen, Yi Chen
2011	—	`conf`	Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs. APPROX-RANDOM Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna
2011	A*	`conf`	Provenance views for module privacy. PODS Susan B. Davidson, Sanjeev Khanna, Tova Milo, Debmalya Panigrahi, Sudeepa Roy
2011	J	`jnl`	Queries with Difference on Probabilistic Databases. Proc. VLDB Endow. Sanjeev Khanna, Sudeepa Roy, Val Tannen
2011	—	`conf`	Social Welfare in One-Sided Matching Markets without Money. APPROX-RANDOM Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna
2011	J	`jnl`	Social Welfare in One-sided Matching Markets without Money CoRR Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna
2010	—	`conf`	An optimal labeling scheme for workflow provenance using skeleton labels. SIGMOD Conference Zhuowei Bao, Susan B. Davidson, Sanjeev Khanna, Sudeepa Roy
2010	J	`jnl`	Approximability of Capacitated Network Design CoRR Deeparnab Chakrabarty, Chandra Chekuri, Sanjeev Khanna, Nitish Korula
2010	A*	`conf`	Approximating pure nash equilibrium in cut, party affiliation, and satisfiability games. EC Anand Bhalgat, Tanmoy Chakraborty, Sanjeev Khanna
2010	—	`conf`	Dynamic and non-uniform pricing strategies for revenue maximization. BQGT Tanmoy Chakraborty, Zhiyi Huang, Sanjeev Khanna
2010	J	`jnl`	Graph Sparsification via Refinement Sampling CoRR Ashish Goel, Michael Kapralov, Sanjeev Khanna
2010	—	`conf`	Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing. WINE Patrick Briest, Parinya Chalermsook, Sanjeev Khanna, Bundit Laekhanukit, Danupon Nanongkai
2010	J	`jnl`	Inapproximability of Edge-Disjoint Paths and low congestion routing on undirected graphs. Comb. Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar, Lisa Zhang
2010	J	`jnl`	Optimal Lower Bounds for Universal and Differentially Private Steiner Tree and TSP CoRR Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna
2010	A*	`conf`	Perfect matchings in o( STOC Ashish Goel, Michael Kapralov, Sanjeev Khanna
2010	J	`jnl`	Perfect matchings via uniform sampling in regular bipartite graphs. ACM Trans. Algorithms Ashish Goel, Michael Kapralov, Sanjeev Khanna
2010	J	`jnl`	Preserving Module Privacy in Workflow Provenance CoRR Susan B. Davidson, Sanjeev Khanna, Debmalya Panigrahi, Sudeepa Roy
2010	J	`jnl`	Robust self-assembly of graphs. Nat. Comput. Stanislav Angelov, Sanjeev Khanna, Mirkó Visontai
2009	J	`jnl`	A Note on Multiflows and Treewidth. Algorithmica Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd
2009	A*	`conf`	An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design. FOCS Julia Chuzhoy, Sanjeev Khanna
2009	J	`jnl`	Approximation algorithms for data placement on parallel disks. ACM Trans. Algorithms Leana Golubchik, Sanjeev Khanna, Samir Khuller, Ramakrishna Thurimella, An Zhu
2009	—	`conf`	Automatic construction of a minimum size motion graph. Symposium on Computer Animation Liming Zhao, Aline Normoyle, Sanjeev Khanna, Alla Safonova
2009	A*	`conf`	Differencing Provenance in Scientific Workflows. ICDE Zhuowei Bao, Sarah Cohen Boulakia, Susan B. Davidson, Anat Eyal, Sanjeev Khanna
2009	J	`jnl`	Dynamic and Non-Uniform Pricing Strategies for Revenue Maximization CoRR Tanmoy Chakraborty, Zhiyi Huang, Sanjeev Khanna
2009	A*	`conf`	Dynamic and Non-uniform Pricing Strategies for Revenue Maximization. FOCS Tanmoy Chakraborty, Zhiyi Huang, Sanjeev Khanna
2009	J	`jnl`	Edge-Disjoint Paths in Planar Graphs with Constant Congestion. SIAM J. Comput. Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd
2009	J	`jnl`	Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing CoRR Patrick Briest, Sanjeev Khanna
2009	—	`conf`	Nash Dynamics in Congestion Games with Similar Resources. WINE Anand Bhalgat, Tanmoy Chakraborty, Sanjeev Khanna
2009	B	`conf`	Nash Dynamics in Constant Player and Bounded Jump Congestion Games. SAGT Tanmoy Chakraborty, Sanjeev Khanna
2009	A*	`conf`	Network bargaining: algorithms and structural results. EC Tanmoy Chakraborty, Michael J. Kearns, Sanjeev Khanna
2009	J	`jnl`	On Allocating Goods to Maximize Fairness CoRR Deeparnab Chakrabarty, Julia Chuzhoy, Sanjeev Khanna
2009	A*	`conf`	On Allocating Goods to Maximize Fairness. FOCS Deeparnab Chakrabarty, Julia Chuzhoy, Sanjeev Khanna
2009	A	`conf`	Optimizing user views for workflows. ICDT Olivier Biton, Susan B. Davidson, Sanjeev Khanna, Sudeepa Roy
2009	J	`jnl`	Perfect Matchings in O(n \log n) Time in Regular Bipartite Graphs CoRR Ashish Goel, Michael Kapralov, Sanjeev Khanna
2009	J	`jnl`	Perfect Matchings in Õ(n CoRR Ashish Goel, Sanjeev Khanna
2009	A*	`conf`	Perfect matchings via uniform sampling in regular bipartite graphs. SODA Ashish Goel, Michael Kapralov, Sanjeev Khanna
2009	J	`jnl`	Polynomial flow-cut gaps and hardness of directed cut problems. J. ACM Julia Chuzhoy, Sanjeev Khanna
2009	J	`jnl`	The Network as a Storage Device: Dynamic Routing with Bounded Buffers. Algorithmica Stanislav Angelov, Sanjeev Khanna, Keshav Kunal
2009	A*	`conf`	The ratio index for budgeted learning, with applications. SODA Ashish Goel, Sanjeev Khanna, Brad Null
2008	A*	`conf`	Adaptive SelectiveVerification. INFOCOM Sanjeev Khanna, Santosh S. Venkatesh, Omid Fatemieh, Fariba Khan, Carl A. Gunter
2008	—	`conf`	Algorithms for 2-Route Cut Problems. ICALP (1) Chandra Chekuri, Sanjeev Khanna
2008	A*	`conf`	Algorithms for Single-Source Vertex Connectivity. FOCS Julia Chuzhoy, Sanjeev Khanna
2008	J	`jnl`	An O(k CoRR Julia Chuzhoy, Sanjeev Khanna
2008	A*	`conf`	Network design for vertex connectivity. STOC Tanmoy Chakraborty, Julia Chuzhoy, Sanjeev Khanna
2008	—	`conf`	On the Network Coding Advantage for Wireless Multicast in Euclidean Space. IPSN Ashish Goel, Sanjeev Khanna
2008	J	`jnl`	On the complexity of graph self-assembly in accretive systems. Nat. Comput. Stanislav Angelov, Sanjeev Khanna, Mirkó Visontai
2008	J	`jnl`	Perfect Matchings via Uniform Sampling in Regular Bipartite Graphs CoRR Ashish Goel, Michael Kapralov, Sanjeev Khanna
2008	B	`conf`	Robust Self-assembly of Graphs. DNA Stanislav Angelov, Sanjeev Khanna, Mirkó Visontai
2008	—	`conf`	STCON in Directed Unique-Path Graphs. FSTTCS Sampath Kannan, Sanjeev Khanna, Sudeepa Roy
2007	—	`conf`	A Formal Investigation of. FSTTCS Sanjeev Khanna, Keshav Kunal, Benjamin C. Pierce
2007	J	`jnl`	Edge-disjoint paths revisited. ACM Trans. Algorithms Chandra Chekuri, Sanjeev Khanna
2007	J	`jnl`	Efficient Enumeration of Phylogenetically Informative Substrings. J. Comput. Biol. Stanislav Angelov, Boulos Harb, Sampath Kannan, Sanjeev Khanna, Junhyong Kim
2007	A*	`conf`	Hardness of routing with congestion in directed graphs. STOC Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar
2007	J	`jnl`	Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs. Electron. Colloquium Comput. Complex. Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar, Lisa Zhang
2007	A*	`conf`	Polynomial flow-cut gaps and hardness of directed cut problems. STOC Julia Chuzhoy, Sanjeev Khanna
2006	A	`conf`	Agreeing to Agree: Conflict Resolution for Optimistically Replicated Data. DISC Michael B. Greenwald, Sanjeev Khanna, Keshav Kunal, Benjamin C. Pierce, Alan Schmitt
2006	J	`jnl`	An O(sqrt(n)) Approximation and Integrality Gap for Disjoint Paths and Unsplittable Flow. Theory Comput. Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd
2006	A*	`conf`	Edge-disjoint paths in Planar graphs with constant congestion. STOC Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd
2006	B	`conf`	Efficient Enumeration of Phylogenetically Informative Substrings. RECOMB Stanislav Angelov, Boulos Harb, Sampath Kannan, Sanjeev Khanna, Junhyong Kim
2006	J	`jnl`	Hardness of Directed Routing with Congestion. Electron. Colloquium Comput. Complex. Julia Chuzhoy, Sanjeev Khanna
2006	A*	`conf`	Hardness of cut problems in directed graphs. STOC Julia Chuzhoy, Sanjeev Khanna
2006	B	`conf`	On the Complexity of Graph Self-assembly in Accretive Systems. DNA Stanislav Angelov, Sanjeev Khanna, Mirkó Visontai
2006	J	`jnl`	Randomized Pursuit-Evasion with Local Visibility. SIAM J. Discret. Math. Volkan Isler, Sampath Kannan, Sanjeev Khanna
2005	J	`jnl`	A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem. SIAM J. Comput. Chandra Chekuri, Sanjeev Khanna
2005	A*	`conf`	Approximating the average response time in broadcast scheduling. SODA Nikhil Bansal, Moses Charikar, Sanjeev Khanna, Joseph Naor
2005	J	`jnl`	Asymmetric J. ACM Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Robert Krauthgamer, Joseph Naor
2005	A*	`conf`	Hardness of the Undirected Edge-Disjoint Paths Problem with Congestion. FOCS Matthew Andrews, Julia Chuzhoy, Sanjeev Khanna, Lisa Zhang
2005	A*	`conf`	Multicommodity flow, well-linked terminals, and routing problems. STOC Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd
2005	J	`jnl`	Randomized pursuit-evasion in a polygonal environment. IEEE Trans. Robotics Volkan Isler, Sampath Kannan, Sanjeev Khanna
2005	J	`jnl`	Target tracking with distributed sensors: The focus of attention problem. Comput. Vis. Image Underst. Volkan Isler, Sanjeev Khanna, John R. Spletzer, Camillo J. Taylor
2005	—	`conf`	The Network as a Storage Device: Dynamic Routing with Bounded Buffers. APPROX-RANDOM Stanislav Angelov, Sanjeev Khanna, Keshav Kunal
2004	J	`jnl`	A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem. SIAM J. Discret. Math. Chandra Chekuri, Sanjeev Khanna, Joseph Naor, Leonid Zosin
2004	C	`conf`	ATDD: An Algorithmic Tool for Domain Discovery in Protein Sequences. WABI Stanislav Angelov, Sanjeev Khanna, Li Li, Fernando Pereira
2004	A*	`conf`	Approximating Longest Directed Paths and Cycles. ICALP Andreas Björklund, Thore Husfeldt, Sanjeev Khanna
2004	—	`ch.`	Approximation Algorithms for Minimizing AverageWeighted Completion Time. Handbook of Scheduling Chandra Chekuri, Sanjeev Khanna
2004	—	`ed.`	Approximation, Randomization, and Combinatorial Optimization, Algorithms and Techniques, 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2004, and 8th International Workshop on Randomization and Computation, RANDOM 2004, Cambridge, MA, USA, August 22-24, 2004, Proceedings APPROX-RANDOM Klaus Jansen, Sanjeev Khanna, José D. P. Rolim, Dana Ron
2004	J	`jnl`	Archiving scientific data. ACM Trans. Database Syst. Peter Buneman, Sanjeev Khanna, Keishi Tajima, Wang Chiew Tan
2004	A*	`conf`	Asymmetric k-center is log STOC Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Joseph Naor
2004	A*	`conf`	DoS Protection for Reliably Authenticated Broadcast. NDSS Carl A. Gunter, Sanjeev Khanna, Kaijun Tan, Santosh S. Venkatesh
2004	A*	`conf`	Edge-Disjoint Paths in Planar Graphs. FOCS Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd
2004	C	`conf`	Genome Identification and Classification by Short Oligo Arrays. WABI Stanislav Angelov, Boulos Harb, Sampath Kannan, Sanjeev Khanna, Junhyong Kim, Li-San Wang
2004	C	`conf`	Locating and Capturing an Evader in a Polygonal Environment. WAFR Volkan Isler, Sampath Kannan, Sanjeev Khanna
2004	A*	`conf`	Machine Minimization for Scheduling Jobs with Interval Constraints. FOCS Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Joseph Naor
2004	A*	`conf`	Multi-processor scheduling to minimize flow time with epsilon resource augmentation. STOC Chandra Chekuri, Ashish Goel, Sanjeev Khanna, Amit Kumar
2004	J	`jnl`	On Multidimensional Packing Problems. SIAM J. Comput. Chandra Chekuri, Sanjeev Khanna
2004	J	`jnl`	On the Hardness of 4-Coloring a 3-Colorable Graph. SIAM J. Discret. Math. Venkatesan Guruswami, Sanjeev Khanna
2004	A*	`conf`	Power-Conserving Computation of Order-Statistics over Sensor Networks. PODS Michael Greenwald, Sanjeev Khanna
2004	A*	`conf`	Randomized pursuit-evasion with limited visibility. SODA Volkan Isler, Sampath Kannan, Sanjeev Khanna
2004	A*	`conf`	Reconstructing strings from random traces. SODA Tugkan Batu, Sampath Kannan, Sanjeev Khanna, Andrew McGregor
2004	J	`jnl`	Special issue: 35th Annual ACM Symposium on Theory of Computing. J. Comput. Syst. Sci. Sanjeev Khanna, Aravind Srinivasan
2004	A*	`conf`	The all-or-nothing multicommodity flow problem. STOC Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd
2003	J	`jnl`	Approximating Longest Directed Path Electron. Colloquium Comput. Complex. Andreas Björklund, Thore Husfeldt, Sanjeev Khanna
2003	J	`jnl`	Asymmetric k-center is log Electron. Colloquium Comput. Complex. Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Joseph Naor
2003	A*	`conf`	Edge disjoint paths revisited. SODA Chandra Chekuri, Sanjeev Khanna
2003	J	`jnl`	Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. J. Comput. Syst. Sci. Venkatesan Guruswami, Sanjeev Khanna, Rajmohan Rajaraman, F. Bruce Shepherd, Mihalis Yannakakis
2003	A*	`conf`	Selection with monotone comparison cost. SODA Sampath Kannan, Sanjeev Khanna
2003	A	`conf`	Target tracking with distributed sensors: the focus of attention problem. IROS Volkan Isler, John R. Spletzer, Sanjeev Khanna, Camillo J. Taylor
2003	J	`jnl`	Time-Constrained Scheduling of Weighted Packets on Trees and Meshes. Algorithmica Micah Adler, Sanjeev Khanna, Rajmohan Rajaraman, Adi Rosén
2002	A*	`conf`	Approximation schemes for preemptive weighted flow time. STOC Chandra Chekuri, Sanjeev Khanna
2002	—	`conf`	Archiving scientific data. SIGMOD Conference Peter Buneman, Sanjeev Khanna, Keishi Tajima, Wang Chiew Tan
2002	A*	`conf`	Control Message Aggregation in Group Communication Protocols. ICALP Sanjeev Khanna, Joseph Naor, Danny Raz
2002	J	`jnl`	Guest Editor's Foreword. J. Comput. Syst. Sci. Sanjeev Khanna
2002	A*	`conf`	On Propagation of Deletions and Annotations Through Views. PODS Peter Buneman, Sanjeev Khanna, Wang Chiew Tan
2001	A*	`conf`	A PTAS for Minimizing Weighted Completion Time on Uniformly Related Machines. ICALP Chandra Chekuri, Sanjeev Khanna
2001	A*	`conf`	A deterministic algorithm for the cost-distance problem. SODA Chandra Chekuri, Sanjeev Khanna, Joseph Naor
2001	A*	`conf`	Algorithms for minimizing weighted flow time. STOC Chandra Chekuri, Sanjeev Khanna, An Zhu
2001	J	`jnl`	Approximation Schemes for Preemptive Weighted Flow Time Electron. Colloquium Comput. Complex. Chandra Chekuri, Sanjeev Khanna
2001	A*	`conf`	Approximation algorithms for the metric labeling problem via a new linear programming formulation. SODA Chandra Chekuri, Sanjeev Khanna, Joseph Naor, Leonid Zosin
2001	—	`book`	Complexity classifications of Boolean constraint satisfaction problems. Nadia Creignou, Sanjeev Khanna, Madhu Sudan
2001	A	`conf`	Fair Real-Time Traffic Scheduling over a Wireless LA. RTSS Maria Adamou, Sanjeev Khanna, Insup Lee, Insik Shin, Shiyu Zhou
2001	A*	`conf`	On Computing Functions with Uncertainty. PODS Sanjeev Khanna, Wang Chiew Tan
2001	—	`conf`	Space-Efficient Online Computation of Quantile Summaries. SIGMOD Conference Michael Greenwald, Sanjeev Khanna
2001	A	`conf`	Why and Where: A Characterization of Data Provenance. ICDT Peter Buneman, Sanjeev Khanna, Wang Chiew Tan
2000	A*	`conf`	A PTAS for the multiple knapsack problem. SODA Chandra Chekuri, Sanjeev Khanna
2000	A*	`conf`	Approximation algorithms for data placement on parallel disks. SODA Leana Golubchik, Sanjeev Khanna, Samir Khuller, Ramakrishna Thurimella, An Zhu
2000	—	`conf`	Data Provenance: Some Basic Issues. FSTTCS Peter Buneman, Sanjeev Khanna, Wang Chiew Tan
2000	A*	`conf`	Directed network design with orientation constraints. SODA Sanjeev Khanna, Joseph Naor, F. Bruce Shepherd
2000	J	`jnl`	On Broadcast Disk Paging. SIAM J. Comput. Sanjeev Khanna, Vincenzo Liberatore
2000	J	`jnl`	On Indexed Data Broadcast J. Comput. Syst. Sci. Sanjeev Khanna, Shiyu Zhou
2000	A	`conf`	On the Hardness of 4-Coloring a 3-Colorable Graph. CCC Venkatesan Guruswami, Sanjeev Khanna
2000	J	`jnl`	On the Hardness of 4-coloring a 3-colorable Graph Electron. Colloquium Comput. Complex. Venkatesan Guruswami, Sanjeev Khanna
2000	J	`jnl`	On the Hardness of Approximating the Chromatic Number. Comb. Sanjeev Khanna, Nathan Linial, Shmuel Safra
2000	J	`jnl`	The Approximability of Constraint Satisfaction Problems. SIAM J. Comput. Sanjeev Khanna, Madhu Sudan, Luca Trevisan, David P. Williamson
2000	A*	`conf`	Watermarking maps: hiding information in structured data. SODA Sanjeev Khanna, Francis Zane
1999	A*	`conf`	Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates. FOCS Foto N. Afrati, Evripidis Bampis, Chandra Chekuri, David R. Karger, Claire Kenyon, Sanjeev Khanna, Ioannis Milis, Maurice Queyranne, Martin Skutella, Clifford Stein, Maxim Sviridenko
1999	A*	`conf`	Design Networks with Bounded Pairwise Distance. STOC Yevgeniy Dodis, Sanjeev Khanna
1999	A*	`conf`	Integrated Scheduling of Unicast and Multicast Traffic in an Input-Queued Switch. INFOCOM Matthew Andrews, Sanjeev Khanna, Krishnan Kumaran
1999	A*	`conf`	Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems. STOC Venkatesan Guruswami, Sanjeev Khanna, Rajmohan Rajaraman, F. Bruce Shepherd, Mihalis Yannakakis
1999	A*	`conf`	On Multi-Dimensional Packing Problems. SODA Chandra Chekuri, Sanjeev Khanna
1999	A*	`conf`	Page Replacement for General Caching Problems. SODA Susanne Albers, Sanjeev Arora, Sanjeev Khanna
1999	A*	`conf`	Space Time Tradeoffs for Graph Properties. ICALP Yevgeniy Dodis, Sanjeev Khanna
1999	A*	`conf`	The 2-Catalog Segmentation Problem. SODA Yevgeniy Dodis, Venkatesan Guruswami, Sanjeev Khanna
1999	J	`jnl`	The Angular-Metric Traveling Salesman Problem. SIAM J. Comput. Alok Aggarwal, Don Coppersmith, Sanjeev Khanna, Rajeev Motwani, Baruch Schieber
1999	B	`conf`	Time-Constrained Scheduling of Weighted Packets on Trees and Meshes. SPAA Micah Adler, Sanjeev Khanna, Rajmohan Rajaraman, Adi Rosén
1998	A*	`conf`	On Approximating Rectangle Tiling and Packing. SODA Sanjeev Khanna, S. Muthukrishnan, Mike Paterson
1998	A*	`conf`	On Broadcast Disk Paging. STOC Sanjeev Khanna, Vincenzo Liberatore
1998	J	`jnl`	On Certificates and Lookahead in Dynamic Graph Problems. Algorithmica Sanjeev Khanna, Rajeev Motwani, Randall H. Wilson
1998	A*	`conf`	On Indexed Data Broadcast. STOC Sanjeev Khanna, Shiyu Zhou
1998	J	`jnl`	On Syntactic versus Computational Views of Approximability. SIAM J. Comput. Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani
1998	A*	`conf`	On Wireless Spectrum Estimation and Generalized Graph Coloring. INFOCOM Krishnan Kumaran, Sanjeev Khanna
1997	A*	`conf`	A Complete Classification of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction. STOC Sanjeev Khanna, Madhu Sudan, David P. Williamson
1997	J	`jnl`	A Graph Partitioning Approach to Sequential Diagnosis. IEEE Trans. Computers Sanjeev Khanna, W. Kent Fuchs
1997	J	`jnl`	A polynomial time approximation scheme for the SONET ring loading problem. Bell Labs Tech. J. Sanjeev Khanna
1997	A	`conf`	Constraint Satisfaction: The Approximability of Minimization Problems. CCC Sanjeev Khanna, Madhu Sudan, Luca Trevisan
1997	A*	`conf`	Efficient Array Partitioning. ICALP Sanjeev Khanna, S. Muthukrishnan, Steven Skiena
1997	J	`jnl`	On the Hardness of Approximating Max k-Cut and its Dual. Chic. J. Theor. Comput. Sci. Viggo Kann, Sanjeev Khanna, Jens Lagergren, Alessandro Panconesi
1997	A*	`conf`	The Angular-Metric Traveling Salesman Problem. SODA Alok Aggarwal, Don Coppersmith, Sanjeev Khanna, Rajeev Motwani, Baruch Schieber
1996	J	`jnl`	A Complete Characterization of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction Electron. Colloquium Comput. Complex. Sanjeev Khanna, Madhu Sudan, David P. Williamson
1996	—	`—`	A structural view of approximation. Sanjeev Khanna
1996	J	`jnl`	Constraint satisfaction: The approximability of minimization problems. Electron. Colloquium Comput. Complex. Sanjeev Khanna, Madhu Sudan, Luca Trevisan
1996	A*	`conf`	On Certificates and Lookahead in Dynamic Graph Problems. SODA Sanjeev Khanna, Rajeev Motwani, Randall H. Wilson
1996	—	`conf`	On the Hardness of Approximating Max k-Cut and Its Dual. ISTCS Viggo Kann, Sanjeev Khanna, Jens Lagergren, Alessandro Panconesi
1996	J	`jnl`	The Optimization Complexity of Constraint Satisfaction Problems Electron. Colloquium Comput. Complex. Sanjeev Khanna, Madhu Sudan
1996	A*	`conf`	Towards a Syntactic Characterization of PTAS. STOC Sanjeev Khanna, Rajeev Motwani
1995	J	`jnl`	A Linear Time Algorithm for Sequential Diagnosis in Hypercubes. J. Parallel Distributed Comput. Sanjeev Khanna, W. Kent Fuchs
1995	J	`jnl`	On Syntactic versus Computational Views of Approximability Electron. Colloquium Comput. Complex. Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani
1994	A*	`conf`	On Syntactic versus Computational Views of Approximability FOCS Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani
1993	—	`conf`	On the Hardness of Approximating the Chromatic Number. ISTCS Sanjeev Khanna, Nathan Linial, Shmuel Safra
1992	C	`conf`	Concurrent Use of Parallel Communication to Enable Remote Visualization. ICCI Kurt Maly, Frank Paterra, C. Michael Overstreet, Ravi Mukkamala, Sanjeev Khanna
1992	—	`conf`	Multiprocessor Architectures for High Speed Networks: A Performance Study. IFIP Congress (1) Kurt Maly, Sanjeev Khanna, C. Michael Overstreet, Ravi Mukkamala, Mohammad Zubair, Y. S. Sekhar
1992	—	`conf`	Parallel TCP/IP for Multiprocessor Workstations. HPN Kurt Maly, Sanjeev Khanna, Ravi Mukkamala, C. Michael Overstreet, Ramesh Yerraballi, Edwin C. Foudriat, B. Madan
1991	J	`jnl`	A carrier sensed multiple access protocol high data rate ring networks. Comput. Commun. Rev. Edwin C. Foudriat, Kurt Maly, C. Michael Overstreet, Sanjeev Khanna, Frank Paterra
1991	J	`jnl`	Logic Programming for Software Verification and Testing. Comput. J. Sanjeev Khanna
1990	C	`conf`	Logic Programming for Software Testing. ICCI Sanjeev Khanna