Sudipto Guha

	2010
113		Tanmoy Chakraborty, Eyal Even-Dar, Sudipto Guha, Yishay Mansour, S. Muthukrishnan: Selective Call Out and Real Time Bidding CoRR abs/1002.3102: (2010)
	2009
112		Sudipto Guha, Zhiyi Huang: Revisiting the Direct Sum Theorem and Space Lower Bounds in Random Order Streams. ICALP (1) 2009: 513-524
111		Kook Jin Ahn, Sudipto Guha: Graph Sparsification in the Semi-streaming Model. ICALP (2) 2009: 328-338
110		Sudipto Guha, Kamesh Munagala: Multi-armed Bandits with Metric Switching Costs. ICALP (2) 2009: 496-507
109		Sudipto Guha: Tight results for clustering and summarizing data streams. ICDT 2009: 268-275
108		Sudipto Guha, Kamesh Munagala: Exceeding expectations and clustering uncertain data. PODS 2009: 269-278
107		Mengmeng Liu, Svilen R. Mihaylov, Zhuowei Bao, Marie Jacob, Zachary G. Ives, Boon Thau Loo, Sudipto Guha: SmartCIS: integrating digital and physical environments. SIGMOD Conference 2009: 1111-1114
106		Shivnath Babu, Sudipto Guha, Kamesh Munagala: Large-scale uncertainty management systems: learning and exploiting your data. SIGMOD Conference 2009: 995-998
105		Sudipto Guha, Kamesh Munagala, Peng Shi: Approximation algorithms for restless bandit problems. SODA 2009: 28-37
104		Amotz Bar-Noy, Sudipto Guha, Yoav Katz, Joseph Naor, Baruch Schieber, Hadas Shachnai: Throughput maximization of real-time scheduling with batching. ACM Transactions on Algorithms 5(2): (2009)
103		Kook Jin Ahn, Sudipto Guha: Graph Sparsification in the Semi-streaming Model CoRR abs/0902.0140: (2009)
102		Dimitris Tsirogiannis, Sudipto Guha, Nick Koudas: Improving the Performance of List Intersection. PVLDB 2(1): 838-849 (2009)
101		Sudipto Guha, Andrew McGregor: Stream Order and Order Statistics: Quantile Estimation in Random-Order Streams. SIAM J. Comput. 38(5): 2044-2059 (2009)
100		Sudipto Guha, Adam Meyerson, Kamesh Munagala: A Constant Factor Approximation for the Single Sink Edge Installation Problem. SIAM J. Comput. 38(6): 2426-2442 (2009)
99		Scott Aaronson, Sudipto Guha, Jon M. Kleinberg, Frank McSherry, Dieter van Melkebeek, Amit Sahai: Special Issue On The Thirty-Eighth Annual ACM Symposium On Theory Of Computing (STOC 2006). SIAM J. Comput. 39(1): (2009)
	2008
98		Svilen R. Mihaylov, Marie Jacob, Zachary G. Ives, Sudipto Guha: A substrate for in-network sensor data integration. DMSN 2008: 35-41
97		Sudipto Guha, Andrew McGregor: Tight Lower Bounds for Multi-pass Stream Computation Via Pass Elimination. ICALP (1) 2008: 760-772
96		Nilesh Bansal, Sudipto Guha, Nick Koudas: Ad-hoc aggregations of ranked lists in the presence of hierarchies. SIGMOD Conference 2008: 67-78
95		Sudipto Guha, Kamesh Munagala, Saswati Sarkar: Information Acquisition and Exploitation in Multichannel Wireless Networks CoRR abs/0804.1724: (2008)
94		Sudipto Guha, Kamesh Munagala: Sequential Design of Experiments via Linear Programming CoRR abs/0805.2630: (2008)
93		Sudipto Guha, Kamesh Munagala: Adaptive Uncertainty Resolution in Bayesian Combinatorial Optimization Problems CoRR abs/0812.1012: (2008)
92		Sudipto Guha, Boulos Harb: Approximation Algorithms for Wavelet Transform Coding of Data Streams. IEEE Transactions on Information Theory 54(2): 811-830 (2008)
91		Sudipto Guha, Piotr Indyk, Andrew McGregor: Sketching information divergences. Machine Learning 72(1-2): 5-19 (2008)
90		Partha Pratim Talukdar, Marie Jacob, Muhammad Salman Mehmood, Koby Crammer, Zachary G. Ives, Fernando Pereira, Sudipto Guha: Learning to create data-integrating queries. PVLDB 1(1): 785-796 (2008)
89		Sudipto Guha, Hyoungmin Park, Kyuseok Shim: Wavelet synopsis for hierarchical range queries with workloads. VLDB J. 17(5): 1079-1099 (2008)
88		Sudipto Guha: On the space-time of optimal, approximate and streaming algorithms for synopsis construction problems. VLDB J. 17(6): 1509-1535 (2008)
	2007
