Search results for "permuta"
showing 10 items of 171 documents
The measurement of rank mobility
2009
Abstract In this paper we investigate the problem of measuring social mobility when the social status of individuals is given by their rank. In order to sensibly represent the rank mobility of subgroups within a given society, we address the problem in terms of partial permutation matrices which include standard (“global”) matrices as a special case. We first provide a characterization of a partial ordering on partial matrices which, in the standard case of global matrices, coincides with the well-known “concordance” ordering. We then provide a characterization of an index of rank mobility based on partial matrices and show that, in the standard case of comparing global matrices, it is equi…
Improving table compression with combinatorial optimization
2002
We study the problem of compressing massive tables within the partition-training paradigm introduced by Buchsbaum et al. [SODA'00], in which a table is partitioned by an off-line training procedure into disjoint intervals of columns, each of which is compressed separately by a standard, on-line compressor like gzip. We provide a new theory that unifies previous experimental observations on partitioning and heuristic observations on column permutation, all of which are used to improve compression rates. Based on the theory, we devise the first on-line training algorithms for table compression, which can be applied to individual files, not just continuously operating sources; and also a new, …
Right-jumps and pattern avoiding permutations
2015
We study the iteration of the process "a particle jumps to the right" in permutations. We prove that the set of permutations obtained in this model after a given number of iterations from the identity is a class of pattern avoiding permutations. We characterize the elements of the basis of this class and we enumerate these "forbidden minimal patterns" by giving their bivariate exponential generating function: we achieve this via a catalytic variable, the number of left-to-right maxima. We show that this generating function is a D-finite function satisfying a nice differential equation of order~2. We give some congruence properties for the coefficients of this generating function, and we sho…
On Block Sensitivity and Fractional Block Sensitivity
2018
We investigate the relation between the block sensitivity bs(f) and fractional block sensitivity fbs(f) complexity measures of Boolean functions. While it is known that fbs(f) = O(bs(f)2), the best known separation achieves $${\rm{fbs}}\left( f \right) = \left( {{{\left( {3\sqrt 2 } \right)}^{ - 1}} + o\left( 1 \right)} \right){\rm{bs}}{\left( f \right)^{3/2}}$$ . We improve the constant factor and show a family of functions that give fbs(f) = (6−1/2 − o(1)) bs(f)3/2.
All Classical Adversary Methods Are Equivalent for Total Functions
2017
We show that all known classical adversary lower bounds on randomized query complexity are equivalent for total functions and are equal to the fractional block sensitivity fbs( f ). That includes the Kolmogorov complexity bound of Laplante and Magniez and the earlier relational adversary bound of Aaronson. This equivalence also implies that for total functions, the relational adversary is equivalent to a simpler lower bound, which we call rank-1 relational adversary. For partial functions, we show unbounded separations between fbs( f ) and other adversary bounds, as well as between the adversary bounds themselves. We also show that, for partial functions, fractional block sensitivity canno…
Quantum lower bound for inverting a permutation with advice
2014
Given a random permutation $f: [N] \to [N]$ as a black box and $y \in [N]$, we want to output $x = f^{-1}(y)$. Supplementary to our input, we are given classical advice in the form of a pre-computed data structure; this advice can depend on the permutation but \emph{not} on the input $y$. Classically, there is a data structure of size $\tilde{O}(S)$ and an algorithm that with the help of the data structure, given $f(x)$, can invert $f$ in time $\tilde{O}(T)$, for every choice of parameters $S$, $T$, such that $S\cdot T \ge N$. We prove a quantum lower bound of $T^2\cdot S \ge \tilde{\Omega}(\epsilon N)$ for quantum algorithms that invert a random permutation $f$ on an $\epsilon$ fraction of…
Mahonian STAT on words
2016
In 2000, Babson and Steingrimsson introduced the notion of what is now known as a permutation vincular pattern, and based on it they re-defined known Mahonian statistics and introduced new ones, proving or conjecturing their Mahonity. These conjectures were proved by Foata and Zeilberger in 2001, and by Foata and Randrianarivony in 2006.In 2010, Burstein refined some of these results by giving a bijection between permutations with a fixed value for the major index and those with the same value for STAT , where STAT is one of the statistics defined and proved to be Mahonian in the 2000 Babson and Steingrimsson's paper. Several other statistics are preserved as well by Burstein's bijection.At…
Sensitivity versus block sensitivity of Boolean functions
2010
Determining the maximal separation between sensitivity and block sensitivity of Boolean functions is of interest for computational complexity theory. We construct a sequence of Boolean functions with bs(f) = 1/2 s(f)^2 + 1/2 s(f). The best known separation previously was bs(f) = 1/2 s(f)^2 due to Rubinstein. We also report results of computer search for functions with at most 12 variables.
More restrictive Gray codes for some classes of pattern avoiding permutations
2009
In a recent article [W.M.B. Dukes, M.F. Flanagan, T. Mansour, V. Vajnovszki, Combinatorial Gray codes for classes of pattern avoiding permutations, Theoret. Comput. Sci. 396 (2008) 35-49], Dukes, Flanagan, Mansour and Vajnovszki present Gray codes for several families of pattern avoiding permutations. In their Gray codes two consecutive objects differ in at most four or five positions, which is not optimal. In this paper, we present a unified construction in order to refine their results (or to find other Gray codes). In particular, we obtain more restrictive Gray codes for the two Wilf classes of Catalan permutations of length n; two consecutive objects differ in at most two or three posit…
Characterizing normal Sylow p-subgroups by character degrees
2012
Abstract Suppose that G is a finite group, let p be a prime and let P ∈ Syl p ( G ) . We prove that P is normal in G if and only if all the irreducible constituents of the permutation character ( 1 P ) G have degree not divisible by p.