Search results for "Linear"
showing 10 items of 7165 documents
Span programs for functions with constant-sized 1-certificates
2012
Besides the Hidden Subgroup Problem, the second large class of quantum speed-ups is for functions with constant-sized 1-certificates. This includes the OR function, solvable by the Grover algorithm, the element distinctness, the triangle and other problems. The usual way to solve them is by quantum walk on the Johnson graph. We propose a solution for the same problems using span programs. The span program is a computational model equivalent to the quantum query algorithm in its strength, and yet very different in its outfit. We prove the power of our approach by designing a quantum algorithm for the triangle problem with query complexity O(n35/27) that is better than O(n13/10) of the best p…
Irredundant tandem motifs
2014
Eliminating the possible redundancy from a set of candidate motifs occurring in an input string is fundamental in many applications. The existing techniques proposed to extract irredundant motifs are not suitable when the motifs to search for are structured, i.e., they are made of two (or several) subwords that co-occur in a text string s of length n. The main effort of this work is studying and characterizing a compact class of tandem motifs, that is, pairs of substrings {m1, m2} occurring in tandem within a maximum distance of d symbols in s, where d is an integer constant given in input. To this aim, we first introduce the concept of maximality, related to four specific conditions that h…
On the consequences of the standard polynomial
1998
The purpose of this paper is to shed some light on the polynomial identities of low degree for the n × n matrix algebra over a field of characteristic 0.Our main result is that we have found all the consequences of degree n + 2 of the standard polynomial have calculated the S n+2-character of the T-ideal generated by this polynomial.
Hölder inequality for functions that are integrable with respect to bilinear maps
2008
Let $(\Omega, \Sigma, \mu)$ be a finite measure space, $1\le p<\infty$, $X$ be a Banach space $X$ and $B:X\times Y \to Z$ be a bounded bilinear map. We say that an $X$-valued function $f$ is $p$-integrable with respect to $B$ whenever $\sup_{\|y\|=1} \int_\Omega \|B(f(w),y)\|^p\,d\mu<\infty$. We get an analogue to Hölder's inequality in this setting.
Divisible Designs Admitting, as an Automorphism Group, an Orthogonal Group or a Unitary Group
2001
We construct some divisible designs starting from a projective space. These divisible designs admit an orthogonal group or a unitary group as an automorphism group.
A Star-Variety With Almost Polynomial Growth
2000
Abstract Let F be a field of characteristic zero. In this paper we construct a finite dimensional F -algebra with involution M and we study its ∗ -polynomial identities; on one hand we determine a generator of the corresponding T -ideal of the free algebra with involution and on the other we give a complete description of the multilinear ∗ -identities through the representation theory of the hyperoctahedral group. As an outcome of this study we show that the ∗ -variety generated by M , var( M , ∗ ) has almost polynomial growth, i.e., the sequence of ∗ -codimensions of M cannot be bounded by any polynomial function but any proper ∗ -subvariety of var( M , ∗ ) has polynomial growth. If G 2 is…
On Banaschewski functions in lattices
1991
hold for all x, y ~ X. We call such a function z a Banaschewski function or a B-function on X. A lattice L is a B-lattice or antitonely complemented, if there is a B-function defined on the whole lattice L. For instance, Boolean lattices as well as orthocomplemented lattices are B-lattices. On the other hand, a B-lattice is not necessarily Boolean or orthocomplemented, although a distributive B-lattice is a Boolean lattice. It is shown later that a matroid (geometric) lattice is also a B-lattice. Naturally, our results include the lemma of Banaschewski [ 1, Lemma 4], by which the lattice of the subspaces of a vector space is a B-lattice. It should be emphasized that a B-function is supposed…
Operators on PIP-Spaces and Indexed PIP-Spaces
2009
As already mentioned, the basic idea of pip-spaces is that vectors should not be considered individually, but only in terms of the subspaces V r (r Є F), the building blocks of the structure. Correspondingly, an operator on a pipspace should be defined in terms of assaying subspaces only, with the proviso that only continuous or bounded operators are allowed. Thus an operator is a coherent collection of continuous operators. We recall that in a nondegenerate pip-space, every assaying subspace V r carries its Mackey topology \(\tau (V_r , V \bar{r})\) and thus its dual is \(V \bar{r}\). This applies in particular to \(V^{\#}\) and V itself. For simplicity, a continuous linear map between two…
A non-linear Bishop–Phelps–BollobÁs type theorem
2018
Packing a Trunk
2003
We report on a project with a German car manufacturer. The task is to compute (approximate) solutions to a specific large-scale packing problem. Given a polyhedral model of a car trunk, the aim is to pack as many identical boxes of size 4 × 2 × 1 units as possible into the interior of the trunk. This measure is important for car manufacturers, because it is a standard in the European Union.