2017/05/03 by John Augustine, Augustine, John, Krishna V. Palem +3
Computer Science · Mathematics · #Algorithm #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #Computer science #Data Structures and Algorithms (cs.DS) #Energy (signal processing) #FOS: Computer and information sciences #Function (biology) #Mathematics #Moore's law #Parallel Computing and Optimization Techniques #Quality (philosophy) #Quantum Computing Algorithms and Architecture #Resource (disambiguation) #Space (punctuation) #Theoretical computer science #cs.CC #cs.DS
paper · pdf · doi:10.48550/arxiv.1705.01497
openalex publication_date 2017/05/03 · arxiv created 2017/05/22 · arxiv updated 2017/05/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Inexact computing aims to compute good solutions that require considerably less resource -- typically energy -- compared to computing exact solutions. While inexactness is motivated by concerns derived from technology scaling and Moore's law, there is no formal or foundational framework for reasoning about this novel approach to designing algorithms. In this work, we present a fundamental relationship between the quality of computing the value of a boolean function and the energy needed to compute it in a mathematically rigorous and general setting. On this basis, one can study the tradeoff between the quality of the solution to a problem and the amount of energy that is consumed. We accomplish this by introducing a computational model to classify problems based on notions of symmetry inspired by physics. We show that some problems are symmetric in that every input bit is, in a sense, equally important, while other problems display a great deal of asymmetry in the importance of input bits. We believe that our model is novel and provides a foundation for inexact Computing. Building on this, we show that asymmetric problems allow us to invest resources favoring the important bits -- a feature that can be leveraged to design efficient inexact algorithms. On the negative side and in contrast, we can prove that the best inexact algorithms for symmetric problems are no better than simply reducing the resource investment uniformly across all bits. Akin to classical theories concerned with space and time complexity, we believe the ability to classify problems as shown in our paper will serve as a basis for formally reasoning about the effectiveness of inexactness in the context of a range of computational problems with energy being the primary resource.