Search

Many concepts discussed in this section are diagram dependent. This is discussed in detail in G. Czedli and G. Gratzer [33], a chapter in LTS1.

A lockdown was ordered in Spain on March 2020 due to the COVID-19 pandemic. The first author, advised by the second author, developed a tale and video (in Spanish) with a simplified explanation of virus propagation for their teenager son, justifying the need to stay at home. The tale and video relate the spread of the virus to fractal trees and aim to raise awareness about the transmission of the disease. The video is available from the web page of the Instituto de Matematica Interdisciplinar of the first author’s university. The code was implemented in Scratch 3 and takes advantage of the “Turtle Geometry” (there is an ulterior version using Maple, available from Mapleprimes). This article includes the English version of the original tale, describes the Scratch 3 code, and details possible derived STEM activities. We plan to experiment them in the classroom during the 2020–2021 academic year.

International audience; We prove that the product version of the 1-2-3 Conjecture, raised by Skowronek-Kaziów in 2012, is true. Namely, for every connected graph with order at least 3, we prove that we can assign labels 1,2,3 to the edges in such a way that no two adjacent vertices are incident to the same product of labels.

International audience; We extend the existing encoding of abstract argumentation frameworks in DL-PA (Dynamic Logic of Propositional Assignments) in order to capture different formalisms for arguing with qualitative forms of uncertainty. More in particular, we encode the main reasoning tasks of (rich) incomplete argumentation frameworks and control argumentation frameworks. After that, and inspired by our encoding, we define and study a new class of structures that are shown to be maximally expressive: constrained incomplete argumentation frameworks.

In the literature on Kleene algebra, a number of variants have been proposed which impose additional structure specified by a theory, such as Kleene algebra with tests (KAT) and the recent Kleene algebra with observations (KAO), or make specific assumptions about certain constants, as for instance in NetKAT. Many of these variants fit within the unifying perspective offered by Kleene algebra with hypotheses, which comes with a canonical language model constructed from a given set of hypotheses. For the case of KAT, this model corresponds to the familiar interpretation of expressions as languages of guarded strings. A relevant question therefore is whether Kleene algebra together with a given set of hypotheses is complete with respect to its canonical language model. In this paper, we revisit, combine and extend existing results on this question to obtain tools for proving completeness in a modular way. We showcase these tools by giving new and modular proofs of completeness for KAT, KAO and NetKAT, and we prove completeness for new variants of KAT: KAT extended with a constant for the full relation, KAT extended with a converse operation, and a version of KAT where the collection of tests only forms a distributive lattice.

The Classic McEliece cryptosystem is one of the most trusted quantum-resistant cryptographic schemes. Deploying it in practical applications, however, is challenging due to the size of its public key. In this work, we bridge this gap. We present an implementation of Classic McEliece on an ARM Cortex-M4 processor, optimized to overcome memory constraints. To this end, we present an algorithm to retrieve the public key ad-hoc. This reduces memory and storage requirements and enables the generation of larger key pairs on the device. To further improve the implementation, we perform the public key operation by streaming the key to avoid storing it as a whole. This additionally reduces the risk of denial of service attacks. Finally, we use these results to implement and run TLS on the embedded device.

Scheduling with testing is a recent online problem within the framework of explorable uncertainty motivated by environments where some preliminary action can influence the duration of a task. Jobs have an unknown processing time that can be explored by running a test. Alternatively, jobs can be executed for the duration of a given upper limit. We consider this problem within the setting of multiple identical parallel machines and present competitive deterministic algorithms and lower bounds for the objective of minimizing the makespan of the schedule. In the non-preemptive setting, we present the SBS algorithm whose competitive ratio approaches 3.1016 if the number of machines becomes large. We compare this result with a simple greedy strategy and a lower bound which approaches 2. In the case of uniform testing times, we can improve the SBS algorithm to be 3-competitive. For the preemptive case we provide a 2-competitive algorithm and a tight lower bound which approaches the same value.

