Questions tagged [arithmetic-circuits]

The tag has no usage guidance.

1
vote
1answer
46 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
59 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{~...
0
votes
0answers
53 views

Which research fields deal with this variant definition of Boolean circuit depth?

Disclaimer: I admit that the question is not very clear. I think it cannot be helped because the question is very open-ended. First of all, I present the interested type of circuits. We only consider ...
8
votes
1answer
212 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 ...
6
votes
0answers
150 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
230 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
91 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
79 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
42 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 ...
6
votes
0answers
144 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
161 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 ...
6
votes
2answers
129 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
77 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
222 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
103 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
502 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
301 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
152 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
350 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
96 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
91 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
115 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
476 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
124 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
694 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
242 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
360 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 ...
9
votes
2answers
760 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
242 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
829 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
264 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
494 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
486 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
186 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
165 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
171 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 ...
13
votes
1answer
223 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
466 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 ...
6
votes
0answers
98 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
186 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
58 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
280 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 ...
5
votes
1answer
186 views

Can a polynomial sized arithmetic ciruits perform integer division?

Can we perform integer division with a polynomial size arithmetic circuit over $\mathbb{Q}$ that takes as input the numerator and denominator?
4
votes
0answers
92 views

Complexity of equivalence testing of arithmetic circuits

I have a very specific problem that appears to be close to equivalence testing for arithmetic circuits (checking whether the computed functions are the same). Since I'm completely new to the field, ...
6
votes
1answer
185 views

arithmetic circuits for polynomials (updated)

I am concerned about the following question, consider $P_n(x)= \sum_{i=0}^n \frac{x^n}{n!}$ Is there a straight line program (or arithmetic circuits) of polynomial size (wrt $n$) for the polynomial ...
7
votes
1answer
325 views

Uniformity vs. nonuniformity in algebraic complexity theory

I understand that the study of Boolean circuits and nonuniform complexity classes was introduced to (hopefully) prove separation of uniform complexity classes. In this sense, nonuniform computational ...
8
votes
0answers
608 views

Complexity of Polynomial Division

Let $P(x)$ be a univariate polynomial with integer coefficients where both coefficients and degrees are in binary and let $q(x)$ be another polynomial also with integer coefficients where the degrees ...
5
votes
1answer
296 views

Degree restriction for polynomials in $\mathsf{VP}$

why do we need the restriction on the degree for a polynomial to be in VP due to which $(\prod_{i=0}^{n} x_i)^{2^n}$ $\notin$ VP even though it has a poly-size circuit?