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 | 81 | 1999 |

Parallel triangle counting in massive streaming graphs K Tangwongsan, A Pavan, S Tirthapura Proceedings of the 22nd ACM international conference on Information …, 2013 | 66 | 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 | 46 | 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 | 38 | 2006 |

Separation of NP-completeness notions A Pavan, AL Selman Proceedings 16th Annual IEEE Conference on Computational Complexity, 78-89, 2001 | 37 | 2001 |

Range-efficient counting of distinct elements in a massive data stream A Pavan, S Tirthapura SIAM Journal on Computing 37 (2), 359-379, 2007 | 36 | 2007 |

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 | 32 | 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 | 29 | 2014 |

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 |

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 | 28 | 2012 |

Autoreducibility, mitoticity, and immunity C Glaßer, M Ogihara, A Pavan, AL Selman, L Zhang Journal of Computer and System Sciences 73 (5), 735-754, 2007 | 27 | 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 |

Hardness hypotheses, derandomization, and circuit complexity JM Hitchcock, A Pavan International Conference on Foundations of Software Technology and …, 2004 | 23 | 2004 |

Kolmogorov complexity in randomness extraction JM Hitchcock, A Pavan, NV Vinodchandran ACM Transactions on Computation Theory (TOCT) 3 (1), 1-12, 2011 | 22 | 2011 |

On the power of unambiguity in logspace A Pavan, R Tewari, NV Vinodchandran arXiv preprint arXiv:1001.2034, 2010 | 19 | 2010 |

Properties of NP-complete sets C Glaßer, A Pavan, AL Selman, S Sengupta SIAM Journal on Computing 36 (2), 516-542, 2006 | 19 | 2006 |

Bi-immunity separates strong NP-completeness notions A Pavan, AL Selman Information and Computation 188 (1), 116-126, 2004 | 18 | 2004 |

Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy A Pavan, AL Selman, S Sengupta, NV Vinodchandran Theoretical Computer Science 385 (1-3), 167-178, 2007 | 17 | 2007 |

Comparing reductions to NP-complete sets JM Hitchcock, A Pavan Information and Computation 205 (5), 694-706, 2007 | 17 | 2007 |