Sustaining Moore’s Law Through Inexactness
A Mathematical Foundation

arXiv:1705.01497v2 [cs.CC] 22 May 2017

John Augustine,1∗ Krishna Palem,2 Parishkrati1
1 Department

of Computer Science and Engineering,
Indian Institute of Technology Madras, Chennai, India.
2 Department of Computer Science, Rice University, Houston, USA.
∗ Corresponding

author; E-mail: augustine@iitm.ac.in.

Abstract
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.

Many believe that the exponential scaling afforded by Moore’s law [Moore, 1965] is reaching its limits as
transistors approach nanometer scales. Many of these limitations are based on physics based limits ranging
over thermodynamics and electromagnetic noise [Kish, 2002] and optics [Ito and Okazaki, 2000]. Given
that information technology is the prime beneficiary of Moore’s law, computers, memories, and related
chip technologies are likely to be affected the most. Given the tremendous value of sustaining Moore’s
law through information technology in a broad sense, much effort has gone into sustaining Moore’s law,
notably through innovations in material science and electrical engineering. Given the focus on information
technology, a central tenet of these innovations has been to preserve the behavior of CMOS transistors and
computing systems built from them.
While many of these innovations revolve around non-traditional materials such as graphene [Novoselov
et al., 2004, Chodos, 2004] supplementing or even replacing CMOS [Anthony, 2014], exciting developments based on alternate and potentially radical models of computing have also emerged. Notable examples
1

include DNA [Adleman, 1994, Boneh et al., 1996], and quantum computing frameworks [Benioff, 1980,
Feynman, 1982, Deutsch, 1985]. However, these exciting approaches and alternate models face a common
and potentially steep hurdle to becoming deployable technologies leading to the preeminence of CMOS as
the material of choice. This brings the importance of Moore’s law back to the fore and consequently, in the
foreseeable future, the centrality of CMOS to growth in information technologies remains.
The central theme of this paper is to develop a coherent theoretical foundation with the goal of reconciling these competing concerns. On the one hand, continuing with CMOS centric systems is widely believed
to result in hardware that is likely to be erroneous or function incorrectly in part. On the other hand, dating
back to the days of Alan Turing [1936] and explicitly tackled by von Neumann [1956], a computer — the
ubiquitous information technology vehicle — has an unstated expectation that it has to function correctly.
This expectation of computers always functioning correctly as an essential feature is at the very heart of our
alarm about the doomsday scenario associated with the end of Moore’s law. For if one can use computers
with faulty components as they are with concomitant but acceptable errors in the computation, we could
continue to use CMOS transistors albeit functioning in a potentially unreliable regime.
Over the past decade, this unorthodox approach to using a computer and related hardware such as memory built out of faulty components, and used in this potentially faulty mode, referred to as inexact computing,
has emerged as a viable alternative to coping with the Moore’s law cliff. Palem and Lingamneni [2013] and
Palem [2014] (and references therein) provide a reasonable overview of inexact computing practice. At its
core, the counterintuitive thesis behind inexactness is to note that, perhaps surprisingly, working with faulty
components can in fact result in computing systems that are thermodynamically more efficient [Palem,
2003a,b, Korkmaz et al., 2006]. This approach simultaneously appeals to another hurdle facing the sustenance of Moore’s law. Quite often referred to as the energy-wall or power-wall, energy dissipation has
reached such prohibitive levels that being able to cope with it is the predominant concern in building computer systems today. For example, to quote from an article from the New York Times [Markoff, 2015] about
the potential afforded through inexact computing: “If such a computer were built in today’s technologies,
a so-called exascale computer would consume electricity equivalent to 200,000 homes and might cost $20
million or more to operate.”
While individual technological artifacts demonstrating the viability of inexact computing might be many,
a coherent understanding of how to design algorithms — essential to using inexact computing in large scale
— and understand the inherent limits to the power of this idea are not there. Such characterizations are
typically the purview of theoretical computer science, where questions of designing efficient algorithms,
and inherent limits to being able to design efficiently are studied. While algorithm design is concerned
with finding efficient ways of solving problems, inherent limits allow us to understand what is not possible
under any circumstance within the context of a mathematically well-defined model. Understanding what is
inherent to computing in abstract terms has been a significant part of these enquiries, and has evolved into
the field referred to as computational complexity [Arora and Barak, 2009, Moore and Mertens, 2011]. In
this paper, we present a computational complexity theoretic foundation to characterizing inexactness, and to
the best of our knowledge for the first time.
As in classical complexity theory, the atomic object at the heart of our foundation is a bit of information.
However, inexactness allows something entirely novel: each bit is characterized by two attributes or dimensions, a cost and a quality. Historically, physical energy was the cost and the probability of correctness was
the quality [Palem, 2003b, 2005]. As shown in Figure 1 (originally reported in [Korkmaz et al., 2006]),
under this interpretation, a cost versus quality relationship was measured in the context of physically constructed CMOS gates. More recently, Frustaci et al. [2015] have presented a voltage-scaled SRAM along
with a characterization of the energy/error tradeoff, where, unsurprisingly, we see that the bitcell error rate

