Trade-off Between the Boolean and Arithmetic Depths of Modulo p Functions
Igor E. Shparlinski · Birkhäuser Basel eBooks · 2003
For a polynomial \(f(X) \in \mathbb{Z}[X]\) we consider Boolean functions producing the second leftmost bit of ⌊ f ( x )⌋ p from the bit representation of x and obtain a lower bound on their sensitivity. Then a similar but a weaker bound is obtained for the sensitivity of Boolean functions producing the second leftmost bit of rational functions modulo p . These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.