Rounds in Combinatorial Search

A set system $\mathcal{H} \subseteq2^{[m]}$ is said to be separating if for every pair of distinct elements x,y∈[m] there exists a set $H\in\mathcal{H}$ such that H contains exactly one of them. The search complexity of a separating system $\mathcal{H} \subseteq 2^{[m]}$ is the minimum number of questions of type “x∈H?” (where $H \in\mathcal{H}$ ) needed in the worst case to determine a hidden element x∈[m]. If we receive the answer before asking a new question then we speak of the adaptive complexity, denoted by $\mathrm{c} (\mathcal{H})$ ; if the questions are all fixed beforehand then we speak of the non-adaptive complexity, denoted by $\mathrm{c}_{na} (\mathcal{H})$ . If we are allowed to ask the questions in at most k rounds then we speak of the k-round complexity of $\mathcal{H}$ , denoted by $\mathrm{c}_{k} (\mathcal{H})$ . It is clear that $|\mathcal{H}| \geq\mathrm{c}_{na} (\mathcal{H}) = \mathrm{c}_{1} (\mathcal{H}) \geq\mathrm{c}_{2} (\mathcal{H}) \geq\cdots\geq\mathrm{c}_{m} (\mathcal{H}) = \mathrm{c} (\mathcal{H})$ . A group of problems raised by G.O.H. Katona is to characterize those separating systems for which some of these inequalities are tight. In this paper we are discussing set systems $\mathcal{H}$ with the property $|\mathcal{H}| = \mathrm{c}_{k} (\mathcal{H}) $ for any k≥3. We give a necessary condition for this property by proving a theorem about traces of hypergraphs which also has its own interest.     

Branching Time Logics \mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha } with Operations Until and Since Based on Bundles of Integer Numbers, Logical Consecutions, Deciding Algorithms

This paper is intended as an attempt to describe logical consequence in branching time logics. We study temporal branching time logics $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ which use the standard operations Until and Next and dual operations Since and Previous (LTL, as standard, uses only Until and Next). Temporal logics $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ are generated by semantics based on Kripke/Hinttikka structures with linear frames of integer numbers $\mathcal {Z}$ with a single node (glued zeros). For $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ , the permissible branching of the node is limited by α (where 1≤α≤ω). We prove that any logic $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ is decidable w.r.t. admissible consecutions (inference rules), i.e. we find an algorithm recognizing consecutions admissible in $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ . As a consequence, it implies that $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ itself is decidable and solves the satisfiability problem.     

Tight Bounds for Distributed Minimum-Weight Spanning Tree Verification

This paper introduces the notion of distributed verification without preprocessing. It focuses on the Minimum-weight Spanning Tree (MST) verification problem and establishes tight upper and lower bounds for the time and message complexities of this problem. Specifically, we provide an MST verification algorithm that achieves simultaneously $\tilde{O}(m)$ messages and $\tilde{O}(\sqrt{n} + D)$ time, where m is the number of edges in the given graph G, n is the number of nodes, and D is G’s diameter. On the other hand, we show that any MST verification algorithm must send $\tilde{\varOmega}(m)$ messages and incur $\tilde{\varOmega}(\sqrt{n} + D)$ time in worst case. Our upper bound result appears to indicate that the verification of an MST may be easier than its construction, since for MST construction, both lower bounds of $\tilde{\varOmega}(m)$ messages and $\tilde{\varOmega}(\sqrt{n} + D)$ time hold, but at the moment there is no known distributed algorithm that constructs an MST and achieves simultaneously $\tilde{O}(m)$ messages and $\tilde{O}(\sqrt{n} + D)$ time. Specifically, the best known time-optimal algorithm (using ${\tilde{O}}(\sqrt {n} + D)$ time) requires O(m+n ^3/2) messages, and the best known message-optimal algorithm (using ${\tilde{O}}(m)$ messages) requires O(n) time. On the other hand, our lower bound results indicate that the verification of an MST is not significantly easier than its construction.     

Computational complexity and approximability of social welfare optimization in multiagent resource allocation

