Sanjeev Khanna

Susan B. Davidson, Sanjeev Khanna, Tova Milo, Sudeepa Roy: Using the crowd for top-k and group-by queries. ICDT 2013: 225-236

Sanjeev Khanna (Ed.): Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013. SIAM 2013

Julia Chuzhoy, Sanjeev Khanna: An O(k³log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design. Theory of Computing 8(1): 401-413 (2012)

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)

Parinya Chalermsook, Julia Chuzhoy, Sampath Kannan, Sanjeev Khanna: Improved Hardness Results for Profit Maximization Pricing Problems with Unlimited Supply. APPROX-RANDOM 2012: 73-84

Justin Hsu, Sanjeev Khanna, Aaron Roth: Distributed Private Heavy Hitters. ICALP (1) 2012: 461-472

Ashish Goel, Michael Kapralov, Sanjeev Khanna: On the communication and streaming complexity of maximum bipartite matching. SODA 2012: 468-485

Anand Bhalgat, Tanmoy Chakraborty, Sanjeev Khanna: Mechanism Design for a Risk Averse Seller. WINE 2012: 198-211

Christian Borgs, Michael Brautbar, Jennifer T. Chayes, Sanjeev Khanna, Brendan Lucier: The Power of Local Information in Social Networks. WINE 2012: 406-419

Justin Hsu, Sanjeev Khanna, Aaron Roth: Distributed Private Heavy Hitters. CoRR abs/1202.4910 (2012)

Christian Borgs, Michael Brautbar, Jennifer T. Chayes, Sanjeev Khanna, Brendan Lucier: The Power of Local Information in Social Networks. CoRR abs/1202.6033 (2012)

Sanjeev Khanna, Sudeepa Roy, Val Tannen: Queries with Difference on Probabilistic Databases. PVLDB 4(11): 1051-1062 (2011)

Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna: Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs. APPROX-RANDOM 2011: 75-86

Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna: Social Welfare in One-Sided Matching Markets without Money. APPROX-RANDOM 2011: 87-98

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

Zhiyi Huang, Sampath Kannan, Sanjeev Khanna: Algorithms for the Generalized Sorting Problem. FOCS 2011: 738-747

Sanjeev Khanna, Madhu Sudan: Delays and the Capacity of Continuous-Time Channels. FOCS 2011: 758-767

Susan B. Davidson, Sanjeev Khanna, Sudeepa Roy, Julia Stoyanovich, Val Tannen, Yi Chen: On provenance and privacy. ICDT 2011: 3-10

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

Deeparnab Chakrabarty, Chandra Chekuri, Sanjeev Khanna, Nitish Korula: Approximability of Capacitated Network Design. IPCO 2011: 78-91

Susan B. Davidson, Sanjeev Khanna, Tova Milo, Debmalya Panigrahi, Sudeepa Roy: Provenance views for module privacy. PODS 2011: 175-186

Anand Bhalgat, Ashish Goel, Sanjeev Khanna: Improved Approximation Results for Stochastic Knapsack Problems. SODA 2011: 1647-1665

Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna: Social Welfare in One-sided Matching Markets without Money. CoRR abs/1104.2964 (2011)

Sanjeev Khanna, Madhu Sudan: Delays and the Capacity of Continuous-time Channels. CoRR abs/1105.3425 (2011)

Anand Bhalgat, Tanmoy Chakraborty, Sanjeev Khanna: Mechanism Design with Risk Aversion. CoRR abs/1107.4722 (2011)

Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar, Lisa Zhang: Inapproximability of Edge-Disjoint Paths and low congestion routing on undirected graphs. Combinatorica 30(5): 485-520 (2010)

Stanislav Angelov, Sanjeev Khanna, Mirkó Visontai: Robust self-assembly of graphs. Natural Computing 9(1): 111-133 (2010)

Ashish Goel, Michael Kapralov, Sanjeev Khanna: Perfect matchings via uniform sampling in regular bipartite graphs. ACM Transactions on Algorithms 6(2) (2010)

Anand Bhalgat, Tanmoy Chakraborty, Sanjeev Khanna: Approximating pure nash equilibrium in cut, party affiliation, and satisfiability games. ACM Conference on Electronic Commerce 2010: 73-82

Zhuowei Bao, Susan B. Davidson, Sanjeev Khanna, Sudeepa Roy: An optimal labeling scheme for workflow provenance using skeleton labels. SIGMOD Conference 2010: 711-722

