Journal Articles
- A. Pavan, N. V. Vinodchandran.
2-Local random reductions to 3-valued
functions
Computational Complexity, To appear.
- J. Hitchcock, A. Pavan.
Comparing reductions to NP-complete
sets
Information and Computation, To appear.
- C. Glasser, M. Ogihara, A. Pavan, A. Selman, L. Zhang.
Autoreducibility, mitoticity, and immunity
Journal of Computer and System Sciences, To appear.
- A. Pavan, S. Tirthapura.
Range-efficient computation of F_0 over massive data
streams
SIAM Journal on Computing, To appear.
- A. Pavan, N. V. Vinodchandran.
Relations between average-case and
worst-case complexity
Theory of Computing Systems, To appear.
- Christian Glasser, A. Pavan, Alan L. Selman, Samik Sengupta.
Properties of NP-complete sets.
SIAM Journal on Computing, To appear.
- John M. Hitchcock, A. Pavan, N. V. Vinodchandran.
Partial bi-immunity, scaled dimension, and NP-completeness.
Theory of Computing Systems, To appear.
- Lance Fortnow, A. Pavan, Samik Sengupta.
Proving SAT does not have small circuits with an application to
the twoqueries problem.
Journal of Computer and System Sciences. Special issue for selected papers from the 18th
IEEE Conference on Computational Complexity. To appear.
- John M. Hitchcock, A. Pavan.
Resource-Bounded Strong Dimension versus
Resource-Bounded Category.
Information Processing Letters. 95(3):377-381, 2005
- Harry Buhrman, Lance 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.
- A. Pavan, Alan L. Selman.
Bi-immunity separates strong NP-completeness
notions.
Information and Computation, 188:116--126(2004).
- A. Pavan, Alan L. Selman.
Separation of NP-completeness notions.
SIAM Journal on Computing, 31(3):906-918 (2002)
- Lance Fortnow, A. Pavan, Alan L. Selman.
Distributionally-hard languages.
Theory of Computing Systems., 34(3):245-262 (2001).
- A. Pavan, Alan L. Selman.
Complete distributional problems, hard languages,
and resource-bounded measure.
Theoretical Computer Science, 234:273-286(2000).
- Jay Belanger, A. Pavan, Jie 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
- A. Pavan, R. Santhanam, N. V. Vinodchandran
Some results on average-case hardness within the Polynomial Hierarchy
Foundations of Software Technology and Theoretical Computer Science, 2006. To
appear.
- 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, N. V. Vinodchandran.
Relations between average-case and
worst-case complexity
15th International Symposium on Fundamentals of Computation Theory ,
LNCS 3623, 422-432 (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).
- John M. Hitchcock, A. Pavan.
Hardness hypotheses, derandomization, and circuit
complexity.
Foundations of Software Technology and Theoretical Computer Science (FSTTCS),
LNCS 3328, 336--347 (2004).
- Christian Glasser, A. Pavan, Alan L. Selman, Samik Sengupta.
Properties of NP-complete sets.
Proceedings of the 19th IEEE Conference on Computational Complexity, 184-197
(2004).
- John M. 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).
- Lance Fortnow, A. Pavan, Samik 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.
- Harry Buhrman, Lance Fortnow, A. Pavan.
Some results on derandomization.
20th Annual Symposium on Theoretical Aspects of Computer Science (STACS),
LNCS 2607:212-222(2003).
- A. Pavan, Alan L. 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, Alan L. Selman.
Separation of NP-completeness notions.
Proceedings of the 16th IEEE Conference on Computational Complexity. 2001.
- Lance Fortnow, A. Pavan, Alan L. 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
Unpublished