On (not) computing the Mobius function using bounded depth circuits
Any function F : {0,...,N-1} -> {-1,1} such that F(x) can be computed from the binary digits of x using a bounded depth circuit is orthogonal to the Mobius function mu in the sense that E_{0 <= x <= N-1} mu(x)F(x) = o(1). The proof combines a result of Linial, Mansour and Nisan...
מחבר ראשי: | Green, B |
---|---|
פורמט: | Journal article |
יצא לאור: |
2011
|
פריטים דומים
-
Quadratic Uniformity of the Mobius Function
מאת: Green, B, et al.
יצא לאור: (2006) -
The Mobius function is strongly orthogonal to nilsequences
מאת: Green, B, et al.
יצא לאור: (2008) -
Compact Circuits for Efficient Möbius Transform
מאת: Subhadeep Banik, et al.
יצא לאור: (2024-03-01) -
Sharp bounds on partition dimension of hexagonal Möbius ladder
מאת: Muhammad Azeem, et al.
יצא לאור: (2022-02-01) -
On Möbius gyrogroup and Möbius gyrovector space
מאת: Kurosh Mavaddat Nezhaad, Ali Reza Ashrafi
יצא לאור: (2023-11-01)