Mathematics of computation through the lens of linear equations and lattices (Q6198651)
From MaRDI portal
scientific article; zbMATH DE number 7821717
Language | Label | Description | Also known as |
---|---|---|---|
English | Mathematics of computation through the lens of linear equations and lattices |
scientific article; zbMATH DE number 7821717 |
Statements
Mathematics of computation through the lens of linear equations and lattices (English)
0 references
20 March 2024
0 references
Summary: Mathematics of computation and, in particular, \textit{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 \textit{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 \textit{lattices}; a solution to which would transform our perception of computation, not only scientifically, but also practically. For the entire collection see [Zbl 07816360].
0 references
computational-complexity
0 references
PCP
0 references
lattices
0 references
linear-algebra
0 references
hardness-of-approximation
0 references
cryptography
0 references
0 references