default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDSanjeev Khanna
Person information
- affiliation: University of Pennsylvania, Philadelphia, PA, USA
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
Books and Theses
- 2001
[b2]Nadia Creignou, Sanjeev Khanna, Madhu Sudan:
Complexity classifications of Boolean constraint satisfaction problems. SIAM monographs on discrete mathematics and applications 7, SIAM 2001, ISBN 978-0-89871-479-1, pp. I-XII, 1-106- 1996
- [b1]Sanjeev Khanna:
A structural view of approximation. Stanford University, USA, 1996
Journal Articles
- 2021
- [j56]Deeparnab Chakrabarty, Sanjeev Khanna:
Better and simpler error analysis of the Sinkhorn-Knopp algorithm for matrix scaling. Math. Program. 188(1): 395-407 (2021) - [j55]Sepehr Assadi, Sanjeev Khanna, Yang Li:
Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem. SIAM J. Comput. 50(3) (2021) - 2020
- [j54]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): 2:1-2:30 (2020) - 2019
- [j53]Ashish Goel, Michael Kapralov, Sanjeev Khanna:
Perfect Matchings in Õ (n 1.5) Time in Regular Bipartite Graphs. Comb. 39(2): 323-354 (2019) - [j52]Sepehr Assadi, Sanjeev Khanna, Yang Li:
The Stochastic Matching Problem with (Very) Few Queries. ACM Trans. Economics and Comput. 7(3): 16:1-16:19 (2019) - 2017
- [j51]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): 279-292 (2017) - [j50]Sepehr Assadi, Sanjeev Khanna, Yang Li, Rakesh Vohra:
Fast Convergence in the Double Oral Auction. ACM Trans. Economics and Comput. 5(4): 20:1-20:18 (2017) - 2016
- [j49]Brett Hemenway, Sanjeev Khanna:
Sensitivity and computational complexity in financial networks. Algorithmic Finance 5(3-4): 95-110 (2016) - [j48]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: 584-594 (2016) - 2015
- [j47]Deeparnab Chakrabarty, Chandra Chekuri, Sanjeev Khanna, Nitish Korula:
Approximability of Capacitated Network Design. Algorithmica 72(2): 493-514 (2015) - [j46]Michael Brautbar, Moez Draief, Sanjeev Khanna:
On the Power of Planned Infections in Networks. Internet Math. 11(4-5): 319-332 (2015) - 2014
- [j45]Susan B. Davidson, Sanjeev Khanna, Tova Milo, Sudeepa Roy:
Top-k and Clustering with Noisy Comparisons. ACM Trans. Database Syst. 39(4): 35:1-35:39 (2014) - 2013
- [j44]Ashish Goel, Michael Kapralov, Sanjeev Khanna:
Perfect Matchings in O(nlog n) Time in Regular Bipartite Graphs. SIAM J. Comput. 42(3): 1392-1404 (2013) - [j43]Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd:
The All-or-Nothing Multicommodity Flow Problem. SIAM J. Comput. 42(4): 1467-1493 (2013) - [j42]Tanmoy Chakraborty, Zhiyi Huang, Sanjeev Khanna:
Dynamic and Nonuniform Pricing Strategies for Revenue Maximization. SIAM J. Comput. 42(6): 2424-2451 (2013) - 2012
- [j41]Julia Chuzhoy, Sanjeev Khanna:
An O(k3log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design. Theory Comput. 8(1): 401-413 (2012) - [j40]Sanjeev Khanna, Santosh S. Venkatesh, Omid Fatemieh, Fariba Khan, Carl A. Gunter:
Adaptive Selective Verification: An Efficient Adaptive Countermeasure to Thwart DoS Attacks. IEEE/ACM Trans. Netw. 20(3): 715-728 (2012) - 2011
- [j39]Sanjeev Khanna, Sudeepa Roy, Val Tannen:
Queries with Difference on Probabilistic Databases. Proc. VLDB Endow. 4(11): 1051-1062 (2011) - 2010
- [j38]Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar, Lisa Zhang:
Inapproximability of Edge-Disjoint Paths and low congestion routing on undirected graphs. Comb. 30(5): 485-520 (2010) - [j37]Stanislav Angelov, Sanjeev Khanna, Mirkó Visontai:
Robust self-assembly of graphs. Nat. Comput. 9(1): 111-133 (2010) - [j36]Ashish Goel, Michael Kapralov, Sanjeev Khanna:
Perfect matchings via uniform sampling in regular bipartite graphs. ACM Trans. Algorithms 6(2): 27:1-27:13 (2010) - 2009
- [j35]Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd:
A Note on Multiflows and Treewidth. Algorithmica 54(3): 400-412 (2009) - [j34]Stanislav Angelov, Sanjeev Khanna, Keshav Kunal:
The Network as a Storage Device: Dynamic Routing with Bounded Buffers. Algorithmica 55(1): 71-94 (2009) - [j33]Julia Chuzhoy, Sanjeev Khanna:
Polynomial flow-cut gaps and hardness of directed cut problems. J. ACM 56(2): 6:1-6:28 (2009) - [j32]Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd:
Edge-Disjoint Paths in Planar Graphs with Constant Congestion. SIAM J. Comput. 39(1): 281-301 (2009) - [j31]Leana Golubchik, Sanjeev Khanna, Samir Khuller, Ramakrishna Thurimella, An Zhu:
Approximation algorithms for data placement on parallel disks. ACM Trans. Algorithms 5(4): 34:1-34:26 (2009) - 2008
- [j30]Stanislav Angelov, Sanjeev Khanna, Mirkó Visontai:
On the complexity of graph self-assembly in accretive systems. Nat. Comput. 7(2): 183-201 (2008) - 2007
- [j29]Stanislav Angelov, Boulos Harb, Sampath Kannan, Sanjeev Khanna, Junhyong Kim:
Efficient Enumeration of Phylogenetically Informative Substrings. J. Comput. Biol. 14(6): 701-723 (2007) - [j28]Chandra Chekuri, Sanjeev Khanna:
Edge-disjoint paths revisited. ACM Trans. Algorithms 3(4): 46 (2007) - 2006
- [j27]Volkan Isler, Sampath Kannan, Sanjeev Khanna:
Randomized Pursuit-Evasion with Local Visibility. SIAM J. Discret. Math. 20(1): 26-41 (2006) - [j26]Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd:
An O(sqrt(n)) Approximation and Integrality Gap for Disjoint Paths and Unsplittable Flow. Theory Comput. 2(7): 137-146 (2006) - 2005
- [j25]Volkan Isler, Sanjeev Khanna, John R. Spletzer, Camillo J. Taylor:
Target tracking with distributed sensors: The focus of attention problem. Comput. Vis. Image Underst. 100(1-2): 225-247 (2005) - [j24]Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Robert Krauthgamer, Joseph Naor:
Asymmetric k-center is log* n-hard to approximate. J. ACM 52(4): 538-551 (2005) - [j23]Chandra Chekuri, Sanjeev Khanna:
A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem. SIAM J. Comput. 35(3): 713-728 (2005) - [j22]Volkan Isler, Sampath Kannan, Sanjeev Khanna:
Randomized pursuit-evasion in a polygonal environment. IEEE Trans. Robotics 21(5): 875-884 (2005) - 2004
- [j21]Sanjeev Khanna, Aravind Srinivasan:
Special issue: 35th Annual ACM Symposium on Theory of Computing. J. Comput. Syst. Sci. 69(3): 305- (2004) - [j20]Chandra Chekuri, Sanjeev Khanna:
On Multidimensional Packing Problems. SIAM J. Comput. 33(4): 837-851 (2004) - [j19]Venkatesan Guruswami, Sanjeev Khanna:
On the Hardness of 4-Coloring a 3-Colorable Graph. SIAM J. Discret. Math. 18(1): 30-40 (2004) - [j18]Chandra Chekuri, Sanjeev Khanna, Joseph Naor, Leonid Zosin:
A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem. SIAM J. Discret. Math. 18(3): 608-625 (2004) - [j17]Peter Buneman, Sanjeev Khanna, Keishi Tajima, Wang Chiew Tan:
Archiving scientific data. ACM Trans. Database Syst. 29: 2-42 (2004) - 2003
- [j16]Micah Adler, Sanjeev Khanna, Rajmohan Rajaraman, Adi Rosén:
Time-Constrained Scheduling of Weighted Packets on Trees and Meshes. Algorithmica 36(2): 123-152 (2003) - [j15]Venkatesan Guruswami, Sanjeev Khanna, Rajmohan Rajaraman, F. Bruce Shepherd, Mihalis Yannakakis:
Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. J. Comput. Syst. Sci. 67(3): 473-496 (2003) - 2002
- [j14]Sanjeev Khanna:
Guest Editor's Foreword. J. Comput. Syst. Sci. 64(4): 749 (2002) - 2000
- [j13]Sanjeev Khanna, Nathan Linial, Shmuel Safra:
On the Hardness of Approximating the Chromatic Number. Comb. 20(3): 393-415 (2000) - [j12]Sanjeev Khanna, Shiyu Zhou:
On Indexed Data Broadcast. J. Comput. Syst. Sci. 60(3): 575-591 (2000) - [j11]Sanjeev Khanna, Vincenzo Liberatore:
On Broadcast Disk Paging. SIAM J. Comput. 29(5): 1683-1702 (2000) - [j10]Sanjeev Khanna, Madhu Sudan, Luca Trevisan, David P. Williamson:
The Approximability of Constraint Satisfaction Problems. SIAM J. Comput. 30(6): 1863-1920 (2000) - 1999
- [j9]Alok Aggarwal, Don Coppersmith, Sanjeev Khanna, Rajeev Motwani, Baruch Schieber:
The Angular-Metric Traveling Salesman Problem. SIAM J. Comput. 29(3): 697-711 (1999) - 1998
- [j8]Sanjeev Khanna, Rajeev Motwani, Randall H. Wilson:
On Certificates and Lookahead in Dynamic Graph Problems. Algorithmica 21(4): 377-394 (1998) - [j7]Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani:
On Syntactic versus Computational Views of Approximability. SIAM J. Comput. 28(1): 164-191 (1998) - 1997
- [j6]Sanjeev Khanna:
A polynomial time approximation scheme for the SONET ring loading problem. Bell Labs Tech. J. 2(2): 36-41 (1997) - [j5]Viggo Kann, Sanjeev Khanna, Jens Lagergren, Alessandro Panconesi:
On the Hardness of Approximating Max k-Cut and its Dual. Chic. J. Theor. Comput. Sci. 1997 (1997) - [j4]Sanjeev Khanna, W. Kent Fuchs:
A Graph Partitioning Approach to Sequential Diagnosis. IEEE Trans. Computers 46(1): 39-47 (1997) - 1995
- [j3]Sanjeev Khanna, W. Kent Fuchs:
A Linear Time Algorithm for Sequential Diagnosis in Hypercubes. J. Parallel Distributed Comput. 26(1): 48-53 (1995) - 1991
- [j2]Edwin C. Foudriat, Kurt Maly, C. Michael Overstreet, Sanjeev Khanna, Frank Paterra:
A carrier sensed multiple access protocol high data rate ring networks. Comput. Commun. Rev. 21(2): 59-70 (1991) - [j1]Sanjeev Khanna:
Logic Programming for Software Verification and Testing. Comput. J. 34(4): 350-357 (1991)
Conference and Workshop Papers
- 2024
- [c177]Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan:
Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs. ICALP 2024: 98:1-98:17 - [c176]Julia Chuzhoy, Sanjeev Khanna:
A Faster Combinatorial Algorithm for Maximum Bipartite Matching. SODA 2024: 2185-2235 - [c175]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: 3997-4061 - [c174]Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan:
Code Sparsification and its Applications. SODA 2024: 5145-5168 - [c173]Julia Chuzhoy, Sanjeev Khanna:
Maximum Bipartite Matching in n2+o(1) Time via a Combinatorial Algorithm. STOC 2024: 83-94 - 2023
- [c172]Yu Chen, Sanjeev Khanna, Zihan Tan:
Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics. ICALP 2023: 37:1-37:16 - [c171]Sanjeev Khanna, Christian Konrad, Cezar-Mihail Alexandru:
Set Cover in the One-pass Edge-arrival Streaming Model. PODS 2023: 127-139 - [c170]Yu Chen, Sanjeev Khanna, Zihan Tan:
Query Complexity of the Metric Steiner Tree Problem. SODA 2023: 4893-4935 - [c169]Sepehr Assadi, Soheil Behnezhad, Sanjeev Khanna, Huan Li:
On Regularity Lemma and Barriers in Streaming and Dynamic Matching. STOC 2023: 131-144 - 2022
- [c168]Arpit Agarwal, Sanjeev Khanna, Prathamesh Patil:
PAC Top-k Identification under SST in Limited Rounds. AISTATS 2022: 6814-6839 - [c167]Arpit Agarwal, Sanjeev Khanna, Prathamesh Patil:
A Sharp Memory-Regret Trade-off for Multi-Pass Streaming Bandits. COLT 2022: 1423-1462 - [c166]Yu Chen, Sanjeev Khanna, Huan Li:
On Weighted Graph Sparsification by Linear Sketching. FOCS 2022: 474-485 - [c165]Sanjeev Khanna, Christian Konrad:
Optimal Bounds for Dominating Set in Graph Streams. ITCS 2022: 93:1-93:23 - [c164]Arpit Agarwal, Sanjeev Khanna, Huan Li, Prathamesh Patil:
Sublinear Algorithms for Hierarchical Clustering. NeurIPS 2022 - [c163]Soheil Behnezhad, Sanjeev Khanna:
New Trade-Offs for Fully Dynamic Matching via Hierarchical EDCS. SODA 2022: 3529-3566 - [c162]Anindya De, Sanjeev Khanna, Huan Li, Hesam Nikpey:
Nearly Tight Bounds for Discrete Search under Outlier Noise. SOSA 2022: 161-173 - 2021
- [c161]Sepehr Assadi, Deeparnab Chakrabarty, Sanjeev Khanna:
Graph Connectivity and Single Element Recovery via Linear and OR Queries. ESA 2021: 7:1-7:19 - [c160]Deeparnab Chakrabarty, Yu Chen, Sanjeev Khanna:
A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization. FOCS 2021: 37-48 - [c159]Yu Chen, Sanjeev Khanna, Ansh Nagda:
Sublinear Time Hypergraph Sparsification via Cut and Edge Sampling Queries. ICALP 2021: 53:1-53:21 - [c158]Anindya De, Sanjeev Khanna, Huan Li, MohammadHesam NikpeySalekde:
Approximate optimization of convex functions with outlier noise. NeurIPS 2021: 8147-8157 - [c157]Naveen Garg, Sanjeev Khanna, Amit Kumar:
Hardness of Approximation for Orienteering with Multiple Time Windows. SODA 2021: 2977-2990 - 2020
- [c156]Yu Chen, Sanjeev Khanna, Ansh Nagda:
Near-linear Size Hypergraph Cut Sparsifiers. FOCS 2020: 61-72 - [c155]Yu Chen, Sampath Kannan, Sanjeev Khanna:
Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation. ICALP 2020: 30:1-30:19 - [c154]Anindya De, Sanjeev Khanna, Huan Li, Hesam Nikpey:
An Efficient PTAS for Stochastic Load Balancing with Poisson Jobs. ICALP 2020: 37:1-37:18 - [c153]Arpit Agarwal, Shivani Agarwal, Sanjeev Khanna, Prathamesh Patil:
Rank Aggregation from Pairwise Comparisons in the Presence of Adversarial Corruptions. ICML 2020: 85-95 - [c152]Rajeev Alur, Yu Chen, Kishor Jothimurugan, Sanjeev Khanna:
Space-efficient Query Evaluation over Probabilistic Event Streams. LICS 2020: 74-87 - [c151]Yu Chen, Sampath Kannan, Sanjeev Khanna:
Near-Perfect Recovery in the One-Dimensional Latent Space Model. WWW 2020: 1932-1942 - 2019
- [c150]Yu Chen, Shahin Jabbari, Michael J. Kearns, Sanjeev Khanna, Jamie Morgenstern:
Network Formation under Random Attack and Probabilistic Spread. IJCAI 2019: 180-186 - [c149]Sepehr Assadi, Michael Kapralov, Sanjeev Khanna:
A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling. ITCS 2019: 6:1-6:20 - [c148]Arpit Agarwal, Sepehr Assadi, Sanjeev Khanna:
Stochastic Submodular Cover with Limited Adaptivity. SODA 2019: 323-342 - [c147]Sepehr Assadi, Yu Chen, Sanjeev Khanna:
Sublinear Algorithms for (Δ + 1) Vertex Coloring. SODA 2019: 767-786 - [c146]Sepehr Assadi, Yu Chen, Sanjeev Khanna:
Polynomial pass lower bounds for graph streaming algorithms. STOC 2019: 265-276 - [c145]Julia Chuzhoy, Sanjeev Khanna:
A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems. STOC 2019: 389-400 - 2018
- [c144]Ashish Chiplunkar, Michael Kapralov, Sanjeev Khanna, Aida Mousavifar, Yuval Peres:
Testing Graph Clusterability: Algorithms and Lower Bounds. FOCS 2018: 497-508 - [c143]Deeparnab Chakrabarty, Sanjeev Khanna:
Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling. SOSA 2018: 4:1-4:11 - [c142]Mudabir Kabir Asathulla, Sanjeev Khanna, Nathaniel Lahn, Sharath Raghvendra:
A Faster Algorithm for Minimum-Cost Bipartite Perfect Matching in Planar Graphs. SODA 2018: 457-476 - [c141]Sepehr Assadi, Sanjeev Khanna:
Tight Bounds on the Round Complexity of the Distributed Maximum Coverage Problem. SODA 2018: 2412-2431 - 2017
- [c140]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: 39-75 - [c139]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: 693-708 - [c138]Sepehr Assadi, Sanjeev Khanna, Yang Li:
The Stochastic Matching Problem: Beating Half with a Non-Adaptive Algorithm. EC 2017: 99-116 - [c137]Michael Kapralov, Sanjeev Khanna, Madhu Sudan, Ameya Velingker:
(1 + Ω(1))-Αpproximation to MAX-CUT Requires Linear Space. SODA 2017: 1703-1722 - [c136]Sepehr Assadi, Sanjeev Khanna, Yang Li:
On Estimating Maximum Matching Size in Graph Streams. SODA 2017: 1723-1742 - [c135]Sepehr Assadi, Sanjeev Khanna:
Randomized Composable Coresets for Matching and Vertex Cover. SPAA 2017: 3-12 - 2016
- [c134]Sepehr Assadi, Sanjeev Khanna, Yang Li, Val Tannen:
Algorithms for Provisioning Queries and Analytics. ICDT 2016: 18:1-18:18 - [c133]Alexander J. T. Gurney, Sanjeev Khanna, Yang Li:
Rapid convergence versus policy expressiveness in interdomain routing. INFOCOM 2016: 1-9 - [c132]Sepehr Assadi, Sanjeev Khanna, Yang Li:
The Stochastic Matching Problem with (Very) Few Queries. EC 2016: 43-60 - [c131]Sepehr Assadi, Sanjeev Khanna, Yang Li, Grigory Yaroslavtsev:
Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model. SODA 2016: 1345-1364 - [c130]Sepehr Assadi, Sanjeev Khanna, Yang Li:
Tight bounds for single-pass streaming complexity of the set cover problem. STOC 2016: 698-711 - [c129]Sanjeev Goyal, Shahin Jabbari, Michael J. Kearns, Sanjeev Khanna, Jamie Morgenstern:
Strategic Network Formation with Attack and Immunization. WINE 2016: 429-443 - 2015
- [c128]Sepehr Assadi, Sanjeev Khanna, Yang Li, Val Tannen:
Dynamic Sketching for Graph Optimization Problems with Applications to Cut-Preserving Sketches. FSTTCS 2015: 52-68 - [c127]Yannis Mantzouratos, Tarik Tosun, Sanjeev Khanna, Mark Yim:
On embeddability of modular robot designs. ICRA 2015: 1911-1918 - [c126]Deeparnab Chakrabarty, Sanjeev Khanna, Shi Li:
On (1, ∊)-Restricted Assignment Makespan Minimization. SODA 2015: 1087-1101 - [c125]Michael Kapralov, Sanjeev Khanna, Madhu Sudan:
Streaming Lower Bounds for Approximating MAX-CUT. SODA 2015: 1263-1282 - [c124]Ashish Goel, Sanjeev Khanna, Sharath Raghvendra, Hongyang Zhang:
Connectivity in Random Forests and Credit Networks. SODA 2015: 2037-2048 - [c123]Sepehr Assadi, Sanjeev Khanna, Yang Li, Rakesh V. Vohra:
Fast Convergence in the Double Oral Auction. WINE 2015: 60-73 - 2014
- [c122]Justin Hsu, Marco Gaboardi, Andreas Haeberlen, Sanjeev Khanna, Arjun Narayan, Benjamin C. Pierce, Aaron Roth:
Differential Privacy: An Economic Method for Choosing Epsilon. CSF 2014: 398-410 - [c121]Johannes Starlinger, Sarah Cohen Boulakia, Sanjeev Khanna, Susan B. Davidson, Ulf Leser:
Layer Decomposition: An Effective Structure-Based Approach for Scientific Workflow Similarity. eScience 2014: 169-176 - [c120]Anand Bhalgat, Sanjeev Khanna:
A Utility Equivalence Theorem for Concave Functions. IPCO 2014: 126-137 - [c119]Sanjeev Khanna:
Matchings, Random Walks, and Sampling. LATA 2014: 32-33 - [c118]Ahmed Hefny, Robert E. Kass, Sanjeev Khanna, Matthew A. Smith, Geoffrey J. Gordon:
Fast and Improved SLEX Analysis of High-Dimensional Time Series. MLINI@NIPS 2014: 94-103 - [c117]Michael Kapralov, Sanjeev Khanna, Madhu Sudan:
Approximating matching size from random streams. SODA 2014: 734-751 - [c116]Ashish Goel, Sanjeev Khanna, Daniel H. Larkin, Robert Endre Tarjan:
Disjoint Set Union with Randomized Linking. SODA 2014: 1005-1017 - [c115]Sanjeev Khanna, Brendan Lucier:
Influence Maximization in Undirected Networks. SODA 2014: 1482-1496 - 2013
- [c114]Susan B. Davidson, Sanjeev Khanna, Tova Milo:
To Show or Not to Show in Workflow Provenance. In Search of Elegance in the Theory and Practice of Computation 2013: 217-226 - [c113]Marek Chrobak, Uriel Feige, Mohammad Taghi Hajiaghayi, Sanjeev Khanna, Fei Li, Seffi Naor:
A Greedy Approximation Algorithm for Minimum-Gap Scheduling. CIAC 2013: 97-109 - [c112]Susan B. Davidson, Sanjeev Khanna, Tova Milo, Sudeepa Roy:
Using the crowd for top-k and group-by queries. ICDT 2013: 225-236 - [c111]Michael Brautbar, Moez Draief, Sanjeev Khanna:
On the Power of Adversarial Infections in Networks. WAW 2013: 44-55 - 2012
- [c110]Parinya Chalermsook, Julia Chuzhoy, Sampath Kannan, Sanjeev Khanna:
Improved Hardness Results for Profit Maximization Pricing Problems with Unlimited Supply. APPROX-RANDOM 2012: 73-84 - [c109]Justin Hsu, Sanjeev Khanna, Aaron Roth:
Distributed Private Heavy Hitters. ICALP (1) 2012: 461-472 - [c108]Ashish Goel, Michael Kapralov, Sanjeev Khanna:
On the communication and streaming complexity of maximum bipartite matching. SODA 2012: 468-485 - [c107]Anand Bhalgat, Tanmoy Chakraborty, Sanjeev Khanna:
Mechanism Design for a Risk Averse Seller. WINE 2012: 198-211 - [c106]Christian Borgs, Michael Brautbar, Jennifer T. Chayes, Sanjeev Khanna, Brendan Lucier:
The Power of Local Information in Social Networks. WINE 2012: 406-419 - 2011
- [c105]Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna:
Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs. APPROX-RANDOM 2011: 75-86 - [c104]Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna:
Social Welfare in One-Sided Matching Markets without Money. APPROX-RANDOM 2011: 87-98 - [c103]Susan B. Davidson, Sanjeev Khanna, Val Tannen, Sudeepa Roy, Yi Chen, Tova Milo, Julia Stoyanovich:
Enabling Privacy in Provenance-Aware Workflow Systems. CIDR 2011: 215-218 - [c102]Zhiyi Huang, Sampath Kannan, Sanjeev Khanna:
Algorithms for the Generalized Sorting Problem. FOCS 2011: 738-747 - [c101]Sanjeev Khanna, Madhu Sudan:
Delays and the Capacity of Continuous-Time Channels. FOCS 2011: 758-767 - [c100]Susan B. Davidson, Sanjeev Khanna, Sudeepa Roy, Julia Stoyanovich, Val Tannen, Yi Chen:
On provenance and privacy. ICDT 2011: 3-10 - [c99]Brendan Juba, Adam Tauman Kalai, Sanjeev Khanna, Madhu Sudan:
Compression without a common prior: an information-theoretic justification for ambiguity in language. ICS 2011: 79-86 - [c98]Deeparnab Chakrabarty, Chandra Chekuri, Sanjeev Khanna, Nitish Korula:
Approximability of Capacitated Network Design. IPCO 2011: 78-91 - [c97]Susan B. Davidson, Sanjeev Khanna, Tova Milo, Debmalya Panigrahi, Sudeepa Roy:
Provenance views for module privacy. PODS 2011: 175-186 - [c96]Anand Bhalgat, Ashish Goel, Sanjeev Khanna:
Improved Approximation Results for Stochastic Knapsack Problems. SODA 2011: 1647-1665 - 2010
- [c95]Tanmoy Chakraborty, Zhiyi Huang, Sanjeev Khanna:
Dynamic and non-uniform pricing strategies for revenue maximization. BQGT 2010: 20:1 - [c94]Anand Bhalgat, Tanmoy Chakraborty, Sanjeev Khanna:
Approximating pure nash equilibrium in cut, party affiliation, and satisfiability games. EC 2010: 73-82 - [c93]Zhuowei Bao, Susan B. Davidson, Sanjeev Khanna, Sudeepa Roy:
An optimal labeling scheme for workflow provenance using skeleton labels. SIGMOD Conference 2010: 711-722 - [c92]Ashish Goel, Michael Kapralov, Sanjeev Khanna:
Perfect matchings in o(n log n) time in regular bipartite graphs. STOC 2010: 39-46 - [c91]Patrick Briest, Parinya Chalermsook, Sanjeev Khanna, Bundit Laekhanukit, Danupon Nanongkai:
Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing. WINE 2010: 444-454 - 2009
- [c90]Deeparnab Chakrabarty, Julia Chuzhoy, Sanjeev Khanna:
On Allocating Goods to Maximize Fairness. FOCS 2009: 107-116 - [c89]Julia Chuzhoy, Sanjeev Khanna:
An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design. FOCS 2009: 437-441 - [c88]Tanmoy Chakraborty, Zhiyi Huang, Sanjeev Khanna:
Dynamic and Non-uniform Pricing Strategies for Revenue Maximization. FOCS 2009: 495-504 - [c87]Zhuowei Bao, Sarah Cohen Boulakia, Susan B. Davidson, Anat Eyal, Sanjeev Khanna:
Differencing Provenance in Scientific Workflows. ICDE 2009: 808-819 - [c86]Olivier Biton, Susan B. Davidson, Sanjeev Khanna, Sudeepa Roy:
Optimizing user views for workflows. ICDT 2009: 310-323 - [c85]Tanmoy Chakraborty, Sanjeev Khanna:
Nash Dynamics in Constant Player and Bounded Jump Congestion Games. SAGT 2009: 196-207 - [c84]Liming Zhao, Aline Normoyle, Sanjeev Khanna, Alla Safonova:
Automatic construction of a minimum size motion graph. Symposium on Computer Animation 2009: 27-35 - [c83]Tanmoy Chakraborty, Michael J. Kearns, Sanjeev Khanna:
Network bargaining: algorithms and structural results. EC 2009: 159-168 - [c82]Ashish Goel, Michael Kapralov, Sanjeev Khanna:
Perfect matchings via uniform sampling in regular bipartite graphs. SODA 2009: 11-17 - [c81]Ashish Goel, Sanjeev Khanna, Brad Null:
The ratio index for budgeted learning, with applications. SODA 2009: 18-27 - [c80]Anand Bhalgat, Tanmoy Chakraborty, Sanjeev Khanna:
Nash Dynamics in Congestion Games with Similar Resources. WINE 2009: 362-373 - 2008
- [c79]Stanislav Angelov, Sanjeev Khanna, Mirkó Visontai:
Robust Self-assembly of Graphs. DNA 2008: 127-143 - [c78]Julia Chuzhoy, Sanjeev Khanna:
Algorithms for Single-Source Vertex Connectivity. FOCS 2008: 105-114 - [c77]Sampath Kannan, Sanjeev Khanna, Sudeepa Roy:
STCON in Directed Unique-Path Graphs. FSTTCS 2008: 256-267 - [c76]Chandra Chekuri, Sanjeev Khanna:
Algorithms for 2-Route Cut Problems. ICALP (1) 2008: 472-484 - [c75]Sanjeev Khanna, Santosh S. Venkatesh, Omid Fatemieh, Fariba Khan, Carl A. Gunter:
Adaptive SelectiveVerification. INFOCOM 2008: 529-537 - [c74]Ashish Goel, Sanjeev Khanna:
On the Network Coding Advantage for Wireless Multicast in Euclidean Space. IPSN 2008: 64-69 - [c73]Tanmoy Chakraborty, Julia Chuzhoy, Sanjeev Khanna:
Network design for vertex connectivity. STOC 2008: 167-176 - 2007
- [c72]Sanjeev Khanna, Keshav Kunal, Benjamin C. Pierce:
A Formal Investigation of. FSTTCS 2007: 485-496 - [c71]Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar:
Hardness of routing with congestion in directed graphs. STOC 2007: 165-178 - [c70]Julia Chuzhoy, Sanjeev Khanna:
Polynomial flow-cut gaps and hardness of directed cut problems. STOC 2007: 179-188 - 2006
- [c69]Stanislav Angelov, Sanjeev Khanna, Mirkó Visontai:
On the Complexity of Graph Self-assembly in Accretive Systems. DNA 2006: 95-110 - [c68]Stanislav Angelov, Boulos Harb, Sampath Kannan, Sanjeev Khanna, Junhyong Kim:
Efficient Enumeration of Phylogenetically Informative Substrings. RECOMB 2006: 248-264 - [c67]Julia Chuzhoy, Sanjeev Khanna:
Hardness of cut problems in directed graphs. STOC 2006: 527-536 - [c66]Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd:
Edge-disjoint paths in Planar graphs with constant congestion. STOC 2006: 757-766 - [c65]Michael B. Greenwald, Sanjeev Khanna, Keshav Kunal, Benjamin C. Pierce, Alan Schmitt:
Agreeing to Agree: Conflict Resolution for Optimistically Replicated Data. DISC 2006: 269-283 - 2005
- [c64]Stanislav Angelov, Sanjeev Khanna, Keshav Kunal:
The Network as a Storage Device: Dynamic Routing with Bounded Buffers. APPROX-RANDOM 2005: 1-13 - [c63]Matthew Andrews, Julia Chuzhoy, Sanjeev Khanna, Lisa Zhang:
Hardness of the Undirected Edge-Disjoint Paths Problem with Congestion. FOCS 2005: 226-244 - [c62]Nikhil Bansal, Moses Charikar, Sanjeev Khanna, Joseph Naor:
Approximating the average response time in broadcast scheduling. SODA 2005: 215-221 - [c61]Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd:
Multicommodity flow, well-linked terminals, and routing problems. STOC 2005: 183-192 - 2004
- [c60]Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd:
Edge-Disjoint Paths in Planar Graphs. FOCS 2004: 71-80 - [c59]Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Joseph Naor:
Machine Minimization for Scheduling Jobs with Interval Constraints. FOCS 2004: 81-90 - [c58]Andreas Björklund, Thore Husfeldt, Sanjeev Khanna:
Approximating Longest Directed Paths and Cycles. ICALP 2004: 222-233 - [c57]Carl A. Gunter, Sanjeev Khanna, Kaijun Tan, Santosh S. Venkatesh:
DoS Protection for Reliably Authenticated Broadcast. NDSS 2004 - [c56]Michael Greenwald, Sanjeev Khanna:
Power-Conserving Computation of Order-Statistics over Sensor Networks. PODS 2004: 275-285 - [c55]Tugkan Batu, Sampath Kannan, Sanjeev Khanna, Andrew McGregor:
Reconstructing strings from random traces. SODA 2004: 910-918 - [c54]Volkan Isler, Sampath Kannan, Sanjeev Khanna:
Randomized pursuit-evasion with limited visibility. SODA 2004: 1060-1069 - [c53]Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Joseph Naor:
Asymmetric k-center is log* n-hard to approximate. STOC 2004: 21-27 - [c52]Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd:
The all-or-nothing multicommodity flow problem. STOC 2004: 156-165 - [c51]Chandra Chekuri, Ashish Goel, Sanjeev Khanna, Amit Kumar:
Multi-processor scheduling to minimize flow time with epsilon resource augmentation. STOC 2004: 363-372 - [c50]Stanislav Angelov, Sanjeev Khanna, Li Li, Fernando Pereira:
ATDD: An Algorithmic Tool for Domain Discovery in Protein Sequences. WABI 2004: 206-217 - [c49]Stanislav Angelov, Boulos Harb, Sampath Kannan, Sanjeev Khanna, Junhyong Kim, Li-San Wang:
Genome Identification and Classification by Short Oligo Arrays. WABI 2004: 400-411 - [c48]Volkan Isler, Sampath Kannan, Sanjeev Khanna:
Locating and Capturing an Evader in a Polygonal Environment. WAFR 2004: 251-266 - 2003
- [c47]Volkan Isler, John R. Spletzer, Sanjeev Khanna, Camillo J. Taylor:
Target tracking with distributed sensors: the focus of attention problem. IROS 2003: 792-798 - [c46]Sampath Kannan, Sanjeev Khanna:
Selection with monotone comparison cost. SODA 2003: 10-17 - [c45]Chandra Chekuri, Sanjeev Khanna:
Edge disjoint paths revisited. SODA 2003: 628-637 - 2002
- [c44]Sanjeev Khanna, Joseph Naor, Danny Raz:
Control Message Aggregation in Group Communication Protocols. ICALP 2002: 135-146 - [c43]Peter Buneman, Sanjeev Khanna, Wang Chiew Tan:
On Propagation of Deletions and Annotations Through Views. PODS 2002: 150-158 - [c42]Peter Buneman, Sanjeev Khanna, Keishi Tajima, Wang Chiew Tan:
Archiving scientific data. SIGMOD Conference 2002: 1-12 - [c41]Chandra Chekuri, Sanjeev Khanna:
Approximation schemes for preemptive weighted flow time. STOC 2002: 297-305 - 2001
- [c40]Chandra Chekuri, Sanjeev Khanna:
A PTAS for Minimizing Weighted Completion Time on Uniformly Related Machines. ICALP 2001: 848-861 - [c39]Peter Buneman, Sanjeev Khanna, Wang Chiew Tan:
Why and Where: A Characterization of Data Provenance. ICDT 2001: 316-330 - [c38]Sanjeev Khanna, Wang Chiew Tan:
On Computing Functions with Uncertainty. PODS 2001 - [c37]Maria Adamou, Sanjeev Khanna, Insup Lee, Insik Shin, Shiyu Zhou:
Fair Real-Time Traffic Scheduling over a Wireless LA. RTSS 2001: 279-288 - [c36]Michael Greenwald, Sanjeev Khanna:
Space-Efficient Online Computation of Quantile Summaries. SIGMOD Conference 2001: 58-66 - [c35]Chandra Chekuri, Sanjeev Khanna, Joseph Naor, Leonid Zosin:
Approximation algorithms for the metric labeling problem via a new linear programming formulation. SODA 2001: 109-118 - [c34]Chandra Chekuri, Sanjeev Khanna, Joseph Naor:
A deterministic algorithm for the cost-distance problem. SODA 2001: 232-233 - [c33]Chandra Chekuri, Sanjeev Khanna, An Zhu:
Algorithms for minimizing weighted flow time. STOC 2001: 84-93 - 2000
- [c32]Venkatesan Guruswami, Sanjeev Khanna:
On the Hardness of 4-Coloring a 3-Colorable Graph. CCC 2000: 188-197 - [c31]Peter Buneman, Sanjeev Khanna, Wang Chiew Tan:
Data Provenance: Some Basic Issues. FSTTCS 2000: 87-93 - [c30]Chandra Chekuri, Sanjeev Khanna:
A PTAS for the multiple knapsack problem. SODA 2000: 213-222 - [c29]Leana Golubchik, Sanjeev Khanna, Samir Khuller, Ramakrishna Thurimella, An Zhu:
Approximation algorithms for data placement on parallel disks. SODA 2000: 223-232 - [c28]Sanjeev Khanna, Francis Zane:
Watermarking maps: hiding information in structured data. SODA 2000: 596-605 - [c27]Sanjeev Khanna, Joseph Naor, F. Bruce Shepherd:
Directed network design with orientation constraints. SODA 2000: 663-671 - 1999
- [c26]Foto N. Afrati, Evripidis Bampis, Chandra Chekuri, David R. Karger, Claire Kenyon, Sanjeev Khanna, Ioannis Milis, Maurice Queyranne, Martin Skutella, Clifford Stein, Maxim Sviridenko:
Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates. FOCS 1999: 32-44 - [c25]Yevgeniy Dodis, Sanjeev Khanna:
Space Time Tradeoffs for Graph Properties. ICALP 1999: 291-300 - [c24]Matthew Andrews, Sanjeev Khanna, Krishnan Kumaran:
Integrated Scheduling of Unicast and Multicast Traffic in an Input-Queued Switch. INFOCOM 1999: 1144-1151 - [c23]Susanne Albers, Sanjeev Arora, Sanjeev Khanna:
Page Replacement for General Caching Problems. SODA 1999: 31-40 - [c22]Chandra Chekuri, Sanjeev Khanna:
On Multi-Dimensional Packing Problems. SODA 1999: 185-194 - [c21]Yevgeniy Dodis, Venkatesan Guruswami, Sanjeev Khanna:
The 2-Catalog Segmentation Problem. SODA 1999: 897-898 - [c20]Micah Adler, Sanjeev Khanna, Rajmohan Rajaraman, Adi Rosén:
Time-Constrained Scheduling of Weighted Packets on Trees and Meshes. SPAA 1999: 1-12 - [c19]Venkatesan Guruswami, Sanjeev Khanna, Rajmohan Rajaraman, F. Bruce Shepherd, Mihalis Yannakakis:
Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems. STOC 1999: 19-28 - [c18]Yevgeniy Dodis, Sanjeev Khanna:
Design Networks with Bounded Pairwise Distance. STOC 1999: 750-759 - 1998
- [c17]Krishnan Kumaran, Sanjeev Khanna:
On Wireless Spectrum Estimation and Generalized Graph Coloring. INFOCOM 1998: 1273-1283 - [c16]Sanjeev Khanna, S. Muthukrishnan, Mike Paterson:
On Approximating Rectangle Tiling and Packing. SODA 1998: 384-393 - [c15]Sanjeev Khanna, Shiyu Zhou:
On Indexed Data Broadcast. STOC 1998: 463-472 - [c14]Sanjeev Khanna, Vincenzo Liberatore:
On Broadcast Disk Paging. STOC 1998: 634-643 - 1997
- [c13]Sanjeev Khanna, Madhu Sudan, Luca Trevisan:
Constraint Satisfaction: The Approximability of Minimization Problems. CCC 1997: 282-296 - [c12]Sanjeev Khanna, S. Muthukrishnan, Steven Skiena:
Efficient Array Partitioning. ICALP 1997: 616-626 - [c11]Alok Aggarwal, Don Coppersmith, Sanjeev Khanna, Rajeev Motwani, Baruch Schieber:
The Angular-Metric Traveling Salesman Problem. SODA 1997: 221-229 - [c10]Sanjeev Khanna, Madhu Sudan, David P. Williamson:
A Complete Classification of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction. STOC 1997: 11-20 - 1996
- [c9]Viggo Kann, Sanjeev Khanna, Jens Lagergren, Alessandro Panconesi:
On the Hardness of Approximating Max k-Cut and Its Dual. ISTCS 1996: 61-67 - [c8]Sanjeev Khanna, Rajeev Motwani, Randall H. Wilson:
On Certificates and Lookahead in Dynamic Graph Problems. SODA 1996: 222-231 - [c7]Sanjeev Khanna, Rajeev Motwani:
Towards a Syntactic Characterization of PTAS. STOC 1996: 329-337 - 1994
- [c6]Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani:
On Syntactic versus Computational Views of Approximability. FOCS 1994: 819-830 - 1993
- [c5]Sanjeev Khanna, Nathan Linial, Shmuel Safra:
On the Hardness of Approximating the Chromatic Number. ISTCS 1993: 250-260 - 1992
- [c4]Kurt Maly, Sanjeev Khanna, Ravi Mukkamala, C. Michael Overstreet, Ramesh Yerraballi, Edwin C. Foudriat, B. Madan:
Parallel TCP/IP for Multiprocessor Workstations. HPN 1992: 103-118 - [c3]Kurt Maly, Frank Paterra, C. Michael Overstreet, Ravi Mukkamala, Sanjeev Khanna:
Concurrent Use of Parallel Communication to Enable Remote Visualization. ICCI 1992: 449-452 - [c2]Kurt Maly, Sanjeev Khanna, C. Michael Overstreet, Ravi Mukkamala, Mohammad Zubair, Y. S. Sekhar:
Multiprocessor Architectures for High Speed Networks: A Performance Study. IFIP Congress (1) 1992: 645-651 - 1990
- [c1]Sanjeev Khanna:
Logic Programming for Software Testing. ICCI 1990: 225-234
Parts in Books or Collections
- 2016
- [p1]Michael B. Greenwald, Sanjeev Khanna:
Quantiles and Equi-depth Histograms over Streams. Data Stream Management 2016: 45-86
Editorship
- 2013
- [e2]Sanjeev Khanna:
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013. SIAM 2013, ISBN 978-1-61197-251-1 [contents] - 2004
- [e1]Klaus Jansen, Sanjeev Khanna, José D. P. Rolim, Dana Ron:
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. Lecture Notes in Computer Science 3122, Springer 2004, ISBN 3-540-22894-2 [contents]
Reference Works
- 2004
- [r1]Chandra Chekuri, Sanjeev Khanna:
Approximation Algorithms for Minimizing AverageWeighted Completion Time. Handbook of Scheduling 2004
Informal and Other Publications
- 2024
- [i69]Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan:
Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs. CoRR abs/2402.13151 (2024) - [i68]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 abs/2402.14950 (2024) - [i67]Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan:
Characterizations of Sparsifiability for Affine CSPs and Symmetric CSPs. CoRR abs/2404.06327 (2024) - [i66]Julia Chuzhoy, Sanjeev Khanna:
Maximum Bipartite Matching in n2+o(1) Time via a Combinatorial Algorithm. CoRR abs/2405.20861 (2024) - [i65]Sepehr Assadi, Sanjeev Khanna:
Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemerédi Graphs. CoRR abs/2406.13573 (2024) - [i64]Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan:
Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers. CoRR abs/2407.03934 (2024) - 2023
- [i63]Sanjeev Khanna, Aaron (Louie) Putterman, Madhu Sudan:
Code Sparsification and its Applications. CoRR abs/2311.00788 (2023) - [i62]Julia Chuzhoy, Sanjeev Khanna:
A Faster Combinatorial Algorithm for Maximum Bipartite Matching. CoRR abs/2312.12584 (2023) - 2022
- [i61]Soheil Behnezhad, Sanjeev Khanna:
New Trade-Offs for Fully Dynamic Matching via Hierarchical EDCS. CoRR abs/2201.02905 (2022) - [i60]Yu Chen, Sanjeev Khanna, Zihan Tan:
Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics. CoRR abs/2203.14798 (2022) - [i59]Arpit Agarwal, Sanjeev Khanna, Prathamesh Patil:
A Sharp Memory-Regret Trade-Off for Multi-Pass Streaming Bandits. CoRR abs/2205.00984 (2022) - [i58]Arpit Agarwal, Sanjeev Khanna, Huan Li, Prathamesh Patil:
Sublinear Algorithms for Hierarchical Clustering. CoRR abs/2206.07633 (2022) - [i57]Sepehr Assadi, Soheil Behnezhad, Sanjeev Khanna, Huan Li:
On Regularity Lemma and Barriers in Streaming and Dynamic Matching. CoRR abs/2207.09354 (2022) - [i56]Yu Chen, Sanjeev Khanna, Huan Li:
On Weighted Graph Sparsification by Linear Sketching. CoRR abs/2209.07729 (2022) - [i55]Yu Chen, Sanjeev Khanna, Zihan Tan:
Query Complexity of the Metric Steiner Tree Problem. CoRR abs/2211.03893 (2022) - 2021
- [i54]Yu Chen, Sanjeev Khanna, Ansh Nagda:
Sublinear Time Hypergraph Sparsification via Cut and Edge Sampling Queries. CoRR abs/2106.10386 (2021) - [i53]Deeparnab Chakrabarty, Yu Chen, Sanjeev Khanna:
A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization and Matroid Intersection. CoRR abs/2111.07474 (2021) - 2020
- [i52]Yu Chen, Sampath Kannan, Sanjeev Khanna:
Near-Perfect Recovery in the One-Dimensional Latent Space Model. CoRR abs/2006.04351 (2020) - [i51]Yu Chen, Sampath Kannan, Sanjeev Khanna:
Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation. CoRR abs/2006.05490 (2020) - [i50]Anindya De, Sanjeev Khanna, Huan Li, Hesam Nikpey:
An Efficient PTAS for Stochastic Load Balancing with Poisson Jobs. CoRR abs/2006.12670 (2020) - [i49]Sepehr Assadi, Deeparnab Chakrabarty, Sanjeev Khanna:
Graph Connectivity and Single Element Recovery via Linear and OR Queries. CoRR abs/2007.06098 (2020) - [i48]Yu Chen, Sanjeev Khanna, Ansh Nagda:
Near-linear Size Hypergraph Cut Sparsifiers. CoRR abs/2009.04992 (2020) - 2019
- [i47]Sepehr Assadi, Yu Chen, Sanjeev Khanna:
Polynomial Pass Lower Bounds for Graph Streaming Algorithms. CoRR abs/1904.04720 (2019) - [i46]Julia Chuzhoy, Sanjeev Khanna:
A New Algorithm for Decremental Single-Source Shortest Paths with Applications to Vertex-Capacitated Flow and Cut Problems. CoRR abs/1905.11512 (2019) - [i45]Yu Chen, Shahin Jabbari, Michael J. Kearns, Sanjeev Khanna, Jamie Morgenstern:
Network Formation under Random Attack and Probabilistic Spread. CoRR abs/1906.00241 (2019) - 2018
- [i44]Deeparnab Chakrabarty, Sanjeev Khanna:
Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling. CoRR abs/1801.02790 (2018) - [i43]Sepehr Assadi, Sanjeev Khanna:
Tight Bounds on the Round Complexity of the Distributed Maximum Coverage Problem. CoRR abs/1801.02793 (2018) - [i42]Sepehr Assadi, Yu Chen, Sanjeev Khanna:
Sublinear Algorithms for (Δ+ 1) Vertex Coloring. CoRR abs/1807.08886 (2018) - [i41]Ashish Chiplunkar, Michael Kapralov, Sanjeev Khanna, Aida Mousavifar, Yuval Peres:
Testing Graph Clusterability: Algorithms and Lower Bounds. CoRR abs/1808.04807 (2018) - [i40]Arpit Agarwal, Sepehr Assadi, Sanjeev Khanna:
Stochastic Submodular Cover with Limited Adaptivity. CoRR abs/1810.13351 (2018) - [i39]Sepehr Assadi, Michael Kapralov, Sanjeev Khanna:
A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling. CoRR abs/1811.07780 (2018) - 2017
- [i38]Sepehr Assadi, Sanjeev Khanna, Yang Li:
On Estimating Maximum Matching Size in Graph Streams. CoRR abs/1701.04364 (2017) - [i37]Sepehr Assadi, Sanjeev Khanna, Yang Li:
The Stochastic Matching Problem: Beating Half with a Non-Adaptive Algorithm. CoRR abs/1705.02280 (2017) - [i36]Sepehr Assadi, Sanjeev Khanna:
Randomized Composable Coresets for Matching and Vertex Cover. CoRR abs/1705.08242 (2017) - 2016
- [i35]Sepehr Assadi, Sanjeev Khanna, Yang Li:
Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem. CoRR abs/1603.05715 (2016) - 2015
- [i34]Sepehr Assadi, Sanjeev Khanna, Yang Li, Grigory Yaroslavtsev:
Tight Bounds for Linear Sketches of Approximate Matchings. CoRR abs/1505.01467 (2015) - [i33]Sepehr Assadi, Sanjeev Khanna, Yang Li, Rakesh Vohra:
Fast Convergence in the Double Oral Auction. CoRR abs/1510.00086 (2015) - [i32]Sepehr Assadi, Sanjeev Khanna, Yang Li, Val Tannen:
Dynamic Sketching for Graph Optimization Problems with Applications to Cut-Preserving Sketches. CoRR abs/1510.03252 (2015) - [i31]Sanjeev Goyal, Shahin Jabbari, Michael J. Kearns, Sanjeev Khanna, Jamie Morgenstern:
Strategic Network Formation with Attack and Immunization. CoRR abs/1511.05196 (2015) - [i30]Sepehr Assadi, Sanjeev Khanna, Yang Li, Val Tannen:
Algorithms for Provisioning Queries and Analytics. CoRR abs/1512.06143 (2015) - 2014
- [i29]Justin Hsu, Marco Gaboardi, Andreas Haeberlen, Sanjeev Khanna, Arjun Narayan, Benjamin C. Pierce, Aaron Roth:
Differential Privacy: An Economic Method for Choosing Epsilon. CoRR abs/1402.3329 (2014) - [i28]Michael Kapralov, Sanjeev Khanna, Madhu Sudan:
Streaming Lower Bounds for Approximating MAX-CUT. CoRR abs/1409.2138 (2014) - [i27]Deeparnab Chakrabarty, Sanjeev Khanna, Shi Li:
On $(1, ε)$-Restricted Assignment Makespan Minimization. CoRR abs/1410.7506 (2014) - 2012
- [i26]Justin Hsu, Sanjeev Khanna, Aaron Roth:
Distributed Private Heavy Hitters. CoRR abs/1202.4910 (2012) - [i25]Christian Borgs, Michael Brautbar, Jennifer T. Chayes, Sanjeev Khanna, Brendan Lucier:
The Power of Local Information in Social Networks. CoRR abs/1202.6033 (2012) - 2011
- [i24]Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna:
Social Welfare in One-sided Matching Markets without Money. CoRR abs/1104.2964 (2011) - [i23]Sanjeev Khanna, Madhu Sudan:
Delays and the Capacity of Continuous-time Channels. CoRR abs/1105.3425 (2011) - [i22]Anand Bhalgat, Tanmoy Chakraborty, Sanjeev Khanna:
Mechanism Design with Risk Aversion. CoRR abs/1107.4722 (2011) - 2010
- [i21]Ashish Goel, Michael Kapralov, Sanjeev Khanna:
Graph Sparsification via Refinement Sampling. CoRR abs/1004.4915 (2010) - [i20]Susan B. Davidson, Sanjeev Khanna, Debmalya Panigrahi, Sudeepa Roy:
Preserving Module Privacy in Workflow Provenance. CoRR abs/1005.5543 (2010) - [i19]Deeparnab Chakrabarty, Chandra Chekuri, Sanjeev Khanna, Nitish Korula:
Approximability of Capacitated Network Design. CoRR abs/1009.5734 (2010) - [i18]Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna:
Optimal Lower Bounds for Universal and Differentially Private Steiner Tree and TSP. CoRR abs/1011.3770 (2010) - 2009
- [i17]Deeparnab Chakrabarty, Julia Chuzhoy, Sanjeev Khanna:
On Allocating Goods to Maximize Fairness. CoRR abs/0901.0205 (2009) - [i16]Ashish Goel, Sanjeev Khanna:
Perfect Matchings in Õ(n1.5) Time in Regular Bipartite Graphs. CoRR abs/0902.1617 (2009) - [i15]Tanmoy Chakraborty, Zhiyi Huang, Sanjeev Khanna:
Dynamic and Non-Uniform Pricing Strategies for Revenue Maximization. CoRR abs/0905.3191 (2009) - [i14]Ashish Goel, Michael Kapralov, Sanjeev Khanna:
Perfect Matchings in O(n \log n) Time in Regular Bipartite Graphs. CoRR abs/0909.3346 (2009) - [i13]Patrick Briest, Sanjeev Khanna:
Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing. CoRR abs/0910.0110 (2009) - 2008
- [i12]Ashish Goel, Michael Kapralov, Sanjeev Khanna:
Perfect Matchings via Uniform Sampling in Regular Bipartite Graphs. CoRR abs/0811.2457 (2008) - [i11]Julia Chuzhoy, Sanjeev Khanna:
An O(k3log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design. CoRR abs/0812.4442 (2008) - 2007
- [i10]Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar, Lisa Zhang:
Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs. Electron. Colloquium Comput. Complex. TR07 (2007) - 2006
- [i9]Julia Chuzhoy, Sanjeev Khanna:
Hardness of Directed Routing with Congestion. Electron. Colloquium Comput. Complex. TR06 (2006) - 2003
- [i8]Andreas Björklund, Thore Husfeldt, Sanjeev Khanna:
Approximating Longest Directed Path. Electron. Colloquium Comput. Complex. TR03 (2003) - [i7]Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Joseph Naor:
Asymmetric k-center is log*n-hard to Approximate. Electron. Colloquium Comput. Complex. TR03 (2003) - 2001
- [i6]Chandra Chekuri, Sanjeev Khanna:
Approximation Schemes for Preemptive Weighted Flow Time. Electron. Colloquium Comput. Complex. TR01 (2001) - 2000
- [i5]Venkatesan Guruswami, Sanjeev Khanna:
On the Hardness of 4-coloring a 3-colorable Graph. Electron. Colloquium Comput. Complex. TR00 (2000) - 1996
- [i4]Sanjeev Khanna, Madhu Sudan:
The Optimization Complexity of Constraint Satisfaction Problems. Electron. Colloquium Comput. Complex. TR96 (1996) - [i3]Sanjeev Khanna, Madhu Sudan, David P. Williamson:
A Complete Characterization of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction. Electron. Colloquium Comput. Complex. TR96 (1996) - [i2]Sanjeev Khanna, Madhu Sudan, Luca Trevisan:
Constraint satisfaction: The approximability of minimization problems. Electron. Colloquium Comput. Complex. TR96 (1996) - 1995
- [i1]Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani:
On Syntactic versus Computational Views of Approximability. Electron. Colloquium Comput. Complex. TR95 (1995)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-10-07 22:05 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