2

Energy per switching (pico Joules)

(BER) drops exponentially as Vdd increases.

0.4

0.3

0.2

0.1

0
0.65

0.7

0.75

0.8

0.85

0.9

0.95

1

p

Figure 1: The quality-cost relationship referred to as the energy-probability relationship (e-p relationship) of a CMOS
switch from [Akgul et al., 2006, Korkmaz et al., 2006], where the energy spent e increases exponentially with increasing probability of correctness
p. Specifically, from [Korkmaz et al., 2006], the probability the operation is correct

p = 1 − 12 erfc 2V√dd2σ , where Vdd is the supply voltage, σ is the standard deviation of additive gaussian noise, and
R∞
2
the complementary error function erfc(x) = √2π x e−u du.

From a historical perspective, our work here builds naturally on the entire theme of computing or reasoning in the presence of uncertainty [Feige et al., 1994, Kenyon and King, 1994], which is concerned about
computing reliably in the presence of erroneous or uncertain information. In this context, the bits in question
have one of our two dimensions, quality alone. As a bit is read, depending on the (unspecified) circumstance,
it can be erroneous with a certain probability. However, early work in inexactness (see Figure 1) showed
that error or quality can in fact be a parameter that can be related through the underlying physics (thermodynamics) to a cost, namely energy. Thus, our work can be viewed as an extension of classical theoretical
foundations to reasoning about uncertainty, to one where we can trade uncertainty with cost: less uncertain
being typically much more expensive! In this sense, the degree of uncertainty of cost is an attribute that we
can trade-off based on what we wish to pay, as opposed to an externally imposed quantity that we are forced
to live with — the theme of prior work in this domain.
In order to have a clear basis for our discussion on computing, let us define a computational problem as
evaluating a Boolean function f : {0, 1}n → Z. Although quite elementary, such Boolean functions possess
the ability to succinctly encode input/output structure of problems in computing without compromising any
of the mathematical rigor needed for careful analysis [O’Donnell, 2014]. Evaluating a Boolean function
f can be represented as a truth table Tf with 2n rows corresponding to each possible n-bit vector, and
n + 1 columns; we will use cf (i, j) (or just c(i, j) when clear from context) to denote the jth element in
the ith row of Tf . The first n columns correspond to the n input bit positions and the (n + 1)th column
represents the output. To facilitate measuring the quality of the solution we produce, we view our output as
a number in Z. Since we are interested in inexact computing, let us suppose that an algorithm outputs f 0 (I)
for an input string I ∈ {0, 1}n , which could be different from the correct output f (I). Then, the absolute
difference |f (I) − f 0 (I)| captures the magnitude of error. Although algorithms we consider in this paper
are deterministic, it must be noted that the magnitude of error will be a random variable because input bits
3

can be read incorrectly with some probability.
Let us consider some elementary examples of Boolean functions. The OR problem for instance takes n
bits as input and outputs a 1 except when all input bits are zeros. The Unary Evaluation problem (or UE in
short)
the number of 1’s in the input, while Binary Evaluation problem (or BE in short) outputs
Pn−1 outputs
i
i=0 2 bi , where (bn−1 , bn−2 , . . . , b0 ) is the input bit string. These problems can be succinctly captured in
truth table representation as show in Table 1.
Table 1: Truth table indicating the input and output for OR, UE, and BE.

