Information Technology Reference
In-Depth Information
Chapter 5
A Selection of Lower Bounds
for Arithmetic Circuits
Neeraj Kayal and Ramprasad Saptharishi
It is convenient to have a measure of the amount of work
involved in a computing process, even though it may be a very
crude one …We might, for instance, count the number of
additions, subtractions, multiplications, divisions, recordings of
numbers,…
from
Rounding-off errors in matrix processes,
Alan M. Turing, 1948
Abstract
This article is a survey of techniques used in arithmetic circuit lower
bounds.
·
·
·
Keywords
Arithmetic circuits
Lower bounds
Determinant
Permanent
Mathematics Subject Classification (2010)
Primary 68Q25, 68W30, Secondary
12E05
5.1 Introduction
Polynomials originated in classical mathematical studies concerning geometry and
solutions to systems of equations. They feature in many classical results in algebra,
number theory, and geometry—e.g. in Galois and Abel's resolution of the solvability
To Somenath Biswas, on his 60th Birthday.