Ashish Goel, Michael Kapralov, Sanjeev Khanna: Perfect matchings in o(n log n) time in regular bipartite graphs. STOC 2010: 39-46

Patrick Briest, Parinya Chalermsook, Sanjeev Khanna, Bundit Laekhanukit, Danupon Nanongkai: Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing. WINE 2010: 444-454

Ashish Goel, Michael Kapralov, Sanjeev Khanna: Graph Sparsification via Refinement Sampling. CoRR abs/1004.4915 (2010)

Susan B. Davidson, Sanjeev Khanna, Debmalya Panigrahi, Sudeepa Roy: Preserving Module Privacy in Workflow Provenance. CoRR abs/1005.5543 (2010)

Deeparnab Chakrabarty, Chandra Chekuri, Sanjeev Khanna, Nitish Korula: Approximability of Capacitated Network Design. CoRR abs/1009.5734 (2010)

Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna: Optimal Lower Bounds for Universal and Differentially Private Steiner Tree and TSP. CoRR abs/1011.3770 (2010)

Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd: A Note on Multiflows and Treewidth. Algorithmica 54(3): 400-412 (2009)

Stanislav Angelov, Sanjeev Khanna, Keshav Kunal: The Network as a Storage Device: Dynamic Routing with Bounded Buffers. Algorithmica 55(1): 71-94 (2009)

Julia Chuzhoy, Sanjeev Khanna: Polynomial flow-cut gaps and hardness of directed cut problems. J. ACM 56(2) (2009)

Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd: Edge-Disjoint Paths in Planar Graphs with Constant Congestion. SIAM J. Comput. 39(1): 281-301 (2009)

Leana Golubchik, Sanjeev Khanna, Samir Khuller, Ramakrishna Thurimella, An Zhu: Approximation algorithms for data placement on parallel disks. ACM Transactions on Algorithms 5(4) (2009)

Deeparnab Chakrabarty, Julia Chuzhoy, Sanjeev Khanna: On Allocating Goods to Maximize Fairness. FOCS 2009: 107-116

Julia Chuzhoy, Sanjeev Khanna: An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design. FOCS 2009: 437-441

Tanmoy Chakraborty, Zhiyi Huang, Sanjeev Khanna: Dynamic and Non-uniform Pricing Strategies for Revenue Maximization. FOCS 2009: 495-504

Zhuowei Bao, Sarah Cohen Boulakia, Susan B. Davidson, Anat Eyal, Sanjeev Khanna: Differencing Provenance in Scientific Workflows. ICDE 2009: 808-819

Olivier Biton, Susan B. Davidson, Sanjeev Khanna, Sudeepa Roy: Optimizing user views for workflows. ICDT 2009: 310-323

Tanmoy Chakraborty, Sanjeev Khanna: Nash Dynamics in Constant Player and Bounded Jump Congestion Games. SAGT 2009: 196-207

Liming Zhao, Aline Normoyle, Sanjeev Khanna, Alla Safonova: Automatic construction of a minimum size motion graph. Symposium on Computer Animation 2009: 27-35

Tanmoy Chakraborty, Michael Kearns, Sanjeev Khanna: Network bargaining: algorithms and structural results. ACM Conference on Electronic Commerce 2009: 159-168

Ashish Goel, Michael Kapralov, Sanjeev Khanna: Perfect matchings via uniform sampling in regular bipartite graphs. SODA 2009: 11-17

Ashish Goel, Sanjeev Khanna, Brad Null: The ratio index for budgeted learning, with applications. SODA 2009: 18-27

Anand Bhalgat, Tanmoy Chakraborty, Sanjeev Khanna: Nash Dynamics in Congestion Games with Similar Resources. WINE 2009: 362-373

Deeparnab Chakrabarty, Julia Chuzhoy, Sanjeev Khanna: On Allocating Goods to Maximize Fairness. CoRR abs/0901.0205 (2009)

Ashish Goel, Sanjeev Khanna: Perfect Matchings in Õ(n^1.5) Time in Regular Bipartite Graphs. CoRR abs/0902.1617 (2009)

Tanmoy Chakraborty, Zhiyi Huang, Sanjeev Khanna: Dynamic and Non-Uniform Pricing Strategies for Revenue Maximization. CoRR abs/0905.3191 (2009)

Ashish Goel, Michael Kapralov, Sanjeev Khanna: Perfect Matchings in O(n \log n) Time in Regular Bipartite Graphs. CoRR abs/0909.3346 (2009)