b2
0
0
0
0
1
1
1
1

b1
0
0
1
1
0
0
1
1

b0
0
1
0
1
0
1
0
1

OR
0
1
1
1
1
1
1
1

UE
0
1
1
2
1
2
2
3

BE
0
1
2
3
4
5
6
7

Let us now impose the two dimensions of cost and quality upon computational problems. Let us suppose
that we invest a cost (or energy) ei on each bit bi . Under finite values of ei , there will be a loss in quality of
the bits. Therefore, our view of the input bits will be restricted to an approximate bit vector (b00 , b01 , . . . , b0n ).
We then (inspired by [Akgul et al., 2006]) model the quality in probabilistic terms as:
Pr[bi 6= b0i ] = 2−ei .
Thus, under a finite energy budget, the outcome will be an approximation with the quality of the approximation increasing as the energy budget is increased.
Let us now consider a thought experiment that brings out two different modes in which algorithms can
operate via a novel and elegant use of permutation groups. Our algorithm must assign each input bit with
an energy value such that the total energy is within some finite budget. Suppose an adversary has the power
to permute the energy values (but not the associated bits) by choosing a permutation π uniformly at random
from some permutation group G (with the two extremes, the identity permutation In and the symmetric
group Sn , being of most interest). This will imply that the energy values associated with each bit could
change. The algorithm is aware of G, but not the exact permutation π chosen by the adversary. The question
that comes to mind now is: how much can the adversary affect the outcome? Clearly, a well-designed
optimal algorithm will try to compensate for this adversarial intrusion in some way, but can it succeed in
mitigating the effects of this adversarial permutation?
Let us consider the OR problem. If any one of the input bits is a 1, the correct output is a 1, and in
this sense, every bit has equal impact on the output. Therefore, intuitively, an optimal algorithm under a
finite energy budget must allocate equal energy to every bit. (We will formally prove this shortly.) When
the energy values across the input bits are the same, the adversary is rendered toothless, and cannot impact
the quality of the outcome in anyway. Therefore, we say that the OR problem is symmetric under G. In
fact, it is straightforward to see that OR is symmetric even under the symmetric group Sn that captures all

4

n! permutations. With a little thought, one can also surmise that the Unary Evaluation problem is also
symmetric under Sn .
To build a contrast, let us consider the Binary Evaluation problem. When the adversary is restricted to
In , an optimal algorithm will assign more energy to bit bn−1 as its “impact” on the output can be as high
as 2n−1 . However, when the adversary is empowered with Sn , the algorithm cannot favor bit bn−1 over b0 .
Therefore, the adversary can significantly affect the quality of the output. Thus, Binary Evaluation is said
to be an asymmetric problem.
There is a curious perhaps even striking connection between the formulation above and the role that
symmetries and asymmetries played in physics at the turn of the last century. Perhaps the earliest work
that historians point to as a basis of this connection is the work of Pierre Curie more than a century ago
widely recognized as Curie’s principle [Chalmers, 1970]. Informally speaking, he ties the appearance of
phenomena to when a system is “transformed.” We can interpret this to mean that for a change of some
type to occur in the system, we need an absence of symmetries. Physicists tend to think of outcomes or
effects in terms of phenomena and so another way of interpreting Curie’s powerful concept is to note that
for a phenomenon to occur or exist, there must be inherent asymmetries in the system. In our own case,
the example of Boolean evaluation mentioned above has a curious analogical connection since the quality
of the output is the basis for observing change and, as noted above, asymmetries are an essential part of
being able to observe change—since symmetric case of the OR function for example will not exhibit any
change. Thus, in our case also, the existence of asymmetries is inherently necessary to observe changes in
the “quality” of what is being computed. We note in passing that Curie’s work is the first that we are aware
of which formally, in a mathematical sense, captures symmetries and asymmetries using a group theoretic
formulation. This approach is also reflected in our own work where we use permutation groups as a basis
for characterizing symmetries and asymmetries, as outlined above through the three examples. We remark
in passing that several conditions must hold for Curie’s principle to be applicable, which physicists have
documented extensively, and our analogical remark is a substantial simplification of the concept.
Following Curie, several historical figures in physics pursued the use of group theoretic symmetries
and asymmetries as formal tools in physics with perhaps another analogical connection to our symmetric
case—the OR problem described above. Best characterized in the work of Emmy Noether [1918] and
again based on a group theoretic foundation—Lie groups to be specific—paraphrased, Noether’s theorem
states that a physical system that embodies symmetries will result in (physical) quantities to be preserved or
conserved under transformations. Thus, changes in systems which embody such symmetries will not yield
observable changes in physical quantities of interest such as momentum and energy. In our own symmetric
case, for example in the OR problem, we can interpret the quality of the output to be preserved under the
(permutation) transformation of the energy vector stated above. Consequently, we can conclude that for
symmetric functions in our sense, the quality is conserved under such transformations. We wish to add that
our own framework in this paper was inspired by the style of thinking central to symmetries and symmetry
breaking in physics as exemplified by the two cases discussed above, but that the connection is analogical—
we do not wish to imply any novel insights in the physics domain based on our work presented in the sequel.
While we illustrated symmetry and asymmetry at the two extremes (OR and UE at one end and BE at
the other), we can clearly envision a host of intermediate problems for which the symmetry is broken at
various levels. We capture the level to which the symmetry can be broken by a parameter called the measure
of broken symmetry or MoBS, which we formally define shortly. We show that the MoBS for symmetric
problems like OR and UE is 1, but exponential in n for asymmetric problems like BE. (See Table 2 for a
complete listing of results.)

5

Problem Name
OR Problem
Unary Evaluation
Binary Evaluation
Comparison two k-bit numbers
Sorting k-bit numbers

MoBS
1
1
Ω(n)
2
)
2Ω(k)
2Ω(k)

Table 2: The MoBS of problems showing dramatic difference under asymmetric situations.

1

Computational Model and a Related Property

Going beyond traditional notions of algorithms designed for exact inputs, in our model of computation, we
empower our algorithms with the ability (within well-defined bounds) to statistically alter noise characteristics in the input data and adapt its computational steps accordingly. We allow an algorithm A to work
withinP
an energy budget E. Given E, the algorithm must specify an energy vector E A = (e0 , e1 , . . . , en−1 )
(with j ej ≤ E) that will be used for reading the n input bits. Moreover, the algorithm is also aware
of the permutation group P A that will be employed for permuting the energy vector. Let σ be a permutation drawn uniformly at random from P A . Let us denote the energy vector E A permuted by σ as
~ A = (eσ(0) , eσ(1) , . . . , eσ(n−1) ). Algorithm A does not have direct access to the input row i in the truth
E
σ
table, but rather receives the input row after the energy vector EσA has been applied to i. More precisely,
each cell c(i, j) is read correctly with probability 1 − 2−eσ(j) and incorrectly with probability 2−eσ(j) . Note
that while A is aware of the permutation group P A , the exact permutation σ is not revealed to A. When
P A contains only the identity permutation, we say that A is clairvoyant because the adversary is incapable
of hiding or altering the association between energy values and bit positions. Otherwise, we say that A is
blindfolded by P A . When P A = Sn , the symmetric group defined on all n! permutations, we simply say
that A is blindfolded. One may astutely wonder if the use of the permutation group is somehow restricting
the adversary. We emphasize that this is not the case. We will go on to show that the best algorithm in the
blindfolded setting elegantly corresponds to the traditional computational model in which equal energy is
invested in each bit.
Let us now consider how algorithm A can compute f . We interpret the behavior of A as an attempt to
decipher either the input row i that was fed in as the input or another row that produces the same output.
Let us suppose that A concludes that the input row is A(i). We restrict A to behave deterministically even
though the input row that it actually sees is random due to the application of EσA . Therefore, we can view
c(A(i), n) as a random variable over the set of all legal output values, i.e., all values in the nth column of Tf ,
but the randomness is over the probability space induced by E A and P A . Thus, the worst case probability
that A is incorrect is maxi Pr[c(A(i), n) 6= c(i, n)] and the quality of the algorithm Q(A) (which in this
case can be interpreted as the expected number of correct executions in the worst case taken over all input
rows before we see an incorrect execution) is simply mini (1/Pr[c(A(i), n) 6= c(i, n)]).
In the clairvoyant setting, each bit j is read incorrectly with probability 2−ej and therefore, a clairvoyant
algorithm can assign energy in proportion to the correctness required for bit j. Let us now consider the
consequence of blindfolding an algorithm.
Claim 1.1 (Blindfolding Claim). WhenP
we blindfold an algorithm, the probability that any bit is read incorrectly is at least 2−E/n , where E = j ej .

