2013
172A Greedy Approximation Algorithm for Minimum-Gap Scheduling. Marek Chrobak, Uriel Feige, Mohammad Taghi Hajiaghayi, Sanjeev Khanna, Fei Li, Seffi Naor. CIAC 2013, 97-109. Web SearchBibTeXDownload
171Using the crowd for top-k and group-by queries. Susan B. Davidson, Sanjeev Khanna, Tova Milo, Sudeepa Roy. ICDT 2013, 225-236. Web SearchBibTeXDownload
2012
170Improved Hardness Results for Profit Maximization Pricing Problems with Unlimited Supply. Parinya Chalermsook, Julia Chuzhoy, Sampath Kannan, Sanjeev Khanna. APPROX-RANDOM 2012, 73-84. Web SearchBibTeXDownload
169Distributed Private Heavy Hitters. Justin Hsu, Sanjeev Khanna, Aaron Roth. CoRR (abs/1202.4910) (2012). Web SearchBibTeXDownload
168The Power of Local Information in Social Networks. Christian Borgs, Michael Brautbar, Jennifer T. Chayes, Sanjeev Khanna, Brendan Lucier. CoRR (abs/1202.6033) (2012). Web SearchBibTeXDownload
167Adaptive Selective Verification: An Efficient Adaptive Countermeasure to Thwart DoS Attacks. Sanjeev Khanna, Santosh S. Venkatesh, Omid Fatemieh, Fariba Khan, Carl A. Gunter. IEEE/ACM Trans. Netw. (20): 715-728 (2012). Web SearchBibTeXDownload
166On the communication and streaming complexity of maximum bipartite matching. Ashish Goel, Michael Kapralov, Sanjeev Khanna. SODA 2012, 468-485. Web SearchBibTeXDownload
165An O(k3log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design. Julia Chuzhoy, Sanjeev Khanna. Theory of Computing (8): 401-413 (2012). Web SearchBibTeXDownload
164Mechanism Design for a Risk Averse Seller. Anand Bhalgat, Tanmoy Chakraborty, Sanjeev Khanna. WINE 2012, 198-211. Web SearchBibTeXDownload
2011
163Optimal Lower Bounds for Universal and Differentially Private Steiner Trees and TSPs. Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna. APPROX-RANDOM 2011, 75-86. Web SearchBibTeXDownload
162Social Welfare in One-Sided Matching Markets without Money. Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna. APPROX-RANDOM 2011, 87-98. Web SearchBibTeXDownload
161Enabling 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
160Delays and the Capacity of Continuous-time Channels. Sanjeev Khanna, Madhu Sudan. CoRR (abs/1105.3425) (2011). Web SearchBibTeXDownload
159Mechanism Design with Risk Aversion. Anand Bhalgat, Tanmoy Chakraborty, Sanjeev Khanna. CoRR (abs/1107.4722) (2011). Web SearchBibTeXDownload
158Social Welfare in One-sided Matching Markets without Money. Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna. CoRR (abs/1104.2964) (2011). Web SearchBibTeXDownload
157Algorithms for the Generalized Sorting Problem. Zhiyi Huang, Sampath Kannan, Sanjeev Khanna. FOCS 2011, 738-747. Web SearchBibTeXDownload
156Delays and the Capacity of Continuous-Time Channels. Sanjeev Khanna, Madhu Sudan. FOCS 2011, 758-767. Web SearchBibTeXDownload
155On provenance and privacy. Susan B. Davidson, Sanjeev Khanna, Sudeepa Roy, Julia Stoyanovich, Val Tannen, Yi Chen. ICDT 2011, 3-10. Web SearchBibTeXDownload
154Compression 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
153Approximability of Capacitated Network Design. Deeparnab Chakrabarty, Chandra Chekuri, Sanjeev Khanna, Nitish Korula. IPCO 2011, 78-91. Web SearchBibTeXDownload
152Provenance views for module privacy. Susan B. Davidson, Sanjeev Khanna, Tova Milo, Debmalya Panigrahi, Sudeepa Roy. PODS 2011, 175-186. Web SearchBibTeXDownload
151Queries with Difference on Probabilistic Databases. Sanjeev Khanna, Sudeepa Roy, Val Tannen. PVLDB (4): 1051-1062 (2011). Web SearchBibTeXDownload
150Improved Approximation Results for Stochastic Knapsack Problems. Anand Bhalgat, Ashish Goel, Sanjeev Khanna. SODA 2011, 1647-1665. Web SearchBibTeXDownload
2010
149Approximating 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
148Perfect matchings via uniform sampling in regular bipartite graphs. Ashish Goel, Michael Kapralov, Sanjeev Khanna. ACM Transactions on Algorithms (6) (2010). Web SearchBibTeXDownload
147Inapproximability 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
146Optimal Lower Bounds for Universal and Differentially Private Steiner Tree and TSP. Anand Bhalgat, Deeparnab Chakrabarty, Sanjeev Khanna. CoRR (abs/1011.3770) (2010). Web SearchBibTeXDownload
145Preserving Module Privacy in Workflow Provenance. Susan B. Davidson, Sanjeev Khanna, Debmalya Panigrahi, Sudeepa Roy. CoRR (abs/1005.5543) (2010). Web SearchBibTeXDownload
144Graph Sparsification via Refinement Sampling. Ashish Goel, Michael Kapralov, Sanjeev Khanna. CoRR (abs/1004.4915) (2010). Web SearchBibTeXDownload
143Approximability of Capacitated Network Design. Deeparnab Chakrabarty, Chandra Chekuri, Sanjeev Khanna, Nitish Korula. CoRR (abs/1009.5734) (2010). Web SearchBibTeXDownload
142Robust self-assembly of graphs. Stanislav Angelov, Sanjeev Khanna, Mirkˇ Visontai. Natural Computing (9): 111-133 (2010). Web SearchBibTeXDownload
141An 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
140Perfect matchings in o(n log n) time in regular bipartite graphs. Ashish Goel, Michael Kapralov, Sanjeev Khanna. STOC 2010, 39-46. Web SearchBibTeXDownload
139Improved 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
138Network bargaining: algorithms and structural results. Tanmoy Chakraborty, Michael Kearns, Sanjeev Khanna. ACM Conference on Electronic Commerce 2009, 159-168. Web SearchBibTeXDownload
137Approximation 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
136A Note on Multiflows and Treewidth. Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd. Algorithmica (54): 400-412 (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
134Dynamic and Non-Uniform Pricing Strategies for Revenue Maximization. Tanmoy Chakraborty, Zhiyi Huang, Sanjeev Khanna. CoRR (abs/0905.3191) (2009). Web SearchBibTeXDownload
133On Allocating Goods to Maximize Fairness. Deeparnab Chakrabarty, Julia Chuzhoy, Sanjeev Khanna. CoRR (abs/0901.0205) (2009). Web SearchBibTeXDownload
132Improved 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
131Perfect Matchings in O(n \\log n) Time in Regular Bipartite Graphs. Ashish Goel, Michael Kapralov, Sanjeev Khanna. CoRR (abs/0909.3346) (2009). Web SearchBibTeXDownload
130Perfect Matchings in Õ(n1.5) Time in Regular Bipartite Graphs. Ashish Goel, Sanjeev Khanna. CoRR (abs/0902.1617) (2009). Web SearchBibTeXDownload
129Dynamic and Non-uniform Pricing Strategies for Revenue Maximization. Tanmoy Chakraborty, Zhiyi Huang, Sanjeev Khanna. FOCS 2009, 495-504. Web SearchBibTeXDownload
128An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design. Julia Chuzhoy, Sanjeev Khanna. FOCS 2009, 437-441. Web SearchBibTeXDownload
127Differencing Provenance in Scientific Workflows. Zhuowei Bao, Sarah Cohen Boulakia, Susan B. Davidson, Anat Eyal, Sanjeev Khanna. ICDE 2009, 808-819. Cited by 2Web SearchBibTeXDownload
126Optimizing user views for workflows. Olivier Biton, Susan B. Davidson, Sanjeev Khanna, Sudeepa Roy. ICDT 2009, 310-323. Cited by 3Web SearchBibTeXDownload
125Polynomial flow-cut gaps and hardness of directed cut problems. Julia Chuzhoy, Sanjeev Khanna. J. ACM (56) (2009). Web SearchBibTeXDownload
124Nash Dynamics in Constant Player and Bounded Jump Congestion Games. Tanmoy Chakraborty, Sanjeev Khanna. SAGT 2009, 196-207. Web SearchBibTeXDownload
123Edge-Disjoint Paths in Planar Graphs with Constant Congestion. Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd. SIAM J. Comput. (39): 281-301 (2009). Web SearchBibTeXDownload
122Perfect matchings via uniform sampling in regular bipartite graphs. Ashish Goel, Michael Kapralov, Sanjeev Khanna. SODA 2009, 11-17. Web SearchBibTeXDownload
121The ratio index for budgeted learning, with applications. Ashish Goel, Sanjeev Khanna, Brad Null. SODA 2009, 18-27. Web SearchBibTeXDownload
120Automatic construction of a minimum size motion graph. Liming Zhao, Aline Normoyle, Sanjeev Khanna, Alla Safonova. Symposium on Computer Animation 2009, 27-35. Web SearchBibTeXDownload
119Nash Dynamics in Congestion Games with Similar Resources. Anand Bhalgat, Tanmoy Chakraborty, Sanjeev Khanna. WINE 2009, 362-373. Web SearchBibTeXDownload
2008
118Perfect Matchings via Uniform Sampling in Regular Bipartite Graphs. Ashish Goel, Michael Kapralov, Sanjeev Khanna. CoRR (abs/0811.2457) (2008). Web SearchBibTeXDownload
117An O(k3log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design. Julia Chuzhoy, Sanjeev Khanna. CoRR (abs/0812.4442) (2008). Web SearchBibTeXDownload
116The Ratio Index for Budgeted Learning, with Applications. Ashish Goel, Sanjeev Khanna, Brad Null. CoRR (abs/0810.0558) (2008). Web SearchBibTeXDownload
115Robust Self-assembly of Graphs. Stanislav Angelov, Sanjeev Khanna, Mirkˇ Visontai. DNA 2008, 127-143. Web SearchBibTeXDownload
114Algorithms for Single-Source Vertex Connectivity. Julia Chuzhoy, Sanjeev Khanna. FOCS 2008, 105-114. Web SearchBibTeXDownload
113STCON in Directed Unique-Path Graphs. Sampath Kannan, Sanjeev Khanna, Sudeepa Roy. FSTTCS 2008, 256-267. Web SearchBibTeXDownload
112Algorithms for 2-Route Cut Problems. Chandra Chekuri, Sanjeev Khanna. ICALP (1) 2008, 472-484. Web SearchBibTeXDownload
111Adaptive SelectiveVerification. Sanjeev Khanna, Santosh S. Venkatesh, Omid Fatemieh, Fariba Khan, Carl A. Gunter. INFOCOM 2008, 529-537. Web SearchBibTeXDownload
110On the Network Coding Advantage for Wireless Multicast in Euclidean Space. Ashish Goel, Sanjeev Khanna. IPSN 2008, 64-69. Web SearchBibTeXDownload
109On the complexity of graph self-assembly in accretive systems. Stanislav Angelov, Sanjeev Khanna, Mirkˇ Visontai. Natural Computing (7): 183-201 (2008). Web SearchBibTeXDownload
108Network design for vertex connectivity. Tanmoy Chakraborty, Julia Chuzhoy, Sanjeev Khanna. STOC 2008, 167-176. Web SearchBibTeXDownload
2007
107Edge-disjoint paths revisited. Chandra Chekuri, Sanjeev Khanna. ACM Transactions on Algorithms (3) (2007). Web SearchBibTeXDownload
106Inapproximability 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
105A Formal Investigation of. Sanjeev Khanna, Keshav Kunal, Benjamin C. Pierce. FSTTCS 2007, 485-496. Web SearchBibTeXDownload
104Efficient 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
103Polynomial flow-cut gaps and hardness of directed cut problems. Julia Chuzhoy, Sanjeev Khanna. STOC 2007, 179-188. Web SearchBibTeXDownload
102Hardness of routing with congestion in directed graphs. Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar. STOC 2007, 165-178. Web SearchBibTeXDownload
2006
101Agreeing 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
100On the Complexity of Graph Self-assembly in Accretive Systems. Stanislav Angelov, Sanjeev Khanna, Mirkˇ Visontai. DNA 2006, 95-110. Web SearchBibTeXDownload
99Hardness of Directed Routing with Congestion. Julia Chuzhoy, Sanjeev Khanna. Electronic Colloquium on Computational Complexity (ECCC) (13) (2006). Web SearchBibTeXDownload
98Efficient Enumeration of Phylogenetically Informative Substrings. Stanislav Angelov, Boulos Harb, Sampath Kannan, Sanjeev Khanna, Junhyong Kim. RECOMB 2006, 248-264. Web SearchBibTeXDownload
97Randomized Pursuit-Evasion with Local Visibility. Volkan Isler, Sampath Kannan, Sanjeev Khanna. SIAM J. Discrete Math. (20): 26-41 (2006). Web SearchBibTeXDownload
96Hardness of cut problems in directed graphs. Julia Chuzhoy, Sanjeev Khanna. STOC 2006, 527-536. Web SearchBibTeXDownload
95Edge-disjoint paths in Planar graphs with constant congestion. Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd. STOC 2006, 757-766. Web SearchBibTeXDownload
94An 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
93The Network as a Storage Device: Dynamic Routing with Bounded Buffers. Stanislav Angelov, Sanjeev Khanna, Keshav Kunal. APPROX-RANDOM 2005, 1-13. Web SearchBibTeXDownload
92Target 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
91Hardness of the Undirected Edge-Disjoint Paths Problem with Congestion. Matthew Andrews, Julia Chuzhoy, Sanjeev Khanna, Lisa Zhang. FOCS 2005, 226-244. Web SearchBibTeXDownload
90Randomized pursuit-evasion in a polygonal environment. Volkan Isler, Sampath Kannan, Sanjeev Khanna. IEEE Transactions on Robotics (21): 875-884 (2005). Web SearchBibTeXDownload
89Asymmetric 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
88A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem. Chandra Chekuri, Sanjeev Khanna. SIAM J. Comput. (35): 713-728 (2005). Web SearchBibTeXDownload
87Approximating the average response time in broadcast scheduling. Nikhil Bansal, Moses Charikar, Sanjeev Khanna, Joseph Naor. SODA 2005, 215-221. Web SearchBibTeXDownload
86Multicommodity flow, well-linked terminals, and routing problems. Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd. STOC 2005, 183-192. Web SearchBibTeXDownload
2004
85Archiving scientific data. Peter Buneman, Sanjeev Khanna, Keishi Tajima, Wang Chiew Tan. ACM Trans. Database Syst. (29): 2-42 (2004). Cited by 163Web SearchBibTeXDownload
84Machine Minimization for Scheduling Jobs with Interval Constraints. Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Joseph Naor. FOCS 2004, 81-90. Cited by 8Web SearchBibTeXDownload
83Edge-Disjoint Paths in Planar Graphs. Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd. FOCS 2004, 71-80. Web SearchBibTeXDownload
82Approximating Longest Directed Paths and Cycles. Andreas Bj÷rklund, Thore Husfeldt, Sanjeev Khanna. ICALP 2004, 222-233. Web SearchBibTeXDownload
81Special issue: 35th Annual ACM Symposium on Theory of Computing. Sanjeev Khanna, Aravind Srinivasan. J. Comput. Syst. Sci. (69): 305 (2004). Web SearchBibTeXDownload
80DoS Protection for Reliably Authenticated Broadcast. Carl A. Gunter, Sanjeev Khanna, Kaijun Tan, Santosh S. Venkatesh. NDSS 2004. Cited by 25Web SearchBibTeXDownload
79Power-Conserving Computation of Order-Statistics over Sensor Networks. Michael Greenwald, Sanjeev Khanna. PODS 2004, 275-285. Web SearchBibTeXDownload
78On Multidimensional Packing Problems. Chandra Chekuri, Sanjeev Khanna. SIAM J. Comput. (33): 837-851 (2004). Web SearchBibTeXDownload
77A 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
76On the Hardness of 4-Coloring a 3-Colorable Graph. Venkatesan Guruswami, Sanjeev Khanna. SIAM J. Discrete Math. (18): 30-40 (2004). Web SearchBibTeXDownload
75Reconstructing strings from random traces. Tugkan Batu, Sampath Kannan, Sanjeev Khanna, Andrew McGregor. SODA 2004, 910-918. Web SearchBibTeXDownload
74Randomized pursuit-evasion with limited visibility. Volkan Isler, Sampath Kannan, Sanjeev Khanna. SODA 2004, 1060-1069. Web SearchBibTeXDownload
73The all-or-nothing multicommodity flow problem. Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd. STOC 2004, 156-165. Web SearchBibTeXDownload
72Asymmetric 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
71Multi-processor scheduling to minimize flow time with epsilon resource augmentation. Chandra Chekuri, Ashish Goel, Sanjeev Khanna, Amit Kumar. STOC 2004, 363-372. Web SearchBibTeXDownload
70ATDD: An Algorithmic Tool for Domain Discovery in Protein Sequences. Stanislav Angelov, Sanjeev Khanna, Li Li, Fernando Pereira. WABI 2004, 206-217. 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
2003
68Time-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
67Approximating Longest Directed Path. Andreas Bj÷rklund, Thore Husfeldt, Sanjeev Khanna. Electronic Colloquium on Computational Complexity (ECCC) (10) (2003). Web SearchBibTeXDownload
66Asymmetric 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
65Target tracking with distributed sensors: the focus of attention problem. Volkan Isler, John R. Spletzer, Sanjeev Khanna, Camillo J. Taylor. IROS 2003, 792-798. 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
54On Computing Functions with Uncertainty. Sanjeev Khanna, Wang Chiew Tan. PODS 2001. Web SearchBibTeXDownload
53Fair Real-Time Traffic Scheduling over a Wireless LA. Maria Adamou, Sanjeev Khanna, Insup Lee, Insik Shin, Shiyu Zhou. RTSS 2001, 279-288. 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
41A PTAS for the multiple knapsack problem. Chandra Chekuri, Sanjeev Khanna. SODA 2000, 213-222. Web SearchBibTeXDownload
40Watermarking maps: hiding information in structured data. Sanjeev Khanna, Francis Zane. SODA 2000, 596-605. Web SearchBibTeXDownload
39Approximation algorithms for data placement on parallel disks. Leana Golubchik, Sanjeev Khanna, Samir Khuller, Ramakrishna Thurimella, An Zhu. SODA 2000, 223-232. 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
29Design Networks with Bounded Pairwise Distance. Yevgeniy Dodis, Sanjeev Khanna. STOC 1999, 750-759. Web SearchBibTeXDownload
28Near-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
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
15Constraint satisfaction: The approximability of minimization 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
13The Optimization Complexity of Constraint Satisfaction 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. ^ Colloquia at Rensselaer Computer Science - Retrieved 2010-12-09 - details
Developed by the Database Group at the University of Wisconsin and Yahoo! Research