The thesis is dedicated to the study of two main partial differential equations (PDEs) in fluid dynamics: the Navier-Stokes equations, which describe the motion of incompressible fluids, and the transport equation with divergence-free velocity fields, whic ...
We use results from communication complexity, both new and old ones, to prove lower bounds for unambiguous finite automata (UFAs). We show three results. 1) Complement: There is a language L recognised by an n-state UFA such that the complement language ̅L ...
Schloss Dagstuhl - Leibniz-Zentrum für Informatik2022
We prove that every online learnable class of functions of Littlestone dimension d admits a learning algorithm with finite information complexity. Towards this end, we use the notion of a globally stable algorithm. Generally, the information complexity of ...
Matrix equations of the kind A(1)X(2)+A(0)X+A(-1)=X, where both the matrix coefficients and the unknown are semi-infinite matrices belonging to a Banach algebra, are considered. These equations, where coefficients are quasi-Toeplitz matrices, are encounter ...
Let R be a semilocal principal ideal domain. Two algebraic objects over R in which scalar extension makes sense (e.g. quadratic spaces) are said to be of the same genus if they become isomorphic after extending scalars to all completions of R and its fract ...
We consider a setup in which confidential i.i.d. samples X1, ..., Xn from an unknown discrete distribution PX are passed through a discrete memoryless privatization channel (a.k.a. mechanism) which guarantees an epsilon-level of local differential privacy. ...
Reo is a coordination language that can be used to model different systems. We propose a technique for symbolic execution of Reo circuits using the symbolic representation of data constraints in Constraint Automata. This technique enables us to obtain the ...
In this paper, we investigate the benefits of instruction set extensions (ISEs) on a 16-bit microcontroller architecture for software implementations of cryptographic hash functions, using the example of the five SHA-3 final round candidates. We identify t ...
Recovery of the sparsity pattern (or support) of an unknown sparse vector from a limited number of noisy linear measurements is an important problem in compressed sensing. In the high-dimensional setting, it is known that recovery with a vanishing fraction ...
Institute of Electrical and Electronics Engineers2012
Quantitative generalizations of classical languages, which assign to each word a real number instead of a Boolean value, have applications in modeling resource-constrained computation. We use weighted automata (finite automata with transition weights) to d ...
Weighted automata are nondeterministic automata with numerical weights on transitions. They can define quantitative languages L that assign to each word w a real number L(w). In the case of infinite words, the value of a run is naturally computed as the ma ...
Model checking transactional memories (TMs) is difficult because of the unbounded number, length, and delay of concurrent transactions, as well as the unbounded size of the memory. We show that, under certain conditions satisfied by most TMs we know of, th ...
The impossibility of reaching deterministic consensus in an asynchronous and crash prone system was established for a weak variant of the problem, usually called weak consensus, where a set of processes need to decide on a common value in {0, 1}, so that b ...
A temporal interface for a software component is a finite automaton that specifies the legal sequences of calls to functions that are provided by the component. We compare and evaluate three different algorithms for automatically extracting temporal interfac ...
A lot of work exists on notions of equivalence and soundness relations of different workflow models, which are used in different domains like e.g. Business Process Modeling, Software and Service Engineering. These definitions are based on different models, ...
