Skip to main content
Theoretical Computer Science

Return to Answer

replaced http://mathoverflow.net/ with https://mathoverflow.net/
Source Link
Community Bot
Community Bot
  • 1

For another non-answer, you might be interested in Sarnak’s conjecture (see e.g. http://gilkalai.wordpress.com/2011/02/21/the-ac0-prime-number-conjecture/, http://rjlipton.wordpress.com/2011/02/23/the-depth-of-the-mobius-function/, http://mathoverflow.net/questions/57543/walsh-fourier-transform-of-the-mobius-functionhttps://mathoverflow.net/questions/57543/walsh-fourier-transform-of-the-mobius-function), which basically states that Möbius function is not correlated with any “simple” Boolean function. It’s not unreasonable to expect it should hold when “simple” is interpreted as polynomial-time. What we know so far is that the conjecture holds for $\mathrm{AC}^0$-functions (proved by Ben Green), and all monotone functions (proved by Jean Bourgain).

For another non-answer, you might be interested in Sarnak’s conjecture (see e.g. http://gilkalai.wordpress.com/2011/02/21/the-ac0-prime-number-conjecture/, http://rjlipton.wordpress.com/2011/02/23/the-depth-of-the-mobius-function/, http://mathoverflow.net/questions/57543/walsh-fourier-transform-of-the-mobius-function), which basically states that Möbius function is not correlated with any “simple” Boolean function. It’s not unreasonable to expect it should hold when “simple” is interpreted as polynomial-time. What we know so far is that the conjecture holds for $\mathrm{AC}^0$-functions (proved by Ben Green), and all monotone functions (proved by Jean Bourgain).

For another non-answer, you might be interested in Sarnak’s conjecture (see e.g. http://gilkalai.wordpress.com/2011/02/21/the-ac0-prime-number-conjecture/, http://rjlipton.wordpress.com/2011/02/23/the-depth-of-the-mobius-function/, https://mathoverflow.net/questions/57543/walsh-fourier-transform-of-the-mobius-function), which basically states that Möbius function is not correlated with any “simple” Boolean function. It’s not unreasonable to expect it should hold when “simple” is interpreted as polynomial-time. What we know so far is that the conjecture holds for $\mathrm{AC}^0$-functions (proved by Ben Green), and all monotone functions (proved by Jean Bourgain).

mention monotone functions
Source Link
Emil Jeřábek
Emil Jeřábek
  • 18.6k
  • 3
  • 64
  • 97

For another non-answer, you might be interested in Sarnak’s conjecture (see e.g. http://gilkalai.wordpress.com/2011/02/21/the-ac0-prime-number-conjecture/, http://rjlipton.wordpress.com/2011/02/23/the-depth-of-the-mobius-function/, http://mathoverflow.net/questions/57543/walsh-fourier-transform-of-the-mobius-function), which basically states that Möbius function is not correlated with any “simple” Boolean function. Ben Green has proved the conjecture when “simple” is interpreted as $\mathrm{AC}^0$, but it’sIt’s not unreasonable to expect it should hold for Pwhen “simple” is interpreted as wellpolynomial-time. What we know so far is that the conjecture holds for $\mathrm{AC}^0$-functions (proved by Ben Green), and all monotone functions (proved by Jean Bourgain).

For another non-answer, you might be interested in Sarnak’s conjecture (see e.g. http://gilkalai.wordpress.com/2011/02/21/the-ac0-prime-number-conjecture/, http://rjlipton.wordpress.com/2011/02/23/the-depth-of-the-mobius-function/, http://mathoverflow.net/questions/57543/walsh-fourier-transform-of-the-mobius-function), which basically states that Möbius function is not correlated with any “simple” function. Ben Green has proved the conjecture when “simple” is interpreted as $\mathrm{AC}^0$, but it’s not unreasonable to expect it should hold for P as well.

For another non-answer, you might be interested in Sarnak’s conjecture (see e.g. http://gilkalai.wordpress.com/2011/02/21/the-ac0-prime-number-conjecture/, http://rjlipton.wordpress.com/2011/02/23/the-depth-of-the-mobius-function/, http://mathoverflow.net/questions/57543/walsh-fourier-transform-of-the-mobius-function), which basically states that Möbius function is not correlated with any “simple” Boolean function. It’s not unreasonable to expect it should hold when “simple” is interpreted as polynomial-time. What we know so far is that the conjecture holds for $\mathrm{AC}^0$-functions (proved by Ben Green), and all monotone functions (proved by Jean Bourgain).

Source Link
Emil Jeřábek
Emil Jeřábek
  • 18.6k
  • 3
  • 64
  • 97

For another non-answer, you might be interested in Sarnak’s conjecture (see e.g. http://gilkalai.wordpress.com/2011/02/21/the-ac0-prime-number-conjecture/, http://rjlipton.wordpress.com/2011/02/23/the-depth-of-the-mobius-function/, http://mathoverflow.net/questions/57543/walsh-fourier-transform-of-the-mobius-function), which basically states that Möbius function is not correlated with any “simple” function. Ben Green has proved the conjecture when “simple” is interpreted as $\mathrm{AC}^0$, but it’s not unreasonable to expect it should hold for P as well.