Search

International audience; In this note, we point out two major errors in the paper "Minimizing total tardiness on parallel machines with preemptions" by Kravchenko and Werner (2012). More precisely, they claimed to have proved that both problems P|pmtn|∑T j and P|r j ,p j =p,pmtn|∑T j are NP -Hard. We give a counter-example to their proofs, letting the complexity of these two problems open.

The spectral gap conjecture of M. van den Berg [2, formula (65)] asserts that λ2 − λ1 ≥ 3π for all convex euclidean domains of diameter 1, where λ1 and λ2 denote the first two eigenvalues of the Dirichlet Laplacian. Notice that equality holds for the 1-dimensional unit interval, which can be regarded also as a degenerate n-dimensional rectangular box. The gap estimate is conjectured to hold more generally for Schrodinger operators with convex potentials, under Dirichlet boundary conditions; see the work of S.-T. Yau and collaborators [9, 11]. This Schrodinger gap conjecture was proved some time ago in 1 dimension by R. Lavine [8], and more recently in all dimensions by B. Andrews and J. Clutterbuck [1]. The proof in this journal by H. Donnelly [3] of the original gap conjecture in 2 dimensions (for the Dirichlet Laplacian with zero potential) is not correct. The Editors of Mathematische Zeitschrift have asked us to describe the flaws in the proof, in order to clarify the state of the literature. Donnelly’s approach to the problem is a natural one: first perform a shape optimization to rule out a non-degenerate minimizing domain, and then analyze the spectral gap for a sequence of domains degenerating to an interval, with the help of results by D. Jerison [5]. (For some history on this approach, and on the gap conjecture more generally, see the report on the AIM meeting “Low Eigenvalues of Laplace and Schrodinger Operators” [10], especially page 12 of the open problems list.) The error lies in the proof of the shape optimization step, as we now explain. Donnelly wishes to prove that no minimizing domain can exist for

In this note, we improve some results of Granville and Soundararajan on the distribution of values of the truncated random Euler product L ( 1 , X ; y ) : = ∏ p ⩽ y ( 1 − X ( p ) / p ) −1 , where the X ( p ) are independent random variables, taking the values ±1 with equal probability p / 2 ( p + 1 ) and 0 with probability 1 / ( p + 1 ) .

International audience; In this paper, we introduce a novel approach for dealing with databases containing inconsistent information. Considering four-valued logics in the context of OWA (Open World Assumption), a database ∆ is a pair (E, R) where E is the extension and R the set of rules. In our formalism, the set E is a set of pairs of the form ϕ, v where ϕ is a fact and v is either t, or b, or f (meaning respectively true, inconsistent or false), given that unknown facts are not stored. Moreover the rules extend Datalog neg rules allowing their heads to be a negative atom. We then define the notion of model of such a database, we show how to compute one particular model called semantics, and we investigate properties of this model. We also show how our approach applies to data integration and we review examples from the literature.

International audience; While recent publications have shown strong relations between impossible differential and zero-correlation distinguishers as well as between zero-correlation and integral distinguishers, we analyze in this paper some relations between the underlying key-recovery attacks against Type-II Feistel networks. The results of this paper are build on the relation presented at ACNS 2013. In particular, using a matrix representation of the round function, we show that we can not only find impossible, integral and multidimensional zero-correlation distinguishers but also find the key-words involved in the underlined key-recovery attacks. Based on this representation, for matrix-method-derived strongly-related zero-correlation and impossible distinguishers, we show that the key-words involved in the zero-correlation attack is a subset of the key-words involved in the impossible differential attack. Other relations between the key-words involved in zero-correlation, impossible and integral attacks are also extracted. Also we show that in this context the data complexity of the multidimensional zero-correlation attack is larger than that of the other two attacks.

International audience; In this paper, we present an algebraic attack against the Flurry and Curry block ciphers [12,13]. Usually, algebraic attacks against block ciphers only require one message/ciphertext pair to be mounted. In this paper, we investigate a different approach. Roughly, the idea is to generate an algebraic system from the knowledge of several well chosen correlated message/ciphertext pairs. Flurry and Curry are two families of ciphers which fully parametrizable and having a sound design strategy against the most common statistical attacks; i.e. linear and differential attacks. These ciphers are then targets of choices for algebraic attacks. It turns out that our new approach permits to go one step further in the (algebraic) cryptanalysis of difficult instances of Flurry and Curry. To explain the behavior of our attack, we have established an interesting connection between algebraic attacks and high order differential cryptanalysis [32]. From extensive experiments, we estimate that our approach – that we will call ”algebraic-high order differential” cryptanalysis – is polynomial when the Sbox is a power function. As a proof of concept, we have been able to break Flurry/Curry – up to 8 rounds – in few hours. We have also investigated the more difficult (and interesting case) of the inverse function. For such function, we have not been able to bound precisely the theoretical complexity, but our experiments indicate that our approach permits to obtain a significant practical gain. We have attacked Flurry/Curry using the inverse Sbox up to 8 rounds.

Let $\mathbb{R}$ be the field of real numbers. We consider the problem of computing the real isolated points of a real algebraic set in $\mathbb{R}^n$ given as the vanishing set of a polynomial system. This problem plays an important role for studying rigidity properties of mechanism in material designs. In this paper, we design an algorithm which solves this problem. It is based on the computations of critical points as well as roadmaps for answering connectivity queries in real algebraic sets. This leads to a probabilistic algorithm of complexity $(nd)^{O(n\log(n))}$ for computing the real isolated points of real algebraic hypersurfaces of degree $d$. It allows us to solve in practice instances which are out of reach of the state-of-the-art., Conference paper ISSAC 2020

Both the Thue-Morse and Rudin-Shapiro sequences are not suitable sequences for cryptography since their expansion complexity is small and their correlation measure of order 2 is large. These facts imply that these sequences are highly predictable despite the fact that they have a large maximum order complexity. Sun and Winterhof (2019) showed that the Thue-Morse sequence along squares keeps a large maximum order complexity. Since, by Christol's theorem, the expansion complexity of this rarefied sequence is no longer bounded, this provides a potentially better candidate for cryptographic applications. Similar results are known for the Rudin-Shapiro sequence and more general pattern sequences. In this paper we generalize these results to any polynomial subsequence (instead of squares) and thereby answer an open problem of Sun and Winterhof. We conclude this paper by some open problems., Comment: 11 pages

