output
20032015
most citedAnisotropic Reinforcement of Nanocomposites Tuned by Magnetic Orientation of the Filler Network

75 citations

researchers with a paper here
collaborating institutions
Showing 2013Show all

7 papers · 1 filter

cs.CC2013

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…

math.CO2013

2-Stack Sorting is polynomial

Adeline Pierrot, Dominique Rossin

In this article, we give a polynomial algorithm to decide whether a given permutation is sortable with two stacks in series. This is indeed a longstanding open problem which wa…

math.LO2013

Randomness and lowness notions via open covers

Laurent Bienvenu, Joseph S. Miller

One of the main lines of research in algorithmic randomness is that of lowness notions. Given a randomness notion R, we ask for which sequences A does relativization to A leave R u…

cs.DM2013★ 5 cited

2-stack pushall sortable permutations

Adeline Pierrot, Dominique Rossin

In the 60's, Knuth introduced stack-sorting and serial compositions of stacks. In particular, one significant question arise out of the work of Knuth: how to decide efficiently if…

cs.DS2013

Various improvements to text fingerprinting

Djamal Belazzougui, Roman Kolpakov, Mathieu Raffinot

Let s = s_1 .. s_n be a text (or sequence) on a finite alphabet Σof size σ. A fingerprint in s is the set of distinct characters appearing in one of its substrings. The problem con…

math.LO2013

The axiomatic power of Kolmogorov complexity

Laurent Bienvenu, Andrei Romashchenko, Alexander Shen +2

The famous Gödel incompleteness theorem states that for every consistent sufficiently rich formal theory T there exist true statements that are unprovable in T. Such statements wo…