Search results for "000 Computer science"
showing 8 items of 18 documents
Adaptive Lower Bound for Testing Monotonicity on the Line
2018
In the property testing model, the task is to distinguish objects possessing some property from the objects that are far from it. One of such properties is monotonicity, when the objects are functions from one poset to another. This is an active area of research. In this paper we study query complexity of $\epsilon$-testing monotonicity of a function $f\colon [n]\to[r]$. All our lower bounds are for adaptive two-sided testers. * We prove a nearly tight lower bound for this problem in terms of $r$. The bound is $\Omega(\frac{\log r}{\log \log r})$ when $\epsilon = 1/2$. No previous satisfactory lower bound in terms of $r$ was known. * We completely characterise query complexity of this probl…
Anti-powers in infinite words
2018
In combinatorics of words, a concatenation of $k$ consecutive equal blocks is called a power of order $k$. In this paper we take a different point of view and define an anti-power of order $k$ as a concatenation of $k$ consecutive pairwise distinct blocks of the same length. As a main result, we show that every infinite word contains powers of any order or anti-powers of any order. That is, the existence of powers or anti-powers is an unavoidable regularity. Indeed, we prove a stronger result, which relates the density of anti-powers to the existence of a factor that occurs with arbitrary exponent. As a consequence, we show that in every aperiodic uniformly recurrent word, anti-powers of ev…
The Fluted Fragment with Transitivity
2019
We study the satisfiability problem for the fluted fragment extended with transitive relations. We show that the logic enjoys the finite model property when only one transitive relation is available. On the other hand we show that the satisfiability problem is undecidable already for the two-variable fragment of the logic in the presence of three transitive relations.
Textureless macula swelling detection with multiple retinal fundus images
2011
Retinal fundus images acquired with nonmydriatic digital fundus cameras are versatile tools for the diagnosis of various retinal diseases. Because of the ease of use of newer camera models and their relatively low cost, these cameras can be employed by operators with limited training for telemedicine or point-of-care (PoC) applications. We propose a novel technique that uses uncalibrated multiple-view fundus images to analyze the swelling of the macula. This innovation enables the detection and quantitative measurement of swollen areas by remote ophthalmologists. This capability is not available with a single image and prone to error with stereo fundus cameras. We also present automatic alg…
Contrasting parental roles shape sex differences in poison frog space use but not navigational performance
2022
Sex differences in vertebrate spatial abilities are typically interpreted under the adaptive specialization hypothesis, which posits that male reproductive success is linked to larger home ranges and better navigational skills. The androgen spillover hypothesis counters that enhanced male spatial performance may be a byproduct of higher androgen levels. Animal groups that include species where females are expected to outperform males based on life-history traits are key for disentangling these hypotheses. We investigated the association between sex differences in reproductive strategies, spatial behavior, and androgen levels in three species of poison frogs. We tracked individuals in natura…
A New Class of Searchable and Provably Highly Compressible String Transformations
2019
The Burrows-Wheeler Transform is a string transformation that plays a fundamental role for the design of self-indexing compressed data structures. Over the years, researchers have successfully extended this transformation outside the domains of strings. However, efforts to find non-trivial alternatives of the original, now 25 years old, Burrows-Wheeler string transformation have met limited success. In this paper we bring new lymph to this area by introducing a whole new family of transformations that have all the "myriad virtues" of the BWT: they can be computed and inverted in linear time, they produce provably highly compressible strings, and they support linear time pattern search direc…
Advancing Design Science Research with Solution-based Probing
2019
We propose solution-based probing as an extension of action design research. The core idea is that researchers bring a prototype solution (probe) into one or more fields and explore to synthesize robust and generalizable design knowledge, along with knowledge of the phenomena and correlations we discover. We believe proposing solutions creates opportunities for researchers to innovate and to document the impact. In addition, solutions can be effective probes for advancing theory, in terms of design theories and in creating exploratory foundations for behavioral and causal theory. We illustrate solution-based probing with four exemplar studies in the areas governance of municipalities, polic…
Feature Extractors for Describing Vehicle Routing Problem Instances
2016
The vehicle routing problem comes in varied forms. In addition to usual variants with diverse constraints and specialized objectives, the problem instances themselves – even from a single shared source - can be distinctly different. Heuristic, metaheuristic, and hybrid algorithms that are typically used to solve these problems are sensitive to this variation and can exhibit erratic performance when applied on new, previously unseen instances. To mitigate this, and to improve their applicability, algorithm developers often choose to expose parameters that allow customization of the algorithm behavior. Unfortunately, finding a good set of values for these parameters can be a tedious task that…