Search results for "combinatoric"
showing 10 items of 1776 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.
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.
Homomorphisms and composition operators on algebras of analytic functions of bounded type
2005
Abstract Let U and V be convex and balanced open subsets of the Banach spaces X and Y, respectively. In this paper we study the following question: given two Frechet algebras of holomorphic functions of bounded type on U and V, respectively, that are algebra isomorphic, can we deduce that X and Y (or X * and Y * ) are isomorphic? We prove that if X * or Y * has the approximation property and H wu ( U ) and H wu ( V ) are topologically algebra isomorphic, then X * and Y * are isomorphic (the converse being true when U and V are the whole space). We get analogous results for H b ( U ) and H b ( V ) , giving conditions under which an algebra isomorphism between H b ( X ) and H b ( Y ) is equiv…
On the optimal approximation rate of certain stochastic integrals
2010
AbstractGiven an increasing function H:[0,1)→[0,∞) and An(H)≔infτ∈Tn(∑i=1n∫ti−1ti(ti−t)H(t)2dt)12, where Tn≔{τ=(ti)i=0n:0=t0<t1<⋯<tn=1}, we characterize the property An(H)≤cn, and give conditions for An(H)≤cnβ and An(H)≥1cnβ for β∈(0,1), both in terms of integrability properties of H. These results are applied to the approximation of stochastic integrals.
The Phagocyte Lattice of Dyck Words
2006
We introduce a new lattice structure on Dyck words. We exhibit efficient algorithms to compute meets and joins of Dyck words.
Every triangle-free induced subgraph of the triangular lattice is(5m,2m)-choosable
2014
A graph G is (a,b)-choosable if for any color list of size a associated with each vertex, one can choose a subset of b colors such that adjacent vertices are colored with disjoint color sets. This paper proves that for any integer m>=1, every finite triangle-free induced subgraph of the triangular lattice is (5m,2m)-choosable.
A Motzkin filter in the Tamari lattice
2015
The Tamari lattice of order n can be defined on the set T n of binary trees endowed with the partial order relation induced by the well-known rotation transformation. In this paper, we restrict our attention to the subset M n of Motzkin trees. This set appears as a filter of the Tamari lattice. We prove that its diameter is 2 n - 5 and that its radius is n - 2 . Enumeration results are given for join and meet irreducible elements, minimal elements and coverings. The set M n endowed with an order relation based on a restricted rotation is then isomorphic to a ranked join-semilattice recently defined in Baril and Pallo (2014). As a consequence, we deduce an upper bound for the rotation distan…
Matchings in three Catalan lattices
2003
In this note we consider a series of lattices that are enumerated by the well-known Catalan numbers. For each of these lattices, we exhibit a matching in a constructive way.
Generating binary trees by Glivenko classes on Tamari lattices
2003
Using algebraic-theoretic results, we give an algorithm for generating binary trees within Glivenko classes in Tamari lattices. Tamari lattices are lattices of binary trees endowed by the well-known rotation transformation.