Search

In the degree-constrained graph orientation problem , the input is an unweighted, undirected graph G = (V , E) and nonnegative integers a v and b v (with a v ≤ b v) for each v ∈ V , and the objective is to assign a direction to every edge in E in such a way that for each v ∈ V , the number of outgoing edges in the resulting directed graph lies in the interval [ a v , b v ]. When such an orientation does not exist, it is desirable to find an orientation that best fits the condition instead. In this paper, we consider the problem of finding an orientation that minimizes the total penalty ∑ v ∈ V c v , where c v is a penalty incurred whenever a vertex v violates its degree constraints. As penalty functions, convex, concave, and step functions are considered in this paper. We show that the problem with any convex penalty function can be solved in O (| E | 1.5 min ⁡ { log ⁡ (| E | ⋅ C) , | E | 0.5 log ⁡ Δ log ⁡ | E | }) time, where Δ and C are the maximum degree and the largest magnitude of a penalty, respectively. In contrast, we show APX-hardness of the problem with step or concave functions. For trees and graphs with treewidth τ , the problem with any penalty function can be solved exactly in O (| V | log ⁡ Δ) time and O (τ 2 Δ 2 τ + 2 | V |) time, respectively. Finally, we consider the generalization of the problem to edge-weighted graphs and establish strong bounds on its inapproximability that hold even in the special case of stars. On the positive side, we can extend our algorithms for unweighted version of the problem to obtain pseudo-polynomial-time algorithms for the edge-weighted problem variant when restricted to trees and graphs with bounded treewidth. Also, we design a PTAS and a linear-time algorithm for stars with further restrictions on the degree constraints and edge weights. [ABSTRACT FROM AUTHOR]

• In identity-based encryption (IBE), a key generation center (KGC), which generates secret keys for a given identity, has the power to decrypt all ciphertexts. • This key escrow problem is one of the main barriers to the widespread real-world use of IBE. • In this paper we formally define an IBE scheme that resolves the key escrow problem. • We present two instantiations in our new security model: a lattice-based construction and a pairing-based construction. The key escrow problem is one of the main barriers to the widespread real-world use of identity-based encryption (IBE). Specifically, a key generation center (KGC), which generates secret keys for a given identity, has the power to decrypt all ciphertexts. At PKC 2009, Chow defined a notion of security against the KGC, that relies on assuming that it cannot discover the underlying identities behind ciphertexts. However, this is not a realistic assumption since, in practice, the KGC manages an identity list, and hence it can easily guess the identities corresponding to given ciphertexts. Chow later amended this issue by introducing a new entity called an identity-certifying authority (ICA) and proposed an anonymous key-issuing protocol. Essentially, this allows the users, KGC, and ICA to interactively generate secret keys without users ever having to reveal their identities to the KGC. Unfortunately, since Chow separately defined the security of IBE and that of the anonymous key-issuing protocol, his IBE definition did not provide any formal treatment when the ICA is used to authenticate the users. Effectively, all of the subsequent works following Chow lack the formal proofs needed to determine whether or not it delivers a secure solution to the key escrow problem. In this paper, based on Chow's work, we formally define an IBE scheme that resolves the key escrow problem and provide formal definitions of security against corrupted users, KGC, and ICA. Along the way, we observe that if we are allowed to assume a fully trusted ICA, as in Chow's work, then we can construct a trivial (and meaningless) IBE scheme that is secure against the KGC. Finally, we present two instantiations in our new security model: a lattice-based construction based on the Gentry–Peikert–Vaikuntanathan IBE scheme (STOC 2008) and Rückert's lattice-based blind signature scheme (ASIACRYPT 2010), and a pairing-based construction based on the Boneh–Franklin IBE scheme (CRYPTO 2001) and Boldyreva's blind signature scheme (PKC 2003). [ABSTRACT FROM AUTHOR]

