Zobrazeno 1 - 10
of 19
pro vyhledávání: '"Sylvain Perifel"'
Autor:
Olivier Carton, Sylvain Perifel
Publikováno v:
Logical Methods in Computer Science, Vol Volume 20, Issue 3 (2024)
In this paper, we give a deterministic pushdown transducer and a normal sequence of digits compressed by it. This solves positively a question left open in a previous paper by V. Becher, P. A. Heiber and the first author.
Externí odkaz:
https://doaj.org/article/d0ac1d73c74949c4a409e974e25c4d08
Publikováno v:
ISSAC
ISSAC '21: International Symposium on Symbolic and Algebraic Computation
ISSAC '21: International Symposium on Symbolic and Algebraic Computation, Jul 2021, Virtual Event Russian Federation, France. pp.35-42, ⟨10.1145/3452143.3465530⟩
ISSAC '21: International Symposium on Symbolic and Algebraic Computation
ISSAC '21: International Symposium on Symbolic and Algebraic Computation, Jul 2021, Virtual Event Russian Federation, France. pp.35-42, ⟨10.1145/3452143.3465530⟩
We consider the cyclotomic identity testing (CIT) problem: given a polynomial $f(x_1,\ldots,x_k)$, decide whether $f(\zeta_n^{e_1},\ldots,\zeta_n^{e_k})$ is zero, where $\zeta_n = e^{2\pi i/n}$ is a primitive complex $n$-th root of unity and $e_1,\ld
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::724cf850c3015c7ea0a0a313a2f22690
https://doi.org/10.1145/3452143.3465530
https://doi.org/10.1145/3452143.3465530
Autor:
Sylvain Perifel, Pascal Koiran
Publikováno v:
computational complexity. 20:1-20
We investigate the following question: if a polynomial can be evaluated at rational points by a polynomial-time boolean algorithm, does it have a polynomial-size arithmetic circuit? We argue that this question is certainly difficult. Answering it neg
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::26cdbdbc06822cebd1f58f884c98088c
https://doi.org/10.1007/s00037-011-0002-8
https://doi.org/10.1007/s00037-011-0002-8
Autor:
Pascal Koiran, Sylvain Perifel
Publikováno v:
MFCS
We extend the transfer theorem of [14] to the complex field. That is, we investigate the links between the class VPSPACE of families of polynomials and the Blum–Shub–Smale model of computation over C. Roughly speaking, a family of polynomials is
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1146cd9898410924e2645f7a083fe9fa
https://doi.org/10.1016/j.tcs.2009.08.026
https://doi.org/10.1016/j.tcs.2009.08.026
Autor:
Sylvain Perifel, Pascal Koiran
Publikováno v:
computational complexity. 18:551-575
We introduce a new class VPSPACE of families of polynomials. Roughly speaking, a family of polynomials is in VPSPACE if its coefficients can be computed in polynomial space. Our main theorem is that if (uniform, constant-free) VPSPACE families can be
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::442a3c94249a4bad5b2e5d5bebbc7b66
https://doi.org/10.1007/s00037-009-0269-1
https://doi.org/10.1007/s00037-009-0269-1
We consider the problem of fixed-polynomial lower bounds on the size of arithmetic circuits computing uniform families of polynomials. Assuming the generalised Riemann hypothesis (GRH), we show that for all k, there exist polynomials with coefficient
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ce6f35b4dcd6bf5e827d90202b024f9f
http://arxiv.org/abs/1304.5910
http://arxiv.org/abs/1304.5910
Publikováno v:
Mathematical Foundations of Computer Science 2013 ISBN: 9783642403125
MFCS
MFCS
We consider the problem of fixed-polynomial lower bounds on the size of arithmetic circuits computing uniform families of polynomials. Assuming the Generalised Riemann Hypothesis (GRH), we show that for all k, there exist polynomials with coefficient
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::5541bbb3343cbf20e801c24512dc7554
https://doi.org/10.1007/978-3-642-40313-2_39
https://doi.org/10.1007/978-3-642-40313-2_39
Publikováno v:
STOC
This work deals with the power of linear algebra in the context of multilinear computation. By linear algebra we mean algebraic branching programs (ABPs) which are known to be computationally equivalent to two basic tools in linear algebra: iterated
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::0812870ab85b6863a47d95f40d0960f4
https://doi.org/10.1145/2213977.2214034
https://doi.org/10.1145/2213977.2214034
Autor:
Sylvain Perifel, Pascal Koiran
Publikováno v:
IEEE Conference on Computational Complexity
We show that the permanent cannot be computed by DLOGTIME-uniform threshold or arithmetic circuits of depth o(log log n) and polynomial size.
Comment: 11 pages
Comment: 11 pages
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ac8bd4880a890e86fc5bde9743c76ed6
https://hal.science/hal-00360507
https://hal.science/hal-00360507
The pressing need for efficient compression schemes for XML documents has recently been focused on stack computation (Hariharan, S., & Shankar, P. in: Proceedings of the 2006 IEEE data compression conference, p. 453, 2006; League, C., & Eng, K. in: P
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1be2198303927b1a5ef0de6828b837b9