Search results for "Conjecture"
showing 10 items of 217 documents
Sensitivity Versus Certificate Complexity of Boolean Functions
2016
Sensitivity, block sensitivity and certificate complexity are basic complexity measures of Boolean functions. The famous sensitivity conjecture claims that sensitivity is polynomially related to block sensitivity. However, it has been notoriously hard to obtain even exponential bounds. Since block sensitivity is known to be polynomially related to certificate complexity, an equivalent of proving this conjecture would be showing that the certificate complexity is polynomially related to sensitivity. Previously, it has been shown that $$bsf \le Cf \le 2^{sf-1} sf - sf-1$$. In this work, we give a better upper bound of $$bsf \le Cf \le \max \left 2^{sf-1}\left sf-\frac{1}{3}\right , sf\right $…
L 2-topological invariants of 3-manifolds
1995
We give results on theL2-Betti numbers and Novikov-Shubin invariants of compact manifolds, especially 3-manifolds. We first study the Betti numbers and Novikov-Shubin invariants of a chain complex of Hilbert modules over a finite von Neumann algebra. We establish inequalities among the Novikov-Shubin invariants of the terms in a short exact sequence of chain complexes. Our algebraic results, along with some analytic results on geometric 3-manifolds, are used to compute theL2-Betti numbers of compact 3-manifolds which satisfy a weak form of the geometrization conjecture, and to compute or estimate their Novikov-Shubin invariants.
Character sums and double cosets
2008
Abstract If G is a p-solvable finite group, P is a self-normalizing Sylow p-subgroup of G with derived subgroup P ′ , and Ψ is the sum of all the irreducible characters of G of degree not divisible by p, then we prove that the integer Ψ ( P ′ z P ′ ) is divisible by | P | for all z ∈ G . This answers a question of J. Alperin.
McKay natural correspondences on characters
2014
Let [math] be a finite group, let [math] be an odd prime, and let [math] . If [math] , then there is a canonical correspondence between the irreducible complex characters of [math] of degree not divisible by [math] belonging to the principal block of [math] and the linear characters of [math] . As a consequence, we give a characterization of finite groups that possess a self-normalizing Sylow [math] -subgroup or a [math] -decomposable Sylow normalizer.
A reduction theorem for a conjecture on products of two π -decomposable groups
2013
[EN] For a set of primes pi, a group X is said to be pi-decomposable if X = X-pi x X-pi' is the direct product of a pi-subgroup X-pi and a pi'-subgroup X-pi', where pi' is the complementary of pi in the set of all prime numbers. The main result of this paper is a reduction theorem for the following conjecture: "Let pi be a set of odd primes. If the finite group G = AB is a product of two pi-decomposable subgroups A = A(pi) x A(pi') and B = B-pi x B-pi', then A(pi)B(pi) = B(pi)A(pi) and this is a Hall pi-subgroup of G." We establish that a minimal counterexample to this conjecture is an almost simple group. The conjecture is then achieved in a forthcoming paper. (C) 2013 Elsevier Inc. All ri…
On a Conjecture by Christian Choffrut
2017
It is one of the most famous open problems to determine the minimum amount of states required by a deterministic finite automaton to distinguish a pair of strings, which was stated by Christian Choffrut more than thirty years ago. We investigate the same question for different automata models and we obtain new upper and lower bounds for some of them including alternating, ultrametric, quantum, and affine finite automata.
Team learning as a game
1997
A machine FIN-learning machine M receives successive values of the function f it is learning; at some point M outputs conjecture which should be a correct index of f. When n machines simultaneously learn the same function f and at least k of these machines outut correct indices of f, we have team learning [k,n]FIN. Papers [DKV92, DK96] show that sometimes a team or a robabilistic learner can simulate another one, if its probability p (or team success ratio k/n) is close enough. On the other hand, there are critical ratios which mae simulation o FIN(p2) by FIN(p1) imossible whenever p2 _< r < p1 or some critical ratio r. Accordingly to [DKV92] the critical ratio closest to 1/2 rom the let is…
Formal Periods and the Period Conjecture
2017
Following Kontsevich (see Kontsevich in Operads and motives in deformation quantization. Lett. Math. Phys. 48(1):35–72, 1999), we now introduce another algebra \(\tilde{\mathbb {P}}(k)\) of formal periods from the same data we have used in order to define the actual period algebra of a field in Chap. 11. The main aim of this chapter is to give conceptual interpretation of this algebra of formal periods. We then use it to formulate and discuss the period conjecture.
Extending Brauer's Height Zero Conjecture to Blocks with Nonabelian Defect Groups
2013
We propose a generalization of Brauer?s Height Zero Conjecture that considers positive heights. We give strong evidence supporting one half of the generalization and obtain some partial results regarding the other half.
A computational criterion for the Kac conjecture
2006
Abstract We give a criterion for the Kac conjecture asserting that the free term of the polynomial counting the absolutely indecomposable representations of a quiver over a finite field of given dimension coincides with the corresponding root multiplicity of the associated Kac–Moody algebra. Our criterion suits very well for computer tests.