Browsing Department of Informatics by Title
Now showing items 579-598 of 915
-
On the Complexity of Intersection Non-emptiness for Star-Free Language Classes
(Journal article; Peer reviewed, 2021)In the Intersection Non-emptiness problem, we are given a list of finite automata A_1, A_2,… , A_m over a common alphabet Σ as input, and the goal is to determine whether some string w ∈ Σ^* lies in the intersection of the ... -
On the Complexity of Recovering Incidence Matrices
(Journal article; Peer reviewed, 2020)The incidence matrix of a graph is a fundamental object naturally appearing in many applications, involving graphs such as social networks, communication networks, or transportation networks. Often, the data collected about ... -
On the Distance Between APN Functions
(Journal article; Peer reviewed, 2020)We investigate the differential properties of a vectorial Boolean function G obtained by modifying an APN function F . This generalizes previous constructions where a function is modified at a few points. We characterize ... -
On the EA-classes of known APN functions in small dimensions
(Journal article; Peer reviewed, 2020)Recently Budaghyan et al. (Cryptogr. Commun. 12, 85–100, 2020) introduced a procedure for investigating if CCZ-equivalence can be more general than EA-equivalence together with inverse transformation (when applicable). In ... -
On the effectiveness of the incremental approach to minimal chordal edge modification
(Journal article; Peer reviewed, 2021)Because edge modification problems are computationally difficult for most target graph classes, considerable attention has been devoted to inclusion-minimal edge modifications, which are usually polynomial-time computable ... -
On the feasibility of distributed systems for interactive visual analysis of omics data
(Master thesis, 2014-06-02)The purpose of this thesis is to discuss the feasibility of developing a distributed interactive visual analysis omics system demonstrating how selected modules from the standalone J-Express Modularized application can be ... -
On the Hardness of Generalized Domination Problems Parameterized by Mim-Width
(Journal article; Peer reviewed, 2022)For nonempty σ, ρ ⊆ ℕ, a vertex set S in a graph G is a (σ, ρ)-dominating set if for all v ∈ S, |N(v) ∩ S| ∈ σ, and for all v ∈ V(G) ⧵ S, |N(v) ∩ S| ∈ ρ. The Min/Max (σ,ρ)-Dominating Set problems ask, given a graph G and ... -
On the IND-CCA1 Security of FHE Schemes
(Journal article; Peer reviewed, 2022)Fully homomorphic encryption (FHE) is a powerful tool in cryptography that allows one to perform arbitrary computations on encrypted material without having to decrypt it first. There are numerous FHE schemes, all of which ... -
On the maximum number of edges in planar graphs of bounded degree and matching number
(Journal article; Peer reviewed, 2023)We determine the maximum number of edges that a planar graph can have as a function of its maximum degree and matching number. -
On the parameterized complexity of deletion to H-free strong components
(Journal article; Peer reviewed, 2020)Directed Feedback Vertex Set (DFVS) is a fundamental computational problem that has received extensive attention in parameterized complexity. In this paper, we initiate the study of a wide generalization, the H-SCC Deletion ... -
On the Parameterized Complexity of the Expected Coverage Problem
(Journal article; Peer reviewed, 2022)The MAXIMUM COVERING LOCATION PROBLEM (MCLP) is a well-studied problem in the field of operations research. Given a network with positive or negative demands on the nodes, a positive integer k, the MCLP seeks to find k ... -
On the Privacy of Two Tag Ownership Transfer Protocols for RFIDs
(Chapter, 2011)In this paper, the privacy of two recent RFID tag ownership transfer protocols are investigated against the tag owners as adversaries. The first protocol called ROTIV is a scheme which provides a privacy-preserving ownership ... -
On the Satisfiability of Smooth Grid CSPs
(Journal article; Peer reviewed, 2022)Many important NP-hard problems, arising in a wide variety of contexts, can be reduced straightforwardly to the satisfiability problem for CSPs whose underlying graph is a grid. In this work, we push forward the study of ... -
On the Security of Non-Linear HB (NLHB) Protocol Against Passive Attack
(Conference lecture, 2012)As a variant of the HB authentication protocol for RFID systems, which relies on the complexity of decoding linear codes against passive attacks, Madhavan et al. presented Non-Linear HB(NLHB) protocol. In contrast to HB, ... -
On the Significance of Distance in Machine Learning
(Doctoral thesis, 2023-10-23)Avstandsbegrepet er grunnleggende i maskinlæring. Hvordan vi velger å måle avstand har betydning, men det er ofte utfordrende å finne et passende avstandsmål. Metrisk læring kan brukes til å lære funksjoner som implementerer ... -
On the Sombor characteristic polynomial and Sombor energy of a graph
(Journal article; Peer reviewed, 2022)Let G be a simple graph with vertex set V(G)={v1,v2,…,vn}. The Sombor matrix of G, denoted by ASO(G), is defined as the n×n matrix whose (i, j)-entry is d2i+d2j−−−−−−√ if vi and vj are adjacent and 0 for another cases. Let ... -
On the strong dominating sets of graphs
(Journal article, 2023) -
On the Tractability of Optimization Problems on H-Graphs
(Journal article; Peer reviewed, 2020)For a graph H, a graph G is an H-graph if it is an intersection graph of connected subgraphs of some subdivision of H. H-graphs naturally generalize several important graph classes like interval graphs or circular-arc ... -
On Two Fundamental Problems on APN Power Functions
(Journal article; Peer reviewed, 2022)The six infinite families of power APN functions are among the oldest known instances of APN functions, and it has been conjectured in 2000 that they exhaust all possible power APN functions. Another long-standing open ... -
On width measures and topological problems on semi-complete digraphs
(Peer reviewed; Journal article, 2019)The topological theory for semi-complete digraphs, pioneered by Chudnovsky, Fradkin, Kim, Scott, and Seymour [10], [11], [12], [28], [43], [39], concentrates on the interplay between the most important width measures — ...