Search results for "complex"

Time-Efficient Quantum Walks for 3-Distinctness

2013

We present two quantum walk algorithms for 3-Distinctness. Both algorithms have time complexity $\tilde{O}(n^{5/7})$, improving the previous $\tilde{O}(n^{3/4})$ and matching the best known upper bound for query complexity (obtained via learning graphs) up to log factors. The first algorithm is based on a connection between quantum walks and electric networks. The second algorithm uses an extension of the quantum walk search framework that facilitates quantum walks with nested updates.

Balls into non-uniform bins

2014

Balls-into-bins games for uniform bins are widely used to model randomized load balancing strategies. Recently, balls-into-bins games have been analysed under the assumption that the selection probabilities for bins are not uniformly distributed. These new models are motivated by properties of many peer-to-peer (P2P) networks, which are not able to perfectly balance the load over the bins. While previous evaluations try to find strategies for uniform bins under non-uniform bin selection probabilities, this paper investigates heterogeneous bins, where the "capacities" of the bins might differ significantly. We show that heterogeneous environments can even help to distribute the load more eve…

Minimal varieties of algebras of exponential growth

2003

Abstract The exponent of a variety of algebras over a field of characteristic zero has been recently proved to be an integer. Through this scale we can now classify all minimal varieties of given exponent and of finite basic rank. As a consequence, we describe the corresponding T-ideals of the free algebra and we compute the asymptotics of the related codimension sequences, verifying in this setting some known conjectures. We also show that the number of these minimal varieties is finite for any given exponent. We finally point out some relations between the exponent of a variety and the Gelfand–Kirillov dimension of the corresponding relatively free algebras of finite rank.

Sobolev classes of Banach space-valued functions and quasiconformal mappings

2001

We give a definition for the class of Sobolev functions from a metric measure space into a Banach space. We give various characterizations of Sobolev classes and study the absolute continuity in measure of Sobolev mappings in the “borderline case”. We show under rather weak assumptions on the source space that quasisymmetric homeomorphisms belong to a Sobolev space of borderline degree; in particular, they are absolutely continuous. This leads to an analytic characterization of quasiconformal mappings between Ahlfors regular Loewner spaces akin to the classical Euclidean situation. As a consequence, we deduce that quasisymmetric maps respect the Cheeger differentials of Lipschitz functions …

Tangency conditions for multivalued mappings

1996

We prove that interiority conditions imply tangency conditions for two multivalued mappings from a topological space into a normed vector space. As a consequence, we obtain the lower semicontinuity of the intersection of two multivalued mappings. An application to the epi-upper semicontinuity of the sum of convex vector-valued mappings is given.

A multilinear Phelps' Lemma

2007

We prove a multilinear version of Phelps' Lemma: if the zero sets of multilinear forms of norm one are 'close', then so are the multilinear forms.

Entire Functions of Bounded Type on Fréchet Spaces

1993

We show that holomorphic mappings of bounded type defined on Frechet spaces extend to the bidual. The relationship between holomorphic mappings of bounded type and of uniformly bounded type is discussed and some algebraic and topological properties of the space of all entire mappings of (uniformly) bounded type are proved, for example a holomorphic version of Schauder's theorem.

A space of projections on the Bergman space

2010

We define a set of projections on the Bergman space A 2 , which is parameterized by an ane subset of a Banach space of holomorphic functions in the disk and which includes the classical Forelli-Rudin projections.

Shadow trees of Mandelbrot sets

2003

A Logical Characterisation of Linear Time on Nondeterministic Turing Machines

1999

The paper gives a logical characterisation of the class NTIME(n) of problems that can be solved on a nondeterministic Turing machine in linear time. It is shown that a set L of strings is in this class if and only if there is a formula of the form ∃f1..∃fk∃R1..∃Rm∀xφv; that is true exactly for all strings in L. In this formula the fi are unary function symbols, the Ri are unary relation symbols and φv; is a quantifierfree formula. Furthermore, the quantification of functions is restricted to non-crossing, decreasing functions and in φv; no equations in which different functions occur are allowed. There are a number of variations of this statement, e.g., it holds also for k = 3. From these r…