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

TR95-043 | 14th September 1995
Eric Allender, Jia Jiao, Meena Mahajan, V Vinay

Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds

We investigate the phenomenon of depth-reduction in commutative
and non-commutative arithmetic circuits. We prove that in the
commutative setting, uniform semi-unbounded arithmetic circuits of
logarithmic depth are as powerful as uniform arithmetic circuits of
polynomial degree; earlier proofs did not work in the ... more >>>


TR95-042 | 14th September 1995
Beate Bollig, Ingo Wegener

Read-once Projections and Formal Circuit Verification with Binary Decision Diagrams

Computational complexity is concerned with the complexity of solving
problems and computing functions and not with the complexity of verifying
circuit designs.
The importance of formal circuit verification is evident.
Therefore, a framework of a complexity theory for formal circuit
verification with binary decision diagrams ... more >>>


TR95-041 | 28th June 1995
Alexander E. Andreev, Andrea E. F. Clementi, Jose Rolim

Optimal Bounds for the Approximation of Boolean Functions and Some Applications

We prove an optimal bound on the Shannon function
$L(n,m,\epsilon)$ which describes the trade-off between the
circuit-size complexity and the degree of approximation; that is
$$L(n,m,\epsilon)\ =\
\Theta\left(\frac{m\epsilon^2}{\log(2 + m\epsilon^2)}\right)+O(n).$$
Our bound applies to any partial boolean function
and any ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint