On interpolation by analytic functions with special properties andsome weak lower bounds on the size of circuits with symmetric gates

摘要

The author investigates the question of whether or not a specificBoolean function in n variables can be interpolated by ananalytic function in the same variables whose partial derivatives of allorders span a subspace of low dimension in the space of analyticfunctions. The upper and lower bounds for this dimension yield some weakcircuit lower bounds. For a particular function, anΩ(n/log n)-size lower bound is obtained for itscomputation by a circuit whose gates are symmetric. For the samefunction an Ω(n) lower bound is obtained for the circuitwith mod_k gates