Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTwo-closure of supersolvable permutation group in polynomial time
249
0
0.0
(
0
)
Added by
Ilia Ponomarenko
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The $2$-closure $overline{G}$ of a permutation group $G$ on $Omega$ is defined to be the largest permutation group on $Omega$, having the same orbits on $OmegatimesOmega$ as $G$. It is proved that if $G$ is supersolvable, then $overline{G}$ can be found in polynomial time in $|Omega|$. As a byproduct of our technique, it is shown that the composition factors of $overline{G}$ are cyclic or alternating of prime degree.
rate research
Read More
Let $m$ be a positive integer and let $Omega$ be a finite set. The $m$-closure of $Gleqoperatorname{Sym}(Omega)$ is the largest permutation group on $Omega$ having the same orbits as $G$ in its induced action on the Cartesian product $Omega^m$. The $1$-closure and $2$-closure of a solvable permutation group need not be solvable. We prove that the $m$-closure of a solvable permutation group is always solvable for $mgeq3$.
We show that, there exists a constant $a$ such that, for every subgroup $H$ of a finite group $G$, the number of maximal subgroups of $G$ containing $H$ is bounded above by $a|G:H|^{3/2}$. In particular, a transitive permutation group of degree $n$ has at most $an^{3/2}$ maximal systems of imprimitivity. When $G$ is soluble, generalizing a classic result of Tim Wall, we prove a much stroger bound, that is, the number of maximal subgroups of $G$ containing $H$ is at most $|G:H|-1$.
We describe how orbital graphs can be used to improve the practical performance of many algorithms for permutation groups, including intersection and stabilizer problems. First we explain how orbital graphs can be integrated in partition backtracking, the current state of the art algorithm for many permutation group problems. We then show how our algorithms perform in practice, demonstrating improvements of several orders of magnitude for some problems.
A cycle base of a permutation group is defined to be a maximal set of its pairwise non-conjugate regular cyclic subgroups. It is proved that a cycle base of a permutation group of degree $n$ can be constructed in polynomial time in~$n$.
We give the first dimension-efficient algorithms for learning Rectified Linear Units (ReLUs), which are functions of the form $mathbf{x} mapsto max(0, mathbf{w} cdot mathbf{x})$ with $mathbf{w} in mathbb{S}^{n-1}$. Our algorithm works in the challenging Reliable Agnostic learning model of Kalai, Kanade, and Mansour (2009) where the learner is given access to a distribution $cal{D}$ on labeled examples but the labeling may be arbitrary. We construct a hypothesis that simultaneously minimizes the false-positive rate and the loss on inputs given positive labels by $cal{D}$, for any convex, bounded, and Lipschitz loss function. The algorithm runs in polynomial-time (in $n$) with respect to any distribution on $mathbb{S}^{n-1}$ (the unit sphere in $n$ dimensions) and for any error parameter $epsilon = Omega(1/log n)$ (this yields a PTAS for a question raised by F. Bach on the complexity of maximizing ReLUs). These results are in contrast to known efficient algorithms for reliably learning linear threshold functions, where $epsilon$ must be $Omega(1)$ and strong assumptions are required on the marginal distribution. We can compose our results to obtain the first set of efficient algorithms for learning constant-depth networks of ReLUs. Our techniques combine kernel methods and polynomial approximations with a dual-loss approach to convex programming. As a byproduct we obtain a number of applications including the first set of efficient algorithms for convex piecewise-linear fitting and the first efficient algorithms for noisy polynomial reconstruction of low-weight polynomials on the unit sphere.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
