Department of Informatics
https://hdl.handle.net/1956/1031
Sun, 22 May 2022 16:20:50 GMT2022-05-22T16:20:50ZOrder-Related Problems Parameterized by Width
https://hdl.handle.net/11250/2995719
Order-Related Problems Parameterized by Width
Arrighi, Emmanuel
In the main body of this thesis, we study two different order theoretic problems. The first problem, called Completion of an Ordering, asks to extend a given finite partial order to a complete linear order while respecting some weight constraints. The second problem is an order reconfiguration problem under width constraints.
While the Completion of an Ordering problem is NP-complete, we show that it lies in FPT when parameterized by the interval width of ρ. This ordering problem can be used to model several ordering problems stemming from diverse application areas, such as graph drawing, computational social choice, and computer memory management. Each application yields a special partial order ρ. We also relate the interval width of ρ to parameterizations for these problems that have been studied earlier in the context of these applications, sometimes improving on parameterized algorithms that have been developed for these parameterizations before. This approach also gives some practical sub-exponential time algorithms for ordering problems.
In our second main result, we combine our parameterized approach with the paradigm of solution diversity. The idea of solution diversity is that instead of aiming at the development of algorithms that output a single optimal solution, the goal is to investigate algorithms that output a small set of sufficiently good solutions that are sufficiently diverse from one another. In this way, the user has the opportunity to choose the solution that is most appropriate to the context at hand. It also displays the richness of the solution space. There, we show that the considered diversity version of the Completion of an Ordering problem is fixed-parameter tractable with respect to natural paramaters that capture the notion of diversity and the notion of sufficiently good solutions. We apply this algorithm in the study of the Kemeny Rank Aggregation class of problems, a well-studied class of problems lying in the intersection of order theory and social choice theory.
Up to this point, we have been looking at problems where the goal is to find an optimal solution or a diverse set of good solutions. In the last part, we shift our focus from finding solutions to studying the solution space of a problem. There we consider the following order reconfiguration problem: Given a graph G together with linear orders τ and τ ′ of the vertices of G, can one transform τ into τ ′ by a sequence of swaps of adjacent elements in such a way that at each time step the resulting linear order has cutwidth (pathwidth) at most w? We show that this problem always has an affirmative answer when the input linear orders τ and τ ′ have cutwidth (pathwidth) at most w/2. Using this result, we establish a connection between two apparently unrelated problems: the reachability problem for two-letter string rewriting systems and the graph isomorphism problem for graphs of bounded cutwidth. This opens an avenue for the study of the famous graph isomorphism problem using techniques from term rewriting theory.
In addition to the main part of this work, we present results on two unrelated problems, namely on the Steiner Tree problem and on the Intersection Non-emptiness problem from automata theory.
Wed, 25 May 2022 00:00:00 GMThttps://hdl.handle.net/11250/29957192022-05-25T00:00:00ZTowards a Spreadsheet-Based Language Workbench
https://hdl.handle.net/11250/2993194
Towards a Spreadsheet-Based Language Workbench
Barash, Mikhail
Spreadsheets are widely used across industries for various purposes, including for storing and manipulating data in a structured form. Such structured forms—expressed using tabular notation—have found their way in language workbenches, which are tools to define (domain-specific modeling) languages and Integrated Development Environments (IDE) for them. There, a tabular notation is oftentimes used as a secondary way to represent concrete syntax of certain language constructs; however, it is not a primary means for (meta)model definition. We present early results on implementing a language workbench where metamodels, models, and editor services are defined only using a tabular notation. We give an overview of the desired functionality of spreadsheet-based language workbenches.
Fri, 01 Jan 2021 00:00:00 GMThttps://hdl.handle.net/11250/29931942021-01-01T00:00:00ZThe salmon louse genome may be much larger than sequencing suggests
https://hdl.handle.net/11250/2993050
The salmon louse genome may be much larger than sequencing suggests
Wyngaard, Grace; Skern-Mauritzen, Rasmus; Malde, Ketil; Prendergast, Rachel; Peruzzi, Stefano
The genome size of organisms impacts their evolution and biology and is often assumed to be characteristic of a species. Here we present the first published estimates of genome size of the ecologically and economically important ectoparasite, Lepeophtheirus salmonis (Copepoda, Caligidae). Four independent L. salmonis genome assemblies of the North Atlantic subspecies Lepeophtheirus salmonis salmonis, including two chromosome level assemblies, yield assemblies ranging from 665 to 790 Mbps. These genome assemblies are congruent in their findings, and appear very complete with Benchmarking Universal Single-Copy Orthologs analyses finding > 92% of expected genes and transcriptome datasets routinely mapping > 90% of reads. However, two cytometric techniques, flow cytometry and Feulgen image analysis densitometry, yield measurements of 1.3–1.6 Gb in the haploid genome. Interestingly, earlier cytometric measurements reported genome sizes of 939 and 567 Mbps in L. salmonis salmonis samples from Bay of Fundy and Norway, respectively. Available data thus suggest that the genome sizes of salmon lice are variable. Current understanding of eukaryotic genome dynamics suggests that the most likely explanation for such variability involves repetitive DNA, which for L. salmonis makes up ≈ 60% of the genome assemblies.
Sat, 01 Jan 2022 00:00:00 GMThttps://hdl.handle.net/11250/29930502022-01-01T00:00:00ZOn the IND-CCA1 Security of FHE Schemes
https://hdl.handle.net/11250/2992810
On the IND-CCA1 Security of FHE Schemes
Hovd, Martha Norberg; Fauzi, Prastudy; Raddum, Håvard
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 are expanded from somewhat homomorphic encryption (SHE) schemes, and some of which are considered viable in practice. However, while these FHE schemes are semantically (IND-CPA) secure, the question of their IND-CCA1 security is much less studied, and we therefore provide an overview of the IND-CCA1 security of all acknowledged FHE schemes in this paper. To give this overview, we grouped the SHE schemes into broad categories based on their similarities and underlying hardness problems. For each category, we show that the SHE schemes are susceptible to either known adaptive key recovery attacks, a natural extension of known attacks, or our proposed attacks. Finally, we discuss the known techniques to achieve IND-CCA1-secure FHE and SHE schemes. We concluded that none of the proposed schemes were IND-CCA1-secure and that the known general constructions all had their shortcomings.
Sat, 01 Jan 2022 00:00:00 GMThttps://hdl.handle.net/11250/29928102022-01-01T00:00:00ZOn Supergraphs Satisfying CMSO Properties
https://hdl.handle.net/11250/2992661
On Supergraphs Satisfying CMSO Properties
Oliveira, Mateus De Oliveira
Let CMSO denote the counting monadic second order logic of graphs. We give a constructive proof that for some computable function f, there is an algorithm A that takes as input a CMSO sentence φ, a positive integer t, and a connected graph G of maximum degree at most Δ, and determines, in time f(|φ|,t)⋅2O(Δ⋅t)⋅|G|O(t), whether G has a supergraph G′ of treewidth at most t such that G′⊨φ. The algorithmic metatheorem described above sheds new light on certain unresolved questions within the framework of graph completion algorithms. In particular, using this metatheorem, we provide an explicit algorithm that determines, in time f(d)⋅2O(Δ⋅d)⋅|G|O(d), whether a connected graph of maximum degree Δ has a planar supergraph of diameter at most d. Additionally, we show that for each fixed k, the problem of determining whether G has an k-outerplanar supergraph of diameter at most d is strongly uniformly fixed parameter tractable with respect to the parameter d. This result can be generalized in two directions. First, the diameter parameter can be replaced by any contraction-closed effectively CMSO-definable parameter p. Examples of such parameters are vertex-cover number, dominating number, and many other contraction-bidimensional parameters. In the second direction, the planarity requirement can be relaxed to bounded genus, and more generally, to bounded local treewidth.
Fri, 01 Jan 2021 00:00:00 GMThttps://hdl.handle.net/11250/29926612021-01-01T00:00:00ZUnitary Branching Programs: Learnability and Lower Bounds
https://hdl.handle.net/11250/2992660
Unitary Branching Programs: Learnability and Lower Bounds
Diaz Andino, Fidel Ernesto; Kokkou, Maria; Oliveira, Mateus De Oliveira; Vadiee, Farhad
Bounded width branching programs are a formalism that can be used to capture the notion of non-uniform constant-space computation. In this work, we study a generalized version of bounded width branching programs where instructions are defined by unitary matrices of bounded dimension. We introduce a new learning framework for these branching programs that leverages on a combination of local search techniques with gradient descent over Riemannian manifolds. We also show that gapped, read-once branching programs of bounded dimension can be learned with a polynomial number of queries in the presence of a teacher. Finally, we provide explicit near-quadratic size lower-bounds for bounded-dimension unitary branching programs, and exponential size lower-bounds for bounded-dimension read-once gapped unitary branching programs. The first lower bound is proven using a combination of Neciporuk’s lower bound technique with classic results from algebraic geometry. The second lower bound is proven within the framework of communication complexity theory.
Fri, 01 Jan 2021 00:00:00 GMThttps://hdl.handle.net/11250/29926602021-01-01T00:00:00ZOn Neural Associative Memory Structures: Storage and Retrieval of Sequences in a Chain of Tournaments
https://hdl.handle.net/11250/2992618
On Neural Associative Memory Structures: Storage and Retrieval of Sequences in a Chain of Tournaments
Abolpour Mofrad, Asieh; Abolpour Mofrad, Samaneh; Yazidi, Anis; Parker, Matthew Geoffrey
Associative memories enjoy many interesting properties in terms of error correction capabilities, robustness to noise, storage capacity, and retrieval performance, and their usage spans over a large set of applications. In this letter, we investigate and extend tournament-based neural networks, originally proposed by Jiang, Gripon, Berrou, and Rabbat (2016), a novel sequence storage associative memory architecture with high memory efficiency and accurate sequence retrieval. We propose a more general method for learning the sequences, which we call feedback tournament-based neural networks. The retrieval process is also extended to both directions: forward and backward—in other words, any large-enough segment of a sequence can produce the whole sequence. Furthermore, two retrieval algorithms, cache-winner and explore-winner, are introduced to increase the retrieval performance. Through simulation results, we shed light on the strengths and weaknesses of each algorithm.
Fri, 01 Jan 2021 00:00:00 GMThttps://hdl.handle.net/11250/29926182021-01-01T00:00:00ZBounds on the nonlinearity of differentially uniform functions by means of their image set size, and on their distance to affine functions
https://hdl.handle.net/11250/2992397
Bounds on the nonlinearity of differentially uniform functions by means of their image set size, and on their distance to affine functions
Carlet, Claude Michael
We revisit and take a closer look at a (not so well known) result of a 2017 paper, showing that the differential uniformity of any vectorial function is bounded from below by an expression depending on the size of its image set. We make explicit the resulting tight lower bound on the image set size of differentially δ -uniform functions (which is the only currently known non-trivial lower bound on the image set size of such functions). We also significantly improve an upper bound on the nonlinearity of vectorial functions obtained in the same reference and involving their image set size. We study when the resulting bound is sharper than the covering radius bound. We obtain as a by-product a lower bound on the Hamming distance between differentially δ -uniform functions and affine functions, which we improve significantly with a second bound. This leads us to study what can be the maximum Hamming distance between vectorial functions and affine functions. We provide an upper bound which is slightly sharper than a bound by Liu, Mesnager and Chen when m<n , and a second upper bound, which is much stronger in the case (happening in practice) where m is near n ; we study the tightness of this latter bound; this leads to an interesting question on APN functions, which we address (negatively). We finally derive an upper bound on the nonlinearity of vectorial functions by means of their Hamming distance to affine functions and make more precise the bound on the differential uniformity which was the starting point of the paper.
Fri, 01 Jan 2021 00:00:00 GMThttps://hdl.handle.net/11250/29923972021-01-01T00:00:00ZParameterized Complexity of Directed Spanner Problems
https://hdl.handle.net/11250/2992164
Parameterized Complexity of Directed Spanner Problems
Fomin, Fedor; Golovach, Petr; Lochet, William Alexandre; Misra, Pranabendu; Saurabh, Saket; Sharma, Roohani
We initiate the parameterized complexity study of minimum t-spanner problems on directed graphs. For a positive integer t, a multiplicative t-spanner of a (directed) graph G is a spanning subgraph H such that the distance between any two vertices in H is at most t times the distance between these vertices in G, that is, H keeps the distances in G up to the distortion (or stretch) factor t. An additive t-spanner is defined as a spanning subgraph that keeps the distances up to the additive distortion parameter t, that is, the distances in H and G differ by at most t. The task of Directed Multiplicative Spanner is, given a directed graph G with m arcs and positive integers t and k, decide whether G has a multiplicative t-spanner with at most \(m-k\) arcs. Similarly, Directed Additive Spanner asks whether G has an additive t-spanner with at most \(m-k\) arcs. We show that (i) Directed Multiplicative Spanner admits a polynomial kernel of size \(\mathcal {O}(k^4t^5)\) and can be solved in randomized \((4t)^k\cdot n^{\mathcal {O}(1)}\) time, (ii) the weighted variant of Directed Multiplicative Spanner can be solved in \(k^{2k}\cdot n^{\mathcal {O}(1)}\) time on directed acyclic graphs, (iii) Directed Additive Spanner is \({{\,\mathrm{\mathsf{W}}\,}}[1]\)-hard when parameterized by k for every fixed \(t\ge 1\) even when the input graphs are restricted to be directed acyclic graphs. The latter claim contrasts with the recent result of Kobayashi from STACS 2020 that the problem for undirected graphs is \({{\,\mathrm{\mathsf{FPT}}\,}}\) when parameterized by t and k.
Fri, 01 Jan 2021 00:00:00 GMThttps://hdl.handle.net/11250/29921642021-01-01T00:00:00ZDimLift: Interactive Hierarchical Data Exploration through Dimensional Bundling
https://hdl.handle.net/11250/2992003
DimLift: Interactive Hierarchical Data Exploration through Dimensional Bundling
Garrison, Laura Ann; Müller, Juliane; Schreiber, Stefanie; Oeltze-Jafra, Steffen; Hauser, Helwig; Bruckner, Stefan
The identification of interesting patterns and relationships is essential to exploratory data analysis. This becomes increasingly difficult in high dimensional datasets. While dimensionality reduction techniques can be utilized to reduce the analysis space, these may unintentionally bury key dimensions within a larger grouping and obfuscate meaningful patterns. With this work we introduce DimLift , a novel visual analysis method for creating and interacting with dimensional bundles . Generated through an iterative dimensionality reduction or user-driven approach, dimensional bundles are expressive groups of dimensions that contribute similarly to the variance of a dataset. Interactive exploration and reconstruction methods via a layered parallel coordinates plot allow users to lift interesting and subtle relationships to the surface, even in complex scenarios of missing and mixed data types. We exemplify the power of this technique in an expert case study on clinical cohort data alongside two additional case examples from nutrition and ecology.
Fri, 01 Jan 2021 00:00:00 GMThttps://hdl.handle.net/11250/29920032021-01-01T00:00:00Z