TR98-050 Authors: Farid Ablayev, Svetlana Ablayeva

Publication: 30th August 1998 09:10

Downloads: 3824

Keywords:

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.