New answers tagged arithmetic-circuits
2
votes
What’s the complexity of this decision problem with bit shifting?
If I had to guess, I'd guess that the problem is hard, but I don't have a rigorous proof. I share below some musings on your problem, even though they don't lead to a clear answer to your question.
...
4
votes
Accepted
Lower bound for constant degree monotone arithmetic circuits
The Nisan--Wigderson polynomials are one example. That is, let
$$
\mathrm{NW}_{n,m,d}(\vec{x}) := \sum_{\substack{p(t) \in \mathbb{F}_m[t] \\ \deg(p) \le d}} x_{1,p(1)} \cdots x_{n,p(n)}.
$$
Let $k$ ...
Top 50 recent answers are included
Related Tags
arithmetic-circuits × 87cc.complexity-theory × 36
circuit-complexity × 36
algebraic-complexity × 20
lower-bounds × 11
reference-request × 6
boolean-functions × 6
determinant × 6
ds.algorithms × 5
circuits × 5
permanent × 4
circuit-depth × 4
polynomials × 3
monotone × 3
lo.logic × 2
optimization × 2
big-picture × 2
matrices × 2
p-vs-np × 2
permutations × 2
gr.group-theory × 2
matrix-product × 2
circuit-families × 2
formulas × 2
cc-complexity-theory × 2