Patrick Briest, Sanjeev Khanna: Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing. CoRR abs/0910.0110 (2009)

Stanislav Angelov, Sanjeev Khanna, Mirkó Visontai: On the complexity of graph self-assembly in accretive systems. Natural Computing 7(2): 183-201 (2008)

Stanislav Angelov, Sanjeev Khanna, Mirkó Visontai: Robust Self-assembly of Graphs. DNA 2008: 127-143

Julia Chuzhoy, Sanjeev Khanna: Algorithms for Single-Source Vertex Connectivity. FOCS 2008: 105-114

Sampath Kannan, Sanjeev Khanna, Sudeepa Roy: STCON in Directed Unique-Path Graphs. FSTTCS 2008: 256-267

Chandra Chekuri, Sanjeev Khanna: Algorithms for 2-Route Cut Problems. ICALP (1) 2008: 472-484

Sanjeev Khanna, Santosh S. Venkatesh, Omid Fatemieh, Fariba Khan, Carl A. Gunter: Adaptive SelectiveVerification. INFOCOM 2008: 529-537

Ashish Goel, Sanjeev Khanna: On the Network Coding Advantage for Wireless Multicast in Euclidean Space. IPSN 2008: 64-69

Tanmoy Chakraborty, Julia Chuzhoy, Sanjeev Khanna: Network design for vertex connectivity. STOC 2008: 167-176

Ashish Goel, Sanjeev Khanna, Brad Null: The Ratio Index for Budgeted Learning, with Applications. CoRR abs/0810.0558 (2008)

Ashish Goel, Michael Kapralov, Sanjeev Khanna: Perfect Matchings via Uniform Sampling in Regular Bipartite Graphs. CoRR abs/0811.2457 (2008)

Julia Chuzhoy, Sanjeev Khanna: An O(k³log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design. CoRR abs/0812.4442 (2008)

Stanislav Angelov, Boulos Harb, Sampath Kannan, Sanjeev Khanna, Junhyong Kim: Efficient Enumeration of Phylogenetically Informative Substrings. Journal of Computational Biology 14(6): 701-723 (2007)

Chandra Chekuri, Sanjeev Khanna: Edge-disjoint paths revisited. ACM Transactions on Algorithms 3(4) (2007)

Sanjeev Khanna, Keshav Kunal, Benjamin C. Pierce: A Formal Investigation of. FSTTCS 2007: 485-496

Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar: Hardness of routing with congestion in directed graphs. STOC 2007: 165-178

Julia Chuzhoy, Sanjeev Khanna: Polynomial flow-cut gaps and hardness of directed cut problems. STOC 2007: 179-188

Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar, Lisa Zhang: Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs. Electronic Colloquium on Computational Complexity (ECCC) 14(113) (2007)

Volkan Isler, Sampath Kannan, Sanjeev Khanna: Randomized Pursuit-Evasion with Local Visibility. SIAM J. Discrete Math. 20(1): 26-41 (2006)

Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd: An O(sqrt(n)) Approximation and Integrality Gap for Disjoint Paths and Unsplittable Flow. Theory of Computing 2(1): 137-146 (2006)

Stanislav Angelov, Sanjeev Khanna, Mirkó Visontai: On the Complexity of Graph Self-assembly in Accretive Systems. DNA 2006: 95-110

Stanislav Angelov, Boulos Harb, Sampath Kannan, Sanjeev Khanna, Junhyong Kim: Efficient Enumeration of Phylogenetically Informative Substrings. RECOMB 2006: 248-264

Julia Chuzhoy, Sanjeev Khanna: Hardness of cut problems in directed graphs. STOC 2006: 527-536

Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd: Edge-disjoint paths in Planar graphs with constant congestion. STOC 2006: 757-766

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

Julia Chuzhoy, Sanjeev Khanna: Hardness of Directed Routing with Congestion. Electronic Colloquium on Computational Complexity (ECCC) 13(109) (2006)

Volkan Isler, Sanjeev Khanna, John R. Spletzer, Camillo J. Taylor: Target tracking with distributed sensors: The focus of attention problem. Computer Vision and Image Understanding 100(1-2): 225-247 (2005)

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)

Chandra Chekuri, Sanjeev Khanna: A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem. SIAM J. Comput. 35(3): 713-728 (2005)