We study approximation algorithms for graph pricing with vertex capacities yet without the traditional envy-free constraint. Specifically, we have a set of items V and a set of customers X where each customer \(i \in X\) has a budget \(b_i\) and is interested in a bundle of items \(S_i \subseteq V\) with \(|S_i| \le 2\). However, there is a limited supply of each item: we only have \(\mu _v\) copies of item v to sell for each \(v \in V\). We should assign a price p(v) to each \(v \in V\) and choose a subset \(Y \subseteq X\) of customers so that each \(i \in Y\) can afford their bundle (\(p(S_i) \le b_i\)) and at most \(\mu _v\) chosen customers have item v in their bundle for each item \(v \in V\). Each customer \(i \in Y\) pays \(p(S_i)\) for the bundle they purchased: our goal is to do this in a way that maximizes revenue. Such pricing problems have been studied from the perspective of envy-freeness where we also must ensure that \(p(S_i) \ge b_i\) for each \(i \notin Y\). However, the version where we simply allocate items to customers after setting prices and do not worry about the envy-free condition has received less attention.

We investigate the problem of monitoring partially observable systems with nondeterministic and probabilistic dynamics. In such systems, every state may be associated with a risk, e.g., the probability of an imminent crash. During runtime, we obtain partial information about the system state in form of observations. The monitor uses this information to estimate the risk of the (unobservable) current system state. Our results are threefold. First, we show that extensions of state estimation approaches do not scale due the combination of nondeterminism and probabilities. While exploiting a geometric interpretation of the state estimates improves the practical runtime, this cannot prevent an exponential memory blowup. Second, we present a tractable algorithm based on model checking conditional reachability probabilities. Third, we provide prototypical implementations and manifest the applicability of our algorithms to a range of benchmarks. The results highlight the possibilities and boundaries of our novel algorithms.

We present a new approximation algorithm for the treewidth problem which constructs a corresponding tree decomposition as well. Our algorithm is a faster variation of Reed’s classical algorithm. For the benefit of the reader, and to be able to compare these two algorithms, we start with a detailed time analysis for Reed’s algorithm. We fill in many details that have been omitted in Reed’s paper. Computing tree decompositions parameterized by the treewidth k is fixed parameter tractable (FPT), meaning that there are algorithms running in time O(f(k)g(n)) where f is a computable function, g(n) is polynomial in n, and n is the number of vertices. An analysis of Reed’s algorithm shows \(f(k) = 2^{O(k \log k)}\) and \(g(n) = n \log n\) for a 5-approximation. Reed simply claims time \(O(n \log n)\) for bounded k for his constant factor approximation algorithm, but the bound of \(2^{\varOmega (k \log k)} n \log n\) is well known. From a practical point of view, we notice that the time of Reed’s algorithm also contains a term of \(O(k^2 2^{24k} n \log n)\), which for small k is much worse than the asymptotically leading term of \(2^{O(k \log k)} n \log n\). We analyze f(k) more precisely, because the purpose of this paper is to improve the running times for all reasonably small values of k.

Can a sender encode a pair of messages \((m_0,m_1)\) jointly, and send their encoding over (say) a binary erasure channel, so that the receiver can decode exactly one of the two messages and the sender does not know which one?

We study a new reconfiguration problem inspired by classic mechanical puzzles: a colored token is placed on each vertex of a given graph; we are also given a set of distinguished cycles on the graph. We are tasked with rearranging the tokens from a given initial configuration to a final one by using cyclic shift operations along the distinguished cycles. We first investigate a large class of graphs, which generalizes several classic puzzles, and we give a characterization of which final configurations can be reached from a given initial configuration. Our proofs are constructive, and yield efficient methods for shifting tokens to reach the desired configurations. On the other hand, when the goal is to find a shortest sequence of shifting operations, we show that the problem is NP-hard, even for puzzles with tokens of only two different colors.

International audience; The Tower variant of the Number Field Sieve (TNFS) is known to be asymptotically the most efficient algorithm to solve the discrete logarithm problem in finite fields of medium characteristics, when the extension degree is composite. A major obstacle to an efficient implementation of TNFS is the collection of algebraic relations, as it happens in dimension greater than 2. This requires the construction of new sieving algorithms which remain efficient as the dimension grows. In this article, we overcome this difficulty by considering a lattice enumeration algorithm which we adapt to this specific context. We also consider a new sieving area, a high-dimensional sphere, whereas previous sieving algorithms for the classical NFS considered an orthotope. Our new sieving technique leads to a much smaller running time, despite the larger dimension of the search space, and even when considering a larger target, as demonstrated by a record computation we performed in a 521-bit finite field GF(p^6). The target finite field is of the same form than finite fields used in recent zero-knowledge proofs in some blockchains. This is the first reported implementation of TNFS.