87		Sudipto Guha, Piotr Indyk, Andrew McGregor: Sketching Information Divergences. COLT 2007: 424-438
86		Sudipto Guha, Kamesh Munagala: Approximation Algorithms for Partial-Information Based Stochastic Control with Markovian Rewards. FOCS 2007: 483-493
85		Sudipto Guha, Andrew McGregor: Lower Bounds for Quantile Estimation in Random-Order and Multi-pass Streaming. ICALP 2007: 704-715
84		Sudipto Guha, Kamesh Munagala: Model-driven optimization using adaptive probes. SODA 2007: 308-317
83		Sudipto Guha, Kamesh Munagala: Approximation algorithms for budgeted learning problems. STOC 2007: 104-113
82		Sudipto Guha, Boulos Harb: Nonlinear Approximation and Image Representation using Wavelets. Web Information Retrieval and Linear Algebra Algorithms 2007
81		Sudipto Guha, Kamesh Munagala, Peng Shi: Approximation Algorithms for Restless Bandit Problems CoRR abs/0711.3861: (2007)
80		Sudipto Guha, Kyuseok Shim: A Note on Linear Time Algorithms for Maximum Error Histograms. IEEE Trans. Knowl. Data Eng. 19(7): 993-997 (2007)
	2006
79		Sudipto Guha, Nick Koudas, Divesh Srivastava, Xiaohui Yu: Reasoning About Approximate Match Query Results. ICDE 2006: 8
78		Ashish Goel, Sudipto Guha, Kamesh Munagala: Asking the right questions: model-driven optimization using probes. PODS 2006: 203-212
77		Sudipto Guha, Andrew McGregor: Approximate quantiles and the order of the stream. PODS 2006: 273-279
76		Sudipto Guha, Kamesh Munagala, Saswati Sarkar: Optimizing transmission rate in wireless channels using adaptive probes. SIGMETRICS/Performance 2006: 381-382
75		Sudipto Guha, Boulos Harb: Approximation algorithms for wavelet transform coding of data streams. SODA 2006: 698-707
74		Sudipto Guha, Andrew McGregor, Suresh Venkatasubramanian: Streaming and sublinear approximation of entropy and information distances. SODA 2006: 733-742
73		Sudipto Guha, H. V. Jagadish, Nick Koudas, Divesh Srivastava, Ting Yu: Integrating XML data sources using approximate joins. ACM Trans. Database Syst. 31(1): 161-207 (2006)
72		Sudipto Guha, Nick Koudas, Kyuseok Shim: Approximation and streaming algorithms for histogram construction problems. ACM Trans. Database Syst. 31(1): 396-438 (2006)
71		Sudipto Guha, Boulos Harb: Approximation algorithms for wavelet transform coding of data streams CoRR abs/cs/0604097: (2006)
70		Chandra Chekuri, Sudipto Guha, Joseph Naor: The Steiner k-Cut Problem. SIAM J. Discrete Math. 20(1): 261-271 (2006)
	2005
