Short Course Description
Mathematics of computation according to linear algebra
The course covers fundamental aspects of computation, including algorithms such as SEMIDEFINITE PROGRAMING, Approximation of Lattice Problems (LLL), Matrix Multiplication and Principal Component Analysis (PCA).
We will also discuss hardness assumptions that enable cryptography (for example, hardness of LEARNING WITH ERRORS that enable ONE WAY FUNCTIONS and public key encryption), Furthermore, discuss which problems can potentially be solved efficiently with quantum computers.
In addition, we will get to know the mathematical object of a Lattice, which in recent decades has become a cornerstone in cryptography and computer science.
We will present innovative topics and ideas at the forefront of the study of the theory of computer science. By looking through the lens of linear equation systems and linear algebra we will present a variety of topics: error correction codes, lattice encryption and encryption in the age of quantum computing, optimization and machine learning problems, lattices, and more.
The course will combine ideas from computer science with mathematics, and will expose students to contemporary research in various fields of computer science.
Course / Module topics: Linear equations - from another angle: codes, computational problems on linear equations. Error Correction Codes: Linear Codes, Reed Salomon and Reed Muller Code, Demard Code, Local Tests. Computational Complexity Using Linear Equations: CVP is difficult. Knitwear: basic definitions and attributes, Minkowski theorems, Fourier transform on knitwear, LLL algorithm. Mean complexity: Shortest Integer Solution problem, SVP to SIS complexity complexity, learning difficulties with errors (LWE) and uses of cryptography. Cryptography: Public key encryption, ONE WAY FUNCTIONS, HASH collision prevention (CRH) functions. Machine optimization and learning: SEMIDEFINITE PROGRAMING, PCA. Algorithms for multiplication of matrices, introduction to quantum computing/introduction to analysis of Boolean functions and Fourier expansion.
Full syllabus is to be published