A Robinson similarity matrix is a symmetric matrix where all entries in all rows and columns are increasing towards the diagonal. A Robinson matrix can be decomposed into the weighted sum of k adjacency matrices of a nested family of unit interval graphs. We study the problem of finding an embedding which gives a simultaneous unit interval embedding for all graphs in the family. This is called a uniform embedding. We give a necessary and sufficient condition for the existence of a uniform embedding, derived from paths in an associated graph. We also give an efficient combinatorial algorithm to find a uniform embedding or give proof that it does not exist, for the case where \(k=2\).

We explore how to give Genetic Programming (GP) a head start to synthesize a programming problem. Our method uses a related problem and introduces a schedule that directs GP to solve the related problem first either fully or to some extent first, or at the same time. In addition, if the related problem’s solutions are written by students or evolved by GP, we explore the extent to which initializing the GP population with some of these solutions provides a head start. We find that having a population solve one programming problem before working to solve a related programming problem helps to a greater extent as the targeted problems and the intermediate problems themselves are selected to be more challenging.

We define nominal equational problems of the form $$\exists \overline{W} \forall \overline{Y} : P$$ ∃ W ¯ ∀ Y ¯ : P , where $$P$$ P consists of conjunctions and disjunctions of equations $$s\approx _\alpha t$$ s ≈ α t , freshness constraints $$a\#t$$ a # t and their negations: $$s \not \approx _\alpha t$$ s ≉ α t and "Equation missing", where $$a$$ a is an atom and $$s, t$$ s , t nominal terms. We give a general definition of solution and a set of simplification rules to compute solutions in the nominal ground term algebra. For the latter, we define notions of solved form from which solutions can be easily extracted and show that the simplification rules are sound, preserving, and complete. With a particular strategy for rule application, the simplification process terminates and thus specifies an algorithm to solve nominal equational problems. These results generalise previous results obtained by Comon and Lescanne for first-order languages to languages with binding operators. In particular, we show that the problem of deciding the validity of a first-order equational formula in a language with binding operators (i.e., validity modulo $$\alpha $$ α -equality) is decidable.

In this paper we study a variant of the classic d -Hitting Set problem with lower and upper capacity constraints, say A and B, respectively. The input to the problem consists of a universe U, a set family, \(\mathscr {S} \), of sets over U, where each set in the family is of size at most d, a non-negative integer k; and additionally two functions \(\alpha :\mathscr {S} \rightarrow \{1,\ldots ,A\}\) and \(\beta :\mathscr {S} \rightarrow \{1,\ldots ,B\}\). The goal is to decide if there exists a hitting set of size at most k such that for every set S in the family \(\mathscr {S} \), the solution contains at least \(\alpha (S)\) elements and at most \(\beta (S)\) elements from S. We call this the \((A, B)\)-Multi d-Hitting Set problem. We study the problem in the realm of parameterized complexity. We show that \((A, B)\)-Multi d-Hitting Set can be solved in \(\mathcal {O}^{\star }(d^{k}) \) time. For the special case when \(d=3\) and \(d=4\), we have an improved bound of \(\mathcal {O}^\star (2.2738^k)\) and \(\mathcal {O}^\star (3.562^{k})\), respectively. The former matches the running time of the classical 3-Hitting Set problem. Furthermore, we show that if we do not have an upper bound constraint and the lower bound constraint is same for all the sets in the family, say \(A>1\), then the problem can be solved even faster than d-Hitting Set.

Goyal and Kumar (STOC ’18, CRYPTO ’18) initiate the study of non-malleability for secret sharing and proposed the definition of information-theoretical non-malleability for secret sharing. Subsequently, Brian, Faonio, and Venturi (CRYPTO ’19, TCC ’19) proposed computational variants of non-malleability for secret sharing and showed that by focusing on computational non-malleability, it is possible to construct more efficient schemes compared to the existing ones. However, their schemes have a drawback that they do not satisfy statistical privacy.

We introduce a new measure on regular languages: their nondeterministic syntactic complexity. It is the least degree of any extension of the ‘canonical boolean representation’ of the syntactic monoid. Equivalently, it is the least number of states of any subatomic nondeterministic acceptor. It turns out that essentially all previous structural work on nondeterministic state-minimality computes this measure. Our approach rests on an algebraic interpretation of nondeterministic finite automata as deterministic finite automata endowed with semilattice structure. Crucially, the latter form a self-dual category.