6

Proof. As a result of the blindfolding, each of the n entries
energy vector is applied with equal probP in the −e
ability and therefore, Pr[jth bit is read incorrectly] = j (1/n)2 σ(j) , where σ is a random permutation.

1/n
P
n−1 −eσ(j)
Since the arithmetic mean is at least the geometric mean, j (1/n)2−eσ(j) ≥ Πj=0
= 2−E/n
2
as claimed.
The implication of this claim is that the probability of error in each bit cannot be improved by employing
an energy vector with non-uniform energy entries. This means that the best algorithm under the blindfolded
setting corresponds to the current trend in computing whereby equal effort or energy is expended in reading
each bit, but the clairvoyant setting opens up the possibility for variations. To capture a sense of the price
we pay when employing uniform energy vectors, we define the measure of broken symmetry (MoBS) for
computing f as
Pr[c(BFE (i), n) 6= c(i, n)]
MoBS(f ) = max max
,
i Pr[c(CVE (i), n) 6= c(i, n)]
E
where CVE and BFE are the optimal clairvoyant and optimal blindfolded algorithms, resp., while both are
restricted to an energy budget of E. When MoBS(f ) = 1 for the problem of computing some function f ,
then, we can infer that computing f is identical under both the clairvoyant and the blindfolded setting. This
reveals an inherent symmetry in the problem.

2

Symmetric Problems

To see how the notion of MoBS helps us understand the applicability of non-uniform energy distributions,
let us consider two fundamental canonical problems. Consider first the Unary Evaluation problem (in
short UE problem) that requires us to count the number k of bits set to 1. Consider the optimal clairvoyant
algorithm CV and let us say that it employs energy vector ECV = (e0 , e1 , . . . , en−1 ). Let (b0 , b1 , . . . , bn−1 )
be the input vector and (b00 , b01 , . . . , b0n−1 ) be the vector read by the algorithm CV under the energy vector
ECV .
P
We claim that ECV is in fact the uniform vector in which each ej = E/n, where E = j ej is the
total energy budget. For the sake of contradiction, let us assume an arbitrary ECV . Consider bit j. Since
Pr[bj 6= b0j ] = 2−ej , we can extend this to stating that Pr[bj = 1] = b0j (1 − 2−ej ) + (1 − b0j )2−ej . Define
Poisson trial variable Xi that takes the value 1 with probability b0j (1 − 2−ej ) + (1 − b0j )2−ej and 0 otherwise.
Since P
each bit j is readP
independently of other bits, the algorithm can be viewed as optimizing how well
X = j Xj estimates j bj . Since X is the sum of n Poisson trials, we can get the optimal estimation by
minimizing the variance of X. Notice that Var[Xj ] = (1 − 2−ej )2−ej . Notice that for any two positions
0
0
j and j 0 , their combined variance Var[Xj ] + Var[Xj0 ] = (1 − 2−ej )2−ej + (1 − 2−ej )2−ej is minimized
when ej = e0j when ej + e0j is fixed. This can be easily extended to computing Var[X] where we can show
that the variance is minimized when ej = E/n for every j. We can therefore claim that CV uses a uniform
energy vector. Thus, MoBS(Unary Evaluation) = 1 because the same optimal algorithm can be employed
in the blindfolded setting.
More generally, MoBS(f ) = 1 for all symmetric Boolean functions f where the outcome f (I) equals
f (σ(I)), where σ is any permutation of the input bits I [O’Donnell, 2014]. The OR problem discussed
earlier is a canonical example. But the set of symmetric problems is larger than the the set of symmetric
Boolean functions. Consider for example, the Tribes problem where (in a simplified sense), the n input bits
are partitioned into two tribes: the first n/2 bits and the second n/2 bits. The output of the Tribes function
is a one iff at least one of the tribes consists of all 1 bits. This function is not a symmetric Boolean function
7

