Search results for "lower bounds"
showing 10 items of 259 documents
Nearly tight bounds on the learnability of evolution
2002
Evolution is often modeled as a stochastic process which modifies DNA. One of the most popular and successful such processes are the Cavender-Farris (CF) trees, which are represented as edge weighted trees. The Phylogeny Construction Problem is that of, given /spl kappa/ samples drawn from a CF tree, output a CF tree which is close to the original. Each CF tree naturally defines a random variable, and the gold standard for reconstructing such trees is the maximum likelihood estimator of this variable. This approach is notoriously computationally expensive. We show that a very simple algorithm, which is a variant on one of the most popular algorithms used by practitioners, converges on the t…
Complete weights andv-peak points of spaces of weighted holomorphic functions
2006
We examine the geometric theory of the weighted spaces of holomorphic functions on bounded open subsets ofC n ,C n ,H v (U) and\(H_{v_o } (U)\), by finding a lower bound for the set of weak*-exposed and weak*-strongly exposed points of the unit ball of\(H_{v_o } (U)'\) and give necessary and sufficient conditions for this set to be naturally homeomorphic toU. We apply these results to examine smoothness and strict convexity of\(H_{v_o } (U)\) and\(H_v (U)\). We also investigate whether\(H_{v_o } (U)\) is a dual space.
How Low Can Approximate Degree and Quantum Query Complexity Be for Total Boolean Functions?
2012
It has long been known that any Boolean function that depends on n input variables has both degree and exact quantum query complexity of Omega(log n), and that this bound is achieved for some functions. In this paper we study the case of approximate degree and bounded-error quantum query complexity. We show that for these measures the correct lower bound is Omega(log n / loglog n), and we exhibit quantum algorithms for two functions where this bound is achieved.
On the effect of analog noise in discrete-time analog computations
1998
We introduce a model for analog computation with discrete time in the presence of analog noise that is flexible enough to cover the most important concrete cases, such as noisy analog neural nets and networks of spiking neurons. This model subsumes the classical model for digital computation in the presence of noise. We show that the presence of arbitrarily small amounts of analog noise reduces the power of analog computational models to that of finite automata, and we also prove a new type of upper bound for the VC-dimension of computational models with analog noise.
High Precision Conservative Surface Mesh Generation for Swept Volumes
2015
We present a novel, efficient, and flexible scheme to generate a high-quality mesh that approximates the outer boundary of a swept volume. Our approach comes with two guarantees. First, the approximation is conservative, i.e., the swept volume is enclosed by the generated mesh. Second, the one-sided Hausdorff distance of the generated mesh to the swept volume is upper bounded by a user defined tolerance. Exploiting this tolerance the algorithm generates a mesh that is adapted to the local complexity of the swept volume boundary, keeping the overall output complexity remarkably low. The algorithm is two-phased: the actual sweep and the mesh generation. In the sweeping phase, we introduce a g…
Dynamic Channel Aggregation Strategies in Cognitive Radio Networks with Spectrum Adaptation
2011
In cognitive radio networks, channel aggregation techniques which combine several channels together as one channel have been proposed in many MAC protocols. In this paper, spectrum adaptation is proposed in channel aggregation and two strategies which dynamically adjust channel occupancy of ongoing traffic flows are further developed. The performance of these strategies is evaluated using continuous time Markov chain models. Moreover, models in the quasi-stationary regime are analyzed and the closed-form capacity expression is derived in this regime. Numerical results demonstrate that the capacity of the secondary network can be improved by using channel aggregation with spectrum adaptation.
Parameter optimization for amplify-and-forward relaying systems with pilot symbol assisted modulation scheme
2009
Article published in the journal:Wireless Sensor Network Also available from publisher: http://dx.doi.org/10.4236/wsn.2009.11003 Cooperative diversity is a promising technology for future wireless networks. In this paper, we consider a cooperative communication system operating in an amplify-and-forward (AF) mode with a pilot symbol assisted modulation (PSAM) scheme. It is assumed that a linear minimum mean square estimator (LMMSE) is used for the channel estimation at the receiver. A simple and easy-to-evaluate asymptotical upper bound (AUB) of the symbol-error-rate (SER) is derived for uncoded AF cooperative communication systems with quadrature amplitude modulation (QAM) constellations. …
The Two-Criteria Topological Design Problem in WAN with Delay Constraint: An Algorithm and Computational Results
2003
The problem is concerned with designing of wide area networks (WAN). The problem consists in selection of flow routes, channel capacities and wide area network topology in order to minimize the total average delay per packet and the leasing cost of channels subject to delay constraint. The problem is NP complete. Then, the branch and bound method is used to construct the exact algorithm. Lower bound of the criterion function is proposed. Computational results are reported. Based on computational experiments, several properties of the considered problem are formulated.
Coupled cluster calculations of the vertical excitation energies of tetracyanoethylene
2003
The vertical spectrum of tetracyanoethylene was studied using coupled cluster theory. It was found that the lowest singlet-singlet transition, which corresponds to the excitation from the highest occupied molecular orbital (HOMO) to the lowest unoccupied molecular orbital (LUMO) excitation, occurs at 5.16 eV in the gas phase and is lowered approximately 0.1 eV due to solvent effects in acetonitrile. A parallel study on the ethene spectrum showed the quality of the basis sets and methods used, by placing the V state 7.92 eV above the ground state and giving an energy for the 0-0 transition of 5.42 eV to be compared with the experimental value of 5.50 eV.
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)]