Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR96-034 | 28th March 1996
Vasken Bohossian, Jehoshua Bruck

On Neural Networks with Minimal Weights

Linear threshold elements are the basic building blocks of artificial neural
networks. A linear threshold element computes a function that is a sign of a
weighted sum of the input variables. The weights are arbitrary integers;
actually, they can be very big integers---exponential in the number of the
input variables. ... more >>>


TR96-033 | 6th March 1996
Bernd Borchert, Desh Ranjan, Frank Stephan

On the Computational Complexity of some Classical Equivalence Relations on Boolean Functions

The paper analyzes in terms of polynomial time many-one reductions
the computational complexity of several natural equivalence
relations on Boolean functions which derive from replacing
variables by expressions. Most of these computational problems
turn out to be between co-NP and Sigma^p_2.

more >>>

TR96-032 | 12th March 1996
Manindra Agrawal, Thomas Thierauf

The Boolean Isomorphism Problem

We investigate the computational complexity of the Boolean Isomorphism problem (BI):
on input of two Boolean formulas F and G decide whether there exists a permutation of
the variables of G such that F and G become equivalent.

Our main result is a one-round interactive proof ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint