TY - JOUR
T1 - Guest Column: Lower Bounds Against Constant-Depth Algebraic Circuits.
AU - Limaye, Nutan
AU - Srinivasan, Srikanth
AU - Tavenas, Sébastien
PY - 2022
Y1 - 2022
N2 - Given a polynomial fpx1; : : : ; xNq, we can wonder how we can evaluate it with a minimal number of arithmetic operations. Indeed, the task of the algorithm designer is to nd evolved processes which decrease this number. In the other direction, it could be interesting to be able to prove that there is no algorithm which does the computation in less than some number of operations. But how one could prove something like that? We will present here some methods which allow us to tackle the problem in the case of constant-depth algebraic circuits.
AB - Given a polynomial fpx1; : : : ; xNq, we can wonder how we can evaluate it with a minimal number of arithmetic operations. Indeed, the task of the algorithm designer is to nd evolved processes which decrease this number. In the other direction, it could be interesting to be able to prove that there is no algorithm which does the computation in less than some number of operations. But how one could prove something like that? We will present here some methods which allow us to tackle the problem in the case of constant-depth algebraic circuits.
KW - Polynomial Evaluation
KW - Arithmetic Operations
KW - Algorithmic Complexity
KW - Constant-Depth Algebraic Circuits
KW - Lower Bound Proof Techniques
U2 - 10.1145/3544979.3544989
DO - 10.1145/3544979.3544989
M3 - Journal article
SN - 0163-5700
VL - 53
JO - SIGACT News
JF - SIGACT News
IS - 3
ER -