This paper is a 'spiritual child' of the 2005 lecture notes Kindergarten Quantum Mechanics Coecke (2005) [24] , which showed how a simple, pictorial extension of Dirac notation allowed several quantum features to be easily expressed and derived, using language even a kindergartner can understand. Central to that approach was the use of pictures and pictorial transformation rules to understand and derive features of quantum theory and computation. However, this approach left many wondering 'where's the beef?' In other words, was this new approach capable of producing new results, or was it simply an aesthetically pleasing way to restate stuff we already know? The aim of this sequel paper is to say 'here's the beef!', and highlight some of the major results of the approach advocated in Kindergarten Quantum Mechanics, and how they are being applied to tackle practical problems on real quantum computers. Toward that end, we will focus mainly on what has become the Swiss army knife of the pictorial formalism: the ZX-calculus , a graphical tool for representing and manipulating complex linear maps on 2 N dimensional space. First we look at some of the ideas behind the ZX-calculus, comparing and contrasting it with the usual quantum circuit formalism. We then survey results from the past few years falling into three categories: (1) completeness of the rules of the ZX-calculus, (2) state-of-the-art quantum circuit optimisation results in commercial and open-source quantum compilers relying on ZX, and (3) the use of ZX in translating real-world stuff like natural language into quantum circuits that can be run on today's (very limited) quantum hardware. We also take the title literally, and outline an ongoing experiment aiming to show that ZX-calculus enables children to do cutting-edge quantum computing stuff. If anything, this would truly confirm that 'kindergarten quantum mechanics' wasn't just a joke. [ABSTRACT FROM AUTHOR]

Suppose an oracle knows a string S that is unknown to us and that we want to determine. The oracle can answer queries of the form "Is s a substring of S ?". In 1995, Skiena and Sundaram showed that, in the worst case, any algorithm needs to ask the oracle σ n / 4 − O (n) queries in order to be able to reconstruct the hidden string, where σ is the size of the alphabet of S and n its length, and gave an algorithm that spends (σ − 1) n + O (σ n) queries to reconstruct S. The main contribution of our paper is to improve the above upper-bound in the context where the string is compressible. We first present a universal algorithm that, given a (computable) compressor that compresses the string to τ bits, performs q = O (τ) substring queries; this algorithm, however, runs in exponential time. For this reason, the second part of the paper focuses on more time-efficient algorithms whose number of queries is bounded by specific compressibility measures. We first show that any string of length n over an integer alphabet of size σ with rle runs can be reconstructed with q = O (rle (σ + log ⁡ n rle)) substring queries in linear time and space. We then present an algorithm that spends q ∈ O (σ g log ⁡ n) substring queries and runs in O (n (log ⁡ n + log ⁡ σ) + q) time using linear space, where g is the size of a smallest straight-line program generating the string. [ABSTRACT FROM AUTHOR]

In this paper we present a series of results which show separations between the standard seeded model of self-assembly, Winfree's abstract Tile Assembly Model (aTAM), and the "seedless" 2-Handed Assembly Model (2HAM), which incorporates the dynamics of hierarchical self-assembly. In particular, we focus on the problem of self-assembling various shapes while minimizing the sizes of tile sets, or "programs", in each of these models in order to compare and contrast the models. A high-level overview of a subset of these results was presented in a paper by the authors in STACS 2013, but in this version we expand and improve the set of results related to showing separations between the two models according to their abilities to self-assemble various shapes. We exhibit classes of finite shapes that can be self-assembled more efficiently in each model. We also demonstrate infinite shapes that can self-assemble in one model but not in the other, as well as a shape which cannot self-assemble in either model. [ABSTRACT FROM AUTHOR]

Solid codes provide outstanding fault-tolerance when used for information transmission through a noisy channel involving not only symbol substitutions, but also synchronisation errors and black-outs. In this paper we provide an automaton theoretic characterisation of solid codes which takes this fault-tolerance into account. The fault-tolerance afforded by a solid code L can be summarised as follows: Consider messages, encoded using L , being sent through a noisy channel. Any code words in L , which are present in the received message, will be decoded correctly, unless they themselves happen to be the results of errors. Thus, errors in the received message will not lead to incorrect decodings of those parts which are error-free. In this paper we consider acceptors which are fault-tolerant in this sense when analysing such received messages. These acceptors characterise the class of solid codes. For finite solid codes an automaton characterisation was published in the sixties by Levenshtein and Romanov. The characterisation uses state-invariant finite-state transducers which act as decoders in such a way that an output is generated exactly when a code word has been read completely. State-invariance means that acceptance does not depend on the initial state — every state can be used as the initial state. The results of Levenshtein and Romanov depend strongly on the fact that the code is finite. In this paper we provide a general automaton theoretic characterisation of arbitrary solid codes without any such restriction. Moreover, the solid code is regular as a language if and only if the automaton used in the characterisation can be reduced to an equivalent finite automaton with equivalent properties. The main results of this paper are as follows: Every acceptor defines a solid code. For every solid code there is a fault-tolerant acceptor defining the code. Such acceptors expose the decomposition of potentially faulty received messages according to the code. For solid codes which are regular as languages these acceptors can be chosen to be finite while preserving all important combinatorial properties. Part of this work was presented at the 14th Journées Montoises of Theoretical Computer Science [32]. [ABSTRACT FROM AUTHOR]

