Search results for "Combinatorics"
showing 10 items of 1770 documents
Dictionary-symbolwise flexible parsing
2012
AbstractLinear-time optimal parsing algorithms are rare in the dictionary-based branch of the data compression theory. A recent result is the Flexible Parsing algorithm of Matias and Sahinalp (1999) that works when the dictionary is prefix closed and the encoding of dictionary pointers has a constant cost. We present the Dictionary-Symbolwise Flexible Parsing algorithm that is optimal for prefix-closed dictionaries and any symbolwise compressor under some natural hypothesis. In the case of LZ78-like algorithms with variable costs and any, linear as usual, symbolwise compressor we show how to implement our parsing algorithm in linear time. In the case of LZ77-like dictionaries and any symbol…
A Logical Key Hierarchy Based approach to preserve content privacy in Decentralized Online Social Networks
2020
Distributed Online Social Networks (DOSNs) have been proposed to shift the control over user data from a unique entity, the online social network provider, to the users of the DOSN themselves. In this paper we focus on the problem of preserving the privacy of the contents shared to large groups of users. In general, content privacy is enforced by encrypting the content, having only authorized parties being able to decrypt it. When efficiency has to be taken into account, new solutions have to be devised that: i) minimize the re-encryption of the contents published in a group when the composition of the group changes; and, ii) enable a fast distribution of the cryptographic keys to all the m…
The Burrows-Wheeler Transform between Data Compression and Combinatorics on Words
2013
The Burrows-Wheeler Transform (BWT) is a tool of fundamental importance in Data Compression and, recently, has found many applications well beyond its original purpose. The main goal of this paper is to highlight the mathematical and combinatorial properties on which the outstanding versatility of the $BWT$ is based, i.e. its reversibility and the clustering effect on the output. Such properties have aroused curiosity and fervent interest in the scientific world both for theoretical aspects and for practical effects. In particular, in this paper we are interested both to survey the theoretical research issues which, by taking their cue from Data Compression, have been developed in the conte…
Automata and forbidden words
1998
Abstract Let L ( M ) be the (factorial) language avoiding a given anti-factorial language M . We design an automaton accepting L ( M ) and built from the language M . The construction is effective if M is finite. If M is the set of minimal forbidden words of a single word ν, the automaton turns out to be the factor automaton of ν (the minimal automaton accepting the set of factors of ν). We also give an algorithm that builds the trie of M from the factor automaton of a single word. It yields a nontrivial upper bound on the number of minimal forbidden words of a word.
Minimal forbidden words and factor automata
1998
International audience; Let L(M) be the (factorial) language avoiding a given antifactorial language M. We design an automaton accepting L(M) and built from the language M. The construction is eff ective if M is finite. If M is the set of minimal forbidden words of a single word v, the automaton turns out to be the factor automaton of v (the minimal automaton accepting the set of factors of v). We also give an algorithm that builds the trie of M from the factor automaton of a single word. It yields a non-trivial upper bound on the number of minimal forbidden words of a word.
Upper bounds on multiparty communication complexity of shifts
1996
We consider some communication complexity problems which arise when proving lower bounds on the complexity of Boolean functions. In particular, we prove an \(O(\frac{n}{{2\sqrt {\log n} }}\log ^{1/4} n)\)upper bound on 3-party communication complexity of shifts, an O(n e ) upper bound on the multiparty communication complexity of shifts for a polylogarithmic number of parties. These bounds are all significant improvements over ones recently considered “unexpected” by Pudlak [5].
Properties and constraints of cheating-immune secret sharing schemes
2006
AbstractA secret sharing scheme is a cryptographic protocol by means of which a dealer shares a secret among a set of participants in such a way that it can be subsequently reconstructed by certain qualified subsets. The setting we consider is the following: in a first phase, the dealer gives in a secure way a piece of information, called a share, to each participant. Then, participants belonging to a qualified subset send in a secure way their shares to a trusted party, referred to as a combiner, who computes the secret and sends it back to the participants.Cheating-immune secret sharing schemes are secret sharing schemes in the above setting where dishonest participants, during the recons…
Relations frequency hypermatrices in mutual, conditional and joint entropy-based information indices.
2012
Graph-theoretic matrix representations constitute the most popular and significant source of topological molecular descriptors (MDs). Recently, we have introduced a novel matrix representation, named the duplex relations frequency matrix, F, derived from the generalization of an incidence matrix whose row entries are connected subgraphs of a given molecular graph G. Using this matrix, a series of information indices (IFIs) were proposed. In this report, an extension of F is presented, introducing for the first time the concept of a hypermatrix in graph-theoretic chemistry. The hypermatrix representation explores the n-tuple participation frequencies of vertices in a set of connected subgrap…
Volume-convergent sequences of Haken 3-manifolds
2003
Abstract Let M be a closed orientable 3-manifold and let Vol(M) denote its Gromov simplicial volume. This paper is devoted to the study of sequences of non-zero degree maps f i :M→N i to Haken manifolds. We prove that any sequence of Haken manifolds (Ni,fi), satisfying limi→∞deg(fi)×Vol(Ni)=Vol(M) is finite up to homeomorphism. As an application, we deduce from this fact that any closed orientable 3-manifold with zero Gromov simplicial volume and in particular any graph manifold dominates at most finitely many Haken 3-manifolds. To cite this article: P. Derbez, C. R. Acad. Sci. Paris, Ser. I 336 (2003).
Clarkson-McCarthy inequalities with unitary and isometry orbits
2020
Abstract A refinement of a trace inequality of McCarthy establishing the uniform convexity of the Schatten p-classes for p > 2 is proved: if A , B are two n-by-n matrices, then there exists some pair of n-by-n unitary matrices U , V such that U | A + B 2 | p U ⁎ + V | A − B 2 | p V ⁎ ≤ | A | p + | B | p 2 . A similar statement holds for compact Hilbert space operators. Another improvement of McCarthy's inequality is given via the new operator parallelogramm law, | A + B | 2 ⊕ | A − B | 2 = U 0 ( | A | 2 + | B | 2 ) U 0 ⁎ + V 0 ( | A | 2 + | B | 2 ) V 0 ⁎ for some pair of 2n-by-n isometry matrices U 0 , V 0 .