PhD Thesis Defense

Zoom link: https://caltech.zoom.us/j/81237732737
Meeting ID: 812 3773 2737

The evolution of the human brain was one of the milestones in the history of information after the emergence of life. The underlying biological, chemical, and physical processes of the brain have amazed scientists for a long time. It is still a mystery how the human brain computes a simple arithmetical operation like $2 + 2 = 4$. This enigma has spurred investigations into understanding the intrinsic architecture of the brain.

This thesis delves into two primary models for brain architecture: Feed-forward Neural Networks and Nearest Neighbor (NN) Representations. Both models are treated under the hypothesis that our brain does not work with "large" numbers and expressive power is derived from connectivity. Thus, when examining a network or, more precisely, a single neuron model, we strive to minimize the bit resolution of weights, potentially augmenting depth or circuit complexity.

For the NN representations, the memory is defined by a set of vectors in R^n (that we call anchors), computation is performed by convergence from an input vector to a nearest neighbor anchor, and the output is a label associated with an anchor. Limited bit resolution in the anchor entries may result in an increase of the size of the NN representation.

In the digital age, computers universally employ the binary numeral system, ensuring the enduring relevance of Boolean functions. This study specifically explores the trade-off between resolution and size for the computation models for Boolean functions. It is established that ``low resolution'' models may require a polynomial or even an exponential increase in the size complexity of the ``high resolution'' model, potentially making the practical implementation unfeasible. Building upon prior research, our goal is to optimize these blow-ups by narrowing the gaps between theoretical upper and lower bounds under various constraints. Additionally, we aim to establish connections between NN representations and neural network models by providing explicit NN representations for well-known Boolean functions in Circuit Complexity Theory.