Symmetric boolean functions as Zhegalkin polynomials

Dyalog APL, 15 bytes

{2|⍺⌹⍉∘.!⍨0,⍳⍵}

Matrix division, basically. Takes input like 0 0 1 1 1 {2|⍺⌹⍉∘.!⍨0,⍳⍵} 4 for T₄({2,3,4}).

{              }        Dyadic function:
              ⍵         Right argument          4
             ⍳          Index vector            1 2 3 4
           0,           Append 0                0 1 2 3 4
      ∘.                Outer product           ——————————
          ⍨             |With itself              1 0 0 0 
        !               |By binomial coeff.       2 1 0 0
     ⍉                  Matrix transpose          3 3 1 0
                        Result at this step: ->   4 6 4 1
   ⍺                    Left argument
    ⌹                   Matrix division (A⌹B is A^-1 B, not A B^-1)
                        (implicitly converts ⍺ to column vector)
 2|                     Modulo 2

Since the transposed matrix of binomial coefficients is lower triangular with determinant 1, its inverse will only contain integers. So to matrix-divide over F₂ we can just matrix-divide over the reals, then mod by 2.

Matrix division is an O(n^3) operation, and calculating each of the O(N^2) binomial coefficients is well below O(n^3), so this runs in O(N^5).

Try it on TryAPL.