ECCC-Report TR98-050https://eccc.weizmann.ac.il/report/1998/050Comments and Revisions published for TR98-050en-usSun, 30 Aug 1998 09:10:11 +0300
Paper TR98-050
| A Discrete Approximation and Communication Complexity Approach to the Superposition Problem |
Farid Ablayev,
Svetlana Ablayeva
https://eccc.weizmann.ac.il/report/1998/050The 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.
Sun, 30 Aug 1998 09:10:11 +0300https://eccc.weizmann.ac.il/report/1998/050