A motif is a frequently occurring subgraph of a given directed or undirected graph G (Milo et al.). Motifs capture higher order organizational structure of G beyond edge relationships, and, therefore, have found wide applications such as in graph clusterin ...
We propose a new approach for normalization and simplification of logical formulas. Our approach is based on algorithms for lattice-like structures. Specifically, we present two efficient algorithms for computing a normal form and deciding the word problem ...
We solve the Bin Packing problem in O^*(2^k) time, where k is the number of items less or equal to one third of the bin capacity. This parameter measures the distance from the polynomially solvable case of only large (i.e., greater than one third) items. O ...
Schloss Dagstuhl – Leibniz-Zentrum fur Informatik2022
We show that a constant factor approximation of the shortest and closest lattice vector problem in any l(p)-norm can be computed in time 2((0.802 + epsilon)n). This matches the currently fastest constant factor approximation algorithm for the shortest vect ...
Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs in these classes have hyperfinite decompositions, where, one removes a small ...
We present a quasilinear time algorithm to decide the word problem on a natural algebraic structures we call orthocomplemented bisemilattices, a subtheory of boolean algebra. We use as a base a variation of Hopcroft, Ullman and Aho algorithm for tree isomo ...
With the increasing prevalence of massive datasets, it becomes important to design algorithmic techniques for dealing with scenarios where the input to be processed does not fit in the memory of a single machine. Many highly successful approaches have emer ...
The goal of this thesis is to study continuous-domain inverse problems for the reconstruction of sparse signals and to develop efficient algorithms to solve such problems computationally. The task is to recover a signal of interest as a continuous function ...
In this thesis we propose and analyze algorithms for some numerical linear algebra tasks: finding low-rank approximations of matrices, computing matrix functions, and estimating the trace of matrices.In the first part, we consider algorithms for building ...
As historical stone masonry structures are vulnerable and prone to damage in earthquakes, investigating their structural integrity is important to reduce injuries and casualties while preserving their historical value. Stone masonry is a composite material ...
