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-...
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 ...
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
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 ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
cc.complexity-theory × 2872complexity-classes × 462
reference-request × 338
np-hardness × 325
ds.algorithms × 240
graph-theory × 232
circuit-complexity × 229
sat × 142
counting-complexity × 138
time-complexity × 136
graph-algorithms × 134
quantum-computing × 113
lower-bounds × 111
reductions × 88
big-picture × 80
approximation-algorithms × 77
approximation-hardness × 77
lo.logic × 75
co.combinatorics × 74
boolean-functions × 71
np × 71
computability × 63
cr.crypto-security × 58
optimization × 56
space-bounded × 55