Journal Articles
- L. Fortnow, A. Pavan, S. Sengupta.
Proving SAT does not have small circuits with an
application to the two queries problem
Journal of Computer and System Sciences 74(3):358--363, 2008.
- C. Glasser, A. Pavan, S. Selman, L. Zhang.
Splitting NP-complete sets
SIAM Journal on Computing 37(5):1517--1535, 2008.
- J. Hitchcock, A. Pavan.
Hardness hypotheses, derandomization, and circuit
complexity
Computational Complexity 17(1):119--146, 2008.
- A. Pavan, N. V. Vinodchandran.
2-Local random reductions to 3-valued functions
Computational Complexity 17(4):501--514, 2008.
- J. Hitchcock, A. Pavan, N. V. Vinodchandran.
Partial bi-immunity, scaled dimension, and NP-completeness.
Theory of Computing Systems, 42(2):131--142, 2008.
- C. Glasser, M. Ogihara, A. Pavan, A. Selman, L. Zhang.
Autoreducibility, mitoticity, and immunity
Journal of Computer and System Sciences, 73(5):735--754, 2007
- J. Hitchcock, A. Pavan.
Comparing reductions to NP-complete
sets
Information and Computation, 205(5):694--706, 2007.
- A. Pavan, A. Selman, S. Sengupta, N. V. Vinodchandran.
Polylogarithmic interactive proofs for CoNP collapse
the exponential hierarchy
Theoretical Computer Science, 385:167--178, 2007.
- A. Pavan, S. Tirthapura.
Range-efficient computation of F_0 over massive data
streams
SIAM Journal on Computing, 37(2):359--379, 2007.
- A. Pavan, F. Wang.
Robustness of PSPACE-complete sets
Information Processing Letters, 103(3):102--104, 2007.
- C. Glasser, A. Pavan, A. Selman, S. Sengupta.
Properties of NP-complete sets.
SIAM Journal on Computing, 36(2):516--542, 2006.
- H. Buhrman, L. Fortnow, A. Pavan.
Some results on derandomization.
Theory of Computing Systems. Special issue on the 20th Symposium on
Theoretical Aspects of Computer Science. 38(2)211-227, 2005.
- J. Hitchcock, A. Pavan.
Resource-Bounded Strong Dimension versus
Resource-Bounded Category.
Information Processing Letters. 95(3):377-381, 2005
- A. Pavan, A. Selman.
Bi-immunity separates strong NP-completeness
notions.
Information and Computation, 188:116--126(2004).
- A. Pavan, A. Selman.
Separation of NP-completeness notions.
SIAM Journal on Computing, 31(3):906-918 (2002)
- L. Fortnow, A. Pavan, A. Selman.
Distributionally-hard languages.
Theory of Computing Systems., 34(3):245-262 (2001).
- A. Pavan, A. Selman.
Complete distributional problems, hard languages,
and resource-bounded measure.
Theoretical Computer Science, 234:273-286(2000).
- J. Belanger, A. Pavan, J. Wang.
Reductions do not preserve fast convergence rates in
average time.
Algorithmica, 23:363-373(1999).
- S. Banerjee, R. K. Ghosh, A. P. K. Reddy
Parallel algorithm for shortest pairs of edge-disjoint
paths.
Journal of Parallel and Distributed Computing, 33:165-171(1996).
Conference Publications
- X. Gu, J. Hitchcock, A. Pavan
Collapsing and separating completeness notions
under average-case and worst-case hypotheses
27th International Symposium on Theoretical Aspects of Computer Science ,
To appear.
- J. Hitchcock, A. Pavan, N. V. Vinodchandran
Kolmogorov complexity in randomness extraction
29th International Conference on Foundations of Software Technology and
Theoretical Computer Science,
LIPIcs 4, 215--226, 2009.
- R. Harkins, J. Hitchcock, A. Pavan
Strong reductions and isomorphism of complete
sets
27th International Conference on Foundations of Software Technology and
Theoretical Computer Science, LNCS 4885, 168--178, 2007.
- A. Pavan, R. Santhanam, N. V. Vinodchandran
Some results on average-case hardness within the
Polynomial Hierarchy
26th International Conference on Foundations of Software Technology and
Theoretical Computer Science, LNCS 4337, 188--199, 2006.
- J. Hitchcock, A. Pavan
Comparing reductions to NP-complete
sets
33rd International Colloquium on Automata, Languages and Programming, LNCS
4051:465-476 (2006).
- L. Fortnow, J. Hitchcock, A. Pavan, N. V. Vinodchandran, F. Wang.
Extracting Kolmogorov complexity with applications to
dimension zero-one laws
33rd International Colloquium on Automata, Languages and Programming, LNCS
4051:355-345 (2006).
- C. Glasser, A. Pavan, A. Selman, L. Zhang.
Redundancy in complete sets
23rd International Symposium on Theoretical Aspects of Computer
Science, LNCS 3884, 444--454 (2006).
- C. Glasser, M. Ogihara, A. Pavan, A. Selman, L. Zhang.
Autoreducibility, mitoticity, and
immunity
30th International Symposium on
Mathematical Foundations of Computer Science, LNCS 3618, 387--398 (2005).
- A. Pavan, S. Tirthapura.
Range-efficient computation of F_0 over massive data
streams
21st International Conference on Data Engineering (ICDE), 32--43 (2005).
- J. Hitchcock, A. Pavan.
Hardness hypotheses, derandomization, and circuit
complexity.
Foundations of Software Technology and Theoretical Computer Science (FSTTCS),
LNCS 3328, 336--347 (2004).
- C. Glasser, A. Pavan, A. Selman, S. Sengupta.
Properties of NP-complete sets.
Proceedings of the 19th IEEE Conference on Computational Complexity, 184-197
(2004).
- J. Hitchcock, A. Pavan, N. V. Vinodchandran.
Partial bi-immunity, scaled dimension, and NP-completeness.
Proceedings of the 19th IEEE Conference on Computational Complexity, 198-203
(2004).
- L. Fortnow, A. Pavan, S. Sengupta.
Proving SAT does not have small circuits with an application to
the twoqueries problem.
Proceedings of the 18th IEEE Conference on Computational Complexity, 347-350, 2003.
- H. Buhrman, L. Fortnow, A. Pavan.
Some results on derandomization.
20th Annual Symposium on Theoretical Aspects of Computer Science (STACS),
LNCS 2607:212-222(2003).
- A. Pavan, A. Selman.
Bi-immunity separates strong NP-completeness
notions.
19th Annual Symposium on Theoretical Aspects of Computer
Science (STACS), LNCS 2285:408-418(2002)
- A. Pavan, A. Selman.
Separation of NP-completeness notions.
Proceedings of the 16th IEEE Conference on Computational Complexity. 2001.
- L. Fortnow, A. Pavan, A. Selman.
Distributionally-hard languages.
Procedings of the 5th International Computing and Combinatorics Conference (COCOON).
LNCS 1627:184-193(1999).
- Jin-Yi Cai, A. Pavan, D. Sivakumar.
On the hardness of permanent.
Proceedings of the 16th Annual Symposium on Theoretical
Aspects of Computer Science (STACS), LNCS 1563:90-99(1999).
Survey Articles