Search results for "Linear function"

Lower space bounds for randomized computation

1994

It is a fundamental problem in the randomized computation how to separate different randomized time or randomized space classes (c.f., e.g., [KV87, KV88]). We have separated randomized space classes below log n in [FK94]. Now we have succeeded to separate small randomized time classes for multi-tape 2-way Turing machines. Surprisingly, these “small” bounds are of type n+f(n) with f(n) not exceeding linear functions. This new approach to “sublinear” time complexity is a natural counterpart to sublinear space complexity. The latter was introduced by considering the input tape and the work tape as separate devices and distinguishing between the space used for processing information and the spa…

Absolutely Convergent Extensions of Nonclosable Positive Linear Functionals

2010

The existence of extensions of a positive linear functional ω defined on a dense *-subalgebra \({\mathfrak{A}_0}\) of a topological *-algebra \({\mathfrak{A}}\), satisfying certain regularity conditions, is examined. The main interest is focused on the case where ω is nonclosable and sufficient conditions for the existence of an absolutely convergent extension of ω are given.

Application of kolmogorov complexity to inductive inference with limited memory

1995

A b s t r a c t . We consider inductive inference with limited memory[l]. We show that there exists a set U of total recursive functions such that U can be learned with linear long-term memory (and no short-term memory); U can be learned with logarithmic long-term memory (and some amount of short-term memory); if U is learned with sublinear long-term memory, then the short-term memory exceeds arbitrary recursive function. Thus an open problem posed by Freivalds, Kinber and Smith[l] is solved. To prove our result, we use Kolmogorov complexity.

PI-algebras with slow codimension growth

2005

Let $c_n(A),\ n=1,2,\ldots,$ be the sequence of codimensions of an algebra $A$ over a field $F$ of characteristic zero. We classify the algebras $A$ (up to PI-equivalence) in case this sequence is bounded by a linear function. We also show that this property is closely related to the following: if $l_n(A), \ n=1,2,\ldots, $ denotes the sequence of colengths of $A$, counting the number of $S_n$-irreducibles appearing in the $n$-th cocharacter of $A$, then $\lim_{n\to \infty} l_n(A)$ exists and is bounded by $2$.

Representable linear functionals on partial *-algebras

2012

A GNS-like *-representation of a partial *-algebra \({{\mathfrak A}}\) defined by certain representable linear functionals on \({{\mathfrak A}}\) is constructed. The study of the interplay with the GNS construction associated with invariant positive sesquilinear forms (ips) leads to the notions of pre-core and of singular form. It is shown that a positive sesquilinear form with pre-core always decomposes into the sum of an ips form and a singular one.

Lower Bounds and Hierarchies for Quantum Memoryless Communication Protocols and Quantum Ordered Binary Decision Diagrams with Repeated Test

2017

We explore multi-round quantum memoryless communication protocols. These are restricted version of multi-round quantum communication protocols. The “memoryless” term means that players forget history from previous rounds, and their behavior is obtained only by input and message from the opposite player. The model is interesting because this allows us to get lower bounds for models like automata, Ordered Binary Decision Diagrams and streaming algorithms. At the same time, we can prove stronger results with this restriction. We present a lower bound for quantum memoryless protocols. Additionally, we show a lower bound for Disjointness function for this model. As an application of communicatio…

1977

The thermal behavior of cycloalkanes (CH2)n with 12 ≤ n ≤ 84 prepared by metathesis reaction of cyclododecene, GPC separation of the oligomers, and hydrogenation has been investigated. The molar enthalpies of fusion being lower by a certain amount than those of the corresponding n-alkanes are a linear function of the chain length n. The entropy of fusion per CH2 increases with chain length in a not-linear mode (when plotted vs. 1/n). The melting points of the cycloalkanes are lower than those of the corresponding n-alkanes, the difference becoming smaller with increasing chain length.

Extensions of positive linear functionals on a *-algebra

2010

The family of all extensions of a nonclosable hermitian positive linear functional defined on a dense *-subalgebra $\Ao$ of a topological *-algebra $\A[\tau]$ is studied with the aim of finding extensions that behave regularly. Under suitable assumptions, special classes of extensions (positive, positively regular, absolutely convergent) are constructed. The obtained results are applied to the commutative integration theory to recover from the abstract setup the well-known extensions of Lebesgue integral and, in noncommutative integration theory, for introducing a generalized non absolutely convergent integral of operators measurable w. r. to a given trace $\sigma$.

Stochastic resonance in a trapping overdamped monostable system.

2009

The response of a trapping overdamped monostable system to a harmonic perturbation is analyzed, in the context of stochastic resonance phenomenon. We consider the dynamics of a Brownian particle moving in a piecewise linear potential with a white Gaussian noise source. Based on linear-response theory and Laplace transform technique, analytical expressions of signal-to-noise ratio (SNR) and signal power amplification (SPA) are obtained. We find that the SNR is a nonmonotonic function of the noise intensity, while the SPA is monotonic. Theoretical results are compared with numerical simulations.

Resonant activation in piecewise linear asymmetric potentials

2011

7 páginas, 8 figuras.-- PACS number(s): 05.40.−a, 05.45.−a, 02.50.Ey