Search

Software systems rely on events for logging, coordination, handling unusual situations, and more. Monitoring event streams from systems that provide services can ensure the service complies with policies, regulations, and other business rules. Notably, monitoring to detect violations of rules as early as possible is much desired as, for example, the service may reclaim more resources from erring enactments. The primary goal of this paper is to develop techniques for detecting violations of time constraints as early as possible. We formalize a model for events and a language to specify constraints on event timing and data. We develop algorithms to detect violations of individual rules, then use a chase process to detect violations of acyclic sets of rules. We also present optimization techniques to reduce monitoring overhead. Finally, we implement and evaluate our algorithms through experiments to demonstrate our approach is feasible and beneficial. [ABSTRACT FROM AUTHOR]

In this paper, we prove that the general CNF satisfiability problem can be solved in O ⁎ (1.0638 L) time, where L is the length of the input CNF-formula (i.e., the total number of literals in the formula), which improves the previous result of O ⁎ (1.0652 L) obtained in 2009. Our algorithm was analyzed by using the measure-and-conquer method. Our improvements are mainly attributed to the following two points: we carefully design branching rules to deal with degree-5 and degree-4 variables to avoid previous bottlenecks; we show that some worst cases will not always happen, and then we can use an amortized technique to get further improvements. In our analyses, we provide some general frameworks for analysis and several lower bounds on the decreasing of the measure to simplify the arguments. These techniques may be used to analyze more algorithms based on the measure-and-conquer method. [ABSTRACT FROM AUTHOR]

A Simple Temporal Network with Uncertainty (STNU) is a data structure for reasoning about time constraints on actions that may have uncertain durations. An STNU is dispatchable if it can be executed in real-time with minimal computation 1) satisfying all constraints no matter how the uncertain durations play out and 2) retaining maximum flexibility. The fastest known algorithm for converting STNUs into dispatchable form runs in O (n 3) time, where n is the number of timepoints. This paper presents a faster algorithm that runs in O (m n + k n 2 + n 2 log ⁡ n) time, where m is the number of edges and k is the number of uncertain durations. This performance is particularly meaningful in fields like Business Process Management, where sparse STNUs can represent temporal processes or plans. For sparse STNUs, our algorithm generates dispatchable forms in time O (n 2 log ⁡ n) , a significant improvement over the O (n 3) -time previous fastest algorithm. [ABSTRACT FROM AUTHOR]

The best lattice reduction algorithm known in theory for approximating the Shortest Vector Problem (SVP) over lattices is the slide reduction algorithm (STOC '08 & CRYPTO '20). In this paper, we first improve the running time analysis of computing slide-reduced bases based on potential functions. This analysis applies to a generic slide reduction algorithm that includes (natural variants of) slide reduction and block-Rankin reduction (ANTS '14). We then present a rigorous dynamic analysis of generic slide reduction using techniques originally applied to a variant of BKZ (CRYPTO '11). This provides guarantees on the quality of the current lattice basis during execution. This dynamic analysis not only implies sharper convergence for these algorithms to find a short nonzero vector (rather than a fully reduced basis), but also allows to heuristically model/trace the practical behaviour of slide reduction. Interestingly, this dynamic analysis inspires us to introduce a new slide reduction variant with better time/quality trade-offs. This is confirmed by both our experiments and simulation, which also show that our variant is competitive with state-of-the-art reduction algorithms. To the best of our knowledge, this work is the first attempt of improving the practical performance of slide reduction beyond speeding up the SVP oracle. [ABSTRACT FROM AUTHOR]

Simple stochastic games are turn-based 2½-player zero-sum graph games with a reachability objective. The problem is to compute the winning probabilities as well as the optimal strategies of both players. In this paper, we compare the three known classes of algorithms – value iteration, strategy iteration and quadratic programming – both theoretically and practically. Further, we suggest several improvements for all algorithms, including the first approach based on quadratic programming that avoids transforming the stochastic game to a stopping one. Our extensive experiments show that these improvements can lead to significant speed-ups. We implemented all algorithms in PRISM-games 3.0, thereby providing the first implementation of quadratic programming for solving simple stochastic games. [ABSTRACT FROM AUTHOR]

