Cotas inferiores para funciones booleanas simétricas

Últimamente he estado estudiando una técnica para encontrar cotas inferiores para árboles de decisión basadas en polinomios. Básicamente, la función booleana se escribe como si fuera un polinomio, e.g. x1∧x2 se puede escribir como un polinomio en dos variables p(x1,x2)=x1⋅x2. Entonces el número de consultas al oráculo es exactamente el grado del polinomio. Para el ejemplo del and tenemos que este número es 2.

Bueno, hay un resultado en computación cuántica que dice que el número de consultas que hace un algoritmo a un oráculo cuántico está acotado por abajo por el grado de un polinomio de bajo grado que aproxima la función booleana. Este es el link al paper original que desarrolló la técnica.

Ahora consideremos la función threshold, donde Thrt(x)=1 si y solo si el número de 1s en x es mayor o igual a t, i.e. |x|≥t. La cota inferior reportada en muchos papers es de . Existe un teorema (Paturi 1992) basado en el método de los polinomios. Este teorema nos permite calcular la cota inferior para cualquier función booleana simétrica. Una función booleana f es simétrica, si dado cualquier entrada x, permutar el orden de los bits no cambia el valor de f(x). Claramente Thrt es simétrica.

Tengo una pregunta en Theoretical Computer Science Stack Exchange que está sin respuesta ya por unos días. Básicamente el problema es que la cota inferior para threshold indicada arriba no sigue en forma directa desde el teorema de Paturi.

Creo que voy a esperar unos días más, y si sigue sin respuesta voy a  poner una recompensa. Pero si algún lector de este blog conoce la respuesta, le voy a estar muy agradecido :-)