4
$\begingroup$

Recently in this beautiful paper, https://arxiv.org/pdf/1705.02397.pdf it has been shown that there is an explicit $Th \circ Th$ function with sign-rank scaling exponentially in dimension. I wanted to get some context for this,

  1. Before this paper was there no other function known in the $Th \circ Th$ or $Th \circ Maj = Maj \circ Th$ or in any other $TC^d$ class with such high sign-rank?

  2. What other functions do we know of which have a high sign-rank? I can see it to be known for only a handful of examples like the Minsky-Pappert function, a depth $3$ $AC^0$ generalization of it (in a Razborov-Sherstov paper) and another in a Bun-Thaler paper and Inner-Product-Mod-2. Are there others? (If yes, then can you kindly link to references to their proof?)

  3. The page 4 and 5 of this paper give some intuition about what makes a Boolean function have a sign-rank. It would be great to know if others have more insights to add to this discussion. Are there maybe any "folklore" thumb-rules which help judge if a function has a high sign-rank?

Improve this question
$\endgroup$

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.