Volkan Isler, Sampath Kannan, Sanjeev Khanna: Randomized pursuit-evasion in a polygonal environment. IEEE Transactions on Robotics 21(5): 875-884 (2005)

Stanislav Angelov, Sanjeev Khanna, Keshav Kunal: The Network as a Storage Device: Dynamic Routing with Bounded Buffers. APPROX-RANDOM 2005: 1-13

Matthew Andrews, Julia Chuzhoy, Sanjeev Khanna, Lisa Zhang: Hardness of the Undirected Edge-Disjoint Paths Problem with Congestion. FOCS 2005: 226-244

Nikhil Bansal, Moses Charikar, Sanjeev Khanna, Joseph Naor: Approximating the average response time in broadcast scheduling. SODA 2005: 215-221

Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd: Multicommodity flow, well-linked terminals, and routing problems. STOC 2005: 183-192

Sanjeev Khanna, Aravind Srinivasan: Special issue: 35th Annual ACM Symposium on Theory of Computing. J. Comput. Syst. Sci. 69(3): 305- (2004)

Chandra Chekuri, Sanjeev Khanna: On Multidimensional Packing Problems. SIAM J. Comput. 33(4): 837-851 (2004)

Venkatesan Guruswami, Sanjeev Khanna: On the Hardness of 4-Coloring a 3-Colorable Graph. SIAM J. Discrete Math. 18(1): 30-40 (2004)

Chandra Chekuri, Sanjeev Khanna, Joseph Naor, Leonid Zosin: A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem. SIAM J. Discrete Math. 18(3): 608-625 (2004)

Peter Buneman, Sanjeev Khanna, Keishi Tajima, Wang Chiew Tan: Archiving scientific data. ACM Trans. Database Syst. 29: 2-42 (2004)

Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd: Edge-Disjoint Paths in Planar Graphs. FOCS 2004: 71-80

Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Joseph Naor: Machine Minimization for Scheduling Jobs with Interval Constraints. FOCS 2004: 81-90

Andreas Björklund, Thore Husfeldt, Sanjeev Khanna: Approximating Longest Directed Paths and Cycles. ICALP 2004: 222-233

Carl A. Gunter, Sanjeev Khanna, Kaijun Tan, Santosh S. Venkatesh: DoS Protection for Reliably Authenticated Broadcast. NDSS 2004

Michael Greenwald, Sanjeev Khanna: Power-Conserving Computation of Order-Statistics over Sensor Networks. PODS 2004: 275-285

Tugkan Batu, Sampath Kannan, Sanjeev Khanna, Andrew McGregor: Reconstructing strings from random traces. SODA 2004: 910-918

Volkan Isler, Sampath Kannan, Sanjeev Khanna: Randomized pursuit-evasion with limited visibility. SODA 2004: 1060-1069

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

Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd: The all-or-nothing multicommodity flow problem. STOC 2004: 156-165

Chandra Chekuri, Ashish Goel, Sanjeev Khanna, Amit Kumar: Multi-processor scheduling to minimize flow time with epsilon resource augmentation. STOC 2004: 363-372

Stanislav Angelov, Sanjeev Khanna, Li Li, Fernando Pereira: ATDD: An Algorithmic Tool for Domain Discovery in Protein Sequences. WABI 2004: 206-217

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

Klaus Jansen, Sanjeev Khanna, José D. P. Rolim, Dana Ron (Eds.): 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

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)

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)

Volkan Isler, John R. Spletzer, Sanjeev Khanna, Camillo J. Taylor: Target tracking with distributed sensors: the focus of attention problem. IROS 2003: 792-798

Sampath Kannan, Sanjeev Khanna: Selection with monotone comparison cost. SODA 2003: 10-17

Chandra Chekuri, Sanjeev Khanna: Edge disjoint paths revisited. SODA 2003: 628-637

Andreas Björklund, Thore Husfeldt, Sanjeev Khanna: Approximating Longest Directed Path. Electronic Colloquium on Computational Complexity (ECCC) 10(032) (2003)

Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Joseph Naor: Asymmetric k-center is log^*n-hard to Approximate. Electronic Colloquium on Computational Complexity (ECCC)(038) (2003)

Sanjeev Khanna: Guest Editor's Foreword. J. Comput. Syst. Sci. 64(4): 749 (2002)

Sanjeev Khanna, Joseph Naor, Danny Raz: Control Message Aggregation in Group Communication Protocols. ICALP 2002: 135-146

