Search

The purpose of this article is to initiate a systematic study of dimension-free relations between basic communication and query complexity measures and various matrix norms. In other words, our goal is to obtain inequalities that bound a parameter solely as a function of another parameter. This is in contrast to perhaps the more common framework in communication complexity where poly-logarithmic dependencies on the number of input bits are tolerated. Dimension-free bounds are also closely related to structural results, where one seeks to describe the structure of Boolean matrices and functions that have low complexity. We prove such theorems for several communication and query complexity measures as well as various matrix and operator norms. In several other cases we show that such bounds do not exist. We propose several conjectures, and establish that, in addition to applications in complexity theory, these problems are central to characterization of the idempotents of the algebra of Schur multipliers, and could lead to new extensions of Cohen's celebrated idempotent theorem regarding the Fourier algebra. [ABSTRACT FROM AUTHOR]

We study hereditary completeness of systems of exponentials on an interval such that the corresponding generating function G is small outside of a lacunary sequence of intervals Ik. We show that, under some technical conditions, an exponential system is hereditarily complete if and only if the logarithmic length of the union of these intervals is infinite, i.e., ∑ k ∫ I k d x 1 + | x | = ∞ . [ABSTRACT FROM AUTHOR]

We establish multiplicity results for geometrically distinct contractible closed Reeb orbits of non-degenerate contact forms on a broad class of prequantization bundles. The results hold under certain index requirements on the contact form and are sharp for unit cotangent bundles of CROSS’s. In particular, we generalize and put in the symplectic-topological context a theorem of Duan, Liu, Long and Wang for the standard contact sphere. We also prove similar results for non-hyperbolic contractible closed orbits and briefly touch upon the multiplicity problem for degenerate forms. On the combinatorial side of the question, we revisit and reprove the enhanced common jump theorem of Duan, Long and Wang, and interpret it as an index recurrence result. [ABSTRACT FROM AUTHOR]

For a class of non-uniformly hyperbolic interval maps, we study rates of escape with respect to conformal measures associated with a family of geometric potentials. We establish the existence of physically relevant conditionally invariant measures and equilibrium states and prove a relation between the rate of escape and pressure with respect to these potentials. As a consequence, we obtain a Bowen formula: we express the Hausdorff dimension of the set of points which never exit through the hole in terms of the relevant pressure function. Finally, we obtain an expression for the derivative of the escape rate in the zero-hole limit. [ABSTRACT FROM AUTHOR]

We introduce the new notion of general bilinear forms (generalizing sesquilinear forms) and prove that for every ring R (not necessarily commutative, possibly without involution) and every right R-module M which is a generator (i.e., R is a summand of M for some n ∈ ℕ), there is a one-to-one correspondence between the anti-automorphisms of End( M) and the general regular bilinear forms on M, considered up to similarity. This generalizes a well-known similar correspondence in the case R is a field. We also demonstrate that there is no such correspondence for arbitrary R-modules. We use the generalized correspondence to show that there is a canonical set isomorphism Inn( R) \Aut( R) ≅ Inn(M( R))\Aut(M( R)), provided R is the only right R-module N satisfying N ≅ R, and also to prove a variant of a theorem of Osborn. Namely, we classify all semisimple rings with involution admitting no non-trivial idempotents that are invariant under the involution. [ABSTRACT FROM AUTHOR]

For a family X of k-subsets of the set {1, ..., n}, let | X| be the cardinality of X and let Γ( X, μ) be the expected maximum weight of a subset from X when the weights of 1, ..., n are chosen independently at random from a symmetric probability distribution μ on ℝ. We consider the inverse isoperimetric problem of finding μ for which Γ( X, μ) gives the best estimate of ln | X|. We prove that the optimal choice of μ is the logistic distribution, in which case Γ( X, μ) provides an asymptotically tight estimate of ln | X| as k −1 ln | X} grows. Since in many important cases Γ( X, μ) can be easily computed, we obtain computationally efficient approximation algorithms for a variety of counting problems. Given μ, we describe families X of a given cardinality with the minimum value of Γ( X, μ), thus extending and sharpening various isoperimetric inequalities in the Boolean cube. [ABSTRACT FROM AUTHOR]

We extend the invertibility principle of J. Bourgain and L. Tzafriri to operators acting on arbitrary decompositions id = ∑ x j ⊕ x j , rather than on the coordinate one. The John's decomposition brings this result to the local theory of Banach spaces. As a consequence, we get a new lemma of Dvoretzky-Rogers type, where the contact points of the unit ball with its maximal volume ellipsoid play a crucial role. We then apply these results to embeddings of l into finite dimensional spaces. [ABSTRACT FROM AUTHOR]

We determine the isomorphic classes of 6 or 8 dimensional semisimple Hopf algebras A over an algebraically closed field such that (dim A)1≠0. [ABSTRACT FROM AUTHOR]

According to Grothendieck Duality Theory [RD], on each variety V over a field k, there is a canonical complex of $$\mathcal{O}_V $$ -modules, the residue complex $$\mathcal{K}_V^{RD \cdot } \cong \pi ^! k$$ . These complexes satisfy (and are characterized by) functorial properties in the category V of k-varieties. In [Ye] a complex $$\mathcal{K}_V^ \cdot $$ is constructed explicitly (when the field k is perfect). The main result of this paper is that the two families of complexes, $$\{ \mathcal{K}_V^{RD \cdot } \} v \in \nu $$ and $$\{ \mathcal{K}_V^{ \cdot } \} v \in \nu $$ , which carry certain additional data (such as trace maps...), are uniquely isomorphic. As a corollary we recover Lipman's canonical dualizing sheaf of [Li], and we obtain formulas for residues of local cohomology classes of differential forms. [ABSTRACT FROM AUTHOR]

A notion of 'nesting' for very weakly Bernoulli distributions is developed and used to prove that any two-point extension of a Bernoulli shift, if it has ergodic square, must itself be Bernoulli. [ABSTRACT FROM AUTHOR]

It is proved that if the Banach-Mazur distance between an n-dimensional Minkowski space B and l satisfies d ( B l ) ≧ c √ n (for some constant c>0 and for big n) then B contains an A( c)-isomorphic copy of l (for k ∼ log log log n). In the special case d ( B l ) = √ n, B contains an isometric copy of l for k ∼ log n. [ABSTRACT FROM AUTHOR]

We show how to get a model of set theory in which ℵ is a strong limit cardinal which violates the generalized continuum hypothesis. Generalizations to other cardinals are also given. [ABSTRACT FROM AUTHOR]