Search

In their celebrated paper (Furst et al., Math. Syst. Theory 17(1), 13---27 (12)), Furst, Saxe, and Sipser used random restrictions to reveal the weakness of Boolean circuits of bounded depth, establishing that constant-depth and polynomial-size circuits cannot compute the parity function. Such local restrictions have played important roles and have found many applications in complexity analysis and algorithm design over the past three decades. In this article, we give a brief overview of two intriguing applications of local restrictions: the first one is for the Isomorphism Conjecture and the second one is for moderately exponential time algorithms for the Boolean formula satisfiability problem.

While 3-SAT is NP-hard, 2-SAT is solvable in polynomial time. Austrin, Guruswami, and H\r{a}stad roved a result known as "$(2+\varepsilon)$-SAT is NP-hard" [FOCS'14/SICOMP'17]. They showed that the problem of distinguishing k-CNF formulas that are g-satisfiable (i.e. some assignment satisfies at least g literals in every clause) from those that are not even 1-satisfiable is NP-hard if $\frac{g}{k} < \frac{1}{2}$ and is in P otherwise. We study a generalisation of SAT on arbitrary finite domains, with clauses that are disjunctions of unary constraints, and establish analogous behaviour. Thus we give a dichotomy for a natural fragment of promise constraint satisfaction problems (PCSPs) on arbitrary finite domains. The hardness side is proved using the algebraic approach, via a new general NP-hardness criterion on polymorphisms of the problem, based on a gap version of the Layered Label Cover problem. We show that previously used criteria are insufficient -- the problem hence gives an interesting benchmark of algebraic techniques for proving hardness of approximation problems such as PCSPs., Comment: Full version of an ICALP 2020 paper

A new and simple proof of the main result of the paper “Laterally closed lattice homomorphisms” by Toumi and Toumi (J Math Anal Appl 324:1178–1194, 2006) is given following the paper “Extension of Riesz homomorphisms, I” by Buskes (J Aust Math Soc Ser A 39(1):107–120, 1985).

We point out that the proof of Theorem 3.3 of Bagchi and Sastry (2013) contains a serious flaw. Accordingly, this theorem needs to be modified. In consequence, we also have to retract Corollary 3.4, Corollary 3.6 and Theorem 3.8 of Bagchi and Sastry (2013).

Borůvka presented in 1926 the first solution of the Minimum Spanning Tree Problem (MST) which is generally regarded as a cornerstone of Combinatorial Optimization. In this paper we present the first English translation of both of his pioneering works. This is followed by the survey of development related to the MST problem and by remarks and historical perspective. Out of many available algorithms to solve MST the Borůvka's algorithm is the basis of the fastest known algorithms.

In this short note we point to an error in the proof of a theorem stated in [L. Balková, E. Pelantová, Š. Starosta, On Brlek-Reutenauer conjecture, Theoret. Comput. Sci. 412 (2011) 5649–5655]. By constructing a counterexample, we show that the assertion of the theorem is actually incorrect. Although this theorem is of a technical character, it was used in an argument leading to a corollary of a general interest to the Brlek-Reutenauer conjecture, and thus as a consequence of this note we have that the proof of the mentioned corollary is also flawed.

Sandewall (1986) presents a theory of multiple inheritance with exceptions (also called non- monotonic inheritance) based on a set of nonmonotonic inference rules, taking advantage at the same time of theories based on nonmonotonic logic as proposed by Etherington and Reiter and of path-based theories as proposed by Touretzky, Horty and Thomason. Flaws in Sandewall's set of rules are shown and a revised set of rules is proposed. This revised set is shown to provide the same conclusion sets on a hierarchy as path-based theories for three classical variants of preclusion. Moreover, although most approaches to inheritance leave it in the metalanguage, it is shown that putting preclusion in the object language provides extensions with desirable general properties which are not always true in the restricted language of conclusion sets.

