8 papers
Deterministic pushdown automata can compress some normal sequences
Olivier Carton, Sylvain Perifel
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. B…
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…
Lempel-Ziv: a "one-bit catastrophe" but not a tragedy
Guillaume Lagarde, Sylvain Perifel
The so-called "one-bit catastrophe" for the compression algorithm LZ'78 asks whether the compression ratio of an infinite word can change when a single bit is added in front of it.…
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.