|| Neural Network Computations with DOMINATION Functions
||Kordag Mehmet Kilic, Jehoshua Bruck, California Institute of Technology, United States|
||D3-S1-T3: Neural Estimation
||Wednesday, 14 July, 22:00 - 22:20
||Wednesday, 14 July, 22:20 - 22:40
We study a new representation of neural networks based on DOMINATION functions. Specifically, we show that a threshold function can be computed by its variables connected via an unweighted bipartite graph to a universal gate computing a DOMINATION function. The DOMINATION function consists of fixed weights that are ascending powers of 2. We derive circuit-size upper and lower bounds for circuits with small weights that compute DOMINATION functions. Interestingly,the circuit-size bounds are dependent on the sparsity of the bipartite graph. In particular, functions with sparsity 1 (like the EQUALITY function) can be implemented by small-size constant-weight circuits.