Search results for "lower bound"
showing 10 items of 269 documents
Multilevel Bandwidth and Radio Labelings of Graphs
2008
This paper introduces a generalization of the graph bandwidth parameter: for a graph G and an integer k ≤ diam(G), the k-level bandwidth Bk(G)of G is defined by Bk(G) = minγ max{|γ(x)-γ(y)|-d(x, y)+1 : x, y ∈ V (G), d(x, y) ≤ k}, the minimum being taken among all proper numberings γ of the vertices of G. We present general bounds on Bk(G) along with more specific results for k = 2 and the exact value for k = diam(G). We also exhibit relations between the k-level bandwidth and radio k-labelings of graphs from which we derive a upper bound for the radio number of an arbitrary graph.
The Minimum Amount of Useful Space: New Results and New Directions
2014
We consider minimal space requirements when using memory with restricted access policy (pushdown - hence giving pushdown automata (PDAs), and counter - hence giving counter automata (CAs)) in connection with two-way and realtime head motion. The main results are that: (i) loglogn is a tight space lower bound for accepting general nonregular languages on weak realtime PDAs, (ii) there exist unary nonregular languages accepted by realtime alternating CAs within weak logn space, (iii) there exist nonregular languages accepted by two-way DPADs within strong loglogn space, and, (iv) there exist unary nonregular languages accepted by two-way CAs with quantum and classical states within middle log…
Words and forbidden factors
2002
AbstractGiven a finite or infinite word v, we consider the set M(v) of minimal forbidden factors of v. We show that the set M(v) is of fundamental importance in determining the structure of the word v. In the case of a finite word w we consider two parameters that are related to the size of M(w): the first counts the minimal forbidden factors of w and the second gives the length of the longest minimal forbidden factor of w. We derive sharp upper and lower bounds for both parameters. We prove also that the second parameter is related to the minimal period of the word w. We are further interested to the algorithmic point of view. Indeed, we design linear time algorithm for the following two p…
Topological lower bounds on the distance between area preserving diffeomorphisms
2000
Area preserving diffeomorphisms of the 2-disk which are Identity near the boundary form a group which can be equipped, using theL2-norm on its Lie algebra, with a right invariant metric. In this paper we give a lower bound on the distance between diffeomorphisms which is invariant under area preserving changes of coordinates and which improves the lower bound induced by the Calabi invariant. In the case of renormalizable and infinitely renormalizable maps, our estimate can be improved and computed.
Optimization problem in inductive inference
1995
Algorithms recognizing to which of n classes some total function belongs are constructed (n > 2). In this construction strategies determining to which of two classes the function belongs are used as subroutines. Upper and lower bounds for number of necessary strategies are obtained in several models: FIN- and EX-identification and EX-identification with limited number of mindchanges. It is proved that in EX-identification it is necessary to use n(n−1)/2 strategies. In FIN-identification [3n/2 − 2] strategies are necessary and sufficient, in EX-identification with one mindchange- n log2n+o(n log2n) strategies.
Exact Quantum Query Complexity of $$\text {EXACT}_{k,l}^n$$
2017
In the exact quantum query model a successful algorithm must always output the correct function value. We investigate the function that is true if exactly k or l of the n input bits given by an oracle are 1. We find an optimal algorithm (for some cases), and a nontrivial general lower and upper bound on the minimum number of queries to the black box.
Quantum Query Complexity for Some Graph Problems
2004
The paper [4] by H. Buhrman and R. de Wolf contains an impressive survey of solved and open problems in quantum query complexity, including many graph problems. We use recent results by A.Ambainis [1] to prove higher lower bounds for some of these problems. Some of our new lower bounds do not close the gap between the best upper and lower bounds. We prove in these cases that it is impossible to provide a better application of Ambainis’ technique for these problems.
Quantum Algorithm for Dyck Language with Multiple Types of Brackets
2021
We consider the recognition problem of the Dyck Language generalized for multiple types of brackets. We provide an algorithm with quantum query complexity \(O(\sqrt{n}(\log n)^{0.5k})\), where n is the length of input and k is the maximal nesting depth of brackets. Additionally, we show the lower bound for this problem which is \(\varOmega (\sqrt{n}c^{k})\) for some constant c.
A generalization of Sardinas and Patterson's algorithm to z-codes
1993
Abstract This paper concerns the framework of z-codes theory. The main contribution consists in an extension of the algorithm of Sardinas and Patterson for deciding whether a finite set of words X is a z-code. To improve the efficiency of this test we have found a tight upper bound on the length of the shortest words that might have a double z-factorization over X. Some remarks on the complexity of the algorithm are also given. Moreover, a slight modification of this algorithm allows us to compute the z-deciphering delay of X.
Quantum Identification of Boolean Oracles
2004
The oracle identification problem (OIP) is, given a set S of M Boolean oracles out of 2 N ones, to determine which oracle in S is the current black-box oracle. We can exploit the information that candidates of the current oracle is restricted to S. The OIP contains several concrete problems such as the original Grover search and the Bernstein-Vazirani problem. Our interest is in the quantum query complexity, for which we present several upper bounds. They are quite general and mostly optimal: (i) The query complexity of OIP is \(O(\sqrt{N {\rm log} M {\rm log} N}{\rm log log} M)\) for anyS such that M = |S| > N, which is better than the obvious bound N if M \(< 2^{N/log^3 N}\). (ii) It is \…