as is witnessed by Tribes(0011)=1 while Tribes(0101)=0. However, the problem of evaluating the Tribes
function is a symmetric problem.

Problems that evaluate
symmetric Boolean func4ons

Set of all
asymmetric
problems
Set of all symmetric problems
with
MoBS
exponen4al
in n.
with MoBS=1
Set of all problems that evaluate Boolean func4ons
Figure 2: A Venn diagram showing the various classes of computational problems that evaluate Boolean functions.

3

Asymmetric Problems

Thankfully, most real-world problems have quite the opposite structure wherein there is significant benefit
to employing non-uniform energy
To illustrate this, consider Binary Evaluation (or BE for short)
P vectors.
j b , which arguably is the most fundamental problem. Clearly, the
2
where we have to compute n−1
j
j=0
(n − 1)th bit has impact 2j , which is significantly more important than the 0th bit and therefore displays a
marked difference from the Unary Evaluation. One can intuitively see that non-uniform energy distribution
ought to provide significant improvement.
In order to formalize this intuition about Binary Evaluation, consider an energy budget of E = n(n +
1)/2. The blindfolded algorithm will use e = (n + 1)/2 unitsPof energy for each bit. The behavior of the
blindfolded algorithm can be viewed as essentially evaluating j wj (b0j (1 − 2−e ) + (1 − b0j )2−e ). Without
loss in generality, if we assume that bit b0n−1 = 0, then, the expected evaluated quantity — taking just the
most significant bit into account and also noting that wn−1 = 2n−1 — is at least 2n−1 ·2−(n+1)/2 = 2(n−3)/2 .
However, in the clairvoyant
setting, we can set ej = j + 1, which respects the energy budget constraint. The
P
−j−1
expected error is j wj 2
= n/2. Under characteristic quality function defined as the reciprocal of the
expected error, therefore, MoBS(BE) = Ω(2n/2 /n). (This analysis is based on the unpublished work by
Chakrapani and Palem [2011].)
Let us similarly analyze Comparison, the problem of comparing two k = n/2 bit numbers x and
y to evaluate which one is larger. In the inexact computing perspective, it is more important to distinguish the two numbers when they are far apart, i.e., when |x − y| is large, than when they are very
8

close to each other. With that perspective in mind, we define the quality function to be 1/(|x − y| ·
Pr[x and y are incorrectly compared]). Let us consider an energy budget of k(k + 1)/2. Under the blindfolded setting, each bit-wise comparison will get (k +1)/2 units of energy, but in the quality optimal setting,
we can assign j + 1 units of energy for comparing jth bit positions, 0 ≤ j ≤ k − 1. Extending the argument
from BE, we will get MoBS(Comparison) = 2Ω(n) .
Let us now consider the Sorting problem that takes L numbers (x1 , x2 , . . . , xL ), each k bits long, and
reorders them in non-decreasing order. This will make the total number of input bits n = kL. Consider
a pair of numbers x`1 and x`2 , `1 6= `2 . As in the case of Comparison, we can tolerate the two numbers
being wrongly ordered in the output sequence when |x`1 − x`2 | is small, but not when the difference is large.
Thus, as a natural extension to the quality function defined for Comparison, we consider the following
as the quality function for Sorting wherein the probability of error in the ordering of a pair of numbers is
weighted by their magnitude difference:
1
.
`1 <`2 (|x`1 − x`2 | · Pr[x`1 and x`2 are wrongly ordered])

QSorting = P

(1)