A central task in multiagent resource allocation, which provides mechanisms to allocate (bundles of) resources to agents, is to maximize social welfare. We assume resources to be indivisible and nonshareable and agents to express their utilities over bundles of resources, where utilities can be represented in the bundle form, the $k$ -additive form, and as straight-line programs. We study the computational complexity of social welfare optimization in multiagent resource allocation, where we consider utilitarian and egalitarian social welfare and social welfare by the Nash product. Solving some of the open problems raised by Chevaleyre et al. (2006) and confirming their conjectures, we prove that egalitarian social welfare optimization is $\mathrm{NP}$ -complete for the bundle form, and both exact utilitarian and exact egalitarian social welfare optimization are $\mathrm{DP}$ -complete, each for both the bundle and the $2$ -additive form, where $\mathrm{DP}$ is the second level of the boolean hierarchy over  $\mathrm{NP}$ . In addition, we prove that social welfare optimization by the Nash product is $\mathrm{NP}$ -complete for both the bundle and the $1$ -additive form, and that the exact variants are $\mathrm{DP}$ -complete for the bundle and the $3$ -additive form. For utility functions represented as straight-line programs, we show $\mathrm{NP}$ -completeness for egalitarian social welfare optimization and social welfare optimization by the Nash product. Finally, we show that social welfare optimization by the Nash product in the $1$ -additive form is hard to approximate, yet we also give fully polynomial-time approximation schemes for egalitarian and Nash product social welfare optimization in the $1$ -additive form with a fixed number of agents.     

Distinguishing and relating higher-order and first-order processes by expressiveness

This is a paper on distinguishing and relating two important kinds of calculi through expressiveness, settling some critical but long unanswered questions. The delimitation of higher-order and first-order process calculi is a basic and pivotal topic in the study of process theory. Particularly, expressiveness studies mutual encodability, which helps decide whether process-passing or name-passing is more fundamental, and the way they ought to be used in both theory and practice. In this paper, we contribute to such demarcation with three major results. Firstly $\pi $ (first-order pi-calculus) can faithfully express $\varPi $ (basic higher-order pi-calculus). The calculus $\varPi $ has the elementary operators (input, output, composition and restriction). This actually is a corollary of a more general result, that $\pi $ can encode $\varPi ^r$ ( $\varPi $ enriched with the relabelling operator). Secondly $\varPi $ cannot interpret $\pi $ reasonably. This is of more significance since it separates $\varPi $ and $\pi $ by drawing a well-defined boundary. Thirdly an encoding from $\pi $ to $\varPi ^r$ is revisited and discussed, which not only implies how to make $\varPi $ more useful but also stresses the importance of name-passing in $\pi $ .     

The Rank-Width of Edge-Coloured Graphs

A C-coloured graph is a graph, that is possibly directed, where the edges are coloured with colours from the set C. Clique-width is a complexity measure for C-coloured graphs, for finite sets C. Rank-width is an equivalent complexity measure for undirected graphs and has good algorithmic and structural properties. It is in particular related to the vertex-minor relation. We discuss some possible extensions of the notion of rank-width to C-coloured graphs. There is not a unique natural notion of rank-width for C-coloured graphs. We define two notions of rank-width for them, both based on a coding of C-coloured graphs by ${\mathbb{F}}^{*}$ -graphs— $\mathbb {F}$ -coloured graphs where each edge has exactly one colour from $\mathbb{F}\setminus \{0\},\ \mathbb{F}$ a field—and named respectively $\mathbb{F}$ -rank-width and $\mathbb {F}$ -bi-rank-width. The two notions are equivalent to clique-width. We then present a notion of vertex-minor for $\mathbb{F}^{*}$ -graphs and prove that $\mathbb{F}^{*}$ -graphs of bounded $\mathbb{F}$ -rank-width are characterised by a list of $\mathbb{F}^{*}$ -graphs to exclude as vertex-minors (this list is finite if $\mathbb{F}$ is finite). An algorithm that decides in time O(n ³) whether an $\mathbb{F}^{*}$ -graph with n vertices has $\mathbb{F}$ -rank-width (resp. $\mathbb{F}$ -bi-rank-width) at most k, for fixed k and fixed finite field $\mathbb{F}$ , is also given. Graph operations to check MSOL-definable properties on $\mathbb{F}^{*}$ -graphs of bounded $\mathbb{F}$ -rank-width (resp. $\mathbb{F}$ -bi-rank-width) are presented. A specialisation of all these notions to graphs without edge colours is presented, which shows that our results generalise the ones in undirected graphs.     

