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)