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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.