This paper provides three nearly-optimal algorithms for scheduling t jobs in the \(\mathsf {CLIQUE}\) model. First, we present a deterministic scheduling algorithm that runs in \(O(\mathsf {Global}\mathsf {Congestion} + \mathsf {dilation})\) rounds for jobs that are sufficiently efficient in terms of their memory. The \(\mathsf {dilation}\) is the maximum round complexity of any of the given jobs, and the \(\mathsf {Global}\mathsf {Congestion}\) is the total number of messages in all jobs divided by the per-round bandwidth of \(n^2\) of the \(\mathsf {CLIQUE}\) model. Both are inherent lower bounds for any scheduling algorithm.

Let \( {\mathscr{C}} \) be a class of graphs closed under taking induced subgraphs. We say that \( {\mathscr{C}} \) has the clique-stable set separation property if there exists \( c \in {\mathbb{N}} \) such that for every graph \( G \in {\mathscr{C}} \) there is a collection \( {\mathscr{P}} \) of partitions (X, Y) of the vertex set of G with |\( {\mathscr{P}}\)| ≤ |V(G)|c and with the following property: if K is a clique of G, and S is a stable set of G, and K ∩ S = \( \emptyset\), then there is (X, Y) ∊ \( {\mathscr{P}}\) with K ⊆ X and S ⊆ Y. In 1991 M. Yannakakis conjectured that the class of all graphs has the clique-stable set separation property, but this conjecture was disproved by M. Goos in 2014. Therefore it is now of interest to understand for which classes of graphs such a constant c exists. In this paper we define two infinite families \( {\mathscr{S}}, {\mathscr{K}}\)of graphs and show that for every S ∊ \( {\mathscr{S}}\) and K ∊ \({\mathscr{K}}\), the class of graphs with no induced subgraph isomorphic to S or K has the clique-stable set separation property.

International audience; The aim of Traffic Engineering is to provide routing configurations in networks such that the used resources are minimized while maintaining a high level of quality of service (QoS). Among the optimization problems arising in this domain, we address in this paper the one related to setting weights in networks that are based on shortest path routing protocols (OSPF, IS-IS). Finding weights that induce efficient routing paths (e.g that minimize the maximum congested link) is a computationally hard problem. We propose to use Monte Carlo Search for the first time for this problem. More specifically we apply Nested Rollout Policy Adaptation (NRPA). We also extend NRPA with the force_exploration algorithm to improve the results. In comparison to other algorithms NRPA scales better with the size of the instance and can be easily extended to take into account additional constraints (cost utilization, delay,. . .) or linear/non-linear optimization criteria. For difficult instances the optimum is not known but a lower bound can be computed. NRPA gives results close to the lower bound on a standard dataset of telecommunication networks.

Forgetting in Answer Set Programming (ASP) aims at reducing the language of a logic program without affecting the consequences over the remaining language. It has recently gained interest in the context of modular ASP where it allows simplifying a program of a module, making it more declarative, by omitting auxiliary atoms or hiding certain atoms/parts of the program not to be disclosed. Unlike for arbitrary programs, it has been shown that forgetting for modular ASP can always be applied, for input, output and hidden atoms, and preserve all dependencies over the remaining language (in line with uniform equivalence). However, the definition of the result is based solely on a semantic characterization in terms of HT-models. Thus, computing an actual result is a complicated process and the result commonly bears no resemblance to the original program, i.e., we are lacking a corresponding syntactic operator. In this paper, we show that there is no forgetting operator that preserves uniform equivalence (modulo the forgotten atoms) between the given program and its forgetting result by only manipulating the rules of the original program that contain the atoms to be forgotten. We then present a forgetting operator that preserves uniform equivalence and is syntactic whenever this is suitable. We also introduce a special class of programs, where syntactic forgetting is always possible, and as a complementary result, establish it as the largest known class where forgetting while preserving all dependencies is always possible. acceptedVersion

