Search results for "lower bound"
showing 10 items of 269 documents
New results for finding common neighborhoods in massive graphs in the data stream model
2008
AbstractWe consider the problem of finding pairs of vertices that share large common neighborhoods in massive graphs. We give lower bounds for randomized, two-sided error algorithms that solve this problem in the data-stream model of computation. Our results correct and improve those of Buchsbaum, Giancarlo, and Westbrook [On finding common neighborhoods in massive graphs, Theoretical Computer Science, 299 (1–3) 707–718 (2004)]
Debt Sustainability and Fiscal Space in a Heterogeneous Monetary Union: Normal Times Vs the Zero Lower Bound
2020
In this paper we study fiscal policy effects and fiscal space for countries in a monetary union with different levels of public debt. We develop a dynamic stochastic general equilibrium (DSGE) model of a two-country monetary union, calibrated to match the characteristics of Spain and Germany, in which debt sustainability is endogenously determined a la Bi (2012) to shape the responses of the risk premium on public debt. Policy shocks change the market’s expectation about future primary surplus, producing a direct effect on the sovereign risk premium and macroeconomic responses of the economy. In normal times the costs of a government spending driven fiscal consolidation in the high-debt cou…
GLOBAL DELAY TIME FOR GENERAL DISTRIBUTED NETWORKS WITH APPLICATIONS TO TIMING ANALYSIS OF DIGITAL MOS INTEGRATED CIRCUITS
1989
We consider here a general nerwork composed by n‐distributed parameters lines (with telegraph‐equations models) and m‐capacitors, all connected by a resistive multiport. An asymptotic stability property drives us to define and evaluate a global parameter (“λ‐delay time”) which describes the speed of signals propagation through the network. Because of its simplicity of calculation and its tightness, the given upper bound of the λ‐delay time is useful in timing analysis of MOS integrated chips.
A Unifying Framework for Perturbative Exponential Factorizations
2021
We propose a framework where Fer and Wilcox expansions for the solution of differential equations are derived from two particular choices for the initial transformation that seeds the product expansion. In this scheme, intermediate expansions can also be envisaged. Recurrence formulas are developed. A new lower bound for the convergence of theWilcox expansion is provided, as well as some applications of the results. In particular, two examples are worked out up to a high order of approximation to illustrate the behavior of the Wilcox expansion.
Geometry and analysis of Dirichlet forms (II)
2014
Abstract Given a regular, strongly local Dirichlet form E , under assumption that the lower bound of the Ricci curvature of Bakry–Emery, the local doubling and local Poincare inequalities are satisfied, we obtain that: (i) the intrinsic differential and distance structures of E coincide; (ii) the Cheeger energy functional Ch d E is a quadratic norm. This shows that (ii) is necessary for the Riemannian Ricci curvature defined by Ambrosio–Gigli–Savare to be bounded from below. This together with some recent results of Ambrosio–Gigli–Savare yields that the heat flow gives a gradient flow of Boltzman–Shannon entropy under the above assumptions. We also obtain an improvement on Kuwada's duality …
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.