Zobrazeno 1 - 10
of 25
pro vyhledávání: '"Computing methodologies, Algebraic algorithms"'
It is a longstanding open problem whether there is an algorithm to decide the Positivity Problem for linear recurrence sequences (LRS) over the integers, namely whether given such a sequence, all its terms are non-negative. Decidability is known for
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::cc0d7be8ed3180f5646a3552d861b6b1
Autor:
Worrell, James
The Skolem Problem asks to determine whether a given integer linear recurrence sequence (LRS) has a zero term. This decision problem arises within a number of different topics in computer science, including loop termination, weighted automata, formal
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::c69bfe28d5bb73bce3fe3f52eba6c75c
Autor:
Bhargava, Vishwas, Ghosh, Sumanta
Publikováno v:
computational complexity. 31
The orbit of an n-variate polynomial f(x) over a field 𝔽 is the set {f(Ax+b) ∣ A ∈ GL(n, 𝔽) and b ∈ 𝔽ⁿ}, and the orbit of a polynomial class is the union of orbits of all the polynomials in it. In this paper, we give improved constru
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8fc1c4f8a49e09073f0d03fb8d601f26
https://doi.org/10.1007/s00037-022-00230-9
https://doi.org/10.1007/s00037-022-00230-9
We study the problems of testing isomorphism of polynomials, algebras, and multilinear forms. Our first main results are average-case algorithms for these problems. For example, we develop an algorithm that takes two cubic forms $f, g\in \mathbb{F}_q
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3a4d7d4537a5c370a35c8b41c01bdd72
https://doi.org/10.46298/jgcc.2022.14.1.9431
https://doi.org/10.46298/jgcc.2022.14.1.9431
Consider a homogeneous degree d polynomial f = T₁ + ⋯ + T_s, T_i = g_i(𝓁_{i,1}, …, 𝓁_{i, m}) where g_i’s are homogeneous m-variate degree d polynomials and 𝓁_{i,j}’s are linear polynomials in n variables. We design a (randomized) l
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::c742ec0698b9a4af3f6f26a9de90ab03
Autor:
Kenison, George
Publikováno v:
Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science (MFCS)
Given an integer linear recurrence sequence $\langle X_n \rangle_n$, the Skolem Problem asks to determine whether there is a natural number $n$ such that $X_n = 0$. Recent work by Lipton, Luca, Nieuwveld, Ouaknine, Purser, and Worrell proved that the
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6733cf695d03123df8674bd5b5fdcb8b
Autor:
Koiran, Pascal, Saha, Subhayan
We study the decomposition of multivariate polynomials as sums of powers of linear forms. We give a randomized algorithm for the following problem: If a homogeneous polynomial f ∈ K[x_1 , . . . , x_n] (where K ⊆ ℂ) of degree d is given as a bla
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c61bdab4e2abb84b4b28f5f0b443631c
http://arxiv.org/abs/2110.05305
http://arxiv.org/abs/2110.05305
Publikováno v:
36th Computational Complexity Conference: CCC2021, July 20-23, 2021, Toronto Canada (Virtual Conference)
36th Computational Complexity Conference
Proc. 36th Computational Complexity Conference, 2021
36th Computational Complexity Conference
Proc. 36th Computational Complexity Conference, 2021
An action of a group on a vector space partitions the latter into a set of orbits. We consider three natural and useful algorithmic "isomorphism" or "classification" problems, namely, orbit equality, orbit closure intersection, and orbit closure cont
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6a3fdcbc30d1c579831936b338448d20
https://doi.org/10.4230/LIPIcs.CCC.2021.32
https://doi.org/10.4230/LIPIcs.CCC.2021.32
Autor:
Grochow, Joshua A., Qiao, Youming
In this paper we study some classical complexity-theoretic questions regarding Group Isomorphism (GpI). We focus on p-groups (groups of prime power order) with odd p, which are believed to be a bottleneck case for GpI, and work in the model of matrix
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2b547035371f36d8497ee4c92c0a500e
https://hdl.handle.net/10453/153700
https://hdl.handle.net/10453/153700
Publikováno v:
ISSAC '20: International Symposium on Symbolic and Algebraic Computation
ISSAC '20: International Symposium on Symbolic and Algebraic Computation, Jul 2020, Kalamata, Greece. pp.257-264, ⟨10.1145/3373207.3404037⟩
ISSAC
ISSAC '20: International Symposium on Symbolic and Algebraic Computation, Jul 2020, Kalamata, Greece. pp.257-264, ⟨10.1145/3373207.3404037⟩
ISSAC
Let K be a field equipped with a valuation. Tropical varieties over K can be defined with a theory of Gr{\"o}bner bases taking into account the valuation of K. Because of the use of the valuation, the theory of tropical Gr{\"o}bner bases has proved t
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::14101c3df560d2ea12044147a44c5313
https://hal.archives-ouvertes.fr/hal-02928709/document
https://hal.archives-ouvertes.fr/hal-02928709/document