Skip to main content

Questions tagged [arithmetic-circuits]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
23 votes
4 answers

Monotone arithmetic circuits

The state of our knowledge about general arithmetic circuits seems to be similar to the state of our knowledge about Boolean circuits, i.e. we don't have good lower-bounds. On the other hand we have ...
Kaveh's user avatar
  • 21.7k
22 votes
2 answers

Lower bound for determinant and permanent

In light of the recent chasm at depth-3 result (which among other things yields a $2^{\sqrt{n}\log{n}}$ depth-3 arithmetic circuit for the $n \times n $ determinant over $\mathbb{C}$), I have the ...
Nikhil's user avatar
  • 1,364
37 votes
5 answers

Integer multiplication when one integer is fixed

$n$ is a parameter in the problem. For every $n$ we pick a random integer $a_n\in\{2^{n-1},2^{n-1}+1,\dots,2^n-1\}$ where $n\in\{1,2,\dots\}$. Problem: Given $n$ what is the complexity of ...
Turbo's user avatar
  • 13k
14 votes
1 answer

Adleman's theorem over infinite semirings?

Adleman has shown in 1978 that $\mathrm{BPP}\subseteq \mathrm{P/poly}$: if a boolean function $f$ of $n$ variables can be computed by a probabilistic boolean circuit of size $M$, then $f$ can be also ...
Stasys's user avatar
  • 6,765
6 votes
1 answer

Lower bounds for Polynomials computing the boolean functions

Expressing a boolean function $f$ $:\{ 0,1 \}^{n} \rightarrow \{0,1 \}$ using a polynomial $P(x_{1},...,x_{n})$, where $x_{1},...,x_{n}$ may be integer, finite fields, or other fields. One of the most ...
shen's user avatar
  • 211
1 vote
0 answers

Boolean formula complexity of arithmetic expressions

This is a followup question to this other question, where I was told that multiplication is in $NC^1$ so can be computed with a circuit of polynomial size and logarithmic depth, hence also with a ...
Nicola Gigante's user avatar