Search results for "Bounded"
showing 10 items of 658 documents
Mass transport problems for the Euclidean distance obtained as limits of p-Laplacian type problems with obstacles
2014
In this paper we analyze a mass transportation problem that consists in moving optimally (paying a transport cost given by the Euclidean distance) an amount of a commodity larger than or equal to a fixed one to fulfil a demand also larger than or equal to a fixed one, with the obligation of paying an extra cost of −g1(x) for extra production of one unit at location x and an extra cost of g2(y) for creating one unit of demand at y. The extra amounts of mass (commodity/demand) are unknowns of the problem. Our approach to this problem is by taking the limit as p→∞ to a double obstacle problem (with obstacles g1, g2) for the p-Laplacian. In fact, under a certain natural constraint on the extra …
Adaptive learning of compressible strings
2020
Suppose an oracle knows a string $S$ that is unknown to us and that we want to determine. The oracle can answer queries of the form "Is $s$ a substring of $S$?". In 1995, Skiena and Sundaram showed that, in the worst case, any algorithm needs to ask the oracle $\sigma n/4 -O(n)$ queries in order to be able to reconstruct the hidden string, where $\sigma$ is the size of the alphabet of $S$ and $n$ its length, and gave an algorithm that spends $(\sigma-1)n+O(\sigma \sqrt{n})$ queries to reconstruct $S$. The main contribution of our paper is to improve the above upper-bound in the context where the string is compressible. We first present a universal algorithm that, given a (computable) compre…
Cyclic Complexity of Words
2014
We introduce and study a complexity function on words $c_x(n),$ called \emph{cyclic complexity}, which counts the number of conjugacy classes of factors of length $n$ of an infinite word $x.$ We extend the well-known Morse-Hedlund theorem to the setting of cyclic complexity by showing that a word is ultimately periodic if and only if it has bounded cyclic complexity. Unlike most complexity functions, cyclic complexity distinguishes between Sturmian words of different slopes. We prove that if $x$ is a Sturmian word and $y$ is a word having the same cyclic complexity of $x,$ then up to renaming letters, $x$ and $y$ have the same set of factors. In particular, $y$ is also Sturmian of slope equ…
Finite state verifiers with constant randomness
2014
We give a new characterization of $\mathsf{NL}$ as the class of languages whose members have certificates that can be verified with small error in polynomial time by finite state machines that use a constant number of random bits, as opposed to its conventional description in terms of deterministic logarithmic-space verifiers. It turns out that allowing two-way interaction with the prover does not change the class of verifiable languages, and that no polynomially bounded amount of randomness is useful for constant-memory computers when used as language recognizers, or public-coin verifiers. A corollary of our main result is that the class of outcome problems corresponding to O(log n)-space …
On the Power of Non-adaptive Learning Graphs
2012
We introduce a notion of the quantum query complexity of a certificate structure. This is a formalisation of a well-known observation that many quantum query algorithms only require the knowledge of the disposition of possible certificates in the input string, not the precise values therein. Next, we derive a dual formulation of the complexity of a non-adaptive learning graph, and use it to show that non-adaptive learning graphs are tight for all certificate structures. By this, we mean that there exists a function possessing the certificate structure and such that a learning graph gives an optimal quantum query algorithm for it. For a special case of certificate structures generated by cer…
Abelian Powers and Repetitions in Sturmian Words
2016
Richomme, Saari and Zamboni (J. Lond. Math. Soc. 83: 79-95, 2011) proved that at every position of a Sturmian word starts an abelian power of exponent $k$ for every $k > 0$. We improve on this result by studying the maximum exponents of abelian powers and abelian repetitions (an abelian repetition is an analogue of a fractional power) in Sturmian words. We give a formula for computing the maximum exponent of an abelian power of abelian period $m$ starting at a given position in any Sturmian word of rotation angle $\alpha$. vAs an analogue of the critical exponent, we introduce the abelian critical exponent $A(s_\alpha)$ of a Sturmian word $s_\alpha$ of angle $\alpha$ as the quantity $A(s_\a…
Abelian-Square-Rich Words
2017
An abelian square is the concatenation of two words that are anagrams of one another. A word of length $n$ can contain at most $\Theta(n^2)$ distinct factors, and there exist words of length $n$ containing $\Theta(n^2)$ distinct abelian-square factors, that is, distinct factors that are abelian squares. This motivates us to study infinite words such that the number of distinct abelian-square factors of length $n$ grows quadratically with $n$. More precisely, we say that an infinite word $w$ is {\it abelian-square-rich} if, for every $n$, every factor of $w$ of length $n$ contains, on average, a number of distinct abelian-square factors that is quadratic in $n$; and {\it uniformly abelian-sq…
Progressive Stochastic Binarization of Deep Networks
2019
A plethora of recent research has focused on improving the memory footprint and inference speed of deep networks by reducing the complexity of (i) numerical representations (for example, by deterministic or stochastic quantization) and (ii) arithmetic operations (for example, by binarization of weights). We propose a stochastic binarization scheme for deep networks that allows for efficient inference on hardware by restricting itself to additions of small integers and fixed shifts. Unlike previous approaches, the underlying randomized approximation is progressive, thus permitting an adaptive control of the accuracy of each operation at run-time. In a low-precision setting, we match the accu…
Robust H;<inf>&#x221E;</inf> filtering for 2-D FM systems: A finite frequency approach
2012
This paper investigates the problem of robust H; ∞ filtering for uncertain two-dimensional (2-D) discrete systems in the Fornasini-Marchesini local state-space (FM LSS) model with polytopic uncertain parameters. The goal of the paper is to design filters such that the finite frequency (FF) H; ∞ norm of the filtering error system has a specified upper bound for all uncertainties. A generalized bounded real lemma (BRL) is first derived for FF H; ∞ performance analysis of nominal 2-D FM LSS systems, and then a method, in terms of solving optimization problems with LMI constraints, is presented for robust FF H; ∞ filter analysis and design. An illustrative example is given to show the improveme…
Convergence of the finite volume method for a conductive-radiative heat transfer problem
2013
We show that the finite volume method rigorously converges to the solution of a conductive-radiative heat transfer problem with nonlocal and nonlinear boundary conditions. To get this result, we start by proving existence of solutions for a finite volume discretization of the original problem. Then, by obtaining uniform boundedness of discrete solutions and their discrete gradients with respect to mesh size, we finally get L 2type convergence of discrete solutions.