Search results for "Bounds"
showing 10 items of 298 documents
Guaranteed error bounds for a class of Picard-Lindelöf iteration methods
2013
We present a new version of the Picard-Lindelof method for ordinary dif- ¨ ferential equations (ODEs) supplied with guaranteed and explicitly computable upper bounds of an approximation error. The upper bounds are based on the Ostrowski estimates and the Banach fixed point theorem for contractive operators. The estimates derived in the paper take into account interpolation and integration errors and, therefore, provide objective information on the accuracy of computed approximations. peerReviewed
On t-covers in finite projective spaces
1979
A t-cover of the finite projective space PG(d,q) is a setS of t-dimensional subspaces such that any point of PG(d,q) is contained in at least one element ofS. In Theorem 1 a lower bound for the cardinality of a t-coverS in PG(d,q) is obtained and in Theorem 2 it is shown that this bound is best possible for all positive integers t,d and for any prime-power q.
On the type of partial t-spreads in finite projective spaces
1985
AbstractA partial t-spread in a projective space P is a set of mutually skew t-dimensional subspaces of P. In this paper, we deal with the question, how many elements of a partial spread L can be contained in a given d-dimensional subspace of P. Our main results run as follows. If any d-dimensional subspace of P contains at least one element of L, then the dimension of P has the upper bound d−1+(d/t). The same conclusion holds, if no d-dimensional subspace contains precisely one element of L. If any d-dimensional subspace has the same number m>0 of elements of L, then L is necessarily a total t-spread. Finally, the ‘type’ of the so-called geometric t-spreads is determined explicitely.
Sensitivity Versus Certificate Complexity of Boolean Functions
2016
Sensitivity, block sensitivity and certificate complexity are basic complexity measures of Boolean functions. The famous sensitivity conjecture claims that sensitivity is polynomially related to block sensitivity. However, it has been notoriously hard to obtain even exponential bounds. Since block sensitivity is known to be polynomially related to certificate complexity, an equivalent of proving this conjecture would be showing that the certificate complexity is polynomially related to sensitivity. Previously, it has been shown that $$bsf \le Cf \le 2^{sf-1} sf - sf-1$$. In this work, we give a better upper bound of $$bsf \le Cf \le \max \left 2^{sf-1}\left sf-\frac{1}{3}\right , sf\right $…
On a Conjecture by Christian Choffrut
2017
It is one of the most famous open problems to determine the minimum amount of states required by a deterministic finite automaton to distinguish a pair of strings, which was stated by Christian Choffrut more than thirty years ago. We investigate the same question for different automata models and we obtain new upper and lower bounds for some of them including alternating, ultrametric, quantum, and affine finite automata.
Affine Automata Verifiers
2021
We initiate the study of the verification power of Affine finite automata (AfA) as a part of Arthur-Merlin (AM) proof systems. We show that every unary language is verified by a real-valued AfA verifier. Then, we focus on the verifiers restricted to have only integer-valued or rational-valued transitions. We observe that rational-valued verifiers can be simulated by integer-valued verifiers, and their protocols can be simulated in nondeterministic polynomial time. We show that this upper bound is tight by presenting an AfA verifier for NP-complete problem SUBSETSUM. We also show that AfAs can verify certain non-affine and non-stochastic unary languages.
Branch and bound for the cutwidth minimization problem
2013
The cutwidth minimization problem consists of finding a linear arrangement of the vertices of a graph where the maximum number of cuts between the edges of the graph and a line separating consecutive vertices is minimized. We first review previous approaches for special classes of graphs, followed by lower bounds and then a linear integer formulation for the general problem. We then propose a branch-and-bound algorithm based on different lower bounds on the cutwidth of partial solutions. Additionally, we introduce a Greedy Randomized Adaptive Search Procedure (GRASP) heuristic to obtain good initial solutions. The combination of the branch-and-bound and GRASP methods results in optimal solu…
The Besov capacity in metric spaces
2016
We study a capacity theory based on a definition of Haj{\l} asz-Besov functions. We prove several properties of this capacity in the general setting of a metric space equipped with a doubling measure. The main results of the paper are lower bound and upper bound estimates for the capacity in terms of a modified Netrusov-Hausdorff content. Important tools are $\gamma$-medians, for which we also prove a new version of a Poincar\'e type inequality.
Nondeterministic Unitary OBDDs
2017
We investigate the width complexity of nondeterministic unitary OBDDs (NUOBDDs). Firstly, we present a generic lower bound on their widths based on the size of strong 1-fooling sets. Then, we present classically “cheap” functions that are “expensive” for NUOBDDs and vice versa by improving the previous gap. We also present a function for which neither classical nor unitary nondeterminism does help. Moreover, based on our results, we present a width hierarchy for NUOBDDs. Lastly, we provide the bounds on the widths of NUOBDDs for the basic Boolean operations negation, union, and intersection.
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…