In this paper, we give a geometric characterization of minimal linear codes. In particular, we relate minimal linear codes to cutting blocking sets, introduced in a recent paper by Bonini and Borello. Using this characterization, we derive some bounds on the length and the distance of minimal codes, according to their dimension and the underlying field size. Furthermore, we show that the family of minimal codes is asymptotically good. Finally, we provide some geometrical constructions of minimal codes., Comment: 22 pages

International audience; We consider the problem of periodic graph exploration in which a mobile entity with constant memory, an agent, has to visit all n nodes of an input simple, connected, undirected graph in a periodic manner. Graphs are assumed to be anonymous, that is, nodes are unlabeled. While visiting a node, the agent may distinguish between the edges incident to it; for each node v, the endpoints of the edges incident to v are uniquely identified by different integer labels called port numbers. We are interested in algorithms for assigning the port numbers together with traversal algorithms for agents using these port numbers to obtain short traversal periods. Periodic graph exploration is unsolvable if the port numbers are set arbitrarily; see Budach (1978) [1]. However, surprisingly small periods can be achieved by carefully assigning the port numbers. Dobrev et al. (2005) [4] described an algorithm for assigning port numbers and an oblivious agent (i.e., an agent with no memory) using it, such that the agent explores any graph with n nodes within the period 10n. When the agent has access to a constant number of memory bits, the optimal length of the period was proved in Gąsieniec et al. (2008) [7] to be no more than 3.75n−2 (using a different assignment of the port numbers and a different traversal algorithm). In this paper, we improve both these bounds. More precisely, we show how to achieve a period length of at most for oblivious agents and a period length of at most 3.5n−2 for agents with constant memory. To obtain our results, we introduce a new, fast graph decomposition technique called a three-layer partition that may also be useful for solving other graph problems in the future. Finally, we present the first non-trivial lower bound, 2.8n−2, on the period length for the oblivious case.

Let be a polynomial of degree D. Computing the set of generalized critical valuesof the mapping (i.e. ) is an important step in algorithms computing sampling points in semi-algebraic sets defined by a single inequality. A previous algorithm allows us to compute the set of generalized critical values of $\widetilde{f}$. This one is based on the computation of the critical locus of a projection on a plane P. This plane Pmust be chosen such that some global properness properties of some projections are satisfied. These properties, which are generically satisfied, are difficult to check in practice. Moreover, choosing randomly the plane Pinduces a growth of the coefficients appearing in the computations. We provide here a new certified algorithm computing the set of generalized critical values of $\widetilde{f}$. This one is still based on the computation of the critical locus on a plane P. The certification process consists here in checking that this critical locus has dimension 1 (which is easy to check in practice), without any assumption of global properness. Moreover, this allows us to limit the growth of coefficients appearing in the computations by choosing a plane Pdefined by sparse equations. Additionally, we prove that the degree of this critical curve is bounded by $(D-1)^{n-1}-\mathfrak{d}$ where $\mathfrak{d}$ is the sum of the degrees of the positive dimensional components of the ideal $\langle \frac{\partial f}{\partial X_1}, \ldots,\frac{\partial f}{\partial X_n}\rangle$. We also provide complexity estimates on the number of arithmetic operations performed by a probabilistic version of our algorithm. Practical experiments at the end of the paper show the relevance and the importance of these results which improve significantly in practice previous contributions.

Some 25 years ago Valiant introduced an algebraic model of computation in order to study the complexity of evaluating families of polynomials. The theory was introduced along with the complexity classes VP and VNP which are analogues of the classical classes P and NP. Families of polynomials that are difficult to evaluate (that is, VNP-complete) includes the permanent and hamiltonian polynomials. In a previous paper the authors together with P. Koiran studied the expressive power of permanent and hamiltonian polynomials of matrices of bounded treewidth, as well as the expressive power of perfect matchings of planar graphs. It was established that the permanent and hamiltonian polynomials of matrices of bounded treewidth are equivalent to arithmetic formulas. Also, the sum of weights of perfect matchings of planar graphs was shown to be equivalent to (weakly) skew circuits. In this paper we continue the research in the direction described above, and study the expressive power of permanents, hamiltonians and perfect matchings of matrices that have bounded pathwidth or bounded cliquewidth. In particular, we prove that permanents, hamiltonians and perfect matchings of matrices that have bounded pathwidth express exactly arithmetic formulas. This is an improvement of our previous result for matrices of bounded treewidth. Also, for matrices of bounded weighted cliquewidth we show membership in VP for these polynomials., 21 pages

A decomposition of a multigraph $G$ is a partition of its edges into subgraphs $G(1), \ldots , G(k)$. It is called an $r$-factorization if every $G(i)$ is $r$-regular and spanning. If $G$ is a subgraph of $H$, a decomposition of $G$ is said to be enclosed in a decomposition of $H$ if, for every $1 \leq i \leq k$, $G(i)$ is a subgraph of $H(i)$. Feghali and Johnson gave necessary and sufficient conditions for a given decomposition of $\lambda K_n$ to be enclosed in some $2$-edge-connected $r$-factorization of $\mu K_{m}$ for some range of values for the parameters $n$, $m$, $\lambda$, $\mu$, $r$: $r=2$, $\mu>\lambda$ and either $m \geq 2n-1$, or $m=2n-2$ and $\mu = 2$ and $\lambda=1$, or $n=3$ and $m=4$. We generalize their result to every $r \geq 2$ and $m \geq 2n - 2$. We also give some sufficient conditions for enclosing a given decomposition of $\lambda K_n$ in some $2$-edge-connected $r$-factorization of $\mu K_{m}$ for every $r \geq 3$ and $m = (2 - C)n$, where $C$ is a constant that depends only on $r$, $\lambda$ and~$\mu$., Comment: 17 pages; fixed the proof of Theorem 1.4 and other minor changes

