75 citations
- Université Paris CitéFR78 papers
- Centre National de la Recherche ScientifiqueFR42 papers
- Délégation Paris 7FR14 papers
- Institut national de recherche en sciences et technologies du numériqueFR14 papers
- Laboratoire Bordelais de Recherche en InformatiqueFR11 papers
- Sorbonne UniversitéFR6 papers
- Laboratoire d'Informatique de l'École PolytechniqueFR5 papers
- École Normale Supérieure de LyonFR4 papers
- Université Paris 8FR4 papers
- Computer Algorithms for MedicineAT3 papers
- École Normale Supérieure - PSLFR3 papers
- École PolytechniqueFR3 papers
Showing 2009 · cs.CCShow all
2 papers · 2 filters
cs.CC2009
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…
cs.CC2009
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.