The Experts below are selected from a list of 231 Experts worldwide ranked by ideXlab platform
Ameya Velingker - One of the best experts on this subject based on the ideXlab platform.
-
an entropy sumset inequality and polynomially fast convergence to shannon capacity over all alphabets
Conference on Computational Complexity, 2015Co-Authors: Venkatesan Guruswami, Ameya VelingkerAbstract:We prove a lower estimate on the increase in entropy when two copies of a conditional random variable X|Y, with X supported on Zq = {0,1,..., q − 1} for prime q, are summed modulo q. Specifically, given two i.i.d. copies (X1, Y1) and (X2, Y2) of a pair of random variables (X, Y), with X taking values in Zq, we show H(X1 + X2 | Y1, Y2) - H(X|Y ) ≥ α(q) · H(X|Y)(1 - H(X|Y)) for some α(q) > 0, where H (·) is the normalized (by factor log2q) entropy. In particular, if X|Y is not close to being fully random or fully deterministic and H(X|Y) ∈ (γ, 1-γ), then the entropy of the sum increases by Ωq (γ). Our motivation is an effective analysis of the finite-length behavior of polar codes, for which the linear dependence on γ is quantitatively important. The assumption of q being prime is necessary: for X supported uniformly on a Proper Subgroup of Zq we have H(X + X) = H(X). For X supported on infinite groups without a finite Subgroup (the torsion-free case) and no conditioning, a sumset inequality for the absolute increase in (unnormalized) entropy was shown by Tao in [20]. We use our sumset inequality to analyze Arikan's construction of polar codes and prove that for any q-ary source X, where q is any fixed prime, and any e > 0, polar codes allow efficient data compression of N i.i.d. copies of X into (H(X) + e)N q-ary symbols, as soon as N is polynomially large in 1/e. We can get capacity-achieving source codes with similar guarantees for composite alphabets, by factoring q into primes and combining different polar codes for each prime in factorization. A consequence of our result for noisy channel coding is that for all discrete memoryless channels, there are explicit codes enabling reliable communication within e > 0 of the symmetric Shannon capacity for a block length and decoding complexity bounded by a polynomial in 1/e. The result was previously shown for the special case of binary-input channels [7, 9], and this work extends the result to channels over any alphabet.
-
Conference on Computational Complexity - An entropy sumset inequality and polynomially fast convergence to shannon capacity over all alphabets
2015Co-Authors: Venkatesan Guruswami, Ameya VelingkerAbstract:We prove a lower estimate on the increase in entropy when two copies of a conditional random variable X|Y, with X supported on Zq = {0,1,..., q − 1} for prime q, are summed modulo q. Specifically, given two i.i.d. copies (X1, Y1) and (X2, Y2) of a pair of random variables (X, Y), with X taking values in Zq, we show H(X1 + X2 | Y1, Y2) - H(X|Y ) ≥ α(q) · H(X|Y)(1 - H(X|Y)) for some α(q) > 0, where H (·) is the normalized (by factor log2q) entropy. In particular, if X|Y is not close to being fully random or fully deterministic and H(X|Y) ∈ (γ, 1-γ), then the entropy of the sum increases by Ωq (γ). Our motivation is an effective analysis of the finite-length behavior of polar codes, for which the linear dependence on γ is quantitatively important. The assumption of q being prime is necessary: for X supported uniformly on a Proper Subgroup of Zq we have H(X + X) = H(X). For X supported on infinite groups without a finite Subgroup (the torsion-free case) and no conditioning, a sumset inequality for the absolute increase in (unnormalized) entropy was shown by Tao in [20]. We use our sumset inequality to analyze Arikan's construction of polar codes and prove that for any q-ary source X, where q is any fixed prime, and any e > 0, polar codes allow efficient data compression of N i.i.d. copies of X into (H(X) + e)N q-ary symbols, as soon as N is polynomially large in 1/e. We can get capacity-achieving source codes with similar guarantees for composite alphabets, by factoring q into primes and combining different polar codes for each prime in factorization. A consequence of our result for noisy channel coding is that for all discrete memoryless channels, there are explicit codes enabling reliable communication within e > 0 of the symmetric Shannon capacity for a block length and decoding complexity bounded by a polynomial in 1/e. The result was previously shown for the special case of binary-input channels [7, 9], and this work extends the result to channels over any alphabet.
Venkatesan Guruswami - One of the best experts on this subject based on the ideXlab platform.
-
an entropy sumset inequality and polynomially fast convergence to shannon capacity over all alphabets
Conference on Computational Complexity, 2015Co-Authors: Venkatesan Guruswami, Ameya VelingkerAbstract:We prove a lower estimate on the increase in entropy when two copies of a conditional random variable X|Y, with X supported on Zq = {0,1,..., q − 1} for prime q, are summed modulo q. Specifically, given two i.i.d. copies (X1, Y1) and (X2, Y2) of a pair of random variables (X, Y), with X taking values in Zq, we show H(X1 + X2 | Y1, Y2) - H(X|Y ) ≥ α(q) · H(X|Y)(1 - H(X|Y)) for some α(q) > 0, where H (·) is the normalized (by factor log2q) entropy. In particular, if X|Y is not close to being fully random or fully deterministic and H(X|Y) ∈ (γ, 1-γ), then the entropy of the sum increases by Ωq (γ). Our motivation is an effective analysis of the finite-length behavior of polar codes, for which the linear dependence on γ is quantitatively important. The assumption of q being prime is necessary: for X supported uniformly on a Proper Subgroup of Zq we have H(X + X) = H(X). For X supported on infinite groups without a finite Subgroup (the torsion-free case) and no conditioning, a sumset inequality for the absolute increase in (unnormalized) entropy was shown by Tao in [20]. We use our sumset inequality to analyze Arikan's construction of polar codes and prove that for any q-ary source X, where q is any fixed prime, and any e > 0, polar codes allow efficient data compression of N i.i.d. copies of X into (H(X) + e)N q-ary symbols, as soon as N is polynomially large in 1/e. We can get capacity-achieving source codes with similar guarantees for composite alphabets, by factoring q into primes and combining different polar codes for each prime in factorization. A consequence of our result for noisy channel coding is that for all discrete memoryless channels, there are explicit codes enabling reliable communication within e > 0 of the symmetric Shannon capacity for a block length and decoding complexity bounded by a polynomial in 1/e. The result was previously shown for the special case of binary-input channels [7, 9], and this work extends the result to channels over any alphabet.
-
Conference on Computational Complexity - An entropy sumset inequality and polynomially fast convergence to shannon capacity over all alphabets
2015Co-Authors: Venkatesan Guruswami, Ameya VelingkerAbstract:We prove a lower estimate on the increase in entropy when two copies of a conditional random variable X|Y, with X supported on Zq = {0,1,..., q − 1} for prime q, are summed modulo q. Specifically, given two i.i.d. copies (X1, Y1) and (X2, Y2) of a pair of random variables (X, Y), with X taking values in Zq, we show H(X1 + X2 | Y1, Y2) - H(X|Y ) ≥ α(q) · H(X|Y)(1 - H(X|Y)) for some α(q) > 0, where H (·) is the normalized (by factor log2q) entropy. In particular, if X|Y is not close to being fully random or fully deterministic and H(X|Y) ∈ (γ, 1-γ), then the entropy of the sum increases by Ωq (γ). Our motivation is an effective analysis of the finite-length behavior of polar codes, for which the linear dependence on γ is quantitatively important. The assumption of q being prime is necessary: for X supported uniformly on a Proper Subgroup of Zq we have H(X + X) = H(X). For X supported on infinite groups without a finite Subgroup (the torsion-free case) and no conditioning, a sumset inequality for the absolute increase in (unnormalized) entropy was shown by Tao in [20]. We use our sumset inequality to analyze Arikan's construction of polar codes and prove that for any q-ary source X, where q is any fixed prime, and any e > 0, polar codes allow efficient data compression of N i.i.d. copies of X into (H(X) + e)N q-ary symbols, as soon as N is polynomially large in 1/e. We can get capacity-achieving source codes with similar guarantees for composite alphabets, by factoring q into primes and combining different polar codes for each prime in factorization. A consequence of our result for noisy channel coding is that for all discrete memoryless channels, there are explicit codes enabling reliable communication within e > 0 of the symmetric Shannon capacity for a block length and decoding complexity bounded by a polynomial in 1/e. The result was previously shown for the special case of binary-input channels [7, 9], and this work extends the result to channels over any alphabet.
O. Yu. Dashkova - One of the best experts on this subject based on the ideXlab platform.
-
Locally soluble AFA-groups
Ukrainian Mathematical Journal, 2013Co-Authors: O. Yu. DashkovaAbstract:Let A be an R G -module, where R is a ring, G is a locally soluble group, C _ G ( A ) = 1; and every Proper Subgroup H of G for which A = C _ A ( H ) is not an Artinian R -module is finitely generated. It is shown that a locally soluble group G satisfying these conditions is hyper-Abelian if R is a Dedekind ring. We describe the structure of the group G in the case where G is a finitely generated soluble group, A = C _ A ( G ) is not an Artinian R -module, and R is a Dedekind ring.
-
Modules over group rings of solvable groups with rank restrictions on Subgroups
Siberian Advances in Mathematics, 2013Co-Authors: O. Yu. DashkovaAbstract:Let A be an R G -module over a commutative ring R , where G is a group of infinite section p -rank (0-rank), C _ G ( A ) = 1, A is not a Noetherian R -module, and the quotient A/C _ A ( H ) is a Noetherian R -module for every Proper Subgroup H of infinite section p -rank (0-rank). We describe the structure of solvable groups G of this type.
-
ON MODULES OVER INTEGER-VALUED GROUP RINGS OF LOCALLY SOLUBLE GROUPS WITH RANK RESTRICTIONS IMPOSED ON SubgroupS
Ukrainian Mathematical Journal, 2012Co-Authors: O. Yu. DashkovaAbstract:We study a $ \mathbb{Z}G $ -module A such that $ \mathbb{Z} $ is the ring of integer numbers, the group G has an infinite sectional p-rank (or an infinite 0-rank), C G (A) = 1, A is not a minimax $ \mathbb{Z} $ -module, and, for any Proper Subgroup H of infinite sectional p-rank (or infinite 0-rank, respectively), the quotient module A/C A (H) is a minimax $ \mathbb{Z} $ -module. It is shown that if the group G is locally soluble, then it is soluble. Some Properties of soluble groups of this kind are discussed.
Gerold Alsmeyer - One of the best experts on this subject based on the ideXlab platform.
-
The Minimal Subgroup of a Random Walk
Journal of Theoretical Probability, 2002Co-Authors: Gerold AlsmeyerAbstract:It is proved that for each random walk ( S _ n )_ n ≥0 on $${\mathbb{R}}$$ ^ d there exists a smallest measurable Subgroup $${\mathbb{G}}$$ of $${\mathbb{R}}$$ ^ d , called minimal Subgroup of ( S _ n )_ n ≥0, such that P ( S _ n ∈ $${\mathbb{G}}$$ )=1 for all n ≥1. $${\mathbb{G}}$$ can be defined as the set of all x ∈ $${\mathbb{R}}$$ ^ d for which the difference of the time averages n ^−1 ∑^ n _ k =1 P ( S _ k ∈ċ) and n ^−1 ∑^ n _ k =1 P ( S _ k + x ∈ċ) converges to 0 in total variation norm as n →∞. The related Subgroup $${\mathbb{G}}$$ * consisting of all x ∈ $${\mathbb{R}}$$ ^ d for which lim_ n →∞ ‖ P ( S _ n ∈ċ)− P ( S _ n + x ∈ċ)‖=0 is also considered and shown to be the minimal Subgroup of the symmetrization of ( S _ n )_ n ≥0. In the final section we consider quasi-invariance and admissible shifts of probability measures on $${\mathbb{R}}$$ ^ d . The main result shows that, up to regular linear transformations, the only Subgroups of $${\mathbb{R}}$$ ^ d admitting a quasi-invariant measure are those of the form $${\mathbb{G}}$$ ′_1×...× $${\mathbb{G}}$$ ′_ k × $${\mathbb{R}}$$ ^ l − k ×{0}^ d − l , 0≤ k ≤ l ≤ d , with $${\mathbb{G}}$$ ′_1,..., $${\mathbb{G}}$$ ′_ k being countable Subgroups of $${\mathbb{R}}$$ . The proof is based on a result recently proved by Kharazishvili^(3) which states no uncountable Proper Subgroup of $${\mathbb{R}}$$ admits a quasi-invariant measure.
A. O. Asar - One of the best experts on this subject based on the ideXlab platform.
-
LOCALLY NILPOTENT P-GROUPS WHOSE Proper SubgroupS ARE HYPERCENTRAL OR NILPOTENT-BY-CHERNIKOV
Journal of the London Mathematical Society, 2000Co-Authors: A. O. AsarAbstract:Let G be a group and P be a Property of groups. If every Proper Subgroup of G satisfies P but G itself does not satisfy it, then G is called a minimal non-P group . In this work we study locally nilpotent minimal non- P groups, where P stands for ‘hypercentral’ or ‘nilpotent-by-Chernikov’. In the first case we show that if G is a minimal non-hypercentral Fitting group in which every Proper Subgroup is solvable, then G is solvable (see Theorem 1.1 below). This result generalizes [ 3 , Theorem 1]. In the second case we show that if every Proper Subgroup of G is nilpotent-by-Chernikov, then G is nilpotent-by-Chernikov (see Theorem 1.3 below). This settles a question which was considered in [ 1–3 , 10 ]. Recently in [ 9 ], the non-periodic case of the above question has been settled but the same work contains an assertion without proof about the periodic case. The main results of this paper are given below (see also [ 13 ]).
