Arrow Research search

Author name cluster

A. Orlitsky

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers
1 author row

Possible papers

2

I&C Journal 1995 Journal Article

Vector Analysis of Threshold Functions

  • V. Roychowdhury
  • K.Y. Siu
  • A. Orlitsky
  • T. Kailath

Viewing n-variable Boolean functions as vectors in R 2 n, we invoke basic tools from linear algebra and linear programming to derive new results on the realizability of Boolean functions using threshold gates. Using this approach, we obtain: (1) a lower bound on the number of input functions required by a threshold gate implementing a given function; (2) a lower bound on the error incurred when a Boolean function is approximated by a linear combination of a set of functions; (3) a limit on the effectiveness of a well known lower-hound technique (based on computing correlations among Boolean functions) for the depth of threshold circuits implementing Boolean functions; (4) a construction showing that every Boolean function ƒ of n input variables is a threshold function of polynomially many input functions, none of which is significantly correlated with ƒ; (5) generalizations of some known results on threshold-circuit complexity, particularly those that are based on spectral analysis.

Details DOI

NeurIPS Conference 1990 Conference Paper

On the Circuit Complexity of Neural Networks

  • V. P. Roychowdhury
  • K. Y. Siu
  • A. Orlitsky
  • T. Kailath

'~le introduce a geometric approach for investigating the power of threshold circuits. Viewing n-variable boolean functions as vectors in 'R'2", we invoke tools from linear algebra and linear programming to derive new results on the realizability of boolean functions using threshold gat. es. Using this approach, one can obtain: (1) upper-bounds on the number of spurious memories in HopfielJ networks, and on the number of functions implementable by a depth-d threshold circuit; (2) a lower bound on the number of ort. hogonal input. functions required to implement. a threshold function; (3) a necessary condit. ion for an arbit. rary set of input. functions to implement a threshold function; (4) a lower bound on the error introduced in approximating boolean functions using sparse polynomials; (5) a limit on the effectiveness of the only known lower-bound technique (based on computing correlations among boolean functions) for the depth of thresh(cid: 173) old circuit. s implement. ing boolean functions, and (6) a constructive proof that every boolean function f of n input variables is a threshold function of polynomially many input functions, none of which is significantly cor(cid: 173) related with f. Some of these results lead t. o genera. lizations of key results concerning threshold circuit complexity, particularly t. hose that are based on the so-called spectral or Ha. rmonic analysis approach. Moreover, our geometric approach yields simple proofs, based on elementary results from linear algebra, for many of these earlier results.

PDF Details
v2026.09.13