Concrete domains have been introduced in Description Logics (DLs) to enable reference to concrete objects (such as numbers) and predefined predicates on these objects (such as numerical comparisons) when defining concepts. To retain decidability when integrating a concrete domain into a decidable DL, the domain must satisfy quite strong restrictions. In previous work, we have analyzed the most prominent such condition, called \(\omega \)-admissibility, from an algebraic point of view. This provided us with useful algebraic tools for proving \(\omega \)-admissibility, which allowed us to find new examples for concrete domains whose integration leaves the prototypical expressive DL \(\mathcal {ALC}\) decidable.

In Artificial Intelligence, Multi-Agent Systems are able to model many kinds of collective behavior and have a wide range of application. Logic is often used to model aspects of agents’ reasoning process. In this paper, we discuss social aspects of such systems. We propose a logical framework (Logic of “Inferable”) which reasons about whether a group of agents can perform an action, highlighting the concepts of action cost and budget that the group must have available in order to perform actions. The focus is on modeling the group dynamics of cooperative agents: if an agent of a group performs an action, that action to be considered as performed by the whole group, and the group can support a component agent in performing actions not affordable by that agent alone.

We present Pay To Transport (P2T), a protocol that lets customers buy an item remotely in an atomic, privacy preserving and trustless manner. P2T needs only basic features of a blockchain scripting language and does not need any tracking systems, arbitrator or deposit to preserve its security properties. For this reason the protocol can be implemented on any permissionless blockchain, regardless of its scripting language, without additional trust. Merchants’ and transporters’ addresses are public, but in P2T the parties never pay those addresses directly. Therefore P2T maintains the privacy of customers, merchant and transporters.

The state-of-the-art superposition-based theorem provers for first-order logic rely on simplification orderings on terms to constrain the applicability of inference rules, which in turn shapes the ensuing search space. The popular Knuth-Bendix simplification ordering is parameterized by symbol precedence—a permutation of the predicate and function symbols of the input problem’s signature. Thus, the choice of precedence has an indirect yet often substantial impact on the amount of work required to complete a proof search successfully.This paper describes and evaluates a symbol precedence recommender, a machine learning system that estimates the best possible precedence based on observations of prover performance on a set of problems and random precedences. Using the graph convolutional neural network technology, the system does not presuppose the problems to be related or share a common signature. When coupled with the theorem prover Vampire and evaluated on the TPTP problem library, the recommender is found to outperform a state-of-the-art heuristic by more than 4 % on unseen problems.

A graph is called a sum graph if its vertices can be labelled by distinct positive integers such that there is an edge between two vertices if and only if the sum of their labels is the label of another vertex of the graph. Most papers on sum graphs consider combinatorial questions like the minimum number of isolated vertices that need to be added to a given graph to make it a sum graph. In this paper, we initiate the study of sum graphs from the viewpoint of computational complexity. Note that every n-vertex sum graph can be represented by a sorted list of n positive integers where edge queries can be answered in \(\mathscr {O}(\log n)\) time. Thus, limiting the size of the vertex labels upper-bounds the space complexity of storing the graph.

The problem of scheduling with testing in the framework of explorable uncertainty models environments where some preliminary action can influence the duration of a task. In the model, each job has an unknown processing time that can be revealed by running a test. Alternatively, jobs may be run untested for the duration of a given upper limit. Recently, Dürr et al. [4] have studied the setting where all testing times are of unit size and have given lower and upper bounds for the objectives of minimizing the sum of completion times and the makespan on a single machine. In this paper, we extend the problem to non-uniform testing times and present the first competitive algorithms. The general setting is motivated for example by online user surveys for market prediction or querying centralized databases in distributed computing. Introducing general testing times gives the problem a new flavor and requires updated methods with new techniques in the analysis. We present constant competitive ratios for the objective of minimizing the sum of completion times in the deterministic case, both in the non-preemptive and preemptive setting. For the preemptive setting, we additionally give a first lower bound. We also present a randomized algorithm with improved competitive ratio. Furthermore, we give tight competitive ratios for the objective of minimizing the makespan, both in the deterministic and the randomized setting.

The search-type problem of evacuating 2 robots in the wireless model from the (Euclidean) unit disk was first introduced and studied by Czyzowicz et al. [DISC’2014]. Since then, the problem has seen a long list of follow-up results pertaining to variations as well as to upper and lower bound improvements. All established results in the area study this 2-dimensional search-type problem in the Euclidean metric space where the search space, i.e. the unit disk, enjoys significant (metric) symmetries.

