All Questions
Tagged with ra.rings-and-algebras computational-complexity
7 questions
3
votes
1
answer
103
views
References: rigorous algorithms for elementary computations in base-b with complexity estimates
Definitions/Notation: Fix positive integers $b$ and $M$. Consider the set of real numbers which can be exactly expressed with $2M+1$ coefficients in base $b$, defined by
$$\mathcal{X}(b,M):=\{x\in \...
- 5,405
4
votes
1
answer
223
views
Recent research on polynomial identities
I work in computational complexity, where I work on the problem of polynomial identity testing over arithmetic circuits. One particular case is when the variables over the polynomial ring don't ...
- 49
3
votes
1
answer
382
views
What is the name for algebras generated by elements, all of whose cubes vanish?
Given a ring $R$ with identity $1$, we can define the exterior algebra of order $k$ over $R$ to be the algebra over $R$, generated by elements $x_1, \dots, x_k$ satisfying $x_i^2 = 0$ for each index $...
- 557
0
votes
0
answers
250
views
What is the computational complexity of solving a highly underdetermined system?
Let $F$ be a finite field with $q$ elements. Consider an underdetermined system of linear equations with $m$ equations and $n$ variables where $n\gg m$. What is the complexity of solving such a highly ...
- 131
2
votes
0
answers
39
views
Complexity of computing roots in general rings
The Rabin Cryptosystem derives its basic security assumption on the observation, that computing roots in integer modulo $n$ rings, is as hard as finding the prime decomposition of $n$.
Mathematically ...
- 2,074
18
votes
2
answers
2k
views
Can Schwartz-Zippel be formulated for commutative rings instead of fields?
The polynomials which occur in the Schwartz-Zippel lemma could be defined for any commutative ring, yet the lemma is restricted to fields. This makes it inapplicable for $(1+x^n)=1+x^n(\operatorname{...
- 2,464
1
vote
1
answer
160
views
Finding reducible polynomials with restricted factors
Given $f(x),g(x) \in \mathbb{Z}[x]$, two irreducible polynomials, is there a polynomial $h(x) \in \mathbb{Z}[x]$ coprime to $f(x)$ such that $f(x) + g(x)h(x)$ is reducible over $\mathbb{Z}[x]$ with ...
- 13.9k