Questions tagged [arithmetic-circuits]

The tag has no usage guidance.

25 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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 ...
10
votes
0answers
155 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,...
8
votes
0answers
904 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 ...
8
votes
0answers
291 views

Grigoriev-Karpinski for the permanent

Grigoriev and Karpinski (ps.Z) showed that any depth-3 circuit over a fixed finite field computing $\mathrm{Det}_n$ requires $2^{\Omega(n)}$ size. I had the misconception(?) until recently that the ...
7
votes
0answers
141 views

Computing the Fourier-Walsh coefficients of an arithmetic circuit

Given an $f$-fan in arithmetic circuit of depth $d$ over $GF(q)$ (for some prime $q$) and the set of variables $(x_1,\ldots,x_n)$, what is the state of the art upper bound for calculating the Fourier-...
6
votes
0answers
104 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) ...
5
votes
0answers
388 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 ...
4
votes
0answers
106 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, ...
4
votes
0answers
102 views

Size depth tradeoffs for monotone arithmetic circuits

Are there any size depth trade-offs known for monotone arithmetic circuits that compute permanent and determinant?
3
votes
0answers
102 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)\...
3
votes
0answers
165 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 ...
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 ...
2
votes
0answers
129 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$...
2
votes
0answers
49 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 ...
2
votes
0answers
157 views

Satisfiability of circuits with infinite input

As we all know, satisfiability of Boolean circuits is NP-complete. I am wondering if there are any studies of circuits with infinite inputs? That is, suppose the input is from the set $\{0,1\}^\omega$...
2
votes
0answers
134 views

Expressive power of (versions of) weighted average

Consider the arithmetic expressions obtained by allowing the constants 0 and 1, boolean variables, and allowing the operations $\min\{s,t\},\max\{s,t\}$, and $1-t$ where $s,t$ are expressions. Clearly ...
1
vote
0answers
67 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 ...
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{~...
1
vote
0answers
92 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$ ...
1
vote
0answers
337 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 ...
0
votes
0answers
54 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?
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 ...
0
votes
0answers
188 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 ...
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, ...