2022 Developer Survey is open! Take survey.
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-...
user avatar
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 ...
user avatar
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 \...
user avatar
  • 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 ...
user avatar
  • 3,186

Only top scored, non community-wiki answers of a minimum length are eligible