The Complexity of solving Linear Equations over a Finite
Ring
V. Arvind and T.C. Vijayaraghavan. In Proceedings of the
22nd Symposium on Theoretical Aspects of Computer Science, LNCS,
Springer. Feb 2005, to appear.
Solvable Group Isomorphism is (almost) in NP\cap coNP
V. Arvind and Jacobo Toran. Proceedings of the 19th IEEE Conference
on Computational Complexity, pp. 91--103, June 2004.
Abelian Permutation Group Problems and Logspace Counting
Classes
V. Arvind and T.C. Vijayaraghavan. Proceedings of the 19th IEEE Conference
on Computational Complexity, pp. 204--214, June 2004.
On the Complexity of Computing Units in a Number Field
V. Arvind, and Piyush P Kurur. Proceedings of the sixth Algorithmic
Number Theory Symposium, pp. 72-86, June 2004.
New Lowness Results for ZPP(NP) and other
Complexity Classes.
V. Arvind and J. Köbler, Journal of Computer and System
Sciences, 65(2): 257-277, 2002. Preliminary version in
Proceedings of the 17th Annual Symp. on Theoretical
Aspects of Computer Science, Springer-Verlag, LNCS 1770, 431--442,
2000.
Arithmetic Complexity, Kleene Closure, and Formal Power Series.
E.W. Allender, V. Arvind, and M. Mahajan, Theory of Computing Systems,
vol. 36, pp. 303--328, 2003.
Nondeterministic Instance Complexity
and Hard-To-Prove Tautologies.
V. Arvind, J. Köebler, M. Mundhenk, and J. Toran, 17th
Annual Symp. on Theoretical Aspects of Computer Science,
February 2000.
Sparse sets, approximable sets, and parallel queries to NP
V. Arvind and J. Toran, Information Processing Letters
Volume 69, Issue 4 , 26 February 1999, Pages 181-188. Preliminary version
in Proc. 16th Annual Symp. on Theoretical Aspects of Computer Science,
February 1999.
On resource-bounded measure and pseudorandomness
V. Arvind and J. Köbler, Theoretical Computer Science
Volume 255, Issues 1-2 , 28 March 2001, Pages 205-221. Preliminary version
in Proc. 17th Conference on Foundations of Software Technology and
Theoretical Computer Science, LNCS Vol. 1346, 235-249, 1997.
Constructivizing membership proofs in complexity classes.
V. Arvind,
In International Journal of Foundations of Computer Science,
8(4) 433--442, 1997, World Scientific.
Quasi-linear truth-table reductions to p-selective sets.
M. Agrawal and V. Arvind, Theoretical Computer Science, 158,
361-370, May 1996.
Geometric sets of low information content.
M. Agrawal and V. Arvind,
Theoretical Computer Science, 158, 193-219, May 1996.
On reductions to sets that avoid EXPSPACE.
V. Arvind, J. Köbler, and M. Mundhenk, Information Processing Letters
Volume 56, Issue 2 , 27 October 1995, Pages 109-114. Preliminary version
was presented at MFCS 1992.
Monotonous and randomized reductions to sparse sets.
V. Arvind, J. Köbler, and M. Mundhenk,
In Informatique Theorique et Applications 30(2), 1996, 155-179.
Preliminary version was presented at the FSTTCS conference, 1992.
On helping and interactive proof systems.
V. Arvind, J. Köbler, and R. Schuler,
International Journal of Foundations of Computer Science,
6(2), 137-153, 1995. Preliminary version was presented at the ISAAC
conference, 1994.