New answers tagged

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. ...
D.W.'s user avatar
  • 11.7k
4 votes

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$ ...
Robert Andrews's user avatar

Top 50 recent answers are included