“Mirror Theory” is the theory that evaluates the number of solutions of affine systems of equalities $$({=})$$ and non equalities ( $$\ne $$ ) in finite groups. It is deeply related to the security and attacks of many generic cryptographic secret key schemes, for example random Feistel schemes (balanced or unbalanced), Misty schemes, Xor of two pseudo-random bijections to generate a pseudo-random function etc. In this paper we will assume that the groups are abelian. Most of time in cryptography the group is $$((\mathbb {Z}/2\mathbb {Z})^n, \oplus )$$ and we will concentrate this paper on these cases. We will present here general definitions, some theorems, and many examples and computer simulations.

International audience; The construction of a Quasi-Cyclic Low Density Parity-Check (QC-LDPC) matrix is usually carried out in two steps. In the first step, a prototype matrix is defined according to certain criteria (size, girth, check and variable node degrees, etc.). The second step involves expansion of the prototype matrix. During this last phase, an integer value is assigned to each non-null position in the prototype matrix corresponding to the right-rotation of the identity matrix. The problem of determining these integer values is complex. State-of-the-art solutions use either some mathematical constructions to guarantee a given girth of the final QC-LDPC code or a random search of values until the target girth is satisfied. In this paper, we propose an alternative/complementary method that reduces the search space by defining large equivalence classes of topologically identical matrices through row and column permutations using additive, structural and multiplicative transformations. Selecting only a single element per equivalence class can reduce the search space by a few orders of magnitude. Then, we use the formalism of constraint programming to list the exhaustive sets of solutions for a given girth and a given expansion factor. An example is presented in all sections of the paper to illustrate the methodology.

In Part I of this paper we studied the irregularities of distribution of binary sequences relative to short arithmetic progressions. First we introduced a quantitative measure for this property. Then we studied the typical and minimal values of this measure for binary sequences of a given length. In this paper our goal is to give constructive bounds for these minimal values.

International audience; This paper deals with compact label-based representations for trees. Consider an $n$-node undirected connected graph $G$ with a predefined numbering on the ports of each node. The {\em all-ports} tree labeling $\cL_{all}$ gives each node $v$ of $G$ a label containing the port numbers of all the {\em tree} edges incident to $v$. The {\em upward} tree labeling $\cL_{up}$ labels each node $v$ by the number of the port leading from $v$ to its parent in the tree. Our measure of interest is the worst case and total length of the labels used by the scheme, denoted $M_{up}(T)$ and $S_{up}(T)$ for $\cL_{up}$ and $M_{all}(T)$ and $S_{all}(T)$ for $\cL_{all}$. The problem studied in this paper is the following: Given a graph $G$ and a predefined port labeling for it, with the ports of each node $v$ numbered by $0,\ldots,\deg(v)-1$, select a rooted spanning tree for $G$ minimizing (one of) these measures. We show that the problem is polynomial for $M_{up}(T)$, $S_{up}(T)$ and $S_{all}(T)$ but NP-hard for $M_{all}(T)$ (even for 3-regular planar graphs). We show that for every graph $G$ and port numbering there exists a spanning tree $T$ for which $S_{up}(T) = O(n\log\log n)$. We give a tight bound of $O(n)$ in the cases of complete graphs with arbitrary labeling and arbitrary graphs with symmetric port assignments. We conclude by discussing some applications for our tree representation schemes.

In this paper we consider space-time codes where the code-words are restricted to either real or quaternion matrices. We prove two separate diversity-multiplexing gain trade-off (DMT) upper bounds for such codes and provide a criterion for a lattice code to achieve these upper bounds. We also point out that lattice codes based on Q-central division algebras satisfy this optimality criterion. As a corollary this result provides a DMT classification for all Q-central division algebra codes that are based on standard embeddings., Comment: 6 pages, 1 figure. Conference paper submitted to the International Symposium on Information Theory 2018

International audience; Decidability of type checking for dependently typed languages usually requires a decidable equality on types. Since bisimilarity on (weakly final) coalgebras such as streams is undecidable, one cannot use it as the equality in type checking. Instead, languages based on dependent types with decidable type checking such as Coq or Agda use intensional equality for type checking. Two streams are definitionally equal if the underlying terms reduce to the same normal form, i.e. if the underlying programs are syntactically equivalent. For reasoning about equality of streams one introduces bisimilarity as a propositional rather than judgemental equality.In this paper we show that it is not possible to strengthen intensional equality in a decidable way while having the property that equality respects one step expansion, which means that a stream with head n and tail s is equal to $\mathrm {cons}(n,s)$ cons(n,s). This property, which would be very useful in type checking, would not necessarily imply that bisimilar streams are equal, and we prove that there exist equalities with this properties which do not coincide with bisimilarity. Whereas a proof that bisimilarity on streams is undecidable is straightforward, proving that respecting one step expansion makes equality undecidable is much more involved and relies on an inseparability result for sets of codes for Turing machines. We prove this theorem both for streams with primitive corecursion and with coiteration as introduction rule.Therefore, pattern matching on streams is, understood literally, not a valid principle, since it assumes that every stream is equal to a stream of the form $\mathrm {cons}(n,s)$ cons(n,s). We relate this problem to the subject reduction problem found when adding pattern matching on coalgebras to Coq and Agda. We discuss how this was solved in Agda by defining coalgebras by their elimination rule and replacing pattern matching on coalgebras by copattern matching, and how this relates to the approach in Agda which uses the type of delayed computations, i.e. the so called “musical notation” for codata types.

