Search results for "Complex."

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.

CHARACTERS INDUCED FROM FULLY RAMIFIED SUBGROUPS

2001

Suppose that G is a finite π-separable group, let cf(G) be the space of complex class functions of G and let Irr(G) be the set of the irreducible complex characters of G. Let K be an arbitrary Hall...

Forbidden Factors and Fragment Assembly

2001

In this paper methods and results related to the notion of minimal forbidden words are applied to the fragment assembly problem. The fragment assembly problem can be formulated, in its simplest form, as follows: reconstruct a word w from a given set I of substrings (fragments ) of a word w . We introduce an hypothesis involving the set of fragments I and the maximal length m(w) of the minimal forbidden factors of w . Such hypothesis allows us to reconstruct uniquely the word w from the set I in linear time. We prove also that, if w is a word randomly generated by a memoryless source with identical symbol probabilities, m(w) is logarithmic with respect to the size of w . This result shows th…

O(n 2 log n) Time On-Line Construction of Two-Dimensional Suffix Trees

2005

The two-dimensional suffix tree of an n × n square matrix A is a compacted trie that represents all square submatrices of Ai¾?[9]. For the off-line case, i.e., A is given in advance to the algorithm, it is known how to build it in optimal time, for any type of alphabet sizei¾?[9,15]. Motivated by applications in Image Compressioni¾?[18], Giancarlo and Guaianai¾?[12] considered the on-line version of the two-dimensional suffix tree and presented an On2log2n-time algorithm, which we refer to as GG. That algorithm is a non-trivial generalization of Ukkonen's on-line algorithm for standard suffix trees [19]. The main contribution in this paper is an Olog n factor improvement in the time complex…

On the exponential growth of graded Capelli polynomials

2013

In a free superalgebra over a field of characteristic zero we consider the graded Capelli polynomials Cap M+1[Y,X] and Cap L+1[Z,X] alternating on M+1 even variables and L+1 odd variables, respectively. Here we compute the superexponent of the variety of superalgebras determinated by Cap M+1[Y,X] and Cap L+1[Z,X]. An essential tool in our computation is the generalized-six-square theorem proved in [3].

Automorphisms of simplicial complexes and their Stanley-Reisner rings

1997

Entropic Profiles, Maximal Motifs and the Discovery of Significant Repetitions in Genomic Sequences

2014

The degree of predictability of a sequence can be measured by its entropy and it is closely related to its repetitiveness and compressibility. Entropic profiles are useful tools to study the under- and over-representation of subsequences, providing also information about the scale of each conserved DNA region. On the other hand, compact classes of repetitive motifs, such as maximal motifs, have been proved to be useful for the identification of significant repetitions and for the compression of biological sequences. In this paper we show that there is a relationship between entropic profiles and maximal motifs, and in particular we prove that the former are a subset of the latter. As a furt…

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 \…

Fast and Simple Approximation of the Diameter and Radius of a Graph

2006

The increasing amount of data to be processed by computers has led to the need for highly efficient algorithms for various computational problems. Moreover, the algorithms should be as simple as possible to be practically applicable. In this paper we propose a very simple approximation algorithm for finding the diameter and the radius of an undirected graph. The algorithm runs in $O(m\sqrt{n})$ time and gives an additive error of $O(\sqrt{n})$ for a graph with n vertices and m edges. Practical experiments show that the results of our algorithm are close to the optimum and compare favorably to the 2/3-approximation algorithm for the diameter problem by Aingworth et al [1].

TERMITE: AnRscript for fast reduction of laser ablation inductively coupled plasma mass spectrometry data and its application to trace element measur…

2017

RATIONALE High spatial resolution Laser Ablation Inductively Coupled Plasma Mass Spectrometry (LA-ICPMS) determination of trace element concentrations is of great interest for geological and environmental studies. Data reduction is a very important aspect of LA-ICP-MS, and several commercial programs for handling LA-ICPMS trace element data are available. Each of these software packages has its specific advantages and disadvantages. METHODS Here we present TERMITE, an R script for the reduction of LA-ICPMS data, which can reduce both spot and line scan measurements. Several parameters can be adjusted by the user, who does not necessarily need prior knowledge in R. Currently, ten reference m…