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.
...
- 11.7k
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$ ...
- 743
Top 50 recent answers are included