Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR98-050 | 6th July 1998 00:00

A Discrete Approximation and Communication Complexity Approach to the Superposition Problem



The superposition (or composition) problem is a problem of
representation of a function $f$ by a superposition of "simpler" (in a
different meanings) set $\Omega$ of functions. In terms of circuits
theory this means a possibility of computing $f$ by a finite circuit
with 1 fan-out gates $\Omega$ of functions.

Using a discrete approximation and communication approach to this
problem we present an explicit continuous function $f$ from Deny
class, that can not be represented by a superposition of a lower
degree functions of the same class on the first level of the
superposition and arbitrary Lipshitc functions on the rest
levels. The construction of the function $f$ is based on particular
Pointer function $g$ (which belongs to the uniform AC$^0$) with linear
one-way communication complexity.

ISSN 1433-8092 | Imprint