Mathematics of computation through the lens of linear equations and lattices

Abstract

Mathematics of computation and, in particular, computational complexity theory, is a fundamental research area in the intersection of computer science and mathematics.

The area revolves around classifying computational problems as feasible or alternatively as infeasible, typically in the worst-case regime.

In some related areas—and even more prominently in practice—the notion of average-case complexity is ubiquitous.

Cryptography is a prime example where proving security of protocols/primitives often necessitates average-case type hardness assumptions.

We take the choice herein to analyze these notions through the lens of linear algebra. This perspective allows us to smoothly present important future research directions, as well as propose conjectures that lay a road-map for future progress.

The goal of this survey is to make research at the core of computation more accessible. More importantly, it gives us an opportunity to naturally state open questions regarding lattices; a solution to which would transform our perception of computation, not only scientifically, but also practically.