Let p, t, q, n, m and r be positive integers, such that p is a prime number, \(q=p^t\), \(\gcd (q,n)=1\), \(m=\text{ ord}_n(q)\), and suppose that the prime factors of r divide n but not \((q^m-1)/n\), and that \(q^m \equiv 1 \pmod {4}\), if 4|r. Also let u such that \(u=\gcd (\frac{q^m-1}{q-1},\frac{q^m-1}{n})\). Assume that \(u=1\) or p is semiprimitive modulo u. Under these conditions, we are going to obtain the explicit factorization of the period polynomial of degree \(\gcd (\frac{q^{mr}-1}{q-1},\frac{q^{mr}-1}{nr})\) for the finite field \({\mathbb {F}}_{q^{mr}}\). In fact, we will see that such polynomial has always integer roots, meaning that the corresponding Gaussian periods are also integer numbers. As an application, we also determine the number of solutions of certain diagonal equations with constant exponent.

The digital age came with an extraordinary ability to generate data across organizations, people, and devices, data that needs to be analyzed, processed and stored. A well-known technique for analyzing this kind of data is Clustering. Many bio-inspired algorithms were proposed for this problem such as the Social Spider Optimization (SSO). In this work, we propose parallel island models of the SSO algorithm for the Clustering problem, using 24 processors for each parallel algorithm. Such models were implemented using static and dynamic topologies, and datasets from the UCI Machine Learning Repository used for the stage of experiments. The achieved average speedups range from 15 to 28 times faster than the SSO algorithm for large and small datasets, respectively, and a parallel model with static ring topology performs a little bit faster than the other parallel models. The parallel algorithms provide results with similar precision to the ones computed with the SSO algorithm.

We study the problem of learning a finite union of integer (axis-aligned) hypercubes over the d-dimensional integer lattice, i.e., whose edges are parallel to the coordinate axes. This is a natural generalization of the classic problem in the computational learning theory of learning rectangles. We provide a learning algorithm with access to a minimally adequate teacher (i.e. membership and equivalence oracles) that solves this problem in polynomial-time, for any fixed dimension d. Over a non-fixed dimension, the problem subsumes the problem of learning DNF boolean formulas, a central open problem in the field. We have also provided extensions to handle infinite hypercubes in the union, as well as showing how subset queries could improve the performance of the learning algorithm in practice. Our problem has a natural application to the problem of monadic decomposition of quantifier-free integer linear arithmetic formulas, which has been actively studied in recent years. In particular, a finite union of integer hypercubes correspond to a finite disjunction of monadic predicates over integer linear arithmetic (without modulo constraints). Our experiments suggest that our learning algorithms substantially outperform the existing algorithms.

The goal of this paper is to open up a new research direction aimed at understanding the power of preprocessing in speeding up algorithms that solve NP-hard problems exactly. We explore this direction for the classic Feedback Vertex Set problem on undirected graphs, leading to a new type of graph structure called antler decomposition, which identifies vertices that belong to an optimal solution. It is an analogue of the celebrated crown decomposition which has been used for Vertex Cover. We develop the graph structure theory around such decompositions and develop fixed-parameter tractable algorithms to find them, parameterized by the number of vertices for which they witness presence in an optimal solution. This reduces the search space of fixed-parameter tractable algorithms parameterized by the solution size that solve Feedback Vertex Set.

Structural runtime models provide a snapshot of the constituents of a system and their state. Capturing the history of runtime models, i.e., previous snapshots, has been shown to be useful for a number of aims. Handling, however, history at runtime poses important challenges to tool support. We present the InTempo tool which is based on the Eclipse Modeling Framework and encodes runtime models as graphs. Key features of InTempo, such as, the integration of temporal requirements into graph queries, the in-memory storage of the model, and a systematic method to contain the model’s memory consumption, intend to address issues which seemingly place limitations on the available tool support. InTempo offers two operation modes which support both runtime and postmortem application scenarios.

Part 5: Autonomous Agents; International audience; Real-word intelligent agents must be able to detect sudden and unexpected changes to their task environment and effectively respond to those changes in order to function properly in the long term. We thus isolate a set of perturbations that agents ought to address and demonstrate how task-agnostic perturbation detection and mitigation mechanisms can be integrated into a cognitive robotic architecture. We present results from experimental evaluations of perturbation mitigation strategies in a multi-robot system that show how intelligent systems can achieve higher levels of autonomy by explicitly handling perturbations.