Simple stochastic games are turn-based 2½-player zero-sum graph games with a reachability objective. The problem is to compute the winning probabilities as well as the optimal strategies of both players. In this paper, we compare the three known classes of algorithms – value iteration, strategy iteration and quadratic programming – both theoretically and practically. Further, we suggest several improvements for all algorithms, including the first approach based on quadratic programming that avoids transforming the stochastic game to a stopping one. Our extensive experiments show that these improvements can lead to significant speed-ups. We implemented all algorithms in PRISM-games 3.0, thereby providing the first implementation of quadratic programming for solving simple stochastic games. [ABSTRACT FROM AUTHOR]

Branching Algebra is the natural branching-time generalization of Allen's Interval Algebra. As in the linear case, the consistency problem for Branching Algebra is NP-hard. Branching Algebra has many potential applications in different areas of Artificial Intelligence; therefore, being able to efficiently solve classical problems expressed in Branching Algebra is very important. This can be achieved in two steps: first, by identifying expressive enough, yet tractable fragments of the whole algebra, and, second, by using such fragments to boost the performances of a backtracking algorithm for the whole language. In this paper we study the properties of several such fragments, both from the algebraic and the computational point of view, and we give an almost complete picture of tractable and non-tractable fragments of the Branching Algebra. [ABSTRACT FROM AUTHOR]

Simon's problem plays an important role in the history of quantum algorithms, as it inspired Shor to discover the celebrated quantum algorithm solving integer factorization in polynomial time. Besides, the quantum algorithm for Simon's problem has been recently applied to break symmetric cryptosystems. Generalized Simon's problem, denoted by GSP (p , n , k) , is a natural extension of Simon's problem: Given a function f : Z p n → X where X is a finite set and the promise that for any x , y ∈ Z p n , f (x) = f (y) iff x − y ∈ S for a subgroup S ≤ Z p n of rank k < n , the goal is to find S. In this paper we consider the query complexity of the problem, that is, the minimum number of queries to f required to find S. First, it is not difficult to design a quantum algorithm solving the above problem with query complexity of O (n − k). However, so far it is not clear what is the classical query complexity of the problem, and revealing this complexity is necessary for clarifying the computational power gap between quantum and classical computing on the problem. To tackle this problem, we prove that any classical (deterministic or randomized) algorithm for GSP (p , n , k) has to query at least Ω (max ⁡ { k , p n − k }) values and any classical nonadaptive deterministic algorithm for GSP (p , n , k) has to query at least Ω (max ⁡ { k , k ⋅ p n − k }) values. Hence, we clearly show the classical computing model is less powerful than the quantum counterpart, in terms of query complexity for the generalized Simon's problem. Moreover, we obtain an upper bound O (max ⁡ { k , k ⋅ p n − k }) on the classical deterministic query complexity of GSP (p , n , k) , by devising a subtle classical algorithm based on group theory and the divide-and-conquer approach. Therefore, we have an almost full characterization of the classical deterministic query complexity of the generalized Simon's problem. [ABSTRACT FROM AUTHOR]

New post-quantum Key Encapsulation Mechanism (KEM) designs, evaluated as part of the NIST PQC standardization Project, pose challenging tradeoffs between communication bandwidth and computational overheads. Several KEM designs evaluated in Round-2 of the project are based on QC-MDPC codes. BIKE-2 uses the smallest communication bandwidth, but its key generation requires a costly polynomial inversion. In this paper, we provide details on the optimized polynomial inversion algorithm for QC-MDPC codes (originally proposed in the conference version of this work). This algorithm makes the runtime of BIKE-2 key generation tolerable. It brings a speedup of 11.4× over the commonly used NTL library, and 83.5× over OpenSSL. We achieve additional speedups by leveraging the latest Intel's Vector-PCLMULQDQ instructions, 14.3× over NTL and 103.9× over OpenSSL. Our algorithm and implementation were the reason that BIKE team chose BIKE-2 as the only scheme for its Round-3 specification (now called BIKE). [ABSTRACT FROM AUTHOR]

