Trade-Offs Between Energy and Depth of Neural Networks, NEURAL COMPUTATION, 36(8) 1541-1567, 2024.07

Uchizawa, K; Abe, H

Single Author

Energy and Output Patterns in Boolean Circuits, Lecture Notes in Computer Science, 14637 185-196, 2024.05

Jayalal Sarma, Kei Uchizawa

Multiple Authorship (Including Foreigners)

Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR Functions, THEORY OF COMPUTING SYSTEMS, 67(3) 569-591, 2023.06

Ogihara, M; Uchizawa, K

Multiple Authorship (Including Foreigners)

Exponential Lower Bounds for Threshold Circuits of Sub-Linear Depth and Energy, Proceedings of 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), - , 2023

内沢 啓

Single Author

An <i>O</i>(<i>n</i>²)-Time Algorithm for Computing a Max-Min 3-Dispersion on a Point Set in Convex Position, IEICE Transactions on Information and Systems, E105D(3) 503-507, 2022.03

KOBAYASHI Yasuaki, NAKANO Shin-ichi, UCHIZAWA Kei, UNO Takeaki, YAMAGUCHI Yutaro, YAMANAKA Katsuhisa

Single Author

LA/EATCS Best Presentation Award, 2019.02, Japan

Grant-in-Aid for Scientific Research(C)，2022.04 - 2025.03

Grant-in-Aid for Scientific Research(C)，2019.04 - 2022.03

Grant-in-Aid for Scientific Research(C)，2016.04 - 2019.03

Foundation of algorithm designs for artificial neural networks，2019.04 - 2022.03，Foundation of algorithm designs for artificial neural networks

We consider computational tasks of deciding if a given neural network possesses various predefined mathematical properties, and investigate how many computational resources are required to compute them. We then show that there exists a property for which it can be computationally very hard to check even if a given neural network is extremely simple (i.e., a neural network is of a single neuron). We also show that another property is computationally hard to check when a given neural network has two layers, while the property is easy to check (solvable in polynomial time) when a given neural network consists of a single neuron. Our results theoretically confirm that extracting information from multi-layer neural network can be computationally very hard.

Japan Society for the Promotion of Science

Limitation of Threshold Circuits designed for Machine Learning，2016.04 - 2019.03，Limitation of Threshold Circuits designed for Machine Learning

In this research, we theoretically investigate a question why neural networks of large depth obtained by a machine learning method show significant performance for various tasks. We consider a particular type of neural networks, called threshold circuits, and then provide mathematical proofs which suggest that large depth contributes to the performance of threshold circuits that carry out (somewhat artificial) information processing. As part of the proofs, we also show detailed constructions (that is, placement of neural computational elements and their connections) of threshold circuits that are guaranteed to be achieve good performance for the information processing.

Japan Society for the Promotion of Science

Computational Complexity Theory for Neural Networks