Questions tagged [arithmetic-circuits]
The arithmetic-circuits tag has no usage guidance.
74
questions
-1
votes
0answers
58 views
Are total recursive functions efficiently invertable?
I'm doing some work with cryptographic primitives that act on arithmetic circuits. We found a result from a few years ago that would suffice for our purposes, but it assumes the functions in question ...
0
votes
0answers
51 views
Number of composite factors as a function of the number of bits of an integer
Is there a standard formula to calculate the number of composite factors using the number of bits of an integer?
3
votes
1answer
81 views
Is homogeneity required in Hyafil's arithmetic circuit decomposition theorem when applied to monotone circuits?
I'm new to circuit complexity, and trying to understand Hyafil's decomposition theorem (Theorem 1 in [1], Lemma 3 in [2], Decomposition Lemma in [3], also mentioned in [4]). My question is: Is ...
1
vote
0answers
66 views
Multiplicative-depth 1 composition of arithmetic circuits
I am trying to find information about the following problem. Let $C_1$ and $C_2$ be any two poly-size arithmetic circuits on input vectors x₁ and x₂ correspondingly. Assume that a third arithmetic ...
2
votes
0answers
127 views
Matrix multiplication when one matrix is fixed
Let $A$ be a fixed positive entried integer matrix of size $a\times n$ with $\ell$ bits per entry
One is allowed to pre-process this matrix as appropriate.
Given another positive integer entried $B$...
3
votes
1answer
166 views
Arithmetic circuits over $GF(p)$ for computing $x \bmod 2$ given input $x \in GF(p)$
Let $p$ be a prime. Suppose we consider the function $f: GF\left(p \right) \rightarrow \left\{0, 1 \right\}$ where $f(x) = x \bmod 2$ for all.
The question is the following: are there any known ...
0
votes
1answer
446 views
How to build comparison operator (comparator) in an arithmetic circuit
I am trying to convert a basic program into an arithmetic circuit. I am stuck on the step of converting the greater than operator into an arithmetic circuit. To be specific, I do not know how to ...
1
vote
0answers
68 views
Straight line programs with $\sqrt{~}$
A straight line program with division is very powerful https://rjlipton.wordpress.com/2012/10/16/one-mans-floor-is-another-mans-ceiling/.
Is it possible to reduce a straight line program with $\sqrt{~...
9
votes
1answer
295 views
Depth reduction for Boolean circuits
This result by Tavenas, Koiran and others show that any polynomial computed by a circuit of size $s$ is computed by a depth-4 homogenous circuit of size $s^{\sqrt{d}}$.
Are there any similar results ...
7
votes
1answer
331 views
Can reciprocal inputs speed up monotone computations?
A $(+,\times,1/x_i)$ circuit is a standard monotone arithmetic $(+,\times)$ circuit with the only difference that now besides the input variables $x_1,\ldots,x_n$, also their reciprocals $1/x_1,\...
5
votes
1answer
232 views
Evaluation of an arithmetic formula where the time depends on the length of the arguments of gates
Let $(X,+,\cdot)$ be a commutative ring. Let $|\cdot|\colon X\to \mathbb{N}$ be a function that satisfies $|x+y|\leq |x|+|y|$ and $|xy|\leq |x|+|y|$. We call the function length, and length is always ...
3
votes
0answers
99 views
Why do most 0/1 matrices need linear arithmetic circuits of size $\Omega(n^2/\log(n))$?
I am reading Alon et al.'s paper Linear Circuits over $GF(2)$ and I am having trouble seeing the counting argument showing that most matrices need a circuit of size $\Omega(n^2/\log n)$. This result ...
3
votes
0answers
86 views
How many arithmetic and max operations does it take to compute Dynnikov's action of the braid groups on $\mathbb{Z}^{2n}$?
A function $f:X^{2}\rightarrow X^{2}$ is said to satisfy the Yang-Baxter equation if
$$(f\times\textrm{Id}_{X})\circ(\textrm{Id}_{X}\times f)\circ(f\times\textrm{Id}_{X})=(\textrm{Id}_{X}\times f)\...
2
votes
0answers
47 views
Arithmetic circuits with restrictions on occurrence of pairs of variables
I am curious if the following model was studied or has some obvious lower bounds:
We want to compute a polynomial $P(x_1,x_2, \dots , x_n)$. Suppose we have a graph G on $n$ nodes that we are going ...
7
votes
4answers
352 views
Reference request: Arithmetic circuit complexity
I am completely new to this field. I want to read the prelims and unfortunately, I don't see any book written for a beginner in this area. Can anyone give me some basic starting points/references(text/...
6
votes
1answer
202 views
VNP is closed under taking coefficients using Valiant's criterion
We consider the family of polynomials
$$\{f_n(x_1,\dots,x_n,y_1,\dots,y_n)\}\in\mathsf{VNP}$$
We want to show that the family
$$\{h_n(x_1,\dots,x_n)\}$$
is in $\mathsf{VNP}$. Where $h_n(x_1,\dots,...
3
votes
0answers
164 views
Circuit's with gate computing only "simple" functions
I was curious if something like that is known or was studied.
Let's call a function simple if it is computable by $AC_0$ circuit of depth $\leq d$ and size $\leq n^k$ for fixed $k,d$.
Now let's ...
7
votes
2answers
138 views
White-box sparse interpolation
Let $C$ be an arithmetic circuit that represents a polynomial $f\in\mathbb K[x_1,\dotsc,x_n]$, with the promise that $f$ has at most $k$ nonzero terms. What is (known about) the complexity of ...
1
vote
0answers
91 views
Tribes function vs (modified) polynomial threshold circuits
Are there lowerbounds known for representing the Tribes function by a circuit consisting of a single layer of polynomial threshold gates feeding into maybe a trivial summing gate? (Even for degree $1$ ...
6
votes
1answer
230 views
Has there been a study of circuits operating on arrays?
Much ink has been spilled studying the theory surrounding computation by combinatorial circuits operating on bits or boolean values - with AND, OR and NOT gates (as those are enough to implement any ...
3
votes
0answers
104 views
Fixed parameter Integer Programming circuit depth complexity
It is well known Lenstra's and Kannan's algorithm achieves $n$-variable parameter $L$-bit integer programming solvability in $O(n^nL)$ time and $O(L)$ space.
If implemented as an arithmetic circuit ...
14
votes
1answer
686 views
VC dimension of polynomials over tropical semirings?
As in this question, I am interested the $\mathbf{BPP}$ vs. $\mathbf{P}$/$\mathrm{poly}$ problem for tropical $(\max,+)$ and $(\min,+)$ circuits. This question reduces to showing upper bounds for the ...
13
votes
1answer
374 views
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 ...
10
votes
0answers
154 views
Checking a long product of matrices
Given a set of n-by-n integer matrices $\{A_1, \dots, A_m\}$, for a word $w=w_1 w_2\cdots w_l$ over $\{1, \dots, m\}$, we define $A_w:=A_{w_1}\cdots A_{w_l}$.
The question is to decide, given $\{A_1,...
5
votes
0answers
387 views
About the ``recent" paper by Razborov in the Annals of Mathematics
Recently this paper on complexity theory was published at the Annals of Mathematics by Razborov, http://annals.math.princeton.edu/2015/181-2/p01. Curiously this seems to have been submitted to the ...
1
vote
1answer
180 views
Optimal evaluation of polynomials / rational functions
A common way to compute the value a polynomial is to write it in Horner form. However, this isn't always the fastest way to evaluate it. Setting aside concerns of numerical precision, take the ...
2
votes
1answer
105 views
Low-depth arithmetic complexity of the product of $k$ matrices
Is anything known about the size of $\Sigma\Pi\Sigma$ (or other constant depth) circuits for the product of $k$ matrices?
Trivial upper bounds (up to small factors) are:
if $k=2$, then there are $\...
0
votes
0answers
119 views
Arithmetic complexity of matrix powering with non-commutative entries
Assume $M\in\Bbb Z_{\geq0}[x_1,\dots,x_n]^{m\times m}$ be an $m\times m$ matrix in $n$ variables with $x_i$ being non-commutative.
What is the complexity class and circuit and formula complexity of ...
12
votes
1answer
531 views
Are arithmetic circuits weaker than boolean?
Let $A(f)$ denote the minimum size of a (non-monotone) arithmetic $(+,\times,-)$ circuit
computing a given multilinear polynomial
$$
f(x_1,\ldots,x_n)=\sum_{e\in E}c_e\prod_{i=1}^n x_i^{e_i}\,,
$$
...
7
votes
1answer
142 views
Lower bounds for noncommutative arithmetic circuits with exact division?
It is known that for general arithmetic circuits there is not much of a difference between standard model and one with division: any circuit with divisions that computes a polynomial can be simulated ...
14
votes
1answer
1k views
Monotone arithmetic circuit complexity of elementary symmetric polynomials?
The $k$-th elementary symmetric polynomial $S_k^n(x_1,\ldots,x_n)$ is the sum of all $\binom{n}{k}$ products of $k$ distinct variables.
I am interested in the monotone arithmetic $(+,\times)$ circuit ...
5
votes
1answer
92 views
How quickly can we decompose a number into a set of residues?
Basically, if we are given a natural $x$, in binary, with $x < m_0 \cdot m_1 \cdot m_2 \cdot \dots \cdot m_n$, how quickly can we find $x \bmod m_0$, $x \bmod m_1$,..., and $x \bmod m_n$? In other ...
10
votes
2answers
270 views
Matrix vector multiplication algorithm using minimal number of additions
Consider the following problem:
Given a matrix $M$
we want to optimize the number of additions in
the multiplication algorithm for computing $v \mapsto Mv$.
I find this problem interesting ...
4
votes
1answer
405 views
Analogies between VNP and NP
Valiant introduced the class VNP with respect to "arithmetic circuits" over 35 years ago in a "rough" analogy to NP. Recently, there have been major advances in the area of arithmetic circuits eg as ...
10
votes
2answers
832 views
Implications of Riemann Hypothesis variants in TCS
The over ~1½ century old Riemann Hypothesis has deep implications in mathematics and a large edifice of math theory is now proved conditionally on it and numerous variants. I recently came across a ...
11
votes
2answers
280 views
Straight line complexity of monomials
Let $k$ be some field. As usual, for an $f\in k[x_{1},x_{2},\ldots,x_{n}]$
we define $L(f)$ to be the straight-line complexity of $f$ over
$k$. Let $F$ be the set of monomials of $f$, namely the ...
23
votes
1answer
940 views
Why is HAMILTONIAN CYCLE so different from PERMANENT?
A polynomial $f(x_1,\ldots,x_n)$ is a monotone projection of a
polynomial $g(y_1,\ldots,y_m)$ if $m$ = poly$(n)$, and there is an assignment
$\pi:\{y_1,\ldots,y_m\}\to\{x_1,\ldots,x_n, 0,1\}$ such ...
1
vote
0answers
334 views
intuition that VP=?VNP is (not?) connected to P=?NP
recently there has been major progress into the VP=?VNP problem for algebraic circuits originated by Valiant, inspiring some optimistic outlook on its eventual or imminent resolution.[1]
what is an ...
21
votes
1answer
565 views
Arithmetic circuits with just one threshold gate
When restricted to $0$-$1$ inputs, every $\{+,\times\}$-circuit $F(x_1,\ldots,x_n)$ computes some
function $F:\{0,1\}^n\to \mathbb{N}$. To obtain a boolean function, we can just add
one fanin-1 ...
15
votes
1answer
530 views
Any polynomial which is hard to count but easy to decide?
Every monotone arithmetic circuit, i.e. a $\{+,\times\}$-circuit, computes some multivariate
polynomial $F(x_1,\ldots,x_n)$ with nonnegative integer coefficients. Given a polynomial
$f(x_1,\ldots,x_n)$...
9
votes
1answer
232 views
Randomized identity-testing for high degree polynomials?
Let $f$ be an $n$-variate polynomial given as an arithmetic circuit of size poly$(n)$, and let $p = 2^{\Omega(n)}$ be a prime.
Can you test if $f$ is identically zero over $\mathbb{Z}_p$, with time ...
2
votes
2answers
202 views
Complexity of smooth non-linear functions
EDIT: A more straightforward way of asking this question is: does evaluating a non-linear function require performing at least one multiplication?
ORIGINAL QUESTION:
I have an infinitely ...
0
votes
0answers
186 views
Greater-Than operator using an Arithmetic Circuit
How can I transform the term $x>C$ (i.e. the term assumes the value $1$ if $x>C$ and assumes the value $0$ otherwise) to an arithmetic circuit that computes it?
Where $x$ is the input to the ...
15
votes
1answer
296 views
What are bounded-treewidth circuits good for?
One can talk of the treewidth of a Boolean circuit, defining it as the treewidth of the "moralized" graph on wires (vertices) obtained as follows: connect wires $a$ and $b$ whenever $b$ is the output ...
5
votes
1answer
604 views
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 ...
6
votes
0answers
103 views
Practical algorithms for finding small arithmetic circuits
I have a multivariate integer polynomial $f : \mathbb{Z}^n \to \mathbb{Z}$ given as either as a circuit or as a list of monomials. I am interested in practical (though obviously exponential time) ...
14
votes
1answer
2k views
A course for learning algebraic complexity
I want to learn about algebraic algorithms and complexity thoery. In particular, I am interested in PIT.
Is there a set of lecture notes, books, papers and surveys for students who have read standard ...
9
votes
1answer
217 views
Checking if a polynomial factors into linear factors
Let $f\in\mathbb{Q}[x_{1},x_{2},\ldots,x_{n}]$ be a polynomial given
by an arithmetic circuit $C$ of size $s$. Given $C$ as the input,
is there a deterministic algorithm to check whether all the ...
0
votes
0answers
60 views
arithmetic formula simplication
Consider a function $f : \mathbb R^m \rightarrow \mathbb R^n$.
Function $f$ can be written down as a simple arithmetic program. It uses addition, subtraction, multiplication and division - however, ...
11
votes
0answers
298 views
Generalizations of the determinant/permanent problem?
A tantalizing open question in computational complexity is to understand the 'behavioral differences' between the determinant and the permanent. While the former is computable in polynomial time with ...
