2022 Developer Survey is open! Take survey.

# Tag Info

Accepted

### $\mathrm{AC}^0$ upper bound for Hamming weight

Yes, the bound is essentially tight. The following is a straightforward construction of depth-$d$ Majority circuits of size 2^{(1-d^{-1})(n^{1/(d-1)}+O(1))\log n}\le2^{n^{1/(d-1)}\log n}=n^{n^{1/(d-...
• 14.7k

### Applications of association schemes to complexity theory and other TCS

Coherent configurations are a close generalization of association schemes they have been used in Graph Isomorphism and Matrix Multiplication. (See e.g. this blog post of Peter Cameron that discusses ...
• 35.6k