In this paper, we address the class of bounded Petri nets with stopwatches (SwPNs), which is an extension of T-time Petri nets (TPNs) where time is associated with transitions. Contrary to TPNs, SwPNs encompass the notion of actions that can be reset, stopped and started. Models can be defined either with discrete-time or dense-time semantics. Unlike dense-time, discrete-time leads to combinatorial explosion (state space is computed by an exhaustive enumeration of states). We can however take advantage from discrete-time, especially when it comes to SwPNs: state and marking reachability problems, undecidable even for bounded nets, become decidable once discrete-time is considered. Thus, to mitigate the issue of combinatorial explosion, we now aim to extend the well-known symbolic handling of time (using convex polyhedra) to the discrete-time setting. This is basically done by computing the state space of discrete-time nets as the discretization of the state space of the corresponding dense-time model. First, we prove that this technique is correct for TPNs but not for SwPNs in general: in fact, for the latter, it may add behaviors that do not really belong to the evolution of the discrete-time net. To overcome this problem, we propose a splitting of the general polyhedron that encompasses the temporal information of the net into an union of simpler polyhedra which are safe with respect to the symbolic successor computation. We then give an algorithm that computes symbolically the state space of discrete-time SwPNs and finally exhibit a way to perform TCTL model-checking on this model.

We point out some minor corrections to the proof of Theorem 4.1 in the above paper. As presented, the proof of Theorem 4.1 uses a reduction from a special version of the Planar 3SAT problem (called RP3SAT) in which each clause has exactly three literals, each variable appears in at most three clauses and the factor graph corresponding to the instance is planar. It is incorrect to use a reduction from RP3SAT to prove the hardness of the predecessor existence problems for SDSs and SyDSs on grids since the RP3SAT problem is efficiently solvable even without the planarity restriction, as shown by Tovey [2]. However, the result of Theorem 4.1 can be established by a reduction from a restricted version of Planar 3SAT (henceforth referred to as Pl-B3SAT) in which each clause has two or three literals and each variable appears in at most three clauses. There is a local replacement-based ultra efficient (decision, parsimonious) reduction from 3SAT to Pl-B3SAT [1]. Thus, Pl-B3SAT is NP-complete, #Pl-B3SAT is #P-complete, Unique-Pl-B3SAT is DP -complete and Ambiguous-Pl-B3SAT is NP-complete. In the proof of Theorem 4.1, when the reduction is carried out from Pl-B3SAT, the constructions of the underlying grids for both SDSs and SyDSs remain the same. The only change is that the local transition functions for each node corresponding to a two literal clause should be the 4-simple-threshold function. (For each node corresponding to a three literal clause, the local transition function remains the 3-simple-threshold function, as in the paper.) Because of this change, some minor modifications are also needed for a few sentences in the discussion of the construction. These modifications are indicated below. (The page and line numbers used in the following discussion correspond to the corrected page proofs for the paper.)

The sets of word-lengths of context-sensitive languages are discussed.

In this paper we show that non-context-free phenomena can be captured using only limited logical means. In particular, we show how to encode a Tree Adjoining Grammar [16] into a weakly equivalent monadic context-free tree grammar (MCFTG). By viewing MCFTG-rules as terms in a free Lawvere theory, we can translate a given MCFTG into a regular tree grammar. The latter is characterizable by both a tree automaton and a corresponding formula in monadic second-order (MSO) logic. The trees of the resulting regular tree language are then unpacked into the intended “linguistic” trees through a model-theoretic interpretation in the form of an MSO transduction based upon tree-walking automata. This two-step approach gives a logical as well as an operational description of the tree sets involved.

Let be G^i, i = 0, 1, 2, the family of all 3-valent 3-connected planar graphs having elementary k-gons only if k = i (mod 3). Improving a result of J. Zaks we can show the inequality @s(G^i=

In this note counterexamples to some questions of Grunbaum on acyclic colorings are constructed.

It is shown that a transversal matroid of rank r on a set of cardinality m is representable over any field of order greater than m + ( inr −1 m ).

We count binary strings where the possible numbers of successive 0's and 1's are restricted.

Lake has constructed graphs G and H such that H contains n disjoint subgraphs isomorphic to G for each positive integer n but H does not contain infinitely many disjoint subgraphs isomorphic to G . Here a concrete example of such graphs with H the lattice points of the plane is given.

Publisher Summary The theory of regular languages and finite automata was developed in the early 1950s and is one of the oldest branches of theoretical computer science. Regular languages constitute the best known family of formal languages, and finite automata constitute the best known family of abstract machine models. The concepts of regular languages and finite automata appear frequently in theoretical computer science and have several important applications. There is a vast literature on these subjects. Despite the fact that many researchers have worked in this field, there remain several difficult open problems. The chapter discusses six of these problems. These problems are of fundamental importance and considerable difficulty. Most of them are intimately involved with the fundamental property of finite automata, namely finiteness. In a monograph published in 1971, McNaughton and Papert included a collection of open problems concerning regular languages. Their list is headed by the star height problem and until now, no progress has been made on such an intriguing question. The bounds on star height apply only to languages whose syntactic monoids are groups. In that case, the corresponding semiautomata are permutation semiautomata.

A square matrix A is transposable ii AT = PAQ for some ljermutation matrices P and Q, and symmiwizable if RA = ( RA)T for some permutation matrix R. A recent paper [I] purports to show that the matrix symmetrizability problem is isomorphism complete, that Is polynomial time equivalent to the graph isomorphism problem. Unfortunately, that paper is based on a misunderstanding about the contents of [4], as we shall indicate. In this r,ote we show that the matrix transposability problem is isomorphism complete, whereas the matrix symmetrizability problem is NPcomp!ete.

It is shown that a construction of Hirschfeld, which yields lower bounds for a certain class of Ramsey numbers, may be combined with a construction of Erdös, Hajnal and Rado, so as to obtain better bounds.

The acyclic number ?$a(G)$? of a graph ?$G$? is the maximum order of an induced forest in ?$G$?. The purpose of this short paper is to propose a conjecture that ?$a(G)\geq \left( 1-\frac{3}{2g}\right)n$? holds for every planar graph ?$G$? of girth ?$g$? and order ?$n$?, which captures three known conjectures on the topic. In support of this conjecture, we prove a weaker result that ?$a(G)\geq \left( 1-\frac{3}{g} \right)n$? holds. In addition, we give a construction showing that the constant ?$\frac{3}{2}$? from the conjecture cannot be decreased. Aciklično število ?$a(G)$? grafa ?$G$? je maksimalni red induciranega gozda v ?$G$?. Namen tega kratkega članka je predstavitev domneve, da ?$a(G)\geq \left( 1-\frac{3}{2g}\right)n$? velja za vsak ravninski graf ?$G$? ožine ?$g$? in reda ?$n$?, ki obsega tri znane hipoteze s tega področja. V podporo tej domnevi dokažemo šibkejši rezultat, da velja ?$a(G)\geq \left( 1-\frac{3}{g} \right)n$?. Poleg tega podamo konstrukcijo, ki pokaže, da konstante ?$\frac{3}{2}$? iz te hipoteze ni mogoče zmanjšati.

In 1978, G. Plotkin [7] conjectured that for the three-element truthvalue dcpo T, if κ > ω then the function space [T$^{κ}$ → T$^{κ}$] is not a retract of T$^{κ}$. In this short paper, we constructively prove a stronger result that if κ > ω then the function space [T$^{κ}$ → T$^{κ}$] is not a retract of the Cartesian product of any family of finite posets. Thus Plotkin's Conjecture is proved to be correct.

In this short paper we prove that even though the latest transitive operator has only one negative entry, we cannot get rid of it by simple operations. The research is motivated by, still unsolved, invariant subspace problem for positive operators.

Axenovich et al. (J. Combin. Theory Ser. B, to appear) considered the problem of the generalized Ramsey theory. In one case, they use the existence of Steiner triple systems, Pippenger and Spencer's theorem on hyperedge coloring, and the probabilistic method to show that r'(Kn,n, C4, 3) ≤ 3n/4(1 + o(1)), wherer'(Kn,n, C4, 3) denotes the minimum number of colors to color the edges of Kn,n such that every 4-cycle receives at least either 3 colors or 2 alternating colors. In this short paper, using techniques from combinatorial design theory, we prove that r'(Kn,n, C4, 3) ≤ (2n/3)+ 9 for all n. The result is the best possible since r'(Kn,n, C4, 3) > ⌊2n/3⌋ as shown by Axenovich et al. (J. Combin. Theory Ser. B, to appear).

Motivation In 2012, Iqbal et al. introduced the colored de Bruijn graph, a variant of the classic de Bruijn graph, which is aimed at ‘detecting and genotyping simple and complex genetic variants in an individual or population’. Because they are intended to be applied to massive population level data, it is essential that the graphs be represented efficiently. Unfortunately, current succinct de Bruijn graph representations are not directly applicable to the colored de Bruijn graph, which requires additional information to be succinctly encoded as well as support for non-standard traversal operations. Results Our data structure dramatically reduces the amount of memory required to store and use the colored de Bruijn graph, with some penalty to runtime, allowing it to be applied in much larger and more ambitious sequence projects than was previously possible. Availability and Implementation https://github.com/cosmo-team/cosmo/tree/VARI Supplementary information Supplementary data are available at Bioinformatics online.

The central idea observes a recursive mapping of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n$$\end{document}n-body intramolecular interactions to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(n+1)$$\end{document}(n+1)-body terms that is consistent with the molecular topology. Iterative application of the line graph transformation is identified as a natural and elegant tool to accomplish the recursion. The procedure readily generalizes to arbitrary \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n$$\end{document}n-body potentials. In particular, the method yields a complete characterization of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$4$$\end{document}4-body interactions. The hierarchical structure of atomic index lists for each interaction order \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n$$\end{document}n is compactly expressed as a directed acyclic graph. A pseudo-code description of the generating algorithm is given. With suitable data structures (e.g., edge lists or adjacency matrices), automatic enumeration and indexing of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n$$\end{document}n-body interactions can be implemented straightforwardly to handle large bio-molecular systems. Explicit examples are discussed, including a chemically relevant effective potential model of taurocholate bile salt.

In this short paper we study the game of Cops and Robbers, played on the vertices of some fixed graph $G$ of order $n$. The minimum number of cops required to capture a robber is called the cop number of $G$. We show that the cop number of graphs of diameter 2 is at most $\sqrt{2n}$, improving a recent result of Lu and Peng by a constant factor. We conjecture that this bound is still not optimal, and obtain some partial results towards the optimal bound., Comment: 5 pages

We erroneously claim that Lemma 5.1 applies to both non-deterministic and deterministic Benenson automata, while it applies only to deterministic ones. The following corrected lemma holds for both deterministic and non-deterministic Benenson automata. It also exponentially improves on the dependence on D for both for circuit depth and size compared to the paper version. Note that compared with the paper version, the circuit depth has an extra logarithmic dependence on n, and the circuit size has an extra linear dependence on n. Theorem 3.2 follows from Lemma 5.1(corrected) as before, by taking D = O(1), S = O(log n), and L = poly(n). Lemma 5.1 (Corrected). A function f : {0, 1}n → {0, 1} computed, possibly non-deterministically, by a Benenson automaton (S,D, L, Σ, n, σ , R) can be computed by a O(log(L/D) logD + log2 D + log n) depth, O(LD2 logD + LDn) size circuit.

The triangle removal lemma states that a simple graph with o(n^3) triangles can be made triangle-free by removing o(n^2) edges. It is natural to ask if this widely used result can be extended to multi-graphs (or equivalently, weighted graphs). In this short paper we rule out the possibility of such an extension by showing that there are multi-graphs with only n^{2+o(1)} triangles that are still far from being triangle-free. On the other hand, we show that for some g(n)=\omega(1), if a multi-graph (or weighted graph) has only g(n)n^2 triangles then it must be close to being triangle-free. The proof relies on variants of the Ruzsa-Szemer\'edi theorem.

We give graph-theoretic formalization of origami, the art of paper folding. Starting from the abstract origami system, we model origami construction as are write sequence of abstract origami's. To reason about the entire origami construction for the computational purposes, we define a labeled hypergraph for origami and give the abstraction of origami fold as a set of algebraic graph rewrite rules. We give detailed description of the fold operation in terms of graph rewriting. The graph-theoretic formalism enables us to reason in two separate domains of discourse, i.e. pure combinatoric domain and geometrical domain R2.

In this short paper, we give a positive answer to a question of C. D. Godsil (1983,Europ. J. Combin.4, 25–32) regarding automorphisms of cubic Cayley graphs of 2-groups: “If Cay(G, S) is a cubic Cayley graph of a 2-groupGandA=AutCay(G, S), doesA1≠1 imply Aut(G, S)≠1?”

This short paper further extends the result of Tomita (1984) to have a weaker sufficient condition for the equivalence of a pair of non-real-time deterministic pushdown automata to be decidable.

We introduce the family of $k$-gap-planar graphs for $k \geq 0$, i.e., graphs that have a drawing in which each crossing is assigned to one of the two involved edges and each edge is assigned at most $k$ of its crossings. This definition is motivated by applications in edge casing, as a $k$-gap-planar graph can be drawn crossing-free after introducing at most $k$ local gaps per edge. We present results on the maximum density of $k$-gap-planar graphs, their relationship to other classes of beyond-planar graphs, characterization of $k$-gap-planar complete graphs, and the computational complexity of recognizing $k$-gap-planar graphs., Comment: A preliminary version of this paper appeared in the Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD 2017)