We consider the problem of computing the diameter of a unicycle graph (i.e., a graph with a unique cycle). We present an O (n) time algorithm for the problem, where n is the number of vertices of the graph. This improves the previous best O (n log ⁡ n) time solution [Oh and Ahn, ISAAC 2016]. Using this algorithm as a subroutine, we solve the problem of adding a shortcut to a tree so that the diameter of the new graph (which is a unicycle graph) is minimized; our algorithm takes O (n 2 log ⁡ n) time and O (n) space. The previous best algorithms solve the problem in O (n 2 log 3 ⁡ n) time and O (n) space [Oh and Ahn, ISAAC 2016], or in O (n 2) time and O (n 2) space [Bilò, ISAAC 2018]. • The paper presents a linear time algorithm for computing the diameter of unicycle graphs. • The paper gives a new algorithm which finds a new edge to add to a tree so that the diameter of the new graph is minimized. • The algorithms rely on certain domination relations among edges of the graphs. [ABSTRACT FROM AUTHOR]

• The copy complexity of a Horn formula equals the copy complexity of the corresponding system of constraints. • The copy complexity of Horn formulas with respect to unit resolution is (m − 1) when copies of derived clauses are allowed. • A polynomial time algorithm that can determine if a 2-CNF formula has a unit read-once resolution refutation. In this paper, we discuss the copy complexity of Horn formulas with respect to unit resolution. A Horn formula is a boolean formula in conjunctive normal form (CNF) with at most one positive literal per clause. Horn formulas find applications in a number of domains, such as program verification (abstract interpretation) and logic programming (answer set programming). Quantified Horn clauses are used extensively in temporal verification of universal properties. Resolution is one of the oldest proof systems (refutation systems) for the boolean satisfiability problem (SAT), when the input is presented in conjunctive normal form (CNF). It is both sound and complete, although inefficient, when compared to other stronger proof systems for boolean formulas. Despite its inefficiency, the simple nature of resolution makes it an integral part of several theorem provers. Unit resolution is a restricted form of resolution in which each resolution step needs to use a clause with only one literal (unit literal clause). While not complete for general CNF formulas, unit resolution is complete for Horn formulas. Read-once resolution is a form of resolution in which each clause (input or derived) may be used in at most one resolution step. As with unit resolution, read-once resolution is incomplete in general and complete for Horn clauses. This paper focuses on a combination of unit resolution and read-once resolution called unit read-once resolution. Unit read-once resolution is incomplete for Horn clauses. In this paper, we study the copy complexity problem in Horn formulas with respect to unit read-once resolution. Briefly, the copy complexity of a formula with respect to unit read-once resolution, is the smallest number k , such that replicating each clause k times guarantees the existence of a unit read-once resolution refutation (UROR). This paper focuses on two problems related to the copy complexity of Horn formulas with respect to unit read-once resolution. We first relate the copy complexity of Horn formulas with respect to unit read-once resolution to the copy complexity of the corresponding Horn constraint system with respect to the addition rule. We also examine a form of copy complexity in which we permit replication of derived clauses, in addition to the input clauses. Finally, we provide a polynomial time algorithm for the problem of checking if a 2-CNF formula has a UROR. [ABSTRACT FROM AUTHOR]