69		Sudipto Guha, Boulos Harb: Wavelet synopsis for data streams: minimizing non-euclidean error. KDD 2005: 88-97
68		Sudipto Guha, Kyuseok Shim: Offline and Data Stream Algorithms for Efficient Computation of Synopsis Structures. VLDB 2005: 1364
67		Sudipto Guha: Space Efficiency in Synopsis Construction Algorithms. VLDB 2005: 409-420
66		Sudipto Guha: How far will you walk to find your shortcut: Space Efficient Synopsis Construction Algorithms CoRR abs/cs/0502075: (2005)
65		Sudipto Guha, Andrew McGregor, Suresh Venkatasubramanian: Streaming and Sublinear Approximation of Entropy and Information Distances CoRR abs/cs/0508122: (2005)
64		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)
63		Moses Charikar, Sudipto Guha: Improved Combinatorial Algorithms for Facility Location Problems. SIAM J. Comput. 34(4): 803-824 (2005)
	2004
62		Tugkan Batu, Sudipto Guha, Sampath Kannan: Inferring Mixtures of Markov Chains. COLT 2004: 186-199
61		Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Joseph Naor: Machine Minimization for Scheduling Jobs with Interval Constraints. FOCS 2004: 81-90
60		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
59		Sudipto Guha, Chulyun Kim, Kyuseok Shim: XWAVE: Approximate Extended Wavelets for Streaming Data. VLDB 2004: 288-299
58		Sudipto Guha, Kyuseok Shim, Jungchul Woo: REHIST: Relative Error Histogram Construction Algorithms. VLDB 2004: 300-311
57		Sudipto Guha, Nick Koudas, Amit Marathe, Divesh Srivastava: Merging the Results of Approximate Match Operations. VLDB 2004: 636-647
	2003
56		Rajeev Alur, Swarat Chaudhuri, Kousha Etessami, Sudipto Guha, Mihalis Yannakakis: Compression of Partially Ordered Strings. CONCUR 2003: 42-56
55		Chandra Chekuri, Sudipto Guha, Joseph Naor: Approximating Steiner k-Cuts. ICALP 2003: 189-199
54		Sudipto Guha, Nick Koudas, Divesh Srivastava, Ting Yu: Index-Based Approximate XML Joins. ICDE 2003: 708-710
53		Sudipto Guha, Dimitrios Gunopulos, Nick Koudas: Correlating synchronous and asynchronous data streams. KDD 2003: 529-534
52		Sudipto Guha, Shankar Krishnan, Kamesh Munagala, Suresh Venkatasubramanian: Application of the two-sided depth test to CSG rendering. SI3D 2003: 177-180
51		Sudipto Guha, Dimitrios Gunopulos, Nick Koudas, Divesh Srivastava, Michail Vlachos: Efficient Approximation Of Optimization Queries Under Parametric Aggregation Constraints. VLDB 2003: 778-789
50		Sudipto Guha, Rajeev Rastogi, Kyuseok Shim: Techniques for Clustering Massive Data Sets. Clustering and Information Retrieval 2003: 35-82
49		Sudipto Guha, Athina Markopoulou, Fouad A. Tobagi: Hierarchical Reliable Multicast: Performance Analysis and Optimal Placement of Proxies. Computer Communications 26(18): 2070-2081 (2003)
48		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)
47		Sudipto Guha, Adam Meyerson, Nina Mishra, Rajeev Motwani, Liadan O'Callaghan: Clustering Data Streams: Theory and Practice. IEEE Trans. Knowl. Data Eng. 15(3): 515-528 (2003)
46		Sudipto Guha, Refael Hassin, Samir Khuller, Einat Or: Capacitated vertex covering. J. Algorithms 48(1): 257-270 (2003)
45		Sudipto Guha, Adam Meyerson, Kamesh Munagala: A constant factor approximation algorithm for the fault-tolerant facility location problem. J. Algorithms 48(2): 429-440 (2003)
	2002