Consider the input in which L/2 of the numbers are of the binary form (100 · · · 0) and the remaining are
of the form (000 · · · 0). There are at least L2 /4 pairs that we call expensive pairs for which the absolute
magnitude difference is 2k−1 . Let us now consider the expensive pairs under the blindfolded and the quality
optimal scenarios. Extending the ideas from comparison, their probabilities of wrongly comparing an expensive pair under the blindfolded setting is at least 2−(k+1)/2 . In the quality optimal setting, however, the
probability will reduce to 2−k . Substituting these probability values into Equation 1 and subsequently into
the formula for MoBS, we get:

P
−(k+1)/2
`1 and `2 are expensive |x`1 − x`2 | · 2
P
MoBS(Sorting) ≥
= 2Ω(k) .
(2)
−k )
(|x
−
x
|
·
2
`1
`2
`1 and `2 are expensive

Remarks
Our work is built on the complexity theoretic philosophy of understanding the inherent resource needs
of problems under various computational models, and classifying them based on those insights. From a
utilitarian perspective, we now know that symmetric problems will not lead to significant gains from the
principles of inexact computing. Thankfully, most real world problems display quite a bit of asymmetry
where, we believe, opportunities abound, thus opening the door for future work in optimization techniques
a practitioner may employ. Moreover, hardware that is capable of trading error for energy is not just a
theoretical possibility, but a reality with several groups spanning industry and academia actively pursuing
their fabrication. In fact, our model with its emphasis on memory errors is in fact a reflection of current
pursuits in memory technology [Frustaci et al., 2015].
Finally, for clarity, we have focussed on problems where the quality of bits are probabilistically independent of each other, but this is somewhat simplistic as evidenced for example by the effect of carry
propagating through adders [Chakrapani, 2008, Parishkrati, 2016]. Arbitrary Boolean functions are likely to
be riddled with much more complex dependencies and we believe that there is significant scope for future
work.

9

Acknowledgements
We thank Dror Fried, Anshumali Shrivastava, and Eli Upfal for providing us with useful comments. We also
thank Jeremy Schlachter for using the analytical model from [Korkmaz et al., 2006] to recreate Figure 1.

References and Notes
Leonard M Adleman. Molecular computation of solutions to combinatorial problems. Nature, 369:40, 1994.
B. E. S. Akgul, L. N. Chakrapani, P. Korkmaz, and K. V. Palem. Probabilistic cmos technology: A survey and future
directions. In 2006 IFIP International Conference on Very Large Scale Integration, pages 1–6, Oct 2006. doi:
10.1109/VLSISOC.2006.313282.
Sebastian Anthony. IBM builds graphene chip that’s 10,000 times faster, using standard cmos processes, Jan 2014.
URL http://www.extremetech.com/extreme/175727-ibm-builds-graphene-chip-thats10000-times-faster-using-standard-cmos-processes.
Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, New
York, NY, USA, 1st edition, 2009. ISBN 0521424267, 9780521424264.
Paul Benioff. The computer as a physical system: A microscopic quantum mechanical hamiltonian model of computers
as represented by turing machines. Journal of Statistical Physics, 22(5):563–591, 1980.
Dan Boneh, Christopher Dunworth, Richard J. Lipton, and Jirı́ Sgall. On the computational power of dna. Discrete
Applied Mathematics, 71(1):79 – 94, 1996. ISSN 0166-218X. URL http://www.sciencedirect.com/
science/article/pii/S0166218X96000583.
Lakshmi N. Chakrapani. Probabilistic boolean logic, arithmetic and architectures. PhD thesis, Georgia Institute of
Technology, 2008.
Lakshmi N. Chakrapani and Krishna V. Palem. Probabilistic arithmetic and computing at the nanoscale. Unpublished
manuscript., 2011.
A. F. Chalmers. Curie’s principle. The British Journal for the Philosophy of Science, 21(2):133–148, 1970. ISSN
00070882, 14643537. URL http://www.jstor.org/stable/686695.
Alan Chodos, editor. Discovery of Graphene, volume 18, October 2004. American Physical Society News.
David Deutsch. Quantum theory, the church-turing principle and the universal quantum computer. In Proceedings of
the Royal Society of London A: Mathematical, Physical and Engineering Sciences, volume 400, pages 97–117. The
Royal Society, 1985.
Uriel Feige, Prabhakar Raghavan, David Peleg, and Eli Upfal. Computing with noisy information. SIAM Journal on
Computing, 23(5):1001–1018, 1994.
Richard P Feynman. Simulating physics with computers. International journal of theoretical physics, 21(6):467–488,
1982.
Fabio Frustaci, Mahmood Khayatzadeh, David Blaauw, Dennis Sylvester, and Massimo Alioto. Sram for error-tolerant
applications with dynamic energy-quality management in 28 nm cmos. IEEE Journal of Solid-State Circuits, 50
(5):1310–1323, May 2015. ISSN 1558-173X. doi: 10.1109/jssc.2015.2408332. URL http://dx.doi.org/
10.1109/JSSC.2015.2408332.
Takashi Ito and Shinji Okazaki. Pushing the limits of lithography. Nature, 406(6799):1027–1031, 2000.

10

Claire Kenyon and Valerie King. On boolean decision trees with faulty nodes. Random Structures and Algorithms, 5
(3):453–464, 1994. ISSN 1098-2418.
Laszlo B Kish. End of moore’s law: thermal (noise) death of integration in micro and nano electronics. Physics
Letters A, 305(3–4):144 – 149, 2002. URL http://www.sciencedirect.com/science/article/pii/
S0375960102013658.
Pinar Korkmaz, Bilge E. S. Akgul, Krishna V. Palem, and Lakshmi N. Chakrapani. Advocating noise as an agent
for ultra-low energy computing: Probabilistic complementary metal–oxide–semiconductor devices and their characteristics. Japanese Journal of Applied Physics, 45(4S):3307, 2006. URL http://stacks.iop.org/13474065/45/i=4S/a=3307.
John Markoff. A climate-modeling strategy that won’t hurt the climate, May 2015.
Cristopher Moore and Stephan Mertens. The Nature of Computation. Oxford University Press, 2011.
G. E. Moore. Cramming more components onto integrated circuits. Electronics, 38(8):114–117, April 1965.
Emmy Noether. Invariante variationsprobleme. Mathematisch-Physikalische Klasse, pages 235–257, 1918.
K. S. Novoselov, A. K. Geim, S. V. Morozov, D. Jiang, Y. Zhang, S. V. Dubonos, I. V. Grigorieva, and A. A.
Firsov. Electric field effect in atomically thin carbon films. Science, 306(5696):666–669, 2004. URL http:
//science.sciencemag.org/content/306/5696/666.
Ryan O’Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014.
K. V. Palem. Energy aware computing through probabilistic switching: a study of limits. IEEE Transactions on
Computers, 54(9):1123–1137, Sept 2005. ISSN 0018-9340.
Krishna Palem and Avinash Lingamneni. Ten years of building broken chips: The physics and engineering of inexact
computing. ACM Trans. Embed. Comput. Syst., 12(2s):87:1–87:23, May 2013. ISSN 1539-9087. doi: 10.1145/
2465787.2465789. URL http://doi.acm.org/10.1145/2465787.2465789.
Krishna V. Palem. Energy Aware Algorithm Design via Probabilistic Computing: From Algorithms and Models to
Moore’s Law and Novel (Semiconductor) Devices, pages 216–216. Springer Berlin Heidelberg, Berlin, Heidelberg,
2003a. ISBN 978-3-540-24596-4.
Krishna V. Palem. Computational Proof as Experiment: Probabilistic Algorithms from a Thermodynamic Perspective,
pages 524–547. Springer Berlin Heidelberg, Berlin, Heidelberg, 2003b. ISBN 978-3-540-39910-0.
Krishna V. Palem. Inexactness and a future of computing. Philosophical Transactions of the Royal Society of London
A: Mathematical, Physical and Engineering Sciences, 372(2018), 2014.
Parishkrati. Exploiting asymmetry in computing. Master’s thesis, Indian Institute of Technology Madras, 2017.
Alan Mathison Turing. On computable numbers, with an application to the entscheidungsproblem. J. of Math, 58
(345-363):5, 1936.
John Von Neumann. Automata Studies, chapter Probabilistic logics and the synthesis of reliable organisms from
unreliable components, pages 43–98. Princeton University Press, 1956.

11