• Bounds on the oriented chromatic number of oriented graph classes are studied. • Algorithms for the oriented chromatic number of oriented graph classes are given. • Parameterized complexity of the oriented chromatic number problem is considered. In this paper we consider colorings of oriented graphs, i.e. digraphs without cycles of length 2. Given some oriented graph G = (V , E) , an oriented r -coloring for G is a partition of the vertex set V into r independent sets, such that all the arcs between two of these sets have the same direction. The oriented chromatic number of G is the smallest integer r such that G permits an oriented r -coloring. Deciding whether an acyclic digraph has an oriented 4-coloring is NP-hard, which motivates to consider the problem on special graph classes. In this paper we consider the Oriented Chromatic Number problem on classes of recursively defined oriented graphs. Oriented co-graphs (short for oriented complement reducible graphs) can be recursively defined from the single vertex graph by applying the disjoint union and order composition. This recursive structure allows to compute an optimal oriented coloring and the oriented chromatic number in linear time. We generalize this result using the concept of perfect orderable graphs. Therefore, we show that for acyclic transitive digraphs every greedy coloring along a topological ordering leads to an optimal oriented coloring. Msp-digraphs (short for minimal series-parallel digraphs) can be defined from the single vertex graph by applying the parallel composition and series composition. We prove an upper bound of 7 for the oriented chromatic number for msp-digraphs and we give an example to show that this is bound best possible. We apply this bound and the recursive structure of msp-digraphs to obtain a linear time solution for computing the oriented chromatic number of msp-digraphs. In order to generalize the results on computing the oriented chromatic number of special graph classes, we consider the parameterized complexity of the Oriented Chromatic Number problem by so-called structural parameters, which are measuring the difficulty of decomposing a graph into a special tree-structure. [ABSTRACT FROM AUTHOR]

We study the Steiner k -eccentricity on trees, which generalizes the previous one in the paper [On the average Steiner 3-eccentricity of trees, arXiv:2005.10319 ]. We achieve much stronger properties for the Steiner k -ecc tree than that in the previous paper. Based on this, a linear time algorithm is devised to calculate the Steiner k -eccentricity of a vertex in a tree. On the other hand, lower and upper bounds of the average Steiner k -eccentricity index of a tree on order n are established based on a novel technique which is quite different and also much easier to follow than the earlier one. [ABSTRACT FROM AUTHOR]

• We propose some lower and upper bounds for the g -component connectivity along with their sharpness. • We characterize some trees and general graphs with the given g -component connectivity. • We suggest characterizations of graphs with given g -component connectivity and Erdös-Gallai-type problems for the g -component connectivity in this paper. Connectivity is a classic metric to evaluate reliability of multiprocessor system under the circumstances of processor failures. Based on connectivity, more refined quantitative indicators for fault tolerance of multiprocessor system have been extensively explored. The g -component connectivity of a graph G , denoted by c κ g (G) , is the minimum number of vertices whose removal from G results in a disconnected graph with at least g -components. So far, the values of the g -component (edge) connectivity of special networks with small g have been extensively investigated. For general graphs, the results of the g -component connectivity are very few. In this paper, we propose some lower and upper bounds for the g -component connectivity along with their sharpness, and then suggest some characterization of trees and general graphs with given g -component connectivity. Furthermore, we fix some related extremal problems. [ABSTRACT FROM AUTHOR]

• New fault-tolerant communication abstraction. • Simple implementations of read/write implementable objects. • Efficient implementations of snapshots and lattice agreement. This paper introduces a new communication abstraction, called Set-Constrained Delivery Broadcast (SCD-broadcast), whose aim is to provide its users with an appropriate abstraction level when they have to implement objects or distributed tasks in an asynchronous message-passing system prone to process crash failures. This abstraction allows each process to broadcast messages and deliver a sequence of sets of messages in such a way that, if a process delivers a set of messages including a message m and later delivers a set of messages including a message m ′ , no process delivers first a set of messages including m ′ and later a set of message including m. After having presented an algorithm implementing SCD-broadcast, the paper investigates its programming power and its computability limits. On the "power" side it presents SCD-broadcast-based algorithms, which are both simple and efficient, building objects (such as snapshot and conflict-free replicated data types), and distributed tasks. On the "computability limits" side it shows that SCD-broadcast and read/write registers are computationally equivalent. [ABSTRACT FROM AUTHOR]

