Skip to main content

Questions tagged [parity]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
73 views

Learning Parities via Gradient Descent

[Disclaimer: Crossposted in cs --> link] In their recent work [DM20] Daniely and Malach prove that a two layer sufficiently wide NN can learn parities via gradient descent (GD). Since [Kearn94] it ...
uzer.name's user avatar
8 votes
0 answers
460 views

How many different proofs are there of parity is not in AC0?

The theorem that Parity is not in $\mathsf{AC}^0$ is one of the gemstones of complexity theory. I wonder how many different proofs there are of this result? What constitutes "different" is also a part ...
Goose's user avatar
  • 81
2 votes
1 answer
240 views

Fourier decomposition in terms of another basis

Given a Boolean function $f:\{-1,1\}^n\rightarrow \{-1,1\}$, it is well know that the Fourier decomposition of $f$ can be written as $f(x)=\sum_{S\subseteq \{1,\ldots,n\}} \widehat{f}(S) \prod_{i\in S}...
Annonymous's user avatar
4 votes
1 answer
136 views

Which $SIZE$-$DEPTH(s, d)$ classes with $log(s(n))^{d(n) - 1} = o(n)$ can we not separate by known methods?

Define $SIZE$-$DEPTH(s, d)$ to be the functions which are computed by circuit families of size $O(s(n))$ and less than depth $d(n)$. We know from Boppana's 1997 paper on the average sensitivity of ...
Samuel Schlesinger's user avatar
4 votes
0 answers
111 views

What is the largest noise rate $\eta(n)$ for which learning parities with noise is easy?

Learning Parity with Noise (LPN) is usually stated with constant noise rate $\eta < 1/2$ on the labels, and it is believed to be hard to learn because of the high statistical dimension of the ...
Jeremy Kun's user avatar
  • 1,318
21 votes
4 answers
2k views

What is the minimum size of a circuit that computes PARITY?

It is a classic result that every fan-in 2 AND-OR-NOT circuit that computes PARITY from the input variables has size at least $3(n-1)$ and this is sharp. (We define size as the number of AND and OR ...
domotorp's user avatar
  • 14.1k