6 papers · 1 filter
Cyclotomic Identity Testing and Applications
Nikhil Balaji, Sylvain Perifel, Mahsa Shirmohammadi +1
We consider the cyclotomic identity testing (CIT) problem: given a polynomial , decide whether is zero, where i…
On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant
Hervé Fournier, Sylvain Perifel, Rémi de Verclos
Assuming the Generalised Riemann Hypothesis (GRH), we show that for all k, there exist polynomials with coefficients in $\MA$ having no arithmetic circuits of size O(n^k) over the…
Polylog space compression, pushdown compression, and Lempel-Ziv are incomparable
Elvira Mayordomo, Philippe Moser, Sylvain Perifel
The pressing need for efficient compression schemes for XML documents has recently been focused on stack computation, and in particular calls for a formulation of information-lossl…
A Superpolynomial Lower Bound on the Size of Uniform Non-constant-depth Threshold Circuits for the Permanent
Pascal Koiran, Sylvain Perifel
We show that the permanent cannot be computed by DLOGTIME-uniform threshold or arithmetic circuits of depth o(log log n) and polynomial size.
Interpolation in Valiant's theory
Pascal Koiran, Sylvain Perifel
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…
VPSPACE and a Transfer Theorem over the Reals
Pascal Koiran, Sylvain Perifel
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 ma…