44		Sudipto Guha, Piotr Indyk, S. Muthukrishnan, Martin Strauss: Histogramming Data Streams with Fast Per-Item Processing. ICALP 2002: 681-692
43		Sudipto Guha, Nick Koudas: Approximating a Data Stream for Querying and Estimation: Algorithms and Performance Evaluation. ICDE 2002: 567-
42		Liadan O'Callaghan, Adam Meyerson, Rajeev Motwani, Nina Mishra, Sudipto Guha: Streaming-Data Algorithms for High-Quality Clustering. ICDE 2002: 685-
41		Sudipto Guha, Nick Koudas, Divesh Srivastava: Fast Algorithms For Hierarchical Range Histogram Construction. PODS 2002: 180-187
40		Sudipto Guha, H. V. Jagadish, Nick Koudas, Divesh Srivastava, Ting Yu: Approximate XML joins. SIGMOD Conference 2002: 287-298
39		Nitin Thaper, Sudipto Guha, Piotr Indyk, Nick Koudas: Dynamic multidimensional histograms. SIGMOD Conference 2002: 428-439
38		Sudipto Guha, Kamesh Munagala: Improved algorithms for the data placement problem. SODA 2002: 106-107
37		Sudipto Guha, Kamesh Munagala: Generalized clustering. SODA 2002: 484-485
36		Amotz Bar-Noy, Sudipto Guha, Yoav Katz, Joseph Naor, Baruch Schieber, Hadas Shachnai: Throughput maximization of real-time scheduling with batching. SODA 2002: 742-751
35		Sudipto Guha, Refael Hassin, Samir Khuller, Einat Or: Capacitated vertex covering with applications. SODA 2002: 858-865
34		Anna C. Gilbert, Sudipto Guha, Piotr Indyk, S. Muthukrishnan, Martin Strauss: Near-optimal sparse fourier representations via sampling. STOC 2002: 152-161
33		Anna C. Gilbert, Sudipto Guha, Piotr Indyk, Yannis Kotidis, S. Muthukrishnan, Martin Strauss: Fast, small-space algorithms for approximate histogram maintenance. STOC 2002: 389-398
32		Moses Charikar, Sudipto Guha, Éva Tardos, David B. Shmoys: A Constant-Factor Approximation Algorithm for the k-Median Problem. J. Comput. Syst. Sci. 65(1): 129-149 (2002)
31		Guy Even, Sudipto Guha, Baruch Schieber: Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas. SIAM J. Comput. 32(1): 231-252 (2002)
	2001
30		Sudipto Guha, Adam Meyerson, Kamesh Munagala: Improved algorithms for fault tolerant facility location. SODA 2001: 636-641
29		Sudipto Guha, Adam Meyerson, Kamesh Munagala: A constant factor approximation for the single sink edge installation problems. STOC 2001: 383-388
28		Sudipto Guha, Nick Koudas, Kyuseok Shim: Data-streams and histograms. STOC 2001: 471-475
27		Sudipto Guha, Rajeev Rastogi, Kyuseok Shim: Cure: An Efficient Clustering Algorithm for Large Databases. Inf. Syst. 26(1): 35-58 (2001)
26		Amotz Bar-Noy, Sudipto Guha, Joseph Naor, Baruch Schieber: Approximating the Throughput of Multiple Machines in Real-Time Scheduling. SIAM J. Comput. 31(2): 331-352 (2001)
	2000
25		Sudipto Guha: Nested Graph Dissection and Approximation Algorithms. FOCS 2000: 126-135
24		Sudipto Guha, Nina Mishra, Rajeev Motwani, Liadan O'Callaghan: Clustering Data Streams. FOCS 2000: 359-366
23		Sudipto Guha, Adam Meyerson, Kamesh Munagala: Hierarchical Placement and Network Design Problems. FOCS 2000: 603-612
22		Guy Even, Sudipto Guha, Baruch Schieber: Improved approximations of crossings in graph drawings. STOC 2000: 296-305
21		Sudipto Guha, Rajeev Rastogi, Kyuseok Shim: ROCK: A Robust Clustering Algorithm for Categorical Attributes. Inf. Syst. 25(5): 345-366 (2000)
20		Amotz Bar-Noy, Sudipto Guha, Joseph Naor, Baruch Schieber: Message Multicasting in Heterogeneous Networks. SIAM J. Comput. 30(2): 347-358 (2000)
	1999