Peter Buneman, Sanjeev Khanna, Wang Chiew Tan: On Propagation of Deletions and Annotations Through Views. PODS 2002: 150-158

Peter Buneman, Sanjeev Khanna, Keishi Tajima, Wang Chiew Tan: Archiving scientific data. SIGMOD Conference 2002: 1-12

Chandra Chekuri, Sanjeev Khanna: Approximation schemes for preemptive weighted flow time. STOC 2002: 297-305

Chandra Chekuri, Sanjeev Khanna: A PTAS for Minimizing Weighted Completion Time on Uniformly Related Machines. ICALP 2001: 848-861

Peter Buneman, Sanjeev Khanna, Wang Chiew Tan: Why and Where: A Characterization of Data Provenance. ICDT 2001: 316-330

Sanjeev Khanna, Wang Chiew Tan: On Computing Functions with Uncertainty. PODS 2001

Maria Adamou, Sanjeev Khanna, Insup Lee, Insik Shin, Shiyu Zhou: Fair Real-Time Traffic Scheduling over a Wireless LA. RTSS 2001: 279-288

Michael Greenwald, Sanjeev Khanna: Space-Efficient Online Computation of Quantile Summaries. SIGMOD Conference 2001: 58-66

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

Chandra Chekuri, Sanjeev Khanna, Joseph Naor: A deterministic algorithm for the cost-distance problem. SODA 2001: 232-233

Chandra Chekuri, Sanjeev Khanna, An Zhu: Algorithms for minimizing weighted flow time. STOC 2001: 84-93

Chandra Chekuri, Sanjeev Khanna: Approximation Schemes for Preemptive Weighted Flow Time. Electronic Colloquium on Computational Complexity (ECCC) 8(065) (2001)

Sanjeev Khanna, Nathan Linial, Shmuel Safra: On the Hardness of Approximating the Chromatic Number. Combinatorica 20(3): 393-415 (2000)

Sanjeev Khanna, Shiyu Zhou: On Indexed Data Broadcast. J. Comput. Syst. Sci. 60(3): 575-591 (2000)

Sanjeev Khanna, Vincenzo Liberatore: On Broadcast Disk Paging. SIAM J. Comput. 29(5): 1683-1702 (2000)

Sanjeev Khanna, Madhu Sudan, Luca Trevisan, David P. Williamson: The Approximability of Constraint Satisfaction Problems. SIAM J. Comput. 30(6): 1863-1920 (2000)

Venkatesan Guruswami, Sanjeev Khanna: On the Hardness of 4-Coloring a 3-Colorable Graph. IEEE Conference on Computational Complexity 2000: 188-197

Peter Buneman, Sanjeev Khanna, Wang Chiew Tan: Data Provenance: Some Basic Issues. FSTTCS 2000: 87-93

Chandra Chekuri, Sanjeev Khanna: A PTAS for the multiple knapsack problem. SODA 2000: 213-222

Leana Golubchik, Sanjeev Khanna, Samir Khuller, Ramakrishna Thurimella, An Zhu: Approximation algorithms for data placement on parallel disks. SODA 2000: 223-232

Sanjeev Khanna, Francis Zane: Watermarking maps: hiding information in structured data. SODA 2000: 596-605

Sanjeev Khanna, Joseph Naor, F. Bruce Shepherd: Directed network design with orientation constraints. SODA 2000: 663-671

Venkatesan Guruswami, Sanjeev Khanna: On the Hardness of 4-coloring a 3-colorable Graph. Electronic Colloquium on Computational Complexity (ECCC) 7(73) (2000)

Alok Aggarwal, Don Coppersmith, Sanjeev Khanna, Rajeev Motwani, Baruch Schieber: The Angular-Metric Traveling Salesman Problem. SIAM J. Comput. 29(3): 697-711 (1999)

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

Yevgeniy Dodis, Sanjeev Khanna: Space Time Tradeoffs for Graph Properties. ICALP 1999: 291-300

Matthew Andrews, Sanjeev Khanna, Krishnan Kumaran: Integrated Scheduling of Unicast and Multicast Traffic in an Input-Queued Switch. INFOCOM 1999: 1144-1151

Susanne Albers, Sanjeev Arora, Sanjeev Khanna: Page Replacement for General Caching Problems. SODA 1999: 31-40

Chandra Chekuri, Sanjeev Khanna: On Multi-Dimensional Packing Problems. SODA 1999: 185-194