• A new seeding algorithm is proposed for the fuzzy C-means problem. • Theoretical guarantees for both the new seeding algorithm and the fuzzy C-means++ algorithm are given. • Numerical experiments show the effectiveness of the new algorithm. As a kind of important soft clustering model, the fuzzy C -means method is widely applied in many fields. In this method, instead of the strict distributive ability in the classical k -means method, all the sample points are endowed with degrees of membership to each center to depict the fuzzy clustering. In this paper, we show that the fuzzy C -means++ algorithm, which introduces the k -means++ algorithm as a seeding strategy, gives a solution for which the approximation guarantee is O (k 2 ln ⁡ k). A novel seeding algorithm is then designed based on the contribution of the fuzzy potential function, which improves the approximation ratio to O (k ln ⁡ k). Preliminary numerical experiments are proposed to support the theoretical results of this paper. [ABSTRACT FROM AUTHOR]

This paper investigates a novel RSA-like cryptosystem proposed by Murru-Saettone. This cryptosystem is constructed from a cubic field connected to the cubic Pell equation and Redei rational functions. The scheme is claimed to be secure against the Wiener-type attack. However, in this paper, we show a Wiener-type attack that can recover the secret key from the continued fraction constructed from public information. [ABSTRACT FROM AUTHOR]

• First-of-its-kind general framework for a CTMC theory of stochastic rewriting systems for rules with conditions. • New rule-algebraic restricted rewriting theory formalism. • First-of-its-kind encoding of bio- and organo-chemical reaction systems via rule-algebraic restricted rewriting theory. The Kappa biochemistry and the MØD organic chemistry frameworks are amongst the most intensely developed applications of rewriting-based methods in the life sciences to date. A typical feature of these types of rewriting theories is the necessity to implement certain structural constraints on the objects to be rewritten (a protein is empirically found to have a certain signature of sites, a carbon atom can form at most four bonds,...). In this paper, we contribute a number of original developments that permit to implement a universal theory of continuous-time Markov chains (CTMCs) for stochastic rewriting systems. Our core mathematical concepts are a novel rule algebra construction for the relevant setting of rewriting rules with conditions, both in Double- and in Sesqui-Pushout semantics, augmented by a suitable stochastic mechanics formalism extension that permits to derive dynamical evolution equations for pattern-counting statistics. A second main contribution of our paper is a novel framework of restricted rewriting theories, which comprises a rule-algebra calculus under the restriction to so-called constraint-preserving completions of application conditions (for rules considered to act only upon objects of the underlying category satisfying a globally fixed set of structural constraints). This novel framework in turn renders a faithful encoding of bio- and organo-chemical rewriting in the sense of Kappa and MØD possible, which allows us to derive a rewriting-based formulation of reaction systems including a full-fledged CTMC semantics as instances of our universal CTMC framework. While offering an interesting new perspective and conceptual simplification of this semantics in the setting of Kappa , both the formal encoding and the CTMC semantics of organo-chemical reaction systems as motivated by the MØD framework are the first such results of their kind. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of finding read-once refutations (ROR) of linear feasibility in a specialized class of constraint systems called UTVPI+ constraint systems (UCS +). The refutations in this paper are analyzed using the ADD inference rule. Recall that a Unit Two Variable Per Inequality (UTVPI) constraint is a constraint of the form a i ⋅ x i + a j ⋅ x j ≤ b , where b ∈ Z , and a i , a j ∈ { 0 , 1 , − 1 }. A conjunction of such constraints is called a UTVPI constraint system (UCS). UCSs find applications in a number of domains such as abstract interpretation and scheduling. We examine a more general form of UCSs that allows for a limited number of non-UTVPI constraints to be added to a UCS. We refer to these more general UCSs as UTVPI+ constraint systems or UCS + s. If a UCS + has only k non-UTVPI constraints, then we refer to it as a UCS k +. Our focus in this paper is on refutations, i.e., proofs of infeasibility in UCS + s. In particular, we study read-once refutations of linear feasibility in UCS + s. Although the problem of finding read-once refutations of UCSs is polynomial time solvable, the presence of non-UTVPI constraints makes the problem NP-hard. However, if the number of non-UTVPI constraints is fixed, then read-once refutations can be found in polynomial time. In fact, in this paper, we show that the ROR problem is fixed-parameter tractable (FPT) for UCS k + s , with respect to k , the number of non-UTVPI constraints in the system. We also provide a lower bound on the efficiency of a class of parameterized algorithms for this problem, based on the Strong Exponential Time Hypothesis. [ABSTRACT FROM AUTHOR]