19		Moses Charikar, Sudipto Guha: Improved Combinatorial Algorithms for the Facility Location and k-Median Problems. FOCS 1999: 378-388
18		Sudipto Guha, Rajeev Rastogi, Kyuseok Shim: ROCK: A Robust Clustering Algorithm for Categorical Attributes. ICDE 1999: 512-521
17		Moses Charikar, Sudipto Guha, Éva Tardos, David B. Shmoys: A Constant-Factor Approximation Algorithm for the k-Median Problem (Extended Abstract). STOC 1999: 1-10
16		Sudipto Guha, Anna Moss, Joseph Naor, Baruch Schieber: Efficient Recovery from Power Outage (Extended Abstract). STOC 1999: 574-582
15		Amotz Bar-Noy, Sudipto Guha, Joseph Naor, Baruch Schieber: Approximating the Throughput of Multiple Machines Under Real-Time Scheduling. STOC 1999: 622-631
14		Sudipto Guha, Samir Khuller: Improved Methods for Approximating Node Weighted Steiner Trees and Connected Dominating Sets. Inf. Comput. 150(1): 57-74 (1999)
13		Sudipto Guha, Samir Khuller: Greedy Strikes Back: Improved Facility Location Algorithms. J. Algorithms 31(1): 228-248 (1999)
12		Moses Charikar, Chandra Chekuri, To-Yat Cheung, Zuo Dai, Ashish Goel, Sudipto Guha, Ming Li: Approximation Algorithms for Directed Steiner Problems. J. Algorithms 33(1): 73-91 (1999)
	1998
11		Moses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha, Serge A. Plotkin: Approximating a Finite Metric by a Small Number of Tree Metrics. FOCS 1998: 379-388
10		Sudipto Guha, Samir Khuller: Improved Methods for Approximating Node Weighted Steiner Trees and Connected Dominating Sets. FSTTCS 1998: 54-65
9		Sudipto Guha, Rajeev Rastogi, Kyuseok Shim: CURE: An Efficient Clustering Algorithm for Large Databases. SIGMOD Conference 1998: 73-84
8		Moses Charikar, Chandra Chekuri, To-Yat Cheung, Zuo Dai, Ashish Goel, Sudipto Guha, Ming Li: Approximation Algorithms for Directed Steiner Problems. SODA 1998: 192-200
7		Sudipto Guha, Samir Khuller: Greedy Strikes Back: Improved Facility Location Algorithms. SODA 1998: 649-657
6		Moses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha: Rounding via Trees: Deterministic Approximation Algorithms for Group Steiner Trees and k-Median. STOC 1998: 114-123
5		Amotz Bar-Noy, Sudipto Guha, Joseph Naor, Baruch Schieber: Multicasting in Heterogeneous Networks. STOC 1998: 448-453
4		Randeep Bhatia, Sudipto Guha, Samir Khuller, Yoram J. Sussmann: Facility Location with Dynamic Distance Function (Extended Abstract). SWAT 1998: 23-34
3		Sudipto Guha, Samir Khuller: Approximation Algorithms for Connected Dominating Sets. Algorithmica 20(4): 374-387 (1998)
2		Randeep Bhatia, Sudipto Guha, Samir Khuller, Yoram J. Sussmann: Facility Location with Dynamic Distance Functions. J. Comb. Optim. 2(3): 199-217 (1998)
	1996
1		Sudipto Guha, Samir Khuller: Approximation Algorithms for Connected Dominating Sets. ESA 1996: 179-193

Coauthor Index

