A Discrete Approximation and Communication Complexity Approach to the Superposition Problem.

Farid Ablayev, Svetlana Ablayeva: A Discrete Approximation and Communication Complexity Approach to the Superposition Problem CSIT 1999 : E/E

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 Lipshitz 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.

Copyright © 1999 by the Institute for Contemporary Education "JurInfoR-MSU". Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the CSIT copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Institute for Contemporary Education JMSUICE. To copy otherwise, or to republish, requires a fee and/or special permission from the JMSUICE.

Printed Edition

Ch. Freytag and V. Wolfengagen (Eds.): CSIT'99, Proceedings of 1st International Workshop on Computer Science and Information Technologies, January 18-22, 1999, Moscow, Russia. MEPhI Publishing 1999, ISBN 5-7262-0263-5

Electronic Edition