Research papers arising from IMPECS

Display # 
1 Jacobian hits circuits: hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits
Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, Nitin Saxena, STOC 2012: 599-614
2 Understanding and combating link farming in the twitter social network.
Saptarshi Ghosh, Bimal Viswanath, Farshad Kooti, Naveen Kumar Sharma, Gautam Korlam, Fabrício Benevenuto, Niloy Ganguly, P. Krishna Gummadi, WWW 2012:61-70
3 Cognos: Crowdsourcing Search for Topic Experts in Microblogs
S. Ghosh, N. Sharma, F. Benevenuto, N. Ganguly, and K. Gummadi, SIGIR 2012:575-590
4 Single source distance oracle for planar digraphs avoiding a failed node or link.
Surender Baswana, Utkarsh Lath, Anuradha S. Mehta, SODA 2012:223-232.
5 Efficient algorithms for maximum weight matchings in general graphs with small edge weights
Chien-Chung Huang and Telikepalli Kavitha, SODA 2012:1400-1412.
6 Popularity vs maximum cardinality in the stable marriage setting
Telikepalli Kavitha, SODA 2012:123-134.
7 Physarum can compute shortest paths
Vincenzo Bonifaci, Kurt Mehlhorn and Girish Varma, SODA 2012:233-240.
8 Resource augmentation for weighted flow-time explained by dual fitting
S. Anand, Naveen Garg and Amit Kumar, SODA 2012:1228-1241.
9 Popular Matchings in the Stable Marriage Problem
Chien-Chung Huang and Telikepalli Kavitha, ICALP 2011:666-677.
10 Meeting Deadlines: How Much Speed Suffices?
S. Anand, Naveen Garg and Nicole Megow, ICALP 2011:232-243.
11 A Case of Depth-3 Identity Testing, Sparse Factorization and Duality
C. Saha, R. Saptharishi, and N .Saxena, Electronic Colloquium on Computational Complexity (ECCC) 18: 21 (2011)
12 On the Sum of Square Roots of Polynomials and Related Problems
N. Kayal and C. Saha, IEEE Conference on Computational Complexity (CCC), pages 292–299, 2011.
13 A 5-approximation for capacitated facility location.
Manisha Bansal, Naveen Garg and Neelima Gupta, ESA 2012.
14 Identity Testing, multilinearity testing, and monomials in Read-Once/Twice Formulas and Branching Programs.
Meena Mahajan, B. V. Raghavendra Rao and Karteek Sreenivasaiah, MFCS 2012:655-667.
15 Inferring Who-is-Who in the Twitter Social Network
Naveen Sharma, Saptarshi Ghosh, Fabricio Benevenuto, Niloy Ganguly, and Krishna P. Gummadi, ACM SIGCOMM Workshop On Social Networks (WOSN) 2012:55-60.
16 Keyword Search on Form Results
Aditya Ramesh, S. Sudarshan, Purva Joshi and Manisha Naik Gaonkar
invited paper, to appear in VLDB Journal


No events


  • The deadline for applying for student exchange is March 30, 2015. Students enrolled in a Ph.D. programme at any Indian…
Copyright © 2017 Joomla! demo site. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.