A surprising result of Bokal et al. proved that the exact minimum value of c such that c-crossing-critical graphs do not have bounded maximum degree is \(c=13\). The key to the result is an inductive construction of a family of 13-crossing-critical graphs with many vertices of arbitrarily high degrees. While the inductive part of the construction is rather easy, it all relies on the fact that a certain 17-vertex base graph has the crossing number 13, which was originally verified only by a machine-readable computer proof. We now provide a relatively short self-contained computer-free proof.

We investigate the problem of drawing two posets of the same ground set so that one is drawn from left to right and the other one is drawn from the bottom up. The input to this problem is a directed graph \(G = (V, E)\) and two sets X, Y with \(X \cup Y = E\), each of which can be interpreted as a partial order of V. The task is to find a planar drawing of G such that each directed edge in X is drawn as an x-monotone edge, and each directed edge in Y is drawn as a y-monotone edge. Such a drawing is called an xy-planar drawing.

Confusion and diffusion are important design principles in block ciphers. The famous structures in block ciphers such as SPN, Feistel and Misty are proposed based on them and towards provable security against differential and linear cryptanalyses. There is few structure based on the two principles in stream ciphers except for Trivium. In this paper, we generalize the design ideas of Trivium to propose a new construction of Galois structure nonlinear feedback shift registers based on confusion and diffusion principles. As an application of this construction, a stream cipher named Bagua is proposed, which is a hardware-oriented primitive of 128-bit initialization vector and 128-bit or 256-bit key. It can be implemented in parallel up to 32 iterations at once, and the maximum throughout can be up to 8 Gbps. One can choose the parallel degree in implementation according to the requirement of throughput and hardware overhead in different application environments. Its resistances against differential and linear cryptanalyses are estimated theoretically and experimentally.

The Hamming Quasi-Cyclic (HQC) proposal is a promising candidate in the second round of the NIST Post-Quantum Cryptography Standardization project. It features small public key sizes, precise estimation of its decryption failure rates and contrary to most of the code-based systems, its security does not rely on hiding the structure of an error-correcting code. In this paper, we propose the first power side-channel attack on the Key Encapsulation Mechanism (KEM) version of HQC. Our attack utilizes a power side-channel to build an oracle that outputs whether the BCH decoder in HQC’s decryption algorithm corrects an error for a chosen ciphertext. Based on the decoding algorithm applied in HQC, it is shown how to design queries such that the output of the oracle allows to retrieve a large part of the secret key. The remaining part of the key can then be determined by an algorithm based on linear algebra. It is shown in experiments that less than 10000 measurements are sufficient to successfully mount the attack on the HQC reference implementation running on an ARM Cortex-M4 microcontroller.

The growing role of models across the life-cycle of enterprises, and their information and software systems, fuels the need for a more fundamental reflection on the foundations of modeling. Two of the core theories of the discipline of enterprise engineering (Factual Information (FI) theory and the Model Universe (MU) theory) aim at contributing to these foundations.

We define the notion of a proof of knowledge in the setting where the verifier is classical, but the prover is quantum, and where the witness that the prover holds is in general a quantum state. We establish simple properties of our definition, including that, if a nondestructive classical proof of quantum knowledge exists for some state, then that state can be cloned by an unbounded adversary, and that, under certain conditions on the parameters in our definition, a proof of knowledge protocol for a hard-to-clone state can be used as a (destructive) quantum money verification protocol. In addition, we provide two examples of protocols (both inspired by private-key classical verification protocols for quantum money schemes) which we can show to be proofs of quantum knowledge under our definition. In so doing, we introduce techniques for the analysis of such protocols which build on results from the literature on nonlocal games. Finally, we show that, under our definition, the verification protocol introduced by Mahadev (FOCS 2018) is a classical argument of quantum knowledge for QMA relations. In all cases, we construct an explicit quantum extractor that is able to produce a quantum witness given black-box quantum (rewinding) access to the prover, the latter of which includes the ability to coherently execute the prover’s black-box circuit controlled on a superposition of messages from the verifier.

