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
    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
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references