Search results for "Complex."
showing 10 items of 5824 documents
Logics with counting and equivalence
2014
We consider the two-variable fragment of first-order logic with counting, subject to the stipulation that a single distinguished binary predicate be interpreted as an equivalence. We show that the satisfiability and finite satisfiability problems for this logic are both NEXPTIME-complete. We further show that the corresponding problems for two-variable first-order logic with counting and two equivalences are both undecidable.
Minimal Morse flows on compact manifolds
2006
Abstract In this paper we prove, using the Poincare–Hopf inequalities, that a minimal number of non-degenerate singularities can be computed in terms only of abstract homological boundary information. Furthermore, this minimal number can be realized on some manifold with non-empty boundary satisfying the abstract homological boundary information. In fact, we present all possible indices and types (connecting or disconnecting) of singularities realizing this minimal number. The Euler characteristics of all manifolds realizing this minimal number are obtained and the associated Lyapunov graphs of Morse type are described and shown to have the lowest topological complexity.
Quantum Algorithms for Learning Symmetric Juntas via Adversary Bound
2014
In this paper, we study the following variant of the junta learning problem. We are given oracle access to a Boolean function f on n variables that only depends on k variables, and, when restricted to them, equals some predefined function h. The task is to identify the variables the function depends on. This is a generalisation of the Bernstein-Vazirani problem (when h is the XOR function) and the combinatorial group testing problem (when h is the OR function). We analyse the general case using the adversary bound, and give an alternative formulation for the quantum query complexity of this problem. We construct optimal quantum query algorithms for the cases when h is the OR function (compl…
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.