On (not) computing the Mobius function using bounded depth circuits

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, 等
出版事項: (2006)

The Mobius function is strongly orthogonal to nilsequences
著者:: Green, B, 等
出版事項: (2008)

Compact Circuits for Efficient Möbius Transform
著者:: Subhadeep Banik, 等
出版事項: (2024-03-01)

Sharp bounds on partition dimension of hexagonal Möbius ladder
著者:: Muhammad Azeem, 等
出版事項: (2022-02-01)

On Möbius gyrogroup and Möbius gyrovector space
著者:: Kurosh Mavaddat Nezhaad, Ali Reza Ashrafi
出版事項: (2023-11-01)

Mobius
著者:: Mathematical Association of South Australia
出版事項: (1967)

Mobius syndrome
著者:: Nirankari M, 等
出版事項: (1963-01-01)

Mobius propeller
著者:: Leonid I. Gretchihin, 等
出版事項: (2014-04-01)

On the Möbius function in all short intervals
著者:: Matomäki, K, 等
出版事項: (2022)

On the Möbius invariant principal functions of Pincus
著者:: Sagar Ghosh, 等
出版事項: (2024-02-01)

The Möbius function of generalized subword order
著者:: Peter R. W. McNamara, 等
出版事項: (2012-01-01)

SIGN PATTERNS OF THE LIOUVILLE AND MÖBIUS FUNCTIONS
著者:: KAISA MATOMÄKI, 等
出版事項: (2016-01-01)

Möbius invariant gradient and α-Bloch functions(Möbius不变梯度和α-Bloch函数)
著者:: ZHUOWen-xin(卓文新), 等
出版事項: (2002-07-01)

Univalent Functions in the Möbius Invariant QK Space
著者:: Fernando Pérez-González, 等
出版事項: (2011-01-01)

Homotopy properties of smooth functions on the Möbius band
著者:: Iryna Kuznietsova, 等
出版事項: (2019-10-01)

Characterizing completely multiplicative functions by generalized Möbius functions
著者:: Vichian Laohakosol, 等
出版事項: (2002-01-01)

Mobius inversion in physics /
著者:: Chen, Nanxian, 1937-
出版事項: (c201)

MRI in Mobius Syndrome
著者:: J Gordon Millichap
出版事項: (2000-10-01)

Expanded Mobius Syndrome
著者:: J Gordon Millichap
出版事項: (2001-06-01)

The Formulas of Möbius-Bretschneider and Möbius-Cagnoli in the Poincaré Disc Model of Hyperbolic Geometry
著者:: Gülcan Balakan, 等
出版事項: (2021-02-01)

Iterating the Sum of Möbius Divisor Function and Euler Totient Function
著者:: Daeyeoul Kim, 等
出版事項: (2019-11-01)

Continuous Quasi Gyrolinear Functionals on Möbius Gyrovector Spaces
著者:: Keiichi Watanabe
出版事項: (2020-01-01)

Ramanujan sums via generalized Möbius functions and applications
著者:: Vichian Laohakosol, 等
出版事項: (2006-01-01)

Fractional Calculus of Analytic Functions Concerned with Möbius Transformations
著者:: Nicoleta Breaz, 等
出版事項: (2016-01-01)

Algorithms of the Möbius function by random forests and neural networks
著者:: Huan Qin, 等
出版事項: (2024-02-01)

A characterization of Möbius transformations
著者:: Piyapong Niamsup
出版事項: (2000-01-01)

Möbius convolutions and the Riemann hypothesis
著者:: Luis Báez-Duarte
出版事項: (2005-01-01)

The Möbius Invariant QTH Spaces
著者:: Munirah Aljuaid
出版事項: (2023-03-01)

Feedback Numbers of Möbius Ladders
著者:: Wang Yijin, 等
出版事項: (2019-01-01)

Möbius梯的(d, 1)-全标号((d, 1)-total labelings of the Möbius Ladders)
著者:: LÜDa-mei(吕大梅), 等
出版事項: (2013-07-01)

Computational limitations for small depth circuits
著者:: Håstad, Johan.
出版事項: (2023)

Optical bistability in mobius microring resonator /
著者:: Ahmad Fakhrurrazi Ahmad Noorden, 1990- author, 等
出版事項: (2015)

Transposition Of Great Vessels And Mobius Syndrome
著者:: J Gordon Millichap
出版事項: (1988-12-01)

Mobius Syndrome and Autistic Spectrum Disorder
著者:: J Gordon Millichap
出版事項: (2001-06-01)

Orthogonal Gyroexpansion in Möbius Gyrovector Spaces
著者:: Keiichi Watanabe
出版事項: (2017-01-01)

…Comic Books, Möbius Strips, Philosophy and…
著者:: Ian Hornsby
出版事項: (2019-04-01)

Faces da Banda de Möbius
著者:: José Carlos Pinto Leivas, 等
出版事項: (2019-06-01)

Poland-Mobius syndrome in an infant girl
著者:: Al-Mazrou Khalid, 等
出版事項: (2009-01-01)

Absorption modes of Möbius strip resonators
著者:: Joshua K. Hamilton, 等
出版事項: (2021-04-01)

Möbius Syndrome: Misoprostol Use and Speech and Language Characteristics
著者:: Zelita Caldeira Ferreira Guedes
出版事項: (2014-03-01)