International audience; While recent publications have shown strong relations between impossible differential and zero-correlation distinguishers as well as between zero-correlation and integral distinguishers, we analyze in this paper some relations between the underlying key-recovery attacks against Type-II Feistel networks. The results of this paper are build on the relation presented at ACNS 2013. In particular, using a matrix representation of the round function, we show that we can not only find impossible, integral and multidimensional zero-correlation distinguishers but also find the key-words involved in the underlined key-recovery attacks. Based on this representation, for matrix-method-derived strongly-related zero-correlation and impossible distinguishers, we show that the key-words involved in the zero-correlation attack is a subset of the key-words involved in the impossible differential attack. Other relations between the key-words involved in zero-correlation, impossible and integral attacks are also extracted. Also we show that in this context the data complexity of the multidimensional zero-correlation attack is larger than that of the other two attacks.

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.

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.

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.

This paper concerns the behavior of an SINR diagram of wireless systems, composed of a set S of n stations embedded in R d , when restricted to the corresponding Voronoi diagram imposed on S. The diagram obtained by restricting the SINR zones to their corresponding Voronoi cells is referred to hereafter as an SINR+Voronoi diagram. Uniform SINR diagrams, where all stations transmit with the same power, are simple and nicely structured, e.g., the station reception zones are convex and “fat”. In contrast, nonuniform SINR diagrams might be complex; the reception zones might be fractured and their boundaries might contain many singular points. In this paper, we establish the perhaps surprising fact that a nonuniform SINR+Voronoi diagram is topologically almost as nice as a uniform SINR diagram. In particular, it is convex and effectively 5 fat. This holds for every power assignment, every path-loss parameter α and every dimension d ≥ 1 . The convexity property also holds for every SINR threshold β > 0 , and the effective fatness property holds for any β > 1 . These fundamental properties provide a theoretical justification to engineering practices basing zonal tessellations on the Voronoi diagram, and help to explain the soundness and efficacy of such practices. We also consider two algorithmic applications. The first concerns the Power Control with Voronoi Diagram (PCVD) problem, where given n stations embedded in some polygon P , it is required to find the power assignment that optimizes the SINR threshold of the transmission station s i for any given reception point p ∈ P in its Voronoi cell . The second application is approximate point location; we show that for SINR+Voronoi zones, this task can be solved considerably more efficiently than in the general non-uniform case.

