Abstract:
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.