Department of Informatics
https://hdl.handle.net/1956/1031
Wed, 28 Jul 2021 22:21:44 GMT2021-07-28T22:21:44ZFinite and Confident Teaching in Expectation: Sampling from Infinite Concept Classes
https://hdl.handle.net/11250/2764704
Finite and Confident Teaching in Expectation: Sampling from Infinite Concept Classes
Hernández-Orallo, José; Telle, Jan Arne
We investigate the teaching of infinite concept classes through the effect of the learning prior (which is used by the learner to derive posteriors giving preference of some concepts over others and by the teacher to devise the teaching examples) and the sampling prior (which determines how the concepts are sampled from the class). We analyse two important classes: Turing machines and finite-state machines. We derive bounds for the teaching dimension when the learning prior is derived from a complexity measure (Kolmogorov complexity and minimal number of states respectively) and analyse the sampling distributions that lead to finite expected teaching dimensions. The learning prior goes beyond a complexity or preference choice when we use it to increase the confidence of identification, expressed as a posterior, which increases as more examples are given. We highlight the existing trade-off between three elements: the bound on teaching dimension, the representativeness of the sample and the certainty of the identification. This has implications for the understanding of what teaching from rich concept classes to machines (and humans) entails.
Wed, 01 Jan 2020 00:00:00 GMThttps://hdl.handle.net/11250/27647042020-01-01T00:00:00ZClose Relatives of Feedback Vertex Set Without Single-Exponential Algorithms Parameterized by Treewidth
https://hdl.handle.net/11250/2764603
Close Relatives of Feedback Vertex Set Without Single-Exponential Algorithms Parameterized by Treewidth
Bergougnoux, Benjamin; Bonnet, Édouard; Brettell, Nick; Kwon, O-Joung
The Cut & Count technique and the rank-based approach have lead to single-exponential FPT algorithms parameterized by treewidth, that is, running in time 2^𝒪(tw)n^𝒪(1), for Feedback Vertex Set and connected versions of the classical graph problems (such as Vertex Cover and Dominating Set). We show that Subset Feedback Vertex Set, Subset Odd Cycle Transversal, Restricted Edge-Subset Feedback Edge Set, Node Multiway Cut, and Multiway Cut are unlikely to have such running times. More precisely, we match algorithms running in time 2^𝒪(tw log tw)n^𝒪(1) with tight lower bounds under the Exponential Time Hypothesis, ruling out 2^o(tw log tw)n^𝒪(1), where n is the number of vertices and tw is the treewidth of the input graph. Our algorithms extend to the weighted case, while our lower bounds also hold for the larger parameter pathwidth and do not require weights. We also show that, in contrast to Odd Cycle Transversal, there is no 2^o(tw log tw)n^𝒪(1)-time algorithm for Even Cycle Transversal.
Wed, 01 Jan 2020 00:00:00 GMThttps://hdl.handle.net/11250/27646032020-01-01T00:00:00ZOn decoding additive generalized twisted Gabidulin codes
https://hdl.handle.net/11250/2764598
On decoding additive generalized twisted Gabidulin codes
Kadir, Wrya; Li, Chunlei
In this paper, we consider an interpolation-based decoding algorithm for a large family of maximum rank distance codes, known as the additive generalized twisted Gabidulin codes, over the finite field Fqn for any prime power q. This paper extends the work of the conference paper Li and Kadir (2019) presented at the International Workshop on Coding and Cryptography 2019, which decoded these codes over finite fields in characteristic two.
Wed, 01 Jan 2020 00:00:00 GMThttps://hdl.handle.net/11250/27645982020-01-01T00:00:00ZMeasures in Visualization Space
https://hdl.handle.net/11250/2764271
Measures in Visualization Space
Bolte, Fabian; Bruckner, Stefan
Measurement is an integral part of modern science, providing the fundamental means for evaluation, comparison, and prediction. In the context of visualization, several different types of measures have been proposed, ranging from approaches that evaluate particular aspects of visualization techniques, their perceptual characteristics, and even economic factors. Furthermore, there are approaches that attempt to provide means for measuring general properties of the visualization process as a whole. Measures can be quantitative or qualitative, and one of the primary goals is to provide objective means for reasoning about visualizations and their effectiveness. As such, they play a central role in the development of scientific theories for visualization. In this chapter, we provide an overview of the current state of the art, survey and classify different types of visualization measures, characterize their strengths and drawbacks, and provide an outline of open challenges for future research.
Postponed access: the file will be available after 2021-08-12
Wed, 01 Jan 2020 00:00:00 GMThttps://hdl.handle.net/11250/27642712020-01-01T00:00:00ZThe directed 2-linkage problem with length constraints
https://hdl.handle.net/11250/2764182
The directed 2-linkage problem with length constraints
Bang-Jensen, J.; Bellitto, Thomas; Lochet, William; Yeo, A.
Postponed access: the file will be available after 2022-01-15
Wed, 01 Jan 2020 00:00:00 GMThttps://hdl.handle.net/11250/27641822020-01-01T00:00:00ZGAPGOM—an R package for gene annotation prediction using GO metrics
https://hdl.handle.net/11250/2764075
GAPGOM—an R package for gene annotation prediction using GO metrics
van Mourik, Casper; Ehsani, Rezvan; Drabløs, Finn
Objective
Properties of gene products can be described or annotated with Gene Ontology (GO) terms. But for many genes we have limited information about their products, for example with respect to function. This is particularly true for long non-coding RNAs (lncRNAs), where the function in most cases is unknown. However, it has been shown that annotation as described by GO terms to some extent can be predicted by enrichment analysis on properties of co-expressed genes.
Results
GAPGOM integrates two relevant algorithms, lncRNA2GOA and TopoICSim, into a user-friendly R package. Here lncRNA2GOA does annotation prediction by co-expression, whereas TopoICSim estimates similarity between GO graphs, which can be used for benchmarking of prediction performance, but also for comparison of GO graphs in general. The package provides an improved implementation of the original tools, with substantial improvements in performance and documentation, unified interfaces, and additional features.
Fri, 01 Jan 2021 00:00:00 GMThttps://hdl.handle.net/11250/27640752021-01-01T00:00:00ZThe differential spectrum of a ternary power mapping
https://hdl.handle.net/11250/2764059
The differential spectrum of a ternary power mapping
Xia, Yongbo; Zhang, Xianglai; Li, Chunlei; Helleseth, Tor
A function f(x)from the finite field GF(pn)to itself is said to be differentially δ-uniform when the maximum number of solutions x ∈GF(pn)of f(x +a) −f(x) =bfor any a ∈GF(pn)∗and b ∈GF(pn)is equal to δ. Let p =3and d =3n−3. When n >1is odd, the power mapping f(x) =xdover GF(3n)was proved to be differentially 2-uniform by Helleseth, Rong and Sandberg in 1999. Fo r even n, they showed that the differential uniformity Δfof f(x)satisfies 1 ≤Δf≤5. In this paper, we present more precise results on the differential property of this power mapping. Fo r d =3n−3with even n >2, we show that the power mapping xdover GF(3n)is differentially 4-uniform when n ≡2 (mod 4) and is differentially 5-uniform when n ≡0 (mod 4). Furthermore, we determine the differential spectrum of xdfor any integer n >1.
Postponed access: the file will be available after 2022-03-06
Wed, 01 Jan 2020 00:00:00 GMThttps://hdl.handle.net/11250/27640592020-01-01T00:00:00ZThe Parameterized Complexity of Guarding Almost Convex Polygons
https://hdl.handle.net/11250/2763994
The Parameterized Complexity of Guarding Almost Convex Polygons
Agrawal, Akanksha; Knudsen, Kristine Vitting Klinkby; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav
The Art Gallery problem is a fundamental visibility problem in Computational Geometry. The input consists of a simple polygon P, (possibly infinite) sets G and C of points within P, and an integer k; the task is to decide if at most k guards can be placed on points in G so that every point in C is visible to at least one guard. In the classic formulation of Art Gallery, G and C consist of all the points within P. Other well-known variants restrict G and C to consist either of all the points on the boundary of P or of all the vertices of P. Recently, three new important discoveries were made: the above mentioned variants of Art Gallery are all W[1]-hard with respect to k [Bonnet and Miltzow, ESA'16], the classic variant has an O(log k)-approximation algorithm [Bonnet and Miltzow, SoCG'17], and it may require irrational guards [Abrahamsen et al., SoCG'17]. Building upon the third result, the classic variant and the case where G consists only of all the points on the boundary of P were both shown to be ∃ℝ-complete [Abrahamsen et al., STOC'18]. Even when both G and C consist only of all the points on the boundary of P, the problem is not known to be in NP. Given the first discovery, the following question was posed by Giannopoulos [Lorentz Center Workshop, 2016]: Is Art Gallery FPT with respect to r, the number of reflex vertices? In light of the developments above, we focus on the variant where G and C consist of all the vertices of P, called Vertex-Vertex Art Gallery. Apart from being a variant of Art Gallery, this case can also be viewed as the classic Dominating Set problem in the visibility graph of a polygon. In this article, we show that the answer to the question by Giannopoulos is positive: Vertex-Vertex Art Gallery is solvable in time r^O(r²)n^O(1). Furthermore, our approach extends to assert that Vertex-Boundary Art Gallery and Boundary-Vertex Art Gallery are both FPT as well. To this end, we utilize structural properties of "almost convex polygons" to present a two-stage reduction from Vertex-Vertex Art Gallery to a new constraint satisfaction problem (whose solution is also provided in this paper) where constraints have arity 2 and involve monotone functions.
Wed, 01 Jan 2020 00:00:00 GMThttps://hdl.handle.net/11250/27639942020-01-01T00:00:00ZA (2 + ε)-Factor Approximation Algorithm for Split Vertex Deletion
https://hdl.handle.net/11250/2763990
A (2 + ε)-Factor Approximation Algorithm for Split Vertex Deletion
Lokshtanov, Daniel; Misra, Pranabendu; Panolan, Fahad; Philip, Geevarghese; Saurabh, Saket
In the Split Vertex Deletion (SVD) problem, the input is an n-vertex undirected graph G and a weight function w: V(G) → ℕ, and the objective is to find a minimum weight subset S of vertices such that G-S is a split graph (i.e., there is bipartition of V(G-S) = C ⊎ I such that C is a clique and I is an independent set in G-S). This problem is a special case of 5-Hitting Set and consequently, there is a simple factor 5-approximation algorithm for this. On the negative side, it is easy to show that the problem does not admit a polynomial time (2-δ)-approximation algorithm, for any fixed δ > 0, unless the Unique Games Conjecture fails. We start by giving a simple quasipolynomial time (n^O(log n)) factor 2-approximation algorithm for SVD using the notion of clique-independent set separating collection. Thus, on the one hand SVD admits a factor 2-approximation in quasipolynomial time, and on the other hand this approximation factor cannot be improved assuming UGC. It naturally leads to the following question: Can SVD be 2-approximated in polynomial time? In this work we almost close this gap and prove that for any ε > 0, there is a n^O(log 1/(ε))-time 2(1+ε)-approximation algorithm.
Wed, 01 Jan 2020 00:00:00 GMThttps://hdl.handle.net/11250/27639902020-01-01T00:00:00ZDevelopment and validation of a universal blood donor genotyping platform: A multinational prospective study
https://hdl.handle.net/11250/2763961
Development and validation of a universal blood donor genotyping platform: A multinational prospective study
Gleadall, Nicholas S.; Veldhuisen, Barbera; Gollub, Jeremy; Butterworth, Adam S.; Ord, John; Penkett, Christopher J.; Timmer, Tiffany C.; Sauer, Carolin M.; Van Der Bolt, Nieke; Brown, Colin; Brügger, Kim; Dilthey, Alexander T.; Duarte, Daniel; Grimsley, Shane; Van Den Hurk, Katja; Jongerius, John M.; Luken, Jessie; Megy, Karyn; Miflin, Gail; Nelson, Christopher S.; Prinsze, Femmeke J.; Sambrook, Jennifer; Simeoni, Ilenia; Sweeting, Michael; Thornton, Nicole; Trompeter, Sara; Tuna, Salih; Varma, Ram; Walker, Matthew R.; Danesh, John; Roberts, David J.; Ouwehand, Willem H.; Stirrups, Kathleen E.; Rendon, Augusto; Westhoff, Connie M.; Di Angelantonio, Emanuele; van der Schoot, C. Ellen; Astle, William J.; Watkins, Nicholas A.; Lane, William J.
Each year, blood transfusions save millions of lives. However, under current blood-matching practices, sensitization to non–self-antigens is an unavoidable adverse side effect of transfusion. We describe a universal donor typing platform that could be adopted by blood services worldwide to facilitate a universal extended blood-matching policy and reduce sensitization rates. This DNA-based test is capable of simultaneously typing most clinically relevant red blood cell (RBC), human platelet (HPA), and human leukocyte (HLA) antigens. Validation was performed, using samples from 7927 European, 27 South Asian, 21 East Asian, and 9 African blood donors enrolled in 2 national biobanks. We illustrated the usefulness of the platform by analyzing antibody data from patients sensitized with multiple RBC alloantibodies. Genotyping results demonstrated concordance of 99.91%, 99.97%, and 99.03% with RBC, HPA, and HLA clinically validated typing results in 89 371, 3016, and 9289 comparisons, respectively. Genotyping increased the total number of antigen typing results available from 110 980 to >1 200 000. Dense donor typing allowed identification of 2 to 6 times more compatible donors to serve 3146 patients with multiple RBC alloantibodies, providing at least 1 match for 176 individuals for whom previously no blood could be found among the same donors. This genotyping technology is already being used to type thousands of donors taking part in national genotyping studies. Extraction of dense antigen-typing data from these cohorts provides blood supply organizations with the opportunity to implement a policy of genomics-based precision matching of blood.
Wed, 01 Jan 2020 00:00:00 GMThttps://hdl.handle.net/11250/27639612020-01-01T00:00:00Z