The classical global criteria for the existence of Hamilton cycles only apply to graphs with large edge density and small diameter. In a series of papers Asratian and Khachatryan developed local criteria for the existence of Hamilton cycles in finite connected graphs, which are analogues of the classical global criteria due to Dirac (1952), Ore (1960), Jung (1978), and Nash-Williams (1971). The idea was to show that the global concept of Hamiltonicity can, under rather general conditions, be captured by local phenomena, using the structure of balls of small radii. (The ball of radius $r$ centered at a vertex $u$ is a subgraph of $G$ induced by the set of vertices whose distances from $u$ do not exceed $r$.) Such results are called localization theorems and present a possibility to extend known classes of finite Hamiltonian graphs. In this paper we formulate a general approach for finding localization theorems and use this approach to formulate local analogues of well-known results of Bauer et al. (1989), Bondy (1980), H\"aggkvist and Nicoghossian (1981), and Moon and Moser (1963). Finally we extend two of our results to infinite locally finite graphs and show that they guarantee the existence of Hamiltonian curves, introduced by K\"undgen, Li and Thomassen (2017)., Comment: 25 pages, 3 figures

$$Q$$ -neutrosophic soft sets are essentially neutrosophic soft sets characterized by three independent two-dimensional membership functions which stand for uncertainty, indeterminacy and falsity. Thus, it can be applied to two-dimensional imprecise, indeterminate and inconsistent data which appear in most real-life problems. Graph theory has now become a major branch of applied mathematics, and it is generally regarded as a branch of combinatorics. In this research paper, we introduce the concept of $$Q$$ -neutrosophic soft graphs (Q- $${\mathcal{N}\mathcal{S}}Gs$$ ) that are made by combining $$Q$$ -neutrosophic soft sets with graphs and describe different methods of their construction. A $$Q$$ -neutrosophic soft graphs model is very much efficient for such real word problems which can construct more precise, flexible, and comparable system as compared to the classical, fuzzy and neutrosophic graph models. In this paper, we first define the concept of $$Q$$ -neutrosophic soft graph (Q- $${\mathcal{N}\mathcal{S}}G$$ ). In this paper we introduce the concept of $$Q$$ - $${\mathcal{N}\mathcal{S}}G$$ , strong Q- $${\mathcal{N}\mathcal{S}}G$$ , union and intersection of Q- $${\mathcal{N}\mathcal{S}}G$$ . The new concept is called Q- $${\mathcal{N}\mathcal{S}}G$$ multicriteria decision-making method (Q- $${\mathcal{N}\mathcal{S}}GMCDM$$ for short). Finally, we describe the utility of the $$Q$$ -neutrosophic soft graph and its applications in communication network and decision-making problem.

