Sanjeev Khanna

Bing Citeseer DBLP Google Google Scholar Kosmix Wikipedia Yahoo!
Loading Google Thumbnails...
2012
163On the communication and streaming complexity of maximum bipartite matching. Ashish Goel, Michael Kapralov, Sanjeev Khanna. SODA 2012, 468-485. Web SearchBibTeXDownload
2011
162Social Welfare in One-Sided Matching Markets without Money. Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna. APPROX-RANDOM 2011, 87-98. Web SearchBibTeXDownload
161Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs. Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna. APPROX-RANDOM 2011, 75-86. Web SearchBibTeXDownload
160Enabling Privacy in Provenance-Aware Workflow Systems. Susan B. Davidson, Sanjeev Khanna, Val Tannen, Sudeepa Roy, Yi Chen, Tova Milo, Julia Stoyanovich. CIDR 2011, 215-218. Web SearchBibTeXDownload
159Social Welfare in One-sided Matching Markets without Money. Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna. CoRR (abs/1104.2964) (2011). Web SearchBibTeXDownload
158Mechanism Design with Risk Aversion. Anand Bhalgat, Tanmoy Chakraborty, Sanjeev Khanna. CoRR (abs/1107.4722) (2011). Web SearchBibTeXDownload
157Delays and the Capacity of Continuous-time Channels. Sanjeev Khanna, Madhu Sudan. CoRR (abs/1105.3425) (2011). Web SearchBibTeXDownload
156Algorithms for the Generalized Sorting Problem. Zhiyi Huang, Sampath Kannan, Sanjeev Khanna. FOCS 2011, 738-747. Web SearchBibTeXDownload
155Delays and the Capacity of Continuous-Time Channels. Sanjeev Khanna, Madhu Sudan. FOCS 2011, 758-767. Web SearchBibTeXDownload
154On provenance and privacy. Susan B. Davidson, Sanjeev Khanna, Sudeepa Roy, Julia Stoyanovich, Val Tannen, Yi Chen. ICDT 2011, 3-10. Web SearchBibTeXDownload
153Compression without a common prior: an information-theoretic justification for ambiguity in language. Brendan Juba, Adam Tauman Kalai, Sanjeev Khanna, Madhu Sudan. ICS 2011, 79-86. Web SearchBibTeXDownload
152Approximability of Capacitated Network Design. Deeparnab Chakrabarty, Chandra Chekuri, Sanjeev Khanna, Nitish Korula. IPCO 2011, 78-91. Web SearchBibTeXDownload
151Provenance views for module privacy. Susan B. Davidson, Sanjeev Khanna, Tova Milo, Debmalya Panigrahi, Sudeepa Roy. PODS 2011, 175-186. Web SearchBibTeXDownload
150Queries with Difference on Probabilistic Databases. Sanjeev Khanna, Sudeepa Roy, Val Tannen. PVLDB (4): 1051-1062 (2011). Web SearchBibTeXDownload
149Improved Approximation Results for Stochastic Knapsack Problems. Anand Bhalgat, Ashish Goel, Sanjeev Khanna. SODA 2011, 1647-1665. Web SearchBibTeXDownload
2010
148Approximating pure nash equilibrium in cut, party affiliation, and satisfiability games. Anand Bhalgat, Tanmoy Chakraborty, Sanjeev Khanna. ACM Conference on Electronic Commerce 2010, 73-82. Web SearchBibTeXDownload
147Perfect matchings via uniform sampling in regular bipartite graphs. Ashish Goel, Michael Kapralov, Sanjeev Khanna. ACM Transactions on Algorithms (6) (2010). Web SearchBibTeXDownload
146Inapproximability of Edge-Disjoint Paths and low congestion routing on undirected graphs. Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar, Lisa Zhang. Combinatorica (30): 485-520 (2010). Web SearchBibTeXDownload
145Approximability of Capacitated Network Design. Deeparnab Chakrabarty, Chandra Chekuri, Sanjeev Khanna, Nitish Korula. CoRR (abs/1009.5734) (2010). Web SearchBibTeXDownload
144Optimal Lower Bounds for Universal and Differentially Private Steiner Tree and TSP. Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna. CoRR (abs/1011.3770) (2010). Web SearchBibTeXDownload
143Preserving Module Privacy in Workflow Provenance. Susan B. Davidson, Sanjeev Khanna, Debmalya Panigrahi, Sudeepa Roy. CoRR (abs/1005.5543) (2010). Web SearchBibTeXDownload
142Graph Sparsification via Refinement Sampling. Ashish Goel, Michael Kapralov, Sanjeev Khanna. CoRR (abs/1004.4915) (2010). Web SearchBibTeXDownload
141Robust self-assembly of graphs. Stanislav Angelov, Sanjeev Khanna, Mirkó Visontai. Natural Computing (9): 111-133 (2010). Web SearchBibTeXDownload
140An optimal labeling scheme for workflow provenance using skeleton labels. Zhuowei Bao, Susan B. Davidson, Sanjeev Khanna, Sudeepa Roy. SIGMOD Conference 2010, 711-722. Web SearchBibTeXDownload
139Perfect matchings in o(n log n) time in regular bipartite graphs. Ashish Goel, Michael Kapralov, Sanjeev Khanna. STOC 2010, 39-46. Web SearchBibTeXDownload
138Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing. Patrick Briest, Parinya Chalermsook, Sanjeev Khanna, Bundit Laekhanukit, Danupon Nanongkai. WINE 2010, 444-454. Web SearchBibTeXDownload
2009
137Network bargaining: algorithms and structural results. Tanmoy Chakraborty, Michael Kearns, Sanjeev Khanna. ACM Conference on Electronic Commerce 2009, 159-168. Web SearchBibTeXDownload
136Approximation algorithms for data placement on parallel disks. Leana Golubchik, Sanjeev Khanna, Samir Khuller, Ramakrishna Thurimella, An Zhu. ACM Transactions on Algorithms (5) (2009). Web SearchBibTeXDownload
135The Network as a Storage Device: Dynamic Routing with Bounded Buffers. Stanislav Angelov, Sanjeev Khanna, Keshav Kunal. Algorithmica (55): 71-94 (2009). Web SearchBibTeXDownload
134A Note on Multiflows and Treewidth. Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd. Algorithmica (54): 400-412 (2009). Web SearchBibTeXDownload
133Perfect Matchings in O(n \\log n) Time in Regular Bipartite Graphs. Ashish Goel, Michael Kapralov, Sanjeev Khanna. CoRR (abs/0909.3346) (2009). Web SearchBibTeXDownload
132On Allocating Goods to Maximize Fairness. Deeparnab Chakrabarty, Julia Chuzhoy, Sanjeev Khanna. CoRR (abs/0901.0205) (2009). Web SearchBibTeXDownload
131Dynamic and Non-Uniform Pricing Strategies for Revenue Maximization. Tanmoy Chakraborty, Zhiyi Huang, Sanjeev Khanna. CoRR (abs/0905.3191) (2009). Web SearchBibTeXDownload
130Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing. Patrick Briest, Parinya Chalermsook, Sanjeev Khanna, Bundit Laekhanukit, Danupon Nanongkai. CoRR (abs/0910.0110) (2009). Web SearchBibTeXDownload
129Perfect Matchings in Õ(n1.5) Time in Regular Bipartite Graphs. Ashish Goel, Sanjeev Khanna. CoRR (abs/0902.1617) (2009). Web SearchBibTeXDownload
128Dynamic and Non-uniform Pricing Strategies for Revenue Maximization. Tanmoy Chakraborty, Zhiyi Huang, Sanjeev Khanna. FOCS 2009, 495-504. Web SearchBibTeXDownload
127An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design. Julia Chuzhoy, Sanjeev Khanna. FOCS 2009, 437-441. Web SearchBibTeXDownload
126Differencing Provenance in Scientific Workflows. Zhuowei Bao, Sarah Cohen Boulakia, Susan B. Davidson, Anat Eyal, Sanjeev Khanna. ICDE 2009, 808-819. Cited by 2Web SearchBibTeXDownload
125Optimizing user views for workflows. Olivier Biton, Susan B. Davidson, Sanjeev Khanna, Sudeepa Roy. ICDT 2009, 310-323. Cited by 3Web SearchBibTeXDownload
124Polynomial flow-cut gaps and hardness of directed cut problems. Julia Chuzhoy, Sanjeev Khanna. J. ACM (56) (2009). Web SearchBibTeXDownload
123Nash Dynamics in Constant Player and Bounded Jump Congestion Games. Tanmoy Chakraborty, Sanjeev Khanna. SAGT 2009, 196-207. Web SearchBibTeXDownload
122Edge-Disjoint Paths in Planar Graphs with Constant Congestion. Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd. SIAM J. Comput. (39): 281-301 (2009). Web SearchBibTeXDownload
121The ratio index for budgeted learning, with applications. Ashish Goel, Sanjeev Khanna, Brad Null. SODA 2009, 18-27. Web SearchBibTeXDownload
120Perfect matchings via uniform sampling in regular bipartite graphs. Ashish Goel, Michael Kapralov, Sanjeev Khanna. SODA 2009, 11-17. Web SearchBibTeXDownload
119Automatic construction of a minimum size motion graph. Liming Zhao, Aline Normoyle, Sanjeev Khanna, Alla Safonova. Symposium on Computer Animation 2009, 27-35. Web SearchBibTeXDownload
118Nash Dynamics in Congestion Games with Similar Resources. Anand Bhalgat, Tanmoy Chakraborty, Sanjeev Khanna. WINE 2009, 362-373. Web SearchBibTeXDownload
2008
117Perfect Matchings via Uniform Sampling in Regular Bipartite Graphs. Ashish Goel, Michael Kapralov, Sanjeev Khanna. CoRR (abs/0811.2457) (2008). Web SearchBibTeXDownload
116An O(k3log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design. Julia Chuzhoy, Sanjeev Khanna. CoRR (abs/0812.4442) (2008). Web SearchBibTeXDownload
115The Ratio Index for Budgeted Learning, with Applications. Ashish Goel, Sanjeev Khanna, Brad Null. CoRR (abs/0810.0558) (2008). Web SearchBibTeXDownload
114Robust Self-assembly of Graphs. Stanislav Angelov, Sanjeev Khanna, Mirkó Visontai. DNA 2008, 127-143. Web SearchBibTeXDownload
113Algorithms for Single-Source Vertex Connectivity. Julia Chuzhoy, Sanjeev Khanna. FOCS 2008, 105-114. Web SearchBibTeXDownload
112STCON in Directed Unique-Path Graphs. Sampath Kannan, Sanjeev Khanna, Sudeepa Roy. FSTTCS 2008, 256-267. Web SearchBibTeXDownload
111Algorithms for 2-Route Cut Problems. Chandra Chekuri, Sanjeev Khanna. ICALP (1) 2008, 472-484. Web SearchBibTeXDownload
110Adaptive SelectiveVerification. Sanjeev Khanna, Santosh S. Venkatesh, Omid Fatemieh, Fariba Khan, Carl A. Gunter. INFOCOM 2008, 529-537. Web SearchBibTeXDownload
109On the Network Coding Advantage for Wireless Multicast in Euclidean Space. Ashish Goel, Sanjeev Khanna. IPSN 2008, 64-69. Web SearchBibTeXDownload
108On the complexity of graph self-assembly in accretive systems. Stanislav Angelov, Sanjeev Khanna, Mirkó Visontai. Natural Computing (7): 183-201 (2008). Web SearchBibTeXDownload
107Network design for vertex connectivity. Tanmoy Chakraborty, Julia Chuzhoy, Sanjeev Khanna. STOC 2008, 167-176. Web SearchBibTeXDownload
2007
106Edge-disjoint paths revisited. Chandra Chekuri, Sanjeev Khanna. ACM Transactions on Algorithms (3) (2007). Web SearchBibTeXDownload
105Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs. Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar, Lisa Zhang. Electronic Colloquium on Computational Complexity (ECCC) (14) (2007). Web SearchBibTeXDownload
104A Formal Investigation of. Sanjeev Khanna, Keshav Kunal, Benjamin C. Pierce. FSTTCS 2007, 485-496. Web SearchBibTeXDownload
103Efficient Enumeration of Phylogenetically Informative Substrings. Stanislav Angelov, Boulos Harb, Sampath Kannan, Sanjeev Khanna, Junhyong Kim. Journal of Computational Biology (14): 701-723 (2007). Web SearchBibTeXDownload
102Hardness of routing with congestion in directed graphs. Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar. STOC 2007, 165-178. Web SearchBibTeXDownload
101Polynomial flow-cut gaps and hardness of directed cut problems. Julia Chuzhoy, Sanjeev Khanna. STOC 2007, 179-188. Web SearchBibTeXDownload
2006
100Agreeing to Agree: Conflict Resolution for Optimistically Replicated Data. Michael B. Greenwald, Sanjeev Khanna, Keshav Kunal, Benjamin C. Pierce, Alan Schmitt. DISC 2006, 269-283. Web SearchBibTeXDownload
99On the Complexity of Graph Self-assembly in Accretive Systems. Stanislav Angelov, Sanjeev Khanna, Mirkó Visontai. DNA 2006, 95-110. Web SearchBibTeXDownload
98Hardness of Directed Routing with Congestion. Julia Chuzhoy, Sanjeev Khanna. Electronic Colloquium on Computational Complexity (ECCC) (13) (2006). Web SearchBibTeXDownload
97Efficient Enumeration of Phylogenetically Informative Substrings. Stanislav Angelov, Boulos Harb, Sampath Kannan, Sanjeev Khanna, Junhyong Kim. RECOMB 2006, 248-264. Web SearchBibTeXDownload
96Randomized Pursuit-Evasion with Local Visibility. Volkan Isler, Sampath Kannan, Sanjeev Khanna. SIAM J. Discrete Math. (20): 26-41 (2006). Web SearchBibTeXDownload
95Hardness of cut problems in directed graphs. Julia Chuzhoy, Sanjeev Khanna. STOC 2006, 527-536. Web SearchBibTeXDownload
94Edge-disjoint paths in Planar graphs with constant congestion. Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd. STOC 2006, 757-766. Web SearchBibTeXDownload
93An O(sqrt(n)) Approximation and Integrality Gap for Disjoint Paths and Unsplittable Flow. Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd. Theory of Computing (2): 137-146 (2006). Web SearchBibTeXDownload
2005
92The Network as a Storage Device: Dynamic Routing with Bounded Buffers. Stanislav Angelov, Sanjeev Khanna, Keshav Kunal. APPROX-RANDOM 2005, 1-13. Web SearchBibTeXDownload
91Target tracking with distributed sensors: The focus of attention problem. Volkan Isler, Sanjeev Khanna, John R. Spletzer, Camillo J. Taylor. Computer Vision and Image Understanding (100): 225-247 (2005). Web SearchBibTeXDownload
90Hardness of the Undirected Edge-Disjoint Paths Problem with Congestion. Matthew Andrews, Julia Chuzhoy, Sanjeev Khanna, Lisa Zhang. FOCS 2005, 226-244. Web SearchBibTeXDownload
89Randomized pursuit-evasion in a polygonal environment. Volkan Isler, Sampath Kannan, Sanjeev Khanna. IEEE Transactions on Robotics (21): 875-884 (2005). Web SearchBibTeXDownload
88Asymmetric k-center is log* n-hard to approximate. Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Robert Krauthgamer, Joseph Naor. J. ACM (52): 538-551 (2005). Cited by 27Web SearchBibTeXDownload
87A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem. Chandra Chekuri, Sanjeev Khanna. SIAM J. Comput. (35): 713-728 (2005). Web SearchBibTeXDownload
86Approximating the average response time in broadcast scheduling. Nikhil Bansal, Moses Charikar, Sanjeev Khanna, Joseph Naor. SODA 2005, 215-221. Web SearchBibTeXDownload
85Multicommodity flow, well-linked terminals, and routing problems. Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd. STOC 2005, 183-192. Web SearchBibTeXDownload
2004
84Archiving scientific data. Peter Buneman, Sanjeev Khanna, Keishi Tajima, Wang Chiew Tan. ACM Trans. Database Syst. (29): 2-42 (2004). Cited by 163Web SearchBibTeXDownload
83Machine Minimization for Scheduling Jobs with Interval Constraints. Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Joseph Naor. FOCS 2004, 81-90. Cited by 8Web SearchBibTeXDownload
82Edge-Disjoint Paths in Planar Graphs. Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd. FOCS 2004, 71-80. Web SearchBibTeXDownload
81Approximating Longest Directed Paths and Cycles. Andreas Björklund, Thore Husfeldt, Sanjeev Khanna. ICALP 2004, 222-233. Web SearchBibTeXDownload
80Special issue: 35th Annual ACM Symposium on Theory of Computing. Sanjeev Khanna, Aravind Srinivasan. J. Comput. Syst. Sci. (69): 305 (2004). Web SearchBibTeXDownload
79DoS Protection for Reliably Authenticated Broadcast. Carl A. Gunter, Sanjeev Khanna, Kaijun Tan, Santosh S. Venkatesh. NDSS 2004. Cited by 25Web SearchBibTeXDownload
78Power-Conserving Computation of Order-Statistics over Sensor Networks. Michael Greenwald, Sanjeev Khanna. PODS 2004, 275-285. Web SearchBibTeXDownload
77On Multidimensional Packing Problems. Chandra Chekuri, Sanjeev Khanna. SIAM J. Comput. (33): 837-851 (2004). Web SearchBibTeXDownload
76A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem. Chandra Chekuri, Sanjeev Khanna, Joseph Naor, Leonid Zosin. SIAM J. Discrete Math. (18): 608-625 (2004). Web SearchBibTeXDownload
75On the Hardness of 4-Coloring a 3-Colorable Graph. Venkatesan Guruswami, Sanjeev Khanna. SIAM J. Discrete Math. (18): 30-40 (2004). Web SearchBibTeXDownload
74Randomized pursuit-evasion with limited visibility. Volkan Isler, Sampath Kannan, Sanjeev Khanna. SODA 2004, 1060-1069. Web SearchBibTeXDownload
73Reconstructing strings from random traces. Tugkan Batu, Sampath Kannan, Sanjeev Khanna, Andrew McGregor. SODA 2004, 910-918. Web SearchBibTeXDownload
72Multi-processor scheduling to minimize flow time with epsilon resource augmentation. Chandra Chekuri, Ashish Goel, Sanjeev Khanna, Amit Kumar. STOC 2004, 363-372. Web SearchBibTeXDownload
71Asymmetric k-center is log* n-hard to approximate. Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Robert Krauthgamer, Joseph Naor. STOC 2004, 21-27. Cited by 27Web SearchBibTeXDownload
70The all-or-nothing multicommodity flow problem. Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd. STOC 2004, 156-165. Web SearchBibTeXDownload
69Genome Identification and Classification by Short Oligo Arrays. Stanislav Angelov, Boulos Harb, Sampath Kannan, Sanjeev Khanna, Junhyong Kim, Li-San Wang. WABI 2004, 400-411. Web SearchBibTeXDownload
68ATDD: An Algorithmic Tool for Domain Discovery in Protein Sequences. Stanislav Angelov, Sanjeev Khanna, Li Li, Fernando Pereira. WABI 2004, 206-217. Web SearchBibTeXDownload
2003
67Time-Constrained Scheduling of Weighted Packets on Trees and Meshes. Micah Adler, Sanjeev Khanna, Rajmohan Rajaraman, Adi Rosén. Algorithmica (36): 123-152 (2003). Web SearchBibTeXDownload
66Approximating Longest Directed Path. Andreas Björklund, Thore Husfeldt, Sanjeev Khanna. Electronic Colloquium on Computational Complexity (ECCC) (10) (2003). Web SearchBibTeXDownload
65Asymmetric k-center is log*n-hard to Approximate. Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Joseph Naor. Electronic Colloquium on Computational Complexity (ECCC) 2003. Web SearchBibTeXDownload
64Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. Venkatesan Guruswami, Sanjeev Khanna, Rajmohan Rajaraman, F. Bruce Shepherd, Mihalis Yannakakis. J. Comput. Syst. Sci. (67): 473-496 (2003). Web SearchBibTeXDownload
63Edge disjoint paths revisited. Chandra Chekuri, Sanjeev Khanna. SODA 2003, 628-637. Web SearchBibTeXDownload
62Selection with monotone comparison cost. Sampath Kannan, Sanjeev Khanna. SODA 2003, 10-17. Web SearchBibTeXDownload
2002
61Control Message Aggregation in Group Communication Protocols. Sanjeev Khanna, Joseph Naor, Danny Raz. ICALP 2002, 135-146. Web SearchBibTeXDownload
60Guest Editor's Foreword. Sandip Das, Emden R. Gansner, Joe Kilian, Jon M. Kleinberg. J. Comput. Syst. Sci. (65): 1 (2002). Web SearchBibTeXDownload
59On Propagation of Deletions and Annotations Through Views. Peter Buneman, Sanjeev Khanna, Wang Chiew Tan. PODS 2002, 150-158. Cited by 98Web SearchBibTeXDownload
58Archiving scientific data. Peter Buneman, Sanjeev Khanna, Keishi Tajima, Wang Chiew Tan. SIGMOD Conference 2002, 1-12. Cited by 163Web SearchBibTeXDownload
57Approximation schemes for preemptive weighted flow time. Chandra Chekuri, Sanjeev Khanna. STOC 2002, 297-305. Web SearchBibTeXDownload
2001
56A PTAS for Minimizing Weighted Completion Time on Uniformly Related Machines. Chandra Chekuri, Sanjeev Khanna. ICALP 2001, 848-861. Web SearchBibTeXDownload
55Why and Where: A Characterization of Data Provenance. Peter Buneman, Sanjeev Khanna, Wang Chiew Tan. ICDT 2001, 316-330. Cited by 411Web SearchBibTeXDownload
54Fair Real-Time Traffic Scheduling over a Wireless LA. Maria Adamou, Sanjeev Khanna, Insup Lee, Insik Shin, Shiyu Zhou. IEEE Real-Time Systems Symposium 2001, 279-288. Web SearchBibTeXDownload
53On Computing Functions with Uncertainty. Sanjeev Khanna, Wang Chiew Tan. PODS 2001. Web SearchBibTeXDownload
52Space-Efficient Online Computation of Quantile Summaries. Michael Greenwald, Sanjeev Khanna. SIGMOD Conference 2001, 58-66. Web SearchBibTeXDownload
51Approximation algorithms for the metric labeling problem via a new linear programming formulation. Chandra Chekuri, Sanjeev Khanna, Joseph Naor, Leonid Zosin. SODA 2001, 109-118. Web SearchBibTeXDownload
50A deterministic algorithm for the cost-distance problem. Chandra Chekuri, Sanjeev Khanna, Joseph Naor. SODA 2001, 232-233. Web SearchBibTeXDownload
49Algorithms for minimizing weighted flow time. Chandra Chekuri, Sanjeev Khanna, An Zhu. STOC 2001, 84-93. Web SearchBibTeXDownload
2000
48On the Hardness of Approximating the Chromatic Number. Sanjeev Khanna, Nathan Linial, Shmuel Safra. Combinatorica (20): 393-415 (2000). Web SearchBibTeXDownload
47On the Hardness of 4-coloring a 3-colorable Graph. Venkatesan Guruswami, Sanjeev Khanna. Electronic Colloquium on Computational Complexity (ECCC) (7) (2000). Web SearchBibTeXDownload
46Data Provenance: Some Basic Issues. Peter Buneman, Sanjeev Khanna, Wang Chiew Tan. FSTTCS 2000, 87-93. Cited by 94Web SearchBibTeXDownload
45On the Hardness of 4-Coloring a 3-Colorable Graph. Venkatesan Guruswami, Sanjeev Khanna. IEEE Conference on Computational Complexity 2000, 188-197. Web SearchBibTeXDownload
44On Indexed Data Broadcast. Sanjeev Khanna, Shiyu Zhou. J. Comput. Syst. Sci. (60): 575-591 (2000). Web SearchBibTeXDownload
43The Approximability of Constraint Satisfaction Problems. Sanjeev Khanna, Madhu Sudan, Luca Trevisan, David P. Williamson. SIAM J. Comput. (30): 1863-1920 (2000). Web SearchBibTeXDownload
42On Broadcast Disk Paging. Sanjeev Khanna, Vincenzo Liberatore. SIAM J. Comput. (29): 1683-1702 (2000). Web SearchBibTeXDownload
41Watermarking maps: hiding information in structured data. Sanjeev Khanna, Francis Zane. SODA 2000, 596-605. Web SearchBibTeXDownload
40Approximation algorithms for data placement on parallel disks. Leana Golubchik, Sanjeev Khanna, Samir Khuller, Ramakrishna Thurimella, An Zhu. SODA 2000, 223-232. Web SearchBibTeXDownload
39A PTAS for the multiple knapsack problem. Chandra Chekuri, Sanjeev Khanna. SODA 2000, 213-222. Web SearchBibTeXDownload
38Directed network design with orientation constraints. Sanjeev Khanna, Joseph Naor, F. Bruce Shepherd. SODA 2000, 663-671. Web SearchBibTeXDownload
1999
37Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates. Foto N. Afrati, Evripidis Bampis, Chandra Chekuri, David R. Karger, Claire Kenyon, Sanjeev Khanna, Ioannis Milis, Maurice Queyranne, Martin Skutella, Clifford Stein, Maxim Sviridenko. FOCS 1999, 32-44. Cited by 123Web SearchBibTeXDownload
36Space Time Tradeoffs for Graph Properties. Yevgeniy Dodis, Sanjeev Khanna. ICALP 1999, 291-300. Web SearchBibTeXDownload
35Integrated Scheduling of Unicast and Multicast Traffic in an Input-Queued Switch. Matthew Andrews, Sanjeev Khanna, Krishnan Kumaran. INFOCOM 1999, 1144-1151. Web SearchBibTeX
34The Angular-Metric Traveling Salesman Problem. Alok Aggarwal, Don Coppersmith, Sanjeev Khanna, Rajeev Motwani, Baruch Schieber. SIAM J. Comput. (29): 697-711 (1999). Cited by 24Web SearchBibTeXDownload
33The 2-Catalog Segmentation Problem. Yevgeniy Dodis, Venkatesan Guruswami, Sanjeev Khanna. SODA 1999, 897-898. Web SearchBibTeXDownload
32On Multi-Dimensional Packing Problems. Chandra Chekuri, Sanjeev Khanna. SODA 1999, 185-194. Web SearchBibTeXDownload
31Page Replacement for General Caching Problems. Susanne Albers, Sanjeev Arora, Sanjeev Khanna. SODA 1999, 31-40. Web SearchBibTeXDownload
30Time-Constrained Scheduling of Weighted Packets on Trees and Meshes. Micah Adler, Sanjeev Khanna, Rajmohan Rajaraman, Adi Rosén. SPAA 1999, 1-12. Web SearchBibTeXDownload
29Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems. Venkatesan Guruswami, Sanjeev Khanna, Rajmohan Rajaraman, F. Bruce Shepherd, Mihalis Yannakakis. STOC 1999, 19-28. Web SearchBibTeXDownload
28Design Networks with Bounded Pairwise Distance. Yevgeniy Dodis, Sanjeev Khanna. STOC 1999, 750-759. Web SearchBibTeXDownload
1998
27On Certificates and Lookahead in Dynamic Graph Problems. Sanjeev Khanna, Rajeev Motwani, Randall H. Wilson. Algorithmica (21): 377-394 (1998). Cited by 36Web SearchBibTeXDownload
26On Wireless Spectrum Estimation and Generalized Graph Coloring. Krishnan Kumaran, Sanjeev Khanna. INFOCOM 1998, 1273-1283. Web SearchBibTeX
25On Syntactic versus Computational Views of Approximability. Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani. SIAM J. Comput. (28): 164-191 (1998). Cited by 231Web SearchBibTeXDownload
24On Approximating Rectangle Tiling and Packing. Sanjeev Khanna, S. Muthukrishnan, Mike Paterson. SODA 1998, 384-393. Cited by 65Web SearchBibTeXDownload
23On Broadcast Disk Paging. Sanjeev Khanna, Vincenzo Liberatore. STOC 1998, 634-643. Web SearchBibTeXDownload
22On Indexed Data Broadcast. Sanjeev Khanna, Shiyu Zhou. STOC 1998, 463-472. Web SearchBibTeXDownload
1997
21On the Hardness of Approximating Max k-Cut and its Dual. Viggo Kann, Sanjeev Khanna, Jens Lagergren, Alessandro Panconesi. Chicago J. Theor. Comput. Sci. (1997) (1997). Web SearchBibTeXDownload
20Efficient Array Partitioning. Sanjeev Khanna, S. Muthukrishnan, Steven Skiena. ICALP 1997, 616-626. Cited by 33Web SearchBibTeXDownload
19Constraint Satisfaction: The Approximability of Minimization Problems. Sanjeev Khanna, Madhu Sudan, Luca Trevisan. IEEE Conference on Computational Complexity 1997, 282-296. Web SearchBibTeXDownload
18A Graph Partitioning Approach to Sequential Diagnosis. Sanjeev Khanna, W. Kent Fuchs. IEEE Trans. Computers (46): 39-47 (1997). Web SearchBibTeXDownload
17The Angular-Metric Traveling Salesman Problem. Alok Aggarwal, Don Coppersmith, Sanjeev Khanna, Rajeev Motwani, Baruch Schieber. SODA 1997, 221-229. Cited by 24Web SearchBibTeXDownload
16A Complete Classification of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction. Sanjeev Khanna, Madhu Sudan, David P. Williamson. STOC 1997, 11-20. Web SearchBibTeXDownload
1996
15The Optimization Complexity of Constraint Satisfaction Problems. Sanjeev Khanna. Electronic Colloquium on Computational Complexity (ECCC) (3) (1996). Web SearchBibTeXDownload
14A Complete Characterization of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction. Sanjeev Khanna. Electronic Colloquium on Computational Complexity (ECCC) (3) (1996). Web SearchBibTeXDownload
13Constraint satisfaction: The approximability of minimization problems. Sanjeev Khanna. Electronic Colloquium on Computational Complexity (ECCC) (3) (1996). Web SearchBibTeXDownload
12On the Hardness of Approximating Max k-Cut and Its Dual. Viggo Kann, Sanjeev Khanna, Jens Lagergren, Alessandro Panconesi. ISTCS 1996, 61-67. Web SearchBibTeX
11On Certificates and Lookahead in Dynamic Graph Problems. Sanjeev Khanna, Rajeev Motwani, Randall H. Wilson. SODA 1996, 222-231. Cited by 36Web SearchBibTeXDownload
10Towards a Syntactic Characterization of PTAS. Sanjeev Khanna, Rajeev Motwani. STOC 1996, 329-337. Cited by 83Web SearchBibTeXDownload
1995
9On Syntactic versus Computational Views of Approximability. Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani. Electronic Colloquium on Computational Complexity (ECCC) (2) (1995). Cited by 231Web SearchBibTeXDownload
8A Linear Time Algorithm for Sequential Diagnosis in Hypercubes. Sanjeev Khanna, W. Kent Fuchs. J. Parallel Distrib. Comput. (26): 48-53 (1995). Web SearchBibTeXDownload
1994
7On Syntactic versus Computational Views of Approximability. Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani. FOCS 1994, 819-830. Cited by 231Web SearchBibTeXDownload
1993
6On the Hardness of Approximating the Chromatic Number. Sanjeev Khanna, Nathan Linial, Shmuel Safra. ISTCS 1993, 250-260. Web SearchBibTeX
1992
5Parallel TCP/IP for Multiprocessor Workstations. Kurt Maly, Sanjeev Khanna, Ravi Mukkamala, C. Michael Overstreet, Ramesh Yerraballi, Edwin C. Foudriat, B. Madan. HPN 1992, 103-118. Web SearchBibTeX
4Concurrent Use of Parallel Communication to Enable Remote Visualization. Kurt Maly, Frank Paterra, C. Michael Overstreet, Ravi Mukkamala, Sanjeev Khanna. ICCI 1992, 449-452. Web SearchBibTeX
3Multiprocessor Architectures for High Speed Networks: A Performance Study. Kurt Maly, Sanjeev Khanna, C. Michael Overstreet, Ravi Mukkamala, Mohammad Zubair, Y. S. Sekhar. IFIP Congress (1) 1992, 645-651. Web SearchBibTeX
1991
2Logic Programming for Software Verification and Testing. Sanjeev Khanna. Comput. J. (34): 350-357 (1991). Web SearchBibTeXDownload
1990
1Logic Programming for Software Testing. Sanjeev Khanna. ICCI 1990, 225-234. Web SearchBibTeXDownload
from DBLP and Google Scholar
References
1. ^ Computer Science Colloquium - Retrieved 2011-04-23 - details
2. ^ Past Speakers | CSE Department at the OSU - Retrieved 2011-04-17 - details
3. ^ Colloquia at Rensselaer Computer Science - Retrieved 2010-12-09 - details
Developed by the Database Group at the University of Wisconsin and Yahoo! Research