1	Scott Aaronson	[99]
2	Kook Jin Ahn	[103] [111]
3	Rajeev Alur	[56]
4	Shivnath Babu	[106]
5	Nilesh Bansal	[96]
6	Zhuowei Bao	[107]
7	Amotz Bar-Noy	[5] [15] [20] [26] [36] [104]
8	Tugkan Batu	[62]
9	Randeep Bhatia	[2] [4]
10	Tanmoy Chakraborty	[113]
11	Moses Charikar	[6] [8] [11] [12] [17] [19] [32] [63]
12	Swarat Chaudhuri	[56]
13	Chandra Chekuri	[6] [8] [11] [12] [55] [70]
14	To-Yat Cheung	[8] [12]
15	Julia Chuzhoy	[48] [60] [61] [64]
16	Koby Crammer	[90]
17	Zuo Dai	[8] [12]
18	Kousha Etessami	[56]
19	Guy Even	[22] [31]
20	Eyal Even-Dar	[113]
21	Anna C. Gilbert	[33] [34]
22	Ashish Goel	[6] [8] [11] [12] [78]
23	Dimitrios Gunopulos	[51] [53]
24	Eran Halperin	[60] [64]
25	Boulos Harb	[69] [71] [75] [82] [92]
26	Refael Hassin	[35] [46]
27	Zhiyi Huang	[112]
28	Piotr Indyk	[33] [34] [39] [44] [87] [91]
29	Zachary G. Ives	[90] [98] [107]
30	Marie Jacob	[90] [98] [107]
31	H. V. Jagadish	[40] [73]
32	Sampath Kannan	[62]
33	Yoav Katz	[36] [104]
34	Sanjeev Khanna	[48] [60] [61] [64]
35	Samir Khuller	[1] [2] [3] [4] [7] [10] [13] [14] [35] [46]
36	Chulyun Kim	[59]
37	Jon M. Kleinberg	[99]
38	Guy Kortsarz	[60] [64]
39	Yannis Kotidis	[33]
40	Nick Koudas	[28] [39] [40] [41] [43] [51] [53] [54] [57] [72] [73] [79] [96] [102]
41	Robert Krauthgamer	[64]
42	Shankar Krishnan	[52]
43	Ming Li	[8] [12]
44	Mengmeng Liu	[107]
45	Boon Thau Loo	[107]
46	Yishay Mansour	[113]
47	Amit Marathe	[57]
48	Athina Markopoulou	[49]
49	Andrew McGregor	[65] [74] [77] [85] [87] [91] [97] [101]
50	Frank McSherry	[99]
51	Muhammad Salman Mehmood	[90]
52	Dieter van Melkebeek	[99]
53	Adam Meyerson	[23] [29] [30] [42] [45] [47] [100]
54	Svilen R. Mihaylov	[98] [107]
55	Nina Mishra	[24] [42] [47]
56	Anna Moss	[16]
57	Rajeev Motwani	[24] [42] [47]
58	Kamesh Munagala	[23] [29] [30] [37] [38] [45] [52] [76] [78] [81] [83] [84] [86] [93] [94] [95] [100] [105] [106] [108] [110]
59	S. Muthukrishnan (S. Muthu Muthukrishnan)	[33] [34] [44] [113]
60	Joseph Naor (Seffi Naor)	[5] [15] [16] [20] [26] [36] [48] [55] [60] [61] [64] [70] [104]
61	Liadan O'Callaghan	[24] [42] [47]
62	Einat Or	[35] [46]
63	Hyoungmin Park	[89]
64	Fernando Pereira	[90]
65	Serge A. Plotkin	[11]
66	Rajeev Rastogi	[9] [18] [21] [27] [50]
67	Amit Sahai	[99]
68	Saswati Sarkar	[76] [95]
69	Baruch Schieber	[5] [15] [16] [20] [22] [26] [31] [36] [104]
70	Hadas Shachnai	[36] [104]
71	Peng Shi	[81] [105]
72	Kyuseok Shim	[9] [18] [21] [27] [28] [50] [58] [59] [68] [72] [80] [89]
73	David B. Shmoys	[17] [32]
74	Divesh Srivastava	[40] [41] [51] [54] [57] [73] [79]
75	Martin Strauss (Martin J. Strauss)	[33] [34] [44]
76	Yoram J. Sussmann	[2] [4]
77	Partha Pratim Talukdar	[90]
78	Éva Tardos	[17] [32]
79	Nitin Thaper	[39]
80	Fouad A. Tobagi	[49]
81	Dimitris Tsirogiannis	[102]
82	Suresh Venkatasubramanian	[52] [65] [74]
83	Michail Vlachos	[51]
84	Jungchul Woo	[58]
85	Mihalis Yannakakis	[56]
86	Ting Yu	[40] [54] [73]
87	Xiaohui Yu	[79]

Colors in the list of coauthors