Yevgeniy Dodis, Venkatesan Guruswami, Sanjeev Khanna: The 2-Catalog Segmentation Problem. SODA 1999: 897-898

Micah Adler, Sanjeev Khanna, Rajmohan Rajaraman, Adi Rosén: Time-Constrained Scheduling of Weighted Packets on Trees and Meshes. SPAA 1999: 1-12

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

Yevgeniy Dodis, Sanjeev Khanna: Design Networks with Bounded Pairwise Distance. STOC 1999: 750-759

Sanjeev Khanna, Rajeev Motwani, Randall H. Wilson: On Certificates and Lookahead in Dynamic Graph Problems. Algorithmica 21(4): 377-394 (1998)

Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani: On Syntactic versus Computational Views of Approximability. SIAM J. Comput. 28(1): 164-191 (1998)

Krishnan Kumaran, Sanjeev Khanna: On Wireless Spectrum Estimation and Generalized Graph Coloring. INFOCOM 1998: 1273-1283

Sanjeev Khanna, S. Muthukrishnan, Mike Paterson: On Approximating Rectangle Tiling and Packing. SODA 1998: 384-393

Sanjeev Khanna, Shiyu Zhou: On Indexed Data Broadcast. STOC 1998: 463-472

Sanjeev Khanna, Vincenzo Liberatore: On Broadcast Disk Paging. STOC 1998: 634-643

Viggo Kann, Sanjeev Khanna, Jens Lagergren, Alessandro Panconesi: On the Hardness of Approximating Max k-Cut and its Dual. Chicago J. Theor. Comput. Sci. 1997 (1997)

Sanjeev Khanna, W. Kent Fuchs: A Graph Partitioning Approach to Sequential Diagnosis. IEEE Trans. Computers 46(1): 39-47 (1997)

Sanjeev Khanna, Madhu Sudan, Luca Trevisan: Constraint Satisfaction: The Approximability of Minimization Problems. IEEE Conference on Computational Complexity 1997: 282-296

Sanjeev Khanna, S. Muthukrishnan, Steven Skiena: Efficient Array Partitioning. ICALP 1997: 616-626

Alok Aggarwal, Don Coppersmith, Sanjeev Khanna, Rajeev Motwani, Baruch Schieber: The Angular-Metric Traveling Salesman Problem. SODA 1997: 221-229

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

Viggo Kann, Sanjeev Khanna, Jens Lagergren, Alessandro Panconesi: On the Hardness of Approximating Max k-Cut and Its Dual. ISTCS 1996: 61-67

Sanjeev Khanna, Rajeev Motwani, Randall H. Wilson: On Certificates and Lookahead in Dynamic Graph Problems. SODA 1996: 222-231

Sanjeev Khanna, Rajeev Motwani: Towards a Syntactic Characterization of PTAS. STOC 1996: 329-337

Sanjeev Khanna, Madhu Sudan: The Optimization Complexity of Constraint Satisfaction Problems. Electronic Colloquium on Computational Complexity (ECCC) 3(28) (1996)

Sanjeev Khanna, Madhu Sudan, David P. Williamson: A Complete Characterization of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction. Electronic Colloquium on Computational Complexity (ECCC) 3(62) (1996)

Sanjeev Khanna, Madhu Sudan, Luca Trevisan: Constraint satisfaction: The approximability of minimization problems. Electronic Colloquium on Computational Complexity (ECCC) 3(64) (1996)

Sanjeev Khanna, W. Kent Fuchs: A Linear Time Algorithm for Sequential Diagnosis in Hypercubes. J. Parallel Distrib. Comput. 26(1): 48-53 (1995)

Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani: On Syntactic versus Computational Views of Approximability. Electronic Colloquium on Computational Complexity (ECCC) 2(23) (1995)

Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani: On Syntactic versus Computational Views of Approximability. FOCS 1994: 819-830

Sanjeev Khanna, Nathan Linial, Shmuel Safra: On the Hardness of Approximating the Chromatic Number. ISTCS 1993: 250-260

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

Kurt Maly, Frank Paterra, C. Michael Overstreet, Ravi Mukkamala, Sanjeev Khanna: Concurrent Use of Parallel Communication to Enable Remote Visualization. ICCI 1992: 449-452

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

Sanjeev Khanna: Logic Programming for Software Verification and Testing. Comput. J. 34(4): 350-357 (1991)

Sanjeev Khanna: Logic Programming for Software Testing. ICCI 1990: 225-234