We show that if \(A=\{a_1< a_2< \ldots < a_k\}\) is a set of real numbers such that the differences of the consecutive elements are distinct, then for and finite \(B \subset \mathbb {R}\), $$ |A+B|\gg |A|^{1/2}|B|. $$ The bound is tight up to the constant.

For timed automata, there is the notion of quasi-equal clocks. Two clocks are quasi-equal if, in each reachable configuration, they are equal or at least one has value 0. There are approaches to exploit quasi-equality of clocks to speed up reachability checking for timed automata. There is a procedure to detect quasi-equal clocks and a syntactical transformation of networks of timed automata where quasi-equal clocks are encoded by one representative clock and one boolean token per clock.

In rendez-vous protocols an arbitrarily large number of indistinguishable finite-state agents interact in pairs. The cut-off problem asks if there exists a number B such that all initial configurations of the protocol with at least B agents in a given initial state can reach a final configuration with all agents in a given final state. In a recent paper [17], Horn and Sangnier prove that the cut-off problem is equivalent to the Petri net reachability problem for protocols with a leader, and in "Image missing" for leaderless protocols. Further, for the special class of symmetric protocols they reduce these bounds to "Image missing" and "Image missing" , respectively. The problem of lowering these upper bounds or finding matching lower bounds is left open. We show that the cut-off problem is "Image missing" -complete for leaderless protocols, "Image missing" -complete for symmetric protocols with a leader, and in "Image missing" for leaderless symmetric protocols, thereby solving all the problems left open in [17].

Many complex activities in production cycles, such as quality control or fault analysis, require highly experienced specialists to perform various operations on (semi)finished products using different tools. In practical scenarios, the next operation selection is complicated since each expert has only a local view on the entire set of operations to be performed. As a result, decisions made by the specialists are suboptimal and might cause high costs. In this paper, we consider a Multi-resource Partial-ordering Flexible Job-shop Scheduling (MPF-JSS) problem where partially-ordered sequences of operations must be scheduled on multiple required resources, such as tools and specialists. The resources are flexible and can perform one or more operations depending on their properties. We model the problem using Answer Set Programming (ASP), which can efficiently handle time assignments using Difference Logic. Moreover, we suggest two multi-shot solving strategies aiming to identify the time bounds allowing for a solution to the schedule optimization problem. Experiments conducted on a set of instances extracted from a medium-sized semiconductor fault analysis lab indicate that our approach can find schedules for 87 out of 91 considered real-world instances.

We describe several additions to the ENIGMA system that guides clause selection in the E automated theorem prover. First, we significantly speed up its neural guidance by adding server-based GPU evaluation. The second addition is motivated by fast weight-based rejection filters that are currently used in systems like E and Prover9. Such systems can be made more intelligent by instead training fast versions of ENIGMA that implement more intelligent pre-filtering. This results in combinations of trainable fast and slow thinking that improves over both the fast-only and slow-only methods. The third addition is based on “judging the children by their parents”, i.e., possibly rejecting an inference before it produces a clause. This is motivated by standard evolutionary mechanisms, where there is always a cost to producing all possible offsprings in the current population. This saves time by not evaluating all clauses by more expensive methods and provides a complementary view of the generated clauses. The methods are evaluated on a large benchmark coming from the Mizar Mathematical Library, showing good improvements over the state of the art .

We address the problem of verifying whether unwanted states, characterized as a given state formula, are reachable in a given parameterized multi-agent system (PMAS), i.e., whether the PMAS is unsafe. As the multi-agent system is parameterized, it only describes the finite set of possible agent templates, while the actual number of concrete agent instances for each template is unbounded and cannot be foreseen. However, as safety depends in general on the number of agent instances, the verification result must be correct irrespective of such a number. After having defined two distinct execution semantics of PMASs, in this paper we focus on an implemented approach for checking safety, which is composed of two steps. First, we have implemented a modeling tool, called SAFE, that allows to specify the agent templates in the PMAS and their possible interactions, and to automatically translate this model into a textual encoding of an array-based system (ABS). Second, we check safety via infinite-state model checking based on satisfiability modulo theories (SMT), by using the general purpose SMT-based model checker MCMT, which accepts ABS specifications as input. We show the correctness guarantees of this approach by relying on the theory of ABSs. Finally we discuss how this approach lends itself to richer parameterized and data-aware MAS settings beyond the state-of-the-art solutions in the literature, using SMT-based results now available thanks to this work.