2
votes
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
2
votes
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
2
votes
Accepted
Complexity of the Complete (3,2) SAT problem?
Consider the standard reduction from 3-coloring to SAT: for each vertex $v \in V$ we introduce three variables, $v_R,v_G,v_B$, add a clause $(v_R \vee v_G \vee v_B)$, and clauses $(\lnot v_R \vee \...
- 1,398
1
vote
Accepted
Parameterized complexity of Hitting Set with slightly bigger parameter
This is FPT, because by interchanging sets with elements in the usual way, this is just set cover where the universe size $n$ is the parameter. This is known to be FPT (see e.g. the parameterized ...
- 3,186
Only top scored, non community-wiki answers of a minimum length are eligible