Memory required to perform a computational task is one of the most fundamental measures used by theoretical computer scientists to assess how difficult a task is. Nevertheless, in practice, memory optimization received limited attention until the emergence of big data applications. More recently, the rapid growth of large-scale machine learning (ML) systems, including large language models (LLMs), has pushed model parameter counts far beyond improvements in memory hardware, raising concerns that memory may soon become the primary bottleneck in serving them. This growing need for memory-efficient alternatives is further amplified by interest in on-device learning, driven by concerns over data security, transmission costs, and the demand for personalized applications. The field of learning theory has already deeply explored the data and time required for various ML tasks; however, our understanding of their memory requirements remains limited. The goal of this project is to systematically address this gap and develop a foundational theory of the capabilities and limits of memory-constrained learning. The new approaches explored in the project aims to unconditionally answer whether the data and time requirements to learn drastically increase when using low-memory algorithms – which include the commonly used methods in practice such as stochastic gradient descent. This project draws tools from various mathematical areas such as complexity theory, learning theory and information theory. The educational plan of this project involves training of undergraduate and graduate students through (1) foundational courses in theoretical computer science (TCS), as well as advanced courses at the intersection of these mathematical areas, and (2) supervised undergraduate and graduate research aligned with the themes of this project. The first two thrusts of this project will systematically characterize the memory requirements of fundamental supervised and unsupervised machine learn