In this paper we present quantum information set decoding (ISD) algorithms for binary linear codes. First, we give an alternative view on the quantum walk based algorithms proposed by Kachigar and Tillich (PQCrypto'17). It is more general and allows to consider any ISD algorithm that has certain properties. The algorithms of May-Meuer-Thomae and Becker-Jeux-May-Meuer satisfy these properties. Second, we translate May-Ozerov Near Neighbour technique (Eurocrypt'15) to an `update-and-query' language more suitable for the quantum walk framework. First, this re-interpretation makes possible to analyse a broader class of algorithms and, second, allows us to combine Near Neighbour search with the quantum walk framework and use both techniques to give a quantum version of Dumer's ISD with Near Neighbour., This is a full and corrected version of the paper appeared in PQCrypto2018

International audience; This paper focuses on compact deterministic self-stabilizing solutions for the leader election problem. When the solution is required to be silent (i.e., when the state of each process remains fixed from some point in time during any execution), there exists a lower bound of Ω(log n) bits of memory per participating node , where n denotes the number of nodes in the system. This lower bound holds even in rings. We present a new deterministic (non-silent) self-stabilizing protocol for n-node rings that uses only O(log log n) memory bits per node, and stabilizes in O(n log 2 n) rounds. Our protocol has several attractive features that make it suitable for practical purposes. First, it assumes an execution model that is used by existing compilers for real networks. Second, the size of the ring (or any upper bound on this size) does not need to be known by any node. Third, the node identifiers can be of various sizes. Finally, no synchrony assumption, besides weak fairness, is assumed. Our result shows that, perhaps surprisingly, silence can be traded for an exponential decrease in memory space without significantly increasing stabilization time or introducing restrictive assumptions. * A preliminary version of this paper has appeared in [12, 13]. † Additional support from the ANR project IRIS.

A complete weighted graph G = ( V , E , w ) is called Δ β -metric, for some β ≥ 1 / 2 , if G satisfies the β-triangle inequality, i.e., w ( u , v ) ≤ β ⋅ ( w ( u , x ) + w ( x , v ) ) for all vertices u , v , x ∈ V . Given a Δ β -metric graph G = ( V , E , w ) and a center c ∈ V , and an integer p, the Δ β -Star p -Hub Center problem ( Δ β -SpHCP) is to find a depth-2 spanning tree T of G rooted at c such that c has exactly p children (also called hubs) and the diameter of T is minimized. In this paper, we study Δ β -SpHCP for all β ≥ 1 2 . We show that for any ϵ > 0 , to approximate the Δ β -SpHCP to a ratio g ( β ) − ϵ is NP-hard and give r ( β ) -approximation algorithms for the same problem where g ( β ) and r ( β ) are functions of β. A subclass of metric graphs is identified that Δ β -SpHCP is polynomial-time solvable. Moreover, some r ( β ) -approximation algorithms given in this paper meet approximation lower bounds.

International audience; Logical formalisms equivalent to weighted automata have been the topic of numerous research papers in the recent years. It started with the seminal result by Droste and Gastin on weighted logics over semir-ings for words. It has been extended in two dimensions by many authors. First, the weight domain has been extended to valuation monoids, valuation structures, etc., to capture more quantitative properties. Along another dimension, different structures such as ranked or unranked trees, nested words, Mazurkiewiz traces, etc., have been considered. The long and involved proofs of equivalences in all these papers are implicitely based on the same core arguments. This article provides a meta-theorem which unifies these different approaches. Towards this, we first introduce a core weighted logic with a minimal number of features and a simplified syntax. Then, we define a new semantics for weighted automata and weighted logics in two phases—an abstract semantics based on multisets of weight structures (independent of particular weight domains) followed by a concrete semantics. We show at the level of the abstract semantics that weighted automata and core weighted logic have the same expressive power. We show how previous results can be recovered from our result by logical reasoning. In this paper, we prove the meta-theorem for words, ranked and unranked trees, showing the robustness of our approach.

International audience; Following the emergence of Kim and Barbulescu's new number field sieve (exTNFS) algorithm at CRYPTO'16 [21] for solving discrete logarithm problem (DLP) over the finite field; pairing-based cryptography researchers are intrigued to find new parameters that confirm standard security levels against exTNFS. Recently, Barbulescu and Duquesne have suggested new parameters [3] for well-studied pairing-friendly curves i.e., Barreto-Naehrig (BN) [5], Barreto-Lynn-Scott (BLS-12) [4] and Kachisa-Schaefer-Scott (KSS-16) [19] curves at 128-bit security level (twist and subgroup attack secure). They have also concluded that in the context of Optimal-Ate pairing with their suggested parameters , BLS-12 and KSS-16 curves are more efficient choices than BN curves. Therefore, this paper selects the atypical and less studied pairing-friendly curve in literature, i.e., KSS-16 which offers quartic twist, while BN and BLS-12 curves have sextic twist. In this paper, the authors optimize Miller's algorithm of Optimal-Ate pairing for the KSS-16 curve by deriving efficient sparse multiplication and implement them. Furthermore , this paper concentrates on the Miller's algorithm to experimentally verify Barbulescu et al.'s estimation. The result shows that Miller's algorithm time with the derived pseudo 8-sparse multiplication is most efficient for KSS-16 than other two curves. Therefore, this paper defends Barbulescu and Duquesne's conclusion for 128-bit security.

International audience; The action of a translation on a continuous object before its digitization generates several digitizations. The dual, introduced by the authors in a previous paper, stands for these digitizations in function of the translation parameters. This paper focuses on the combinatorics of the dual by making a link between the digitization number and the boundary curve, especially through its dual representation. The convex case is then studied and a few signicant examples are exhibited.

In this paper, we propose an adaptation of partial difference equations (PDEs) level set method for nonmonotonic front propagation on weighted graphs. This adaptation leads to a PDE, whose coefficients are data geometry dependent. Our motivation is to extend their applications to any discrete data that can be represented by a weighted graph. This paper follows several preliminaries of our works, and introduces several significant improvements: A simplified and explicit representation of a front on a weighted graph, a new formulation of the level set equation on weighted graphs considering both time-dependent and stationary versions of this equation in the case of signed velocities, and an efficient algorithm that generalized the fast marching to graphs with signed velocities. We propose to use this method for image processing and for high-dimensional data classification.

The notion of privacy in the probing model, introduced by Ishai, Sahai, and Wagner in 2003, is nowadays frequently involved to assess the security of circuits manipulating sensitive information. However, provable security in this model still comes at the cost of a significant overhead both in terms of arithmetic complexity and randomness complexity. In this paper, we deal with this issue for circuits processing multiplication over finite fields. Our contributions are manifold. Extending the work of Belaid, Benhamouda, Passelegue, Prouff, Thillard, and Vergnaud at Eurocrypt 2016, we introduce an algebraic characterization of the privacy for multiplication in any finite field and we propose a novel algebraic characterization for non-interference (a stronger security notion in this setting). Then, we present two generic constructions of multiplication circuits in finite fields that achieve non-interference in the probing model. Denoting by d the number of probes used by the adversary, the first proposal reduces the number of bilinear multiplications (i.e., of general multiplications of two non-constant values in the finite field) to only \(2d+1\) whereas the state-of-the-art was \(O(d^2)\). The second proposal reduces the randomness complexity to d random elements in the underlying finite field, hence improving the \(O(d \log d)\) randomness complexity achieved by Belaid et al. in their paper. This construction is almost optimal since we also prove that d / 2 is a lower bound. Eventually, we show that both algebraic constructions can always be instantiated in large enough finite fields. Furthermore, for the important cases \(d \in \{2,3\}\), we illustrate that they perform well in practice by presenting explicit realizations for finite fields of practical interest.

The triangle partition problem is a generalization of the well-known graph matching problem consisting of finding the maximum number of independent edges in a given graph, i.e., edges with no common node. Triangle partition instead aims to find the maximum number of disjoint triangles. The triangle partition problem is known to be NP-complete. Thus, in this paper, the focus is on the local maximization variant, called maximal triangle partition (MTP). Thus, paper presents a new self-stabilizing algorithm for MTP that converges in O(m) moves under the unfair distributed daemon.

A complete weighted graph \(G= (V, E, w)\) is called \(\varDelta _{\beta }\)-metric, for some \(\beta \ge 1/2\), if G satisfies the \(\beta \)-triangle inequality, i.e., \(w(u,v) \le \beta \cdot (w(u,x) + w(x,v))\) for all vertices \(u,v,x\in V\). Given a \(\varDelta _{\beta }\)-metric graph \(G=(V, E, w)\) and a center \(c\in V\), and an integer p, the \(\varDelta _{\beta }\)-Star p-Hub Center Problem (\(\varDelta _{\beta }\)-SpHCP) is to find a depth-2 spanning tree T of G rooted at c such that c has exactly p children and the diameter of T is minimized. The children of c in T are called hubs. For \(\beta = 1\), \(\varDelta _{\beta }\)-SpHCP is NP-hard. (Chen et al., COCOON 2016) proved that for any \(\varepsilon >0\), it is NP-hard to approximate the \(\varDelta _{\beta }\)-SpHCP to within a ratio \(1.5-\varepsilon \) for \(\beta = 1\). In the same paper, a \(\frac{5}{3}\)-approximation algorithm was given for \(\varDelta _{\beta }\)-SpHCP for \(\beta = 1\). In this paper, we study \(\varDelta _{\beta }\)-SpHCP for all \(\beta \ge \frac{1}{2}\). We show that for any \(\varepsilon > 0\), to approximate the \(\varDelta _{\beta }\)-SpHCP to a ratio \(g(\beta ) - \varepsilon \) is NP-hard and we give \(r(\beta )\)-approximation algorithms for the same problem where \(g(\beta )\) and \(r(\beta )\) are functions of \(\beta \). If \(\beta \le \frac{3 - \sqrt{3}}{2}\), we have \(r(\beta ) = g(\beta ) = 1\), i.e., \(\varDelta _{\beta }\)-SpHCP is polynomial time solvable. If \(\frac{3-\sqrt{3}}{2} < \beta \le \frac{2}{3}\), we have \(r(\beta ) = g(\beta ) = \frac{1 + 2\beta - 2\beta ^2}{4(1-\beta )}\). For \(\frac{2}{3} \le \beta \le 1\), \(r(\beta ) = \min \{\frac{1 + 2\beta - 2\beta ^2}{4(1-\beta )}, 1 + \frac{4\beta ^2}{5\beta +1}\}\). Moreover, for \(\beta \ge 1\), we have \(r(\beta ) = \min \{\beta + \frac{4\beta ^2- 2\beta }{2 + \beta }, 2\beta + 1\}\). For \(\beta \ge 2\), the approximability of the problem (i.e., upper and lower bound) is linear in \(\beta \).

This work is a companion paper of Gamboa, Nagel, Rouault (J. Funct. Anal. 2016). We continue to explore the connections between large deviations for random objects issued from random matrix theory and sum rules. Here, we are concerned essentially with measures on the unit circle whose support is an arc that is possibly proper. We particularly focus on two matrix models. The first one is the Gross-Witten ensemble. In the gapped regime we give a probabilistic interpretation of a Simon sum rule. The second matrix model is the Hua-Pickrell ensemble. Unlike the Gross-Witten ensemble the potential is here infinite at one point. Surprisingly, but as in the above mentioned paper, we obtain a completely new sum rule for the deviation to the equilibrium measure of the Hua-Pickrell ensemble. The extension to matrix measures is also studied., Extended version with further details, comments and updated references

Best paper award of the 36th Computers and Information in Engineering Conference – Advanced Modeling & Simulation (AMS); International audience; This article proposes the use of polytopes in $\mathcal{HV}$-description to solve tolerance analysis problems. Polytopes are defined by a finite set of half-spaces representing geometric, contact or functional specifications. However, the list of the vertices of the polytopes are useful for computing other operations as Minkowski sums. Then, this paper proposes a truncation algorithm to obtain the $\mathcal{V}$-description of polytopes in $\mathbb{R}^n$ from its $\mathcal{H}$-description. It is detailed how intersections of polytopes can be calculated by means of the truncation algorithm. Minkowski sums as well can be computed using this algorithm making use of the duality property of polytopes. Therefore, a Minkowski sum can be calculated intersecting some half-spaces in the dual space. Finally, the approach based on $\mathcal{HV}$-polytopes is illustrated by the tolerance analysis of a real industrial case using the open source software PolitoCAT and politopix.

In a recent paper, Kaiser and Stehlik (J Combin Theory Ser B 113:1–17, 2015) have extended the concept of quadrangulation of a surface to higher dimension, and showed that every quadrangulation of the n-dimensional projective space \(\mathbb{P}^{n}\) is at least (n + 2)-chromatic, unless it is bipartite. They conjectured that for any integers k ≥ 1 and n ≥ 2k + 1, the Schrijver graph SG(n, k) contains a spanning subgraph which is a non-bipartite quadrangulation of \(\mathbb{P}^{n-2k}\). The purpose of this paper is to prove the conjecture.

In 1967, Schmidt wrote a seminal paper (Schmidt in Ann Math 85:430–472, 1967) on heights of subspaces of $$\mathbb {R}^n$$ or $$\mathbb {C}^n$$ defined over a number field K, and diophantine approximation problems. The going-down Theorem— one of the main theorems he proved in his paper—remains valid in two cases depending on whether the embedding of K in the complex field $$\mathbb {C}$$ is a real or a complex non-real embedding. For the latter, and more generally as soon as K is not totally real, at some point of the proof, the arguments in Schmidt (Ann Math 85:430–472, 1967) do not exactly work as announced. In this note, Schmidt’s ideas are worked out in details and his proof of the complex case is presented, solving the aforementioned problem. Some definitions of Schmidt are reformulated in terms of multilinear algebra and wedge product, following the approaches of Laurent (Analytic number theory, essays in honour of Klaus Roth. Cambridge University Press, Cambridge, pp 306–314, 2009), Bugeaud and Laurent (Mathematische Zeitschrift 265(2):249–262, 2010) and Roy (Journal de theorie des nombres de Bordeaux 27:591–603, 2015), Roy (Mathematische Zeitschrift 283(1–2):143–155, 2016). In Laurent (Analytic number theory, essays in honour of Klaus Roth. Cambridge University Press, Cambridge, pp 306–314, 2009) Laurent introduces in the case $$K=\mathbb {Q}$$ a family of exponents and he gives a series of inequalities relating them. In Sect. 5 these exponents are defined for an arbitrary number field K. Using the going-up and the going-down Theorems Laurent’s inequalities are generalized to this setting.

Many recent papers deal with the enumeration of 2-dimensional walks with prescribed steps confined to the positive quadrant. The classification is now complete for walks with steps in $\{0, \pm 1\}^2$: the generating function is D-finite if and only if a certain group associated with the step set is finite. We explore in this paper the analogous problem for 3-dimensional walks confined to the positive octant. The first difficulty is their number: there are 11074225 non-trivial and non-equivalent step sets in $\{0, \pm 1\}^3$ (instead of 79 in the quadrant case). We focus on the 35548 that have at most six steps. We apply to them a combined approach, first experimental and then rigorous. On the experimental side, we try to guess differential equations. We also try to determine if the associated group is finite. The largest finite groups that we find have order 48 -- the larger ones have order at least 200 and we believe them to be infinite. No differential equation has been detected in those cases. On the rigorous side, we apply three main techniques to prove D-finiteness. The algebraic kernel method, applied earlier to quadrant walks, works in many cases. Certain, more challenging, cases turn out to have a special Hadamard structure, which allows us to solve them via a reduction to problems of smaller dimension. Finally, for two special cases, we had to resort to computer algebra proofs. We prove with these techniques all the guessed differential equations. This leaves us with exactly 19 very intriguing step sets for which the group is finite, but the nature of the generating function still unclear., Final version, to appear in Annals of Combinatorics. 36 pages

In the paper [H. Bourles, B. Marinescu, U. Oberst, Weak exponential stability (w.e.s.) of linear time-varying (LTV) differential behaviors, Linear Algebra Appl. 486 (2015) 523–571] we studied the problem of the title. If a finitely generated torsion module over an appropriate ring of differential operators and its associated autonomous system are regular singular the system is never w.e.s. In contrast we computed a square complex matrix for each irregular singular module and showed that the system is w.e.s. resp. not stable if all eigenvalues of the matrix have positive real parts resp. if at least one eigenvalue has negative real part. In this supplement of the quoted paper we show that the spectrum of the matrix and the decay exponent are isomorphy invariants of the module. The proofs make essential use of results exposed in [P. Maisonobe, C. Sabbah, D -module coherents et holonomes, Hermann, Paris, 1993]. We also complement the main w.e.s. result of our quoted paper by the case where at least one eigenvalue of the matrix is purely imaginary.

Part 2: Regular Papers; International audience; We study 2-dimensional cellular automata as language recog-nizers. We are looking for closure properties, similar to the one existing in one dimension. Some results are already known for the most used neighbourhoods, however many problems remain open concerning more general neighbourhoods. In this paper we provide a construction to prove a constant acceleration theorem for extended von Neumann neighbourhoods. We then use this theorem and some classical tools to prove the equivalence of those neighbourhoods, considering the set of languages recognizable in real time.

The main task of the paper is to investigate the question of the recognition of digital polyhedra with a fixed number of facets: given a finite lattice set $$S\subset \mathbb {Z}^d$$ and an integer n, does there exist a polyhedron P of $$\mathbb {R}^d$$ with n facets and $$P\cap \mathbb {Z}^d=S$$? The problem can be stated in terms of polyhedral separation of the set S and its complementary $$S^c=\mathbb {Z}^d / S$$. The difficulty is that the set $$S^c$$ is not finite. It makes the classical algorithms intractable for this purpose. This problem is overcome by introducing a partial order "is in the shadow of". Its minimal lattice elements are called the jewels. The main result of the paper is within the domain of the geometry of numbers: under some assumptions on the lattice set S if $$S\subset \mathbb {Z}^2$$ is not degenerated or if the interior of the convex hull of $$S\subset \mathbb {Z}^d$$ contains an integer point, it has only a finite number of lattice jewels. In this case, we provide an algorithm of recognition of a digital polyhedron with n facets which always finishes.

Specifying the bidegrees (n, m) of mixed polynomials P (z, ¯ z) of the single complex variable z, with complex coefficients, allows to investigate interesting roots structures and counting; intermediate between complex and real algebra. Multivariate mixed polynomials appeared in recent papers dealing with Milnor fibrations, but in this paper we focus on the univariate case and m = 1, which is closely related to the important subject of harmonic maps. Here we adapt, to this setting, two algorithms of computer algebra: Vandermonde interpolation and a bissection-exclusion method for root isolation. Implemented in Maple, they are used to explore some interesting classes of examples.

In a previous paper, we proved that the limit of the collection of possible eigenvalues of output states of a random quantum channel is a deterministic, compact set K_{k,t}. We also showed that the set K_{k,t} is obtained, up to an intersection, as the unit ball of the dual of a free compression norm. In this paper, we identify the maximum of l^p norms on the set K_{k,t} and prove that the maximum is attained on a vector of shape (a,b,...,b) where a > b. In particular, we compute the precise limit value of the minimum output entropy of a single random quantum channel. As a corollary, we show that for any eps > 0, it is possible to obtain a violation for the additivity of the minimum output entropy for an output dimension as low as 183, and that for appropriate choice of parameters, the violation can be as large as log 2 - eps. Conversely, our result implies that, with probability one, one does not obtain a violation of additivity using conjugate random quantum channels and the Bell state, in dimension 182 and less., v3: appendix replaced by Lemma 3.8

We study the complexity of deciding whether a given digraph D has a vertex-partition into two disjoint subdigraphs with given structural properties. Let H and E denote the following two sets of natural properties of digraphs: H = {acyclic, complete, arcless, oriented (no 2-cycle), semicomplete, symmetric, tournament} and E = {strongly connected, connected, minimum out-degree at least 1, minimum in-degree at least 1, minimum semi-degree at least 1, minimum degree at least 1, having an out-branching, having an in-branching}. In this paper, we determine the complexity of deciding, for any fixed pair of positive integers k 1 , k 2 , whether a given digraph has a vertex partition into two digraphs D 1 , D 2 such that | V ( D i ) | ź k i and D i has property P i for i = 1 , 2 when P 1 ź H and P 2 ź H ź E . We also classify the complexity of the same problems when restricted to strongly connected digraphs.The complexity of the 2-partition problems where both P 1 and P 2 are in E is determined in the companion paper 2.

In this paper, a sum rule means a relationship between a functional defined on a subset of all probability measures on R involving the reverse Kullback-Leibler divergence with respect to a particular distribution and recursion coefficients related to the orthogonal polynomial construction. The first sum rule is the Szegýo-Verblunsky theorem (see Simon (2011) Theorem 1.8.6 p. 29) and concerns the case of trigonometrical polynomials on the torus. More recently, Killip and Simon (Killip and Simon (2003)) have given a revival interest to this subject by showing a quite surprising sum rule for measures dominating the semicircular distribution. Indeed, this sum rule includes a contribution of the atomic part of the measure away from the support of the circular law. In this paper, we recover this sum rules by using only large deviations tools on random matrices. Furthermore, we obtain new (up to our knowledge) magic sum rules for the reverse Kullback-Leibler divergence with respect to the Pastur-Marchenko or Kesten-McKay distributions. As in the semicircular case, these formulas generally include a contribution of the atomic part appearing away from the support of the reference measure. From the point of view of large deviations, we obtain these formulas by showing a large deviation principle for the point mass measure concentrated on random eigenvalues of classical ensembles and combine it with a large deviation principle due to Gamboa and Rouault (2011) for the recursion coefficients.

Banach Center Publications; International audience; Let ε be an algebraic unit for which the rank of the group of units of the order ℤ[ε] is equal to 1. Assume that ε is not a complex root of unity. It is natural to wonder whether ε is a fundamental unit of this order. It turns out that the answer is in general yes, and that a fundamental unit of this order can be explicitly given (as an explicit polynomial in ε) in the rare cases when the answer is no. This paper is a self-contained exposition of the solution to this problem, solution which was up to now scattered in many papers in the literature.

It has been a challenging problem to determine the smallest graph class where a problem is proved to be hard. In the literature, this has been pointed out to be very important in order to establish the real nature of a combinatorial problem.An oriented k -coloring of an oriented graph G ? = ( V , E ? ) is a partition of V into k subsets such that there are no two adjacent vertices belonging to the same subset, and all the arcs between a pair of subsets have the same orientation. The decision problem k - oriented chromatic number ( ocn k ) consists of an oriented graph G ? and an integer k 0 , plus the question if there exists an oriented k -coloring of G ? . By its strong appeal, many papers have presented NP-completeness proofs for ocn k . It was not known the complexity status of ocn k when the input graph G ? satisfies that the underlying graph G has maximum degree 3.In this paper we prove that ocn 4 is NP-complete for an acyclic oriented graph G ? such that G is at same time: connected, planar, bipartite, and with maximum degree 3.Our result defines a P versus NP-complete dichotomy with respect to the maximum degree Δ ( G ) : ocn k is polynomial if Δ ( G ) < 3 and NP-complete if Δ ( G ) ? 3 , since it is known that ocn 3 is in P, and that ocn k is in P when the underlying graph has Δ ( G ) ? 2 .

In a graph, a matching cut is an edge cut that is a matching. Matching Cut is the problem of deciding whether or not a given graph has a matching cut, which is known to be NP-complete. This paper provides a first branching algorithm solving Matching Cut in time O * ( 2 n / 2 ) = O * ( 1.4143 n ) for an n-vertex input graph, and shows that Matching Cut parameterized by the vertex cover number ? ( G ) can be solved by a single-exponential algorithm in time 2 ? ( G ) O ( n 2 ) . Moreover, the paper also gives a polynomially solvable case for Matching Cut which covers previous known results on graphs of maximum degree three, line graphs, and claw-free graphs.

In this paper, we consider Markov chains of the form $X^{n}_{(k+1)/n}=\psi _{k}(X^{n}_{k/n},Z_{k+1}/\sqrt{n},1/n)$ where the innovation comes from the sequence $Z_{k},k\in \mathbb{N} ^{\ast }$ of independent centered random variables with arbitrary law. Then, we study the convergence $\mathbb{E} [f(X^{n}_t)]\rightarrow \mathbb{E} [f(X_t)]$ where $(X_t)_{t \geqslant 0}$ is a Markov process in continuous time. This may be considered as an invariance principle, which generalizes the classical Central Limit Theorem to Markov chains. Alternatively (and this is the main motivation of our paper), $X^{n}$ may be an approximation scheme used in order to compute $\mathbb{E} [f(X_t)]$ by Monte Carlo methods. Estimates of the error are given for smooth test functions $f$ as well as for measurable and bounded $f.$ In order to prove convergence for measurable test functions we assume that $Z_{k}$ satisfies Doeblin’s condition and we use Malliavin calculus type integration by parts formulas based on the smooth part of the law of $Z_{k}$. As an application, we will give estimates of the error in total variation distance for the Ninomiya Victoir scheme.

This paper addresses set invariance properties for linear time-delay systems. More precisely, the first goal of the article is to review known necessary and/or sufficient conditions for the existence of invariant sets with respect to dynamical systems described by linear discrete time-delay difference equations (dDDEs). Secondly, we address the construction of invariant sets in the original state space (also called D -invariant sets) by exploiting the forward mappings. The notion of D -invariance is appealing since it provides a region of attraction, which is difficult to obtain for delay systems without taking into account the delayed states in some appropriate extended state space model. The present paper contains a sufficient condition for the existence of ellipsoidal D -contractive sets for dDDEs, and a necessary and sufficient condition for the existence of D -invariant sets in relation to linear time-varying dDDE stability. Another contribution is the clarification of the relationship between convexity (convex hull operation) and D -invariance of linear dDDEs. In short, it is shown that the convex hull of the union of two or more D -invariant sets is not necessarily D -invariant, while the convex hull of a non-convex D -invariant set is D -invariant.

The flag variety of a complex reductive linear algebraic group G is by definition the quotient G/B by a Borel subgroup. It can be regarded as the set of Borel subalgebras of Lie(G). Given a nilpotent element e in Lie(G), one calls Springer fiber the subvariety formed by the Borel subalgebras which contain e. Springer fibers have in general a complicated structure (not irreducible, singular). Nevertheless, a theorem by C. De Concini, G. Lusztig, and C. Procesi asserts that, when G is classical, a Springer fiber can always be paved by finitely many subvarieties isomorphic to affine spaces. In this paper, we study varieties generalizing the Springer fibers to the context of partial flag varieties, that is, subvarieties of the quotient G/P by a parabolic subgroup (instead of a Borel subgroup). The main result of the paper is a generalization of De Concini, Lusztig, and Procesi's theorem to this context., Comment: 39 pages, v2: fixed some mistakes, revision of Section 8

International audience; Emergy is becoming an important sustainability ratio. Emergy analysis of real systems cannot be summarized to the trivial analysis of systems with several sources and one product. In such case only the application of the first rule of emergy algebra (all sources of emergy to a process are assigned to the process output) is required and the result can be stored in a simple table.But real systems of interest (ecosystems, complex chemical production systems, etc) are interconnected systems with feedbacks, splits and by-products. As a consequence mathematical foundations for exact emergy analysis appear to be necessary. Indeed, emergy computation within an energy system diagram is based on four rules, the use of which is sometimes confusing. The complexity of the computation of emergy within interconnected system comes also from the fact that it does not obey Kirchoff-like circuit law. Thus, linear algebra approach fails.Emergy computation follows a logic of memorization, thus the evaluation principles deal with pathways. An emergy pathway is a pathway from a source of emergy to a product which represents the sequel of assignations of the emergy source by the processes of the interconnected system.Looking at pathways in ecosystems analysis is not a new subject. Because of the rules of emergy computation (specifically the no double counting rule) among an abundant classification of pathways in ecosystems the emergy pathways appear to be particular elements of only two classes of pathways: the class of simple pathways and the class of terminal non-feedback cycle pathways.This paper is the companion paper of a previous paper written by the same authors. In the previous paper it is explained how to compute emergy flowing on a given arc of an emergy graph assuming all emergy pathways ending by this arc known. As explained in this paper an emergy graph is a transformed graph from an energy system diagram.The aims of this paper are as follows. (i) Explain how to transform an energy system diagram into an emergy graph. (ii) Provide a clear and new algorithm easily programmable to compute emergy pathways. (iii) Insert this new algorithm in the whole procedure for computing an emergy flowing between two processes. (iv) Apply the whole procedure on a real world example. This example shows that the emergy content from meadowland-sun can either carry out by the milk or by the electricity (when considering the biogas and the CHP plant). In the general case, this emergy amount is lesser than the total meadowland-sun emergy.

Acyclicity constraints are prevalent in knowledge representation and applications where acyclic data structures such as DAGs and trees play a role. Recently, such constraints have been considered in the satisfiability modulo theories (SMT) framework, and in this paper we carry out an analogous extension to the answer set programming (ASP) paradigm. The resulting formalism, ASP modulo acyclicity, offers a rich set of primitives to express constraints related to recursive structures. In the technical results of the paper, we relate the new generalization with standard ASP by showing (i) how acyclicity extensions translate into normal rules, (ii) how weight constraint programs can be instrumented by acyclicity extensions to capture stability in analogy to unfounded set checking, and (iii) how the gap between supported and stable models is effectively closed in the presence of such an extension. Moreover, we present an efficient implementation of acyclicity constraints by incorporating a respective propagator into the state-of-the-art ASP solver CLASP. The implementation provides a unique combination of traditional unfounded set checking with acyclicity propagation. In the experimental part, we evaluate the interplay of these orthogonal checks by equipping logic programs with supplementary acyclicity constraints. The performance results show that native support for acyclicity constraints is a worthwhile addition, furnishing a complementary modeling construct in ASP itself as well as effective means for translation-based ASP solving.

A substring of a string is unbordered if its only border is the empty string. The study of unbordered substrings goes back to the paper of Ehrenfeucht and Silberger [Discr. Math 26 1979]. The main focus of their and subsequent papers was to elucidate the relationship between the longest unbordered substring and the minimal period of strings. In this paper, we consider the algorithmic problem of computing the longest unbordered substring of a string. The problem was introduced recently by G. Kucherov et al.i¾ź[CPM 2015], where the authors showed that the average-case running time of the simple, border-array based algorithm can be bounded by $$\mathcal {O}\max \{n, n^2/\sigma ^4\}$$ for $$\sigma $$ being the size of the alphabet. The worst-case running time remained $$\mathcal {O}n^2$$. Here we propose two algorithms, both presenting substantial theoretical improvements to the result of [11]. The first algorithm has $$\mathcal {O}n \log n$$ average-case running time and $$\mathcal {O}n^2$$ worst-case running time, and the second algorithm has $$\mathcal {O}n^{1.5}$$ worst-case running time.