The Orbit problem is in the GapL hierarchy.
V. Arvind, T.C. Vijayaraghavan. COCOON 2008, to appear.
New results on Noncommutative and Commutative Polynomial
Identity Testing.
V. Arvind, Partha Mukhopadhyay, Srikanth
Srinivasan. CCC 2008, to appear.
A Logspace Algorithm for Partial 2-Tree Canonization.
V. Arvind, Bireswar Das, Johannes Köbler. Third
International Computer Science Symposium in Russia (CSR 2008), Moscow,
Russia, June 7-12, 2008. Lecture Notes in Computer Science 5010
Springer 2008, 40-51.
Algorithmic Problems for Metrics on Permutation
Groups.
V. Arvind, Pushkar S. Joglekar. 34th Conference on
Current Trends in Theory and Practice of Computer Science, NovĂ˝
Smokovec, Slovakia, January 19-25, 2008, Proceedings. Lecture Notes in
Computer Science 4910 Springer 2008, 136-147 (SOFSEM 2008).
The Monomial Ideal Membership Problem and Polynomial
Identity Testing.
V. Arvind, Partha Mukhopadhyay. 18th
International Symposium on Algorithms and Computation (ISAAC 2007),
Sendai, Japan, December 17-19, 2007, Proceedings. Lecture Notes in
Computer Science 4835 Springer 2007, 800-811.
On Computing the
Distinguishing Numbers of Planar Graphs and Beyond: a Counting
Approach.
V. Arvind, Christine Cheng, and N. Devanur. In
arXiv:math/0703927. SIAM Journal of Discrete Mathematics 22:4(2008)
pp.1297-1324.
A Polynomial Time Nilpotence Test for Galois Groups and Related
Results
V. Arvind and Piyush P Kurur. Proceedings of the 31st
Mathematical Foundations of Computer Science, MFCS 2006, LNCS,
Springer, to appear, Stará Lesná, Slovakia, August 28 - September 1,
2006.
The Complexity of Black-Box Ring Problems
V. Arvind, Bireswar
Das, and Partha Mukhopadhyay. Proceedings of the The Twelfth Annual
International Computing and Combinatorics Conference (COCOON'06),
LNCS, Springer, to appear, Taipei, Taiwan, August 15-18, 2006.
SZK Proofs for Black-Box Group Problems
V. Arvind and Bireswar
Das. Proceedings of the first International Computer Science Symposium
in Russia, CSR 2006, LNCS Volume 3967, Springer Verlag,
St. Petersburg, Russia, June 2006, pp. 6--17.
On Hypergraph and Graph Isomorphism for Bounded Color Classes
V. Arvind and Johannes Köbler. In Proceedings of the 23rd
Symposium on Theoretical Aspects of Computer Science, LNCS Volume
3884, Springer Verlag, Feb 2006, pp. 384--395.
Isomorphism Testing: Perspective and Open
Problems
V. Arvind and Jacobo Torán. The Computational
Complexity Column, Bulletin European Association of Theoretical
Computer Science, Number 86, June, 2005.
Bounded Color Multiplicity Graph Isomorphism in in the #L
Hierarchy
V. Arvind, Piyush P Kurur, and T.C. Vijayaraghavan.
20th IEEE Conference on Computational Complexity, 2005.
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.
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.
Upper Bounds for the Complexity of some Galois Theory Problems
V. Arvind, and Piyush P Kurur. To be presented at the 14th
Intl. Symposium on Algorithms, Automata and Computation, Dec 2003.
Graph Isomorphism is in SPP
V. Arvind, and Piyush P Kurur, IEEE Foundations of Computer
Science, pp. 743-750, 2002. The downloadable version is the older
technical report.
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.
The complexity of modular graph automorphism
V. Arvind, R. Beigel, and A. Lozano, SIAM Journal on Computing,
vol 30, no. 4, pp. 1299--1320, 2000. Preliminary version
in Proc. 15th Annual Symp. on Theoretical Aspects of Computer Science,
LNCS 1373, Springer-Verlag, February 1998.
A nonadaptive NC checker for permutation
group intersection
V. Arvind and J. Toran, Theoretical Computer Science, Volume 259,
Issues 1-2 , 28 May 2001, Pages 597-611. Preliminary version in the
Proceedings of the 12th Conference on Computational Complexity,
IEEE Computer Society, June 1997.
The counting complexity
of group-definable languages
V. Arvind and N.V. Vinodchandran, Theoretical Computer Science
Volume 242, Issues 1-2 , 6 July 2000, Pages 199-218.
Solvable black-box group problems are low for PP.
V. Arvind and N.V. Vinodchandran,
Theoretical Computer Science, 180 (1997), 17-47.
A note on decision versus search for graph automorphism.
M. Agrawal and V. Arvind, In Information and Computation,
Vol. 131:2 (1996), 179-189.