Counting and sampling triangles from a graph stream A Pavan, K Tangwongsan, S Tirthapura, KL Wu Proceedings of the VLDB Endowment 6 (14), 1870-1881, 2013 | 216 | 2013 |
On the hardness of permanent JY Cai, A Pavan, D Sivakumar Annual Symposium on Theoretical Aspects of Computer Science, 90-99, 1999 | 87 | 1999 |
Parallel triangle counting in massive streaming graphs K Tangwongsan, A Pavan, S Tirthapura Proceedings of the 22nd ACM international conference on Information …, 2013 | 60 | 2013 |
On the NP-completeness of the minimum circuit size problem JM Hitchcock, A Pavan 35th IARCS Annual Conference on Foundations of Software Technology and …, 2015 | 47 | 2015 |
Extracting Kolmogorov complexity with applications to dimension zero-one laws L Fortnow, JM Hitchcock, A Pavan, NV Vinodchandran, F Wang Automata, Languages and Programming: 33rd International Colloquium, ICALP …, 2006 | 39 | 2006 |
Range-efficient counting of distinct elements in a massive data stream A Pavan, S Tirthapura SIAM Journal on Computing 37 (2), 359-379, 2007 | 37 | 2007 |
Separation of NP-completeness notions A Pavan, AL Selman Proceedings 16th Annual IEEE Conference on Computational Complexity, 78-89, 2001 | 37 | 2001 |
An O (n½+?)-Space and Polynomial-Time Algorithm for Directed Planar Reachability T Imai, K Nakagawa, A Pavan, NV Vinodchandran, O Watanabe 2013 IEEE Conference on Computational Complexity, 277-286, 2013 | 33 | 2013 |
New time-space upperbounds for directed reachability in high-genus and h-minor-free graphs D Chakraborty, A Pavan, R Tewari, NV Vinodchandran, LF Yang 34th International Conference on Foundation of Software Technology and …, 2014 | 30 | 2014 |
Space-efficient estimation of statistics over sub-sampled streams A McGregor, A Pavan, S Tirthapura, D Woodruff Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on Principles of …, 2012 | 29 | 2012 |
Range-efficient computation of F/sub 0/over massive data streams A Pavan, S Tirthapura 21st International Conference on Data Engineering (ICDE'05), 32-43, 2005 | 29 | 2005 |
Autoreducibility, mitoticity, and immunity C Glaßer, M Ogihara, A Pavan, AL Selman, L Zhang Journal of Computer and System Sciences, 2007 | 28 | 2007 |
Proving SAT does not have small circuits with an application to the two queries problem L Fortnow, A Pavan, S Sengupta Journal of Computer and System Sciences 74 (3), 358-363, 2008 | 24 | 2008 |
Kolmogorov complexity in randomness extraction JM Hitchcock, A Pavan, NV Vinodchandran ACM Transactions on Computation Theory (TOCT) 3 (1), 1-12, 2011 | 22 | 2011 |
Hardness hypotheses, derandomization, and circuit complexity JM Hitchcock, A Pavan International Conference on Foundations of Software Technology and …, 2004 | 22 | 2004 |
The magazine archive includes every article published in Communications of the ACM for over the past 50 years. ACM Join Communications of the ACM 44 (6), 15-20, 2001 | 22 | 2001 |
On the power of unambiguity in logspace A Pavan, R Tewari, NV Vinodchandran arXiv preprint arXiv:1001.2034, 2010 | 20 | 2010 |
Properties of NP-complete sets C Glaßer, A Pavan, AL Selman, S Sengupta SIAM Journal on Computing 36 (2), 516-542, 2006 | 20 | 2006 |
On approximating total variation distance A Bhattacharyya, S Gayen, KS Meel, D Myrisiotis, A Pavan, ... arXiv preprint arXiv:2206.07209, 2022 | 17 | 2022 |
On pseudodeterministic approximation algorithms P Dixon, A Pavan, NV Vinodchandran 43rd International Symposium on Mathematical Foundations of Computer Science …, 2018 | 17 | 2018 |