Distributivity of fuzzy implications over t-norms and t-conorms provides an effective way to solve the combinatorial rule explosion problems caused by addition of inputs in fuzzy inference systems, and hence has received considerable attention in the literature. In this paper, we explore the distributivity of a newly-born class of ordinal sum fuzzy implications with respect to t-norms and t-conorms, where the involving fuzzy implications are constructed by following the structure of ( S , N ) -implications generated from ordinal sum t-conorms and fuzzy negations, and are called N-ordinal sum fuzzy implications with the typical feature that the summand domains of linear transformations of given fuzzy implications are rectangles displayed almost along the minor diagonal of [ 0 , 1 ] 2 . The main results of this paper are characterizations of the t-norm and t-conorm solutions to the four usual distributive equations of N-ordinal sum fuzzy implications, where, of particular interest is that the t-norm and t-conorm solutions have the ordinal sum representations with only one nontrivial summand, and then the necessary and sufficient conditions under which N-ordinal sum fuzzy implications distribute over t-norms and t-conorms in different ways are obtained.

Range partitioning is a typical and mostly used data partitioning method and has became a core operation in most of big data computing platforms. Given an input L of N data items admitting a total order, the goal of range partitioning is to divide the whole input into k ranges containing the same number of data items. There is a trivial lower bound Ω ( N ) for the exact partitioning algorithms, since they need to at least make a full scan of the whole data. In the context of big data computing, even algorithms with O ( N ) time are not always thought to be efficient enough, the ultimate goal of designing algorithms on big data is usually to solve problems within sublinear time. Therefore, it is well motivated and important to study sublinear algorithms for the range partitioning problem. The paper aims to answer three questions. For the internal memory (RAM) model, since sophisticated sampling based ( ϵ , δ ) -approximation partitioning algorithm with O ( k log ⁡ ( N / δ ) ϵ 2 ) time cost has been proposed, the first question is what a lower bound we can obtain for sublinear partitioning algorithms. For the external memory (I/O) model, as far as we know, no previous works give external partitioning algorithms with performance guarantee within sublinear time, therefore the two questions are what the upper bound and the lower bound we can achieve for sublinear external partitioning algorithms. To answer the above questions, based on the RAM and I/O model, the paper studies the lower and upper bounds for the range partitioning problem. For the RAM model, a lower bound Ω ( k ( 1 − δ ) ϵ 2 ) for the cost of sampling based partitioning algorithms is proved. For the I/O model, two lower bounds of the sampling cost required by sublinear external range partitioning algorithms are proved, which indicate that at least a full scan of the whole input is needed in the worst case and a general sublinear external partitioning algorithm does not exist. Motivated by the hard instances utilized in the proof of lower bounds, a model for describing the input distributions of the range partitioning problem in practical applications is proposed. Finally, for the special cases described by the model, a sublinear external partitioning algorithm with O ( k log ⁡ ( N / δ ) w B ϵ 2 ) I/O cost is designed.