An efficient simulation algorithm on Kripke structures

A number of algorithms for computing the simulation preorder (and equivalence) on Kripke structures are available. Let $\varSigma $ denote the state space, ${\rightarrow }$ the transition relation and $P_{\mathrm {sim}}$ the partition of $\varSigma $ induced by simulation equivalence. While some algorithms are designed to reach the best space bounds, whose dominating additive term is $|P_{\mathrm {sim}}|^2$ , other algorithms are devised to attain the best time complexity $O(|P_{\mathrm {sim}}||{\rightarrow }|)$ . We present a novel simulation algorithm which is both space and time efficient: it runs in $O(|P_ {\mathrm {sim}}|^2 \log |P_{\mathrm {sim}}| + |\varSigma |\log |\varSigma |)$ space and $O(|P_{\mathrm {sim}}||{\rightarrow }|\log |\varSigma |)$ time. Our simulation algorithm thus reaches the best space bounds while closely approaching the best time complexity.     

Arithmetizing Classes Around \textsf{NC} 1 and \textsf{L}

The parallel complexity class $\textsf{NC}$ ¹ has many equivalent models such as polynomial size formulae and bounded width branching programs. Caussinus et al. (J. Comput. Syst. Sci. 57:200–212, 1992) considered arithmetizations of two of these classes, $\textsf{\#NC}$ ¹ and $\textsf{\#BWBP}$ . We further this study to include arithmetization of other classes. In particular, we show that counting paths in branching programs over visibly pushdown automata is in $\textsf{FLogDCFL}$ , while counting proof-trees in logarithmic width formulae has the same power as $\textsf{\#NC}$ ¹. We also consider polynomial-degree restrictions of $\textsf{SC}$ ⁱ , denoted $\textsf{sSC}$ ⁱ , and show that the Boolean class $\textsf{sSC}$ ¹ is sandwiched between $\textsf{NC}$ ¹ and $\textsf{L}$ , whereas $\textsf{sSC}$ ⁰ equals $\textsf{NC}$ ¹. On the other hand, the arithmetic class $\textsf{\#sSC}$ ⁰ contains $\textsf{\#BWBP}$ and is contained in $\textsf{FL}$ , and $\textsf{\#sSC}$ ¹ contains $\textsf{\#NC}$ ¹ and is in $\textsf{SC}$ ². We also investigate some closure properties of the newly defined arithmetic classes.     

On matrices, automata, and double counting in constraint programming

Matrix models are ubiquitous for constraint problems. Many such problems have a matrix of variables $\mathcal{M}$ , with the same constraint C defined by a finite-state automaton $\mathcal{A}$ on each row of $\mathcal{M}$ and a global cardinality constraint $\mathit{gcc}$ on each column of $\mathcal{M}$ . We give two methods for deriving, by double counting, necessary conditions on the cardinality variables of the $\mathit{gcc}$ constraints from the automaton $\mathcal{A}$ . The first method yields linear necessary conditions and simple arithmetic constraints. The second method introduces the cardinality automaton, which abstracts the overall behaviour of all the row automata and can be encoded by a set of linear constraints. We also provide a domain consistency filtering algorithm for the conjunction of lexicographic ordering constraints between adjacent rows of $\mathcal{M}$ and (possibly different) automaton constraints on the rows. We evaluate the impact of our methods in terms of runtime and search effort on a large set of nurse rostering problem instances.     

On reducing factorization to the discrete logarithm problem modulo a composite

The discrete logarithm problem modulo a composite??abbreviate it as DLPC??is the following: given a (possibly) composite integer n??? 1 and elements ${a, b \in \mathbb{Z}_n^*}$ , determine an ${x \in \mathbb{N}}$ satisfying a ^x ?=?b if one exists. The question whether integer factoring can be reduced in deterministic polynomial time to the DLPC remains open. In this paper we consider the problem ${{\rm DLPC}_\varepsilon}$ obtained by adding in the DLPC the constraint ${x\le (1-\varepsilon)n}$ , where ${\varepsilon}$ is an arbitrary fixed number, ${0 < \varepsilon\le\frac{1}{2}}$ . We prove that factoring n reduces in deterministic subexponential time to the ${{\rm DLPC}_\varepsilon}$ with ${O_\varepsilon((\ln n)^2)}$ queries for moduli less or equal to n.     

Vertex Cover Kernelization Revisited

An important result in the study of polynomial-time preprocessing shows that there is an algorithm which given an instance (G,k) of Vertex Cover outputs an equivalent instance (G′,k′) in polynomial time with the guarantee that G′ has at most 2k′ vertices (and thus $\mathcal{O}((k')^{2})$ edges) with k′≤k. Using the terminology of parameterized complexity we say that k-Vertex Cover has a kernel with 2k vertices. There is complexity-theoretic evidence that both 2k vertices and Θ(k ²) edges are optimal for the kernel size. In this paper we consider the Vertex Cover problem with a different parameter, the size $\mathop{\mathrm{\mbox{\textsc{fvs}}}}(G)$ of a minimum feedback vertex set for G. This refined parameter is structurally smaller than the parameter k associated to the vertex covering number $\mathop{\mathrm{\mbox {\textsc{vc}}}}(G)$ since $\mathop{\mathrm{\mbox{\textsc{fvs}}}}(G)\leq\mathop{\mathrm{\mbox{\textsc{vc}}}}(G)$ and the difference can be arbitrarily large. We give a kernel for Vertex Cover with a number of vertices that is cubic in $\mathop{\mathrm{\mbox{\textsc{fvs}}}}(G)$ : an instance (G,X,k) of Vertex Cover, where X is a feedback vertex set for G, can be transformed in polynomial time into an equivalent instance (G′,X′,k′) such that |V(G′)|≤2k and $|V(G')| \in\mathcal{O}(|X'|^{3})$ . A similar result holds when the feedback vertex set X is not given along with the input. In sharp contrast we show that the Weighted Vertex Cover problem does not have a polynomial kernel when parameterized by the cardinality of a given vertex cover of the graph unless NP ? coNP/poly and the polynomial hierarchy collapses to the third level.     

Self-Referential Justifications in Epistemic Logic

This paper is devoted to the study of self-referential proofs and/or justifications, i.e., valid proofs that prove statements about these same proofs. The goal is to investigate whether such self-referential justifications are present in the reasoning described by standard modal epistemic logics such as  $\mathsf{S4}$ . We argue that the modal language by itself is too coarse to capture this concept of self-referentiality and that the language of justification logic can serve as an adequate refinement. We consider well-known modal logics of knowledge/belief and show, using explicit justifications, that $\mathsf{S4}$ , $\mathsf{D4}$ , $\mathsf{K4}$ , and  $\mathsf{T}$ with their respective justification counterparts  $\mathsf{LP}$ , $\mathsf{JD4}$ , $\mathsf{J4}$ , and  $\mathsf{JT}$ describe knowledge that is self-referential in some strong sense. We also demonstrate that self-referentiality can be avoided for  $\mathsf{K}$ and  $\mathsf{D}$ . In order to prove the former result, we develop a machinery of minimal evidence functions used to effectively build models for justification logics. We observe that the calculus used to construct the minimal functions axiomatizes the reflected fragments of justification logics. We also discuss difficulties that result from an introduction of negative introspection.     

A new PAC bound for intersection-closed concept classes

For hyper-rectangles in $\mathbb{R}^{d}$ Auer (1997) proved a PAC bound of $O(\frac{1}{\varepsilon}(d+\log \frac{1}{\delta}))$ , where $\varepsilon$ and $\delta$ are the accuracy and confidence parameters. It is still an open question whether one can obtain the same bound for intersection-closed concept classes of VC-dimension $d$ in general. We present a step towards a solution of this problem showing on one hand a new PAC bound of $O(\frac{1}{\varepsilon}(d\log d + \log \frac{1}{\delta}))$ for arbitrary intersection-closed concept classes, complementing the well-known bounds $O(\frac{1}{\varepsilon}(\log \frac{1}{\delta}+d\log \frac{1}{\varepsilon}))$ and $O(\frac{d}{\varepsilon}\log \frac{1}{\delta})$ of Blumer et al. and (1989) and Haussler, Littlestone and Warmuth (1994). Our bound is established using the closure algorithm, that generates as its hypothesis the intersection of all concepts that are consistent with the positive training examples. On the other hand, we show that many intersection-closed concept classes including e.g. maximum intersection-closed classes satisfy an additional combinatorial property that allows a proof of the optimal bound of $O(\frac{1}{\varepsilon}(d+\log \frac{1}{\delta}))$ . For such improved bounds the choice of the learning algorithm is crucial, as there are consistent learning algorithms that need $\Omega(\frac{1}{\varepsilon}(d\log\frac{1}{\varepsilon} +\log\frac{1}{\delta}))$ examples to learn some particular maximum intersection-closed concept classes.     

Delayed theory combination vs. Nelson-Oppen for satisfiability modulo theories: a comparative analysis

Most state-of-the-art approaches for Satisfiability Modulo Theories $(SMT(\mathcal{T}))$ rely on the integration between a SAT solver and a decision procedure for sets of literals in the background theory $\mathcal{T} (\mathcal{T}{\text {-}}solver)$ . Often $\mathcal{T}$ is the combination $\mathcal{T}_1 \cup \mathcal{T}_2$ of two (or more) simpler theories $(SMT(\mathcal{T}_1 \cup \mathcal{T}_2))$ , s.t. the specific ${\mathcal{T}_i}{\text {-}}solvers$ must be combined. Up to a few years ago, the standard approach to $SMT(\mathcal{T}_1 \cup \mathcal{T}_2)$ was to integrate the SAT solver with one combined $\mathcal{T}_1 \cup \mathcal{T}_2{\text {-}}solver$ , obtained from two distinct ${\mathcal{T}_i}{\text {-}}solvers$ by means of evolutions of Nelson and Oppen’s (NO) combination procedure, in which the ${\mathcal{T}_i}{\text {-}}solvers$ deduce and exchange interface equalities. Nowadays many state-of-the-art SMT solvers use evolutions of a more recent $SMT(\mathcal{T}_1 \cup \mathcal{T}_2)$ procedure called Delayed Theory Combination (DTC), in which each ${\mathcal{T}_i}{\text {-}}solver$ interacts directly and only with the SAT solver, in such a way that part or all of the (possibly very expensive) reasoning effort on interface equalities is delegated to the SAT solver itself. In this paper we present a comparative analysis of DTC vs. NO for $SMT(\mathcal{T}_1 \cup \mathcal{T}_2)$ . On the one hand, we explain the advantages of DTC in exploiting the power of modern SAT solvers to reduce the search. On the other hand, we show that the extra amount of Boolean search required to the SAT solver can be controlled. In fact, we prove two novel theoretical results, for both convex and non-convex theories and for different deduction capabilities of the ${\mathcal{T}_i}{\text {-}}solvers$ , which relate the amount of extra Boolean search required to the SAT solver by DTC with the number of deductions and case-splits required to the ${\mathcal{T}_i}{\text {-}}solvers$ by NO in order to perform the same tasks: (i) under the same hypotheses of deduction capabilities of the ${\mathcal{T}_i}{\text {-}}solvers$ required by NO, DTC causes no extra Boolean search; (ii) using ${\mathcal{T}_i}{\text {-}}solvers$ with limited or no deduction capabilities, the extra Boolean search required can be reduced down to a negligible amount by controlling the quality of the $\mathcal{T}$ -conflict sets returned by the ${\mathcal{T}_i}{\text {-}}solvers$ .     

Leader election using loneliness detection

We consider the problem of leader election (LE) in single-hop radio networks with synchronized time slots for transmitting and receiving messages. We assume that the actual number n of processes is unknown, while the size u of the ID space is known, but is possibly much larger. We consider two types of collision detection: strong (SCD), whereby all processes detect collisions, and weak (WCD), whereby only non-transmitting processes detect collisions. We introduce loneliness detection (LD) as a key subproblem for solving LE in WCD systems. LD informs all processes whether the system contains exactly one process or more than one. We show that LD captures the difference in power between SCD and WCD, by providing an implementation of SCD over WCD and LD. We present two algorithms that solve deterministic and probabilistic LD in WCD systems with time costs of ${\mathcal{O}(\log \frac{u}{n})}$ and ${\mathcal{O}(\min( \log \frac{u}{n}, \frac{\log (1/\epsilon)}{n}))}$ , respectively, where ${\epsilon}$ is the error probability. We also provide matching lower bounds. Assuming LD is solved, we show that SCD systems can be emulated in WCD systems with factor-2 overhead in time. We present two algorithms that solve deterministic and probabilistic LE in SCD systems with time costs of ${\mathcal{O}(\log u)}$ and ${\mathcal{O}(\min ( \log u, \log \log n + \log (\frac{1}{\epsilon})))}$ , respectively, where ${\epsilon}$ is the error probability. We provide matching lower bounds.     

Quantum discord in spin systems with dipole–dipole interaction

The behavior of total quantum correlations (discord) in dimers consisting of dipolar-coupled spins 1/2 are studied. We found that the discord $Q=0$ at absolute zero temperature. As the temperature $T$ increases, the quantum correlations in the system increase at first from zero to its maximum and then decrease to zero according to the asymptotic law $T^{-2}$ . It is also shown that in absence of external magnetic field $B$ , the classical correlations $C$ at $T\rightarrow 0$ are, vice versa, maximal. Our calculations predict that in crystalline gypsum $\hbox {CaSO}_{4}\cdot \hbox {2H}_{2}{\hbox {O}}$ the value of natural $(B=0)$ quantum discord between nuclear spins of hydrogen atoms is maximal at the temperature of 0.644  $\upmu $ K, and for 1,2-dichloroethane $\hbox {H}_{2}$ ClC– $\hbox {CH}_{2}{\hbox {Cl}}$ the discord achieves the largest value at $T=0.517~\upmu $ K. In both cases, the discord equals $Q\approx 0.083$  bit/dimer what is $8.3\,\%$ of its upper limit in two-qubit systems. We estimate also that for gypsum at room temperature $Q\sim 10^{-18}$  bit/dimer, and for 1,2-dichloroethane at $T=90$  K the discord is $Q\sim 10^{-17}$  bit per a dimer.     

Error Analysis of a Compact ADI Scheme for the 2D Fractional Subdiffusion Equation

In this paper, a Crank–Nicolson-type compact ADI scheme is proposed for solving two-dimensional fractional subdiffusion equation. The unique solvability, unconditional stability and convergence of the scheme are proved rigorously. Two error estimates are presented. One is $\mathcal{O }(\tau ^{\min \{2-\frac{\gamma }{2},\,2\gamma \}}+h_1^4+h^4_2)$ in standard $H^1$ norm, where $\tau $ is the temporal grid size and $h_1,h_2$ are spatial grid sizes; the other is $\mathcal{O }(\tau ^{2\gamma }+h_1^4+h^4_2)$ in $H^1_{\gamma }$ norm, a generalized norm which is associated with the Riemann–Liouville fractional integral operator. Numerical results are presented to support the theoretical analysis.     

Polyadic tense \theta-valued \Lukasiewicz–Moisil algebras

In this paper we introduce the polyadic tense $\theta$ -valued $\L$ ukasiewicz–Moisil algebras (=polyadic tense $\hbox{LM}_{\theta}$ -algebras), as a common generalization of polyadic tense Boolean algebras and polyadic $\hbox{LM}_{\theta}$ -algebras. Our main result is a representation theorem for polyadic tense $\hbox{LM}_{\theta}$ -algebras.