Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR96-040 | 18th February 1997 00:00

The Isomorphism Problem for One-Time-Only Branching Programs and Arithmetic Circuits Revision of: TR96-040

RSS-Feed




Revision #1
Authors: Thomas Thierauf
Accepted on: 18th February 1997 00:00
Downloads: 1089
Keywords: 


Abstract:


Paper:

TR96-040 | 21st May 1996 00:00

The Isomorphismproblem for One-Time-Only Branching Programs





TR96-040
Authors: Thomas Thierauf
Publication: 23rd July 1996 18:03
Downloads: 863
Keywords: 


Abstract:

We investigate the computational complexity of the
isomorphism problem for one-time-only branching programs (BP1-Iso):
on input of two one-time-only branching programs B and B',
decide whether there exists a permutation of the variables of B'
such that it becomes equivalent to B.

Our main result is a two-round interactive proof for the complement of BP1-Iso.
The protocol is based on the Schwartz-Zippel Theorem
to probabilistically check polynomial idendities.
As a consequence,
BP1-Iso cannot be NP hard unless the polynomial hierarchy collapses.

We extend the protocol to get an interactive proof to decide the
non-isomorphism of multivariate polynomials over an arbitrary field.

Finally, we show that BP1-Iso has a zero-knowledge interactive proof.


Comment(s):

Comment #1 to TR96-040 | 11th May 2001 12:35

Revision Comment on: TR96-040





Comment #1
Authors: Thomas Thierauf
Accepted on: 11th May 2001 12:35
Downloads: 1162
Keywords: 


Abstract:





ISSN 1433-8092 | Imprint