Aggregate signatures are used to create one short proof of authenticity and integrity from a set of digital signatures. However, one invalid signature in the set invalidates the entire aggregate, giving no information on which signatures are valid. Hartung et al. (2016) propose a fault-tolerant aggregate signature scheme based on combinatorial group testing. Given a bound $d$ on the number of invalid signatures among $n$ signatures to be aggregated, this scheme uses $d$-cover-free families to determine which signatures are invalid. These combinatorial structures guarantee a moderate increase on the size of the aggregate signature that can reach the best possible compression ratio of $O(\frac{n}{\log n})$, for fixed $d$, coming from an information theoretical bound. The case where the total number of signatures grows dynamically (unbounded scheme) was not satisfactorily solved in their original paper, since explicit constructions had constant compression ratios. In the present paper, we propose efficient solutions for the unbounded scheme, relying on sequences of $d$-cover-free families that we call {\em nested families}. Some of our constructions yield high compression ratio close to \rmv{the information theoretical bound}\todo{the best known upper bound}. We also propose the use of $(d,\lambda)$-cover-free families to support the loss of up to $\lambda-1$ parts of the aggregate., Comment: 30 pages

Multiplication is an essential step in a lot of calculations. In this paper we look at multiplication of 2 binary polynomials of degree at most n-1, modulo an irreducible polynomial of degree n with 2n input and n output qubits, without ancillary qubits, assuming no errors. With straightforward schoolbook methods this would result in a quadratic number of Toffoli gates and a linear number of CNOT gates. This paper introduces a new algorithm that uses the same space, but by utilizing space-efficient variants of Karatsuba multiplication methods it requires only O(n^{\log_2(3)}) Toffoli gates at the cost of a higher CNOT gate count: theoretically up to O(n^2) but in examples the CNOT gate count looks a lot better.

The paper discusses the concept of fuzzy set theory, interval-valued fuzzy set, intuitionistic fuzzy set, interval-valued intuitionistic fuzzy set, neutrosophic set and its operational laws. The paper presents the $$ \alpha ,\beta ,\gamma $$ -cut of single-valued triangular neutrosophic numbers and introduces the arithmetic operations of triangular neutrosophic numbers using $$ \alpha ,\beta ,\gamma $$ -cut. Then, possibilistic mean of truth membership function, indeterminacy membership function and falsity membership function is defined. The proposed approach converts each triangular neutrosophic number in linear programming problem to weighted value using possibilistic mean to determine the crisp linear programming problem. The proposed approach also considers the risk attitude of expert while deciding the parameters of linear programming model.

A recent paper by Afek, Ellen, and Gafni introduced a family of deterministic objects O m , k , for m , k ≥ 2 , with consensus numbers m such that, for each k ≥ 2 , O m , k is computationally less powerful than O m , k + 1 in systems with at least m k + m + k processes. This paper gives a wait-free implementation of O m , k from ( m + 1 ) -consensus objects and registers in systems with finitely many processes. In order to do so, it introduces a new family of objects which helps us to understand the power of m-consensus in a system with more than m processes.