A real number x is absolutely normal if, for every base b ≥ 2 , every two equally long strings of digits appear with equal asymptotic frequency in the base- b expansion of x. This paper presents an explicit algorithm that generates the binary expansion of an absolutely normal number x , with the n th bit of x appearing after n polylog (n) computation steps. This speed is achieved by simultaneously computing and diagonalizing against a martingale that incorporates Lempel-Ziv parsing algorithms in all bases. [ABSTRACT FROM AUTHOR]

In this paper, we propose a novel algorithm to learn a Büchi automaton from a teacher who knows an ω -regular language. The learned Büchi automaton can be a nondeterministic Büchi automaton or a limit deterministic Büchi automaton. The learning algorithm is based on learning a formalism called family of DFAs (FDFAs) recently proposed by Angluin and Fisman. The main catch is that we use a classification tree structure instead of the standard observation table structure. The worst case storage space required by our algorithm is quadratically better than that required by the table-based algorithm proposed by Angluin and Fisman. We implement the proposed learning algorithms in the learning library ROLL (Regular Omega Language Learning), which also consists of other complete ω -regular learning algorithms available in the literature. Experimental results show that our tree-based learning algorithms have the best performance among others regarding the number of solved learning tasks. [ABSTRACT FROM AUTHOR]

Model checking (MC) for Halpern and Shoham's interval temporal logic HS has been recently shown to be decidable. An intriguing open question is its exact complexity for full HS : it is at least EXPSPACE -hard, and the only known upper bound, which exploits an abstract representation of Kripke structure paths (descriptor), is non-elementary. In this paper, we provide a uniform framework to MC for full HS and meaningful fragments of it, with a specific type of descriptor for each fragment. Then, we devise a general MC alternating algorithm, parameterized by the descriptor's type, which has a polynomially bounded number of alternations and whose running time is bounded by the length of minimal representatives of descriptors (certificates). We analyze its complexity and give tight bounds on the length of certificates. For two types of descriptor, we obtain exponential upper and lower bounds; for the other ones, we provide non-elementary lower bounds. [ABSTRACT FROM AUTHOR]

A Simple Temporal Network (STN) consists of time points modeling temporal events and constraints modeling the minimal and maximal temporal distance between them. A Simple Temporal Network with Decisions (STND) extends an STN to model temporal plans with decisions. STNDs label time points and constraints by conjunctions of literals saying for which scenarios (i.e., complete truth value assignments to the propositions) they are relevant. In this paper, we deal with the use of STNDs for modeling and synthesizing execution strategies. We propose an incremental hybrid SAT-based consistency checking algorithm for STNDs that is faster than the one previously proposed and allows for the synthesis of all consistent scenarios and related early execution schedules (offline temporal planning). We carry out an experimental evaluation with Kappa, a tool that we developed for STNDs. We also show that any STND can be easily translated into a disjunctive temporal network and vice versa. [ABSTRACT FROM AUTHOR]

A variant of adaptive arithmetic coding is proposed, adding cryptographic features to this classical compression method. The idea is to perform the updates of the frequency tables for characters of the underlying alphabet selectively, according to some randomly chosen secret key K. We give empirical evidence that with reasonably chosen parameters, the compression performance is not hurt, and discuss also aspects of how to improve the security of the system being used as an encryption method. To keep the paper self-contained, we add a short description of the arithmetic coding algorithm that is necessary to understand the details of the new suggested method. [ABSTRACT FROM AUTHOR]