1,721,891 research outputs found
Quantitative Coding and Complexity Theory of Continuous Data: Part I: Motivation, Definition, Consequences
No full textWhen encoding real numbers as (necessarily infinite) bit-strings, the na & iuml;ve binary/decimal expansion is wellknown [doi:10.1112/plms/s2-43.6.544] computably "unreasonable", rendering, for example, tripling qualitatively discontinuous on Cantor's sequence space. Encoding reals as sequences of (finite integer numerators and denominators, in binary, of) rational approximations does make common operations qualitatively computable, yet admits no bounds on their computational complexity/quantitative continuity. Dyadic approximations, on the other hand, are known polynomially, and signed binary expansions even linearly, "reasonable" in a rigorous sense recalled in the introduction of this work. But how to distinguish between un/suitable encodings of spaces common in Calculus beyond the reals, such as Banach or Sobolev? With respect to qualitative computability/continuity on topological spaces, the technical condition of admissibility had been identified [doi:10.1016/0304-3975(85)90208-7] for an encoding over Cantor space (historically called a representation) to be "reasonable" [doi:10.1007/978-3-030-59234-9_9]. Roughly speaking, admissibility requires the representation to be (i) continuous, and to be (ii) maximal with respect to continuous reduction. Admissible representations exist for a large class of spaces. And for (precisely) these does the Kreitz-Weihrauch-sometimes aka Main-Theorem of Computable Analysis hold, which characterizes continuity of functions by continuity of mappings translating codes, so-called realizers. We refine qualitative computability/continuity on topological spaces to quantitative continuity/complexity on metric spaces by proposing a notion, and investigating the properties, of polynomially/linearly admissible representations. Roughly speaking, these are (i) close to "optimally" continuous, namely linearly/polynomially relative to the space's entropy, and they are (ii) maximal with respect to relative linear/polynomial quantitatively continuous reductions defined in the main text. Quantitatively admissible representations are closed under composition over generalized ground spaces beyond Cantor's. Such representations exhibit a quantitative strengthening of the qualitative Main Theorem, namely now characterizing quantitative continuity of functions by quantitative continuity of realizers. A large class of compact metric spaces is shown to admit polynomially admissible representations over compact ultrametric spaces, and some even a generalization of the linearly admissible signed binary encoding. Quantitative admissibility thus provides the desired criterion for complexity-theoretically "reasonable" encodings.
Definable relations in finite dimensional subspace lattices with involution. Part II: Quantifier-free and homogeneous descriptions
No full textFor finite dimensional hermitean inner product spaces V, over ∗ -fields F, and in the presence of orthogonal bases providing form elements in the prime subfield of F, we show that quantifier-free definable relations in the subspace lattice L(V) , endowed with the involution induced by orthogonality, admit quantifier-free descriptions within F, also in terms of Grassmann–Plücker coordinates. In the latter setting, homogeneous descriptions are obtained if one allows quantification type Σ1 . In absence of involution, these results remain valid.
On the Computational Complexity of Positive Linear Functionals on
No full textThe Lebesgue integration has been related to polynomial counting complexity in several ways, even when restricted to smooth functions. We prove analogue results for the integration operator associated with the Cantor measure as well as a more general second-order #P#P-hardness criterion for such operators. We also give a simple criterion for relative polynomial time complexity and obtain a better understanding of the complexity of integration operators using the Lebesgue decomposition theorem
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Computational Complexity of Real Powering and Improved Solving Linear Differential Equations
No full textWe re-consider the problem of solving systems of differential equations approximately up to guaranteed absolute error 1/2(n) from the rigorous perspective of sequential and parallel time (i.e. Boolean circuit depth, equivalently: Turing machine space) complexity. While solutions to general smooth ODEs are known "PSPACE-complete" [Kawamura'10], we show that (i) The Cauchy problem for linear ODEs can be solved in NC2(,) that is, within polylogarithmic parallel time O(log(2) n) by Boolean circuits of polynomial size. (ii) The Cauchy problem for linear analytic PDEs, having a unique solution by the Cauchy-Kovalevskaya theorem, can be also solved in polylogarithmic parallel time, thus generalizing the case of analytic ODEs [Bournez/Graca/Pouly'11]. (iii) Well-posed Cauchy and boundary-value problems for linear PDEs in classes of continuously differentiable functions are solvable in the counting complexity class #P-#P : improving over common numerical approaches yielding exponential sequential time or parallel polynomial time. Our results build on efficient algorithms and their analyses for real polynomial, matrix and operator powering which do not occur in the discrete case and may be of independent interest
Variations on the Author
Full text link“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
- …