The paper determines the number of states in finite automata necessary to represent “unambiguous” variants of the union, concatenation, and Kleene star operations on formal languages. For the disjoint union of languages represented by an m-state and an n-state deterministic finite automata (DFA), the state complexity is m n − 1 ; for the unambiguous concatenation, it is known to be m 2 n − 1 − 2 n − 2 (Daley et al., “Orthogonal concatenation: language equations and state complexity” , J. UCS, 2010), and this paper shows that this number of states is necessary already over a binary alphabet; for the unambiguous star, the state complexity function is determined to be 3 8 2 n + 1 . In the case of a unary alphabet, disjoint union requires up to 1 2 m n states in a DFA, unambiguous concatenation has state complexity m + n − 2 , and unambiguous star requires n − 2 states in the worst case. For nondeterministic finite automata, as well as for unambiguous finite automata, the complexity for disjoint union is m + n , for unambiguous concatenation, square, and star, the resulting complexities are m + n , 2n, and n + 1 , respectively, and all of them are witnessed by binary languages. In the unary nondeterministic or unambiguous case, the corresponding complexities are m + n for disjoint union, m + n − 1 and 2 n − 1 for unambiguous concatenation and square, respectively, and n − 1 for unambiguous star.

In the papers (Benoumhani 1996;1997), Benoumhani defined two polynomials F m , n , 1 ( x ) and F m , n , 2 ( x ) . Then, he defined A m ( n , k ) and B m ( n , k ) to be the polynomials satisfying F m , n , 1 ( x ) = ∑ k = 0 n A m ( n , k ) x n − k ( x + 1 ) k and F m , n , 1 ( x ) = ∑ k = 0 n B m ( n , k ) x n − k ( x + 1 ) k . In this paper, we give a combinatorial interpretation of the coefficients of A m + 1 ( n , k ) and prove a symmetry of the coefficients, i.e., [ m s ] A m + 1 ( n , k ) = [ m n − s ] A m + 1 ( n , n − k ) . We give a combinatorial interpretation of B m + 1 ( n , k ) and prove that B m + 1 ( n , n − 1 ) is a polynomial in m with non-negative integer coefficients. We also prove that if n ≥ 6 then all coefficients of B m + 1 ( n , n − 2 ) except the coefficient of m n − 1 are non-negative integers. For all n , the coefficient of m n − 1 in B m + 1 ( n , n − 2 ) is − ( n − 1 ) , and when n ≤ 5 some other coefficients of B m + 1 ( n , n − 2 ) are also negative.

There have been several works for studying the security of CRT-RSA with small CRT exponents d p and d q by using lattice-based Coppersmith's method. Thus far, two attack scenarios have been mainly studied: (1) d q is small with unbalanced prime factors p ≪ q . (2) Both d p and d q are small for balanced p ≈ q . The best attacks for the both scenarios were proposed by Takayasu-Lu-Peng (Eurocrypt'17, Journal of Cryptology'19) and the attack conditions are much better than the other known attacks. Although the attacks have been very useful for studying the security of CRT-RSA, the structures of their proposed lattices are not well understood. In this paper, to further study the security of CRT-RSA, we first define a generalized attack scenario to unify the previous ones. Specifically, all p , q , d p , and d q can be of arbitrary sizes. Furthermore, we propose improved attacks in this paper when d p and/or p is sufficiently small. Technically, we construct a lattice whose basis vectors are chosen flexibly depending on the sizes of p , q , d p , and d q . Since the attack scenarios (1) and (2) are simpler than our general scenario, the previous Takayasu-Lu-Peng's lattices are simple special cases of ours. We are able to achieve the flexible lattice constructions by exploiting implicit but essential structures of Takayasu-Lu-Peng's lattices. We check the validity of our proposed attacks by computer experiments. We believe that the deeper understanding of the lattice structures will be useful for studying the security of CRT-RSA even in other scenarios.