| Paper ID | D3-S1-T3.2 |
| Paper Title |
Neural Network Computations with DOMINATION Functions |
| Authors |
Kordag Mehmet Kilic, Jehoshua Bruck, California Institute of Technology, United States |
| Session |
D3-S1-T3: Neural Estimation |
| Chaired Session: |
Wednesday, 14 July, 22:00 - 22:20 |
| Engagement Session: |
Wednesday, 14 July, 22:20 - 22:40 |
| Abstract |
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.
|
