Recursive decomposition and bounds of the lattice of Moore co-families

A collection of sets on a ground set U _n (U _n ?=?{1,2,...,n}) closed under intersection and containing U _n is known as a Moore family. The set of Moore families for a fixed n is in bijection with the set of Moore co-families (union-closed families containing the empty set) denoted $\mathbb{M}_n$ . In this paper, we propose a recursive definition of the set of Moore co-families on U _n . Then we apply this decomposition result to compute a lower bound on $|\mathbb M_n|$ as a function of $|\mathbb M_{n-1}|$ , the Dedekind numbers and the binomial coefficients. These results follow the work carried out in [1] to enumerate the number of Moore families on U ₇.     

Multi-letter quantum finite automata: decidability of the equivalence and minimization of states

Multi-letter quantum finite automata (QFAs) can be thought of quantum variants of the one-way multi-head finite automata (Hromkovi?, Acta Informatica 19:377?C384, 1983). It has been shown that this new one-way QFAs (multi-letter QFAs) can accept with no error some regular languages, for example (a?+?b)*b, that are not acceptable by QFAs of Moore and Crutchfield (Theor Comput Sci 237:275?C306, 2000) as well as Kondacs and Watrous (66?C75, 1997; Observe that 1-letter QFAs are exactly measure-once QFAs (MO-1QFAs) of Moore and Crutchfield (Theor Comput Sci 237:275?C306, 2000)). In this paper, we study the decidability of the equivalence and minimization problems of multi-letter QFAs. Three new results presented in this paper are the following ones: (1) Given a k ₁-letter QFA ${{\mathcal A}_1}$ and a k ₂-letter QFA ${{\mathcal A}_2}$ over the same input alphabet ??, they are equivalent if and only if they are (n ² m ^k-1?m ^k-1?+?k)-equivalent, where m =?|??| is the cardinality of ??, k =?max(k ₁,k ₂), and n =?n ₁?+?n ₂, with n ₁ and n ₂ being numbers of states of ${{\mathcal A}_{1}}$ and ${{\mathcal A}_{2}}$ , respectively. When k =?1, this result implies the decidability of equivalence of measure-once QFAs (Moore and Crutchfield in Theor Comput Sci 237:275?C306, 2000). (It is worth mentioning that our technical method is essentially different from the previous ones used in the literature.) (2) A polynomial-time O(m ^2k-1 n ⁸?+?km ^k n ⁶) algorithm is designed to determine the equivalence of any two multi-letter QFAs (see Theorems 2 and 3; Observe that if a brute force algorithm to determine equivalence would be used, as suggested by the decidability outcome of the point (1), the worst case time complexity would be exponential). Observe also that time complexity is expressed here in terms of the number of states of the multi-letter QFAs and k can be seen as a constant. (3) It is shown that the states minimization problem of multi-letter QFAs is solvable in EXPSPACE. This implies also that the state minimization problem of MO-1QFAs (see Moore and Crutchfield in Theor Comput Sci 237:275?C306, 2000, page 304, Problem 5), an open problem stated in that paper, is also solvable in EXPSPACE.     

Parallel computation of disease transforms

Distance transforms are an important computational tool for the processing of binary images. For ann ×n image, distance transforms can be computed in time \(\mathcal{O}\) (n) on a mesh-connected computer and in polylogarithmic time on hypercube related structures. We investigate the possibilities of computing distance transforms in polylogarithmic time on the pyramid computer and the mesh of trees. For the pyramid, we obtain a polynomial lower bound using a result by Miller and Stout, so we turn our attention to the mesh of trees. We give a very simple \(\mathcal{O}\) (logn) algorithm for the distance transform with respect to theL ₁-metric, an \(\mathcal{O}\) (log² n) algorithm for the transform with respect to theL _∞-metric, and find that the Euclidean metric is much more difficult. Based on evidence from number theory, we conjecture the impossibility of computing the Euclidean distance transform in polylogarithmic time on a mesh of trees. Instead, we approximate the distance transform up to a given error. This works for anyL _k -metric and takes time \(\mathcal{O}\) (log³ n).     

Modifikationen des Pollard-Algorithmus

The factorization algorithm of Pollard generates a sequence in ? _n by $$x_0 : = 2;x_{i + 1} : = x_i^2 - 1(\bmod n),i = 1,2,3,...$$ wheren denotes the integer to be factored. The algorithm finds an factorp ofn within \(0\left( {\sqrt p } \right)\) macrosteps (=multiplications/divisions in ? _n ) on average. An empirical analysis of the Pollard algorithm using modified sequences $$x_{i + 1} = b \cdot x_i^\alpha + c(\bmod n),i = 1,2,...$$ withx ₀,b,c,α∈? and α≥2 shows, that a factorp ofn under the assumption gcd (α,p-1)≠1 now is found within $$0\left( {\sqrt {\frac{p}{{ged(\alpha ,p - 1}}} } \right)$$ macrosteps on average.     

A Unified Approach to Approximating Partial Covering Problems

An instance of the generalized partial cover problem consists of a ground set U and a family of subsets ${\mathcal{S}}\subseteq 2^{U}$ . Each element e??U is associated with a profit p(e), whereas each subset $S\in \mathcal{S}$ has a cost c(S). The objective is to find a minimum cost subcollection $\mathcal{S}'\subseteq \mathcal{S}$ such that the combined profit of the elements covered by $\mathcal{S}'$ is at least P, a specified profit bound. In the prize-collecting version of this problem, there is no strict requirement to cover any element; however, if the subsets we pick leave an element e??U uncovered, we incur a penalty of ??(e). The goal is to identify a subcollection $\mathcal{S}'\subseteq \mathcal{S}$ that minimizes the cost of $\mathcal{S}'$ plus the penalties of uncovered elements. Although problem-specific connections between the partial cover and the prize-collecting variants of a given covering problem have been explored and exploited, a more general connection remained open. The main contribution of this paper is to establish a formal relationship between these two variants. As a result, we present a unified framework for approximating problems that can be formulated or interpreted as special cases of generalized partial cover. We demonstrate the applicability of our method on a diverse collection of covering problems, for some of which we obtain the first non-trivial approximability results.     

Numerical solutions of AXB = C for mirrorsymmetric matrix X under a specified submatrix constraint

Mirrorsymmetric matrices, which are the iteraction matrices of mirrorsymmetric structures, have important application in studying odd/even-mode decomposition of symmetric multiconductor transmission lines (MTL). In this paper we present an efficient algorithm for minimizing ${\|AXB-C\|}$ where ${\|\cdot\|}$ is the Frobenius norm, ${A\in \mathbb{R}^{m\times n}}$ , ${B\in \mathbb{R}^{n\times s}}$ , ${C\in \mathbb{R}^{m\times s}}$ and ${X\in \mathbb{R}^{n\times n}}$ is mirrorsymmetric with a specified central submatrix [x _ij ] _{r≤i, j≤n-r} . Our algorithm produces a suitable X such that AXB = C in finitely many steps, if such an X exists. We show that the algorithm is stable any case, and we give results of numerical experiments that support this claim.     

Randomness Buys Depth for Approximate Counting

We show that the promise problem of distinguishing n-bit strings of relative Hamming weight \({1/2 + \Omega(1/{\rm lg}^{d-1} n)}\) from strings of weight \({1/2 - \Omega(1/{\rm \lg}^{d - 1} n)}\) can be solved by explicit, randomized (unbounded fan-in) poly(n)-size depth-d circuits with error \({\leq 1/3}\) , but cannot be solved by deterministic poly(n)-size depth-(d+1) circuits, for every \({d \geq 2}\) ; and the depth of both is tight. Our bounds match Ajtai’s simulation of randomized depth-d circuits by deterministic depth-(d + 2) circuits (Ann. Pure Appl. Logic; ’83) and provide an example where randomization buys resources. To rule out deterministic circuits, we combine Håstad’s switching lemma with an earlier depth-3 lower bound by the author (Computational Complexity 2009). To exhibit randomized circuits, we combine recent analyses by Amano (ICALP ’09) and Brody and Verbin (FOCS ’10) with derandomization. To make these circuits explicit, we construct a new, simple pseudorandom generator that fools tests \({A_1 \times A_2 \times \cdots \times A_{{\rm lg}{n}}}\) for \({A_i \subseteq [n], |A_{i}| = n/2}\) with error 1/n and seed length O(lg n), improving on the seed length \({\Omega({\rm lg}\, n\, {\rm lg}\, {\rm lg}\, n)}\) of previous constructions.     

Fixed-Parameter Tractability of Satisfying Beyond the Number of Variables

We consider a CNF formula F as a multiset of clauses: F={c ₁,…,c _m }. The set of variables of F will be denoted by V(F). Let B _F denote the bipartite graph with partite sets V(F) and F and with an edge between v∈V(F) and c∈F if v∈c or $\bar{v} \in c$ . The matching number ν(F) of F is the size of a maximum matching in B _F . In our main result, we prove that the following parameterization of MaxSat (denoted by (ν(F)+k)-SAT) is fixed-parameter tractable: Given a formula F, decide whether we can satisfy at least ν(F)+k clauses in F, where k is the parameter. A formula F is called variable-matched if ν(F)=|V(F)|. Let δ(F)=|F|?|V(F)| and δ ^?(F)=max _F′?F δ(F′). Our main result implies fixed-parameter tractability of MaxSat parameterized by δ(F) for variable-matched formulas F; this complements related results of Kullmann (IEEE Conference on Computational Complexity, pp. 116–124, 2000) and Szeider (J. Comput. Syst. Sci. 69(4):656–674, 2004) for MaxSat parameterized by δ ^?(F). To obtain our main result, we reduce (ν(F)+k)-SAT into the following parameterization of the Hitting Set problem (denoted by (m?k)-Hitting Set): given a collection $\mathcal{C}$ of m subsets of a ground set U of n elements, decide whether there is X?U such that C∩X≠? for each $C\in \mathcal{C}$ and |X|≤m?k, where k is the parameter. Gutin, Jones and Yeo (Theor. Comput. Sci. 412(41):5744–5751, 2011) proved that (m?k)-Hitting Set is fixed-parameter tractable by obtaining an exponential kernel for the problem. We obtain two algorithms for (m?k)-Hitting Set: a deterministic algorithm of runtime $O((2e)^{2k+O(\log^{2} k)} (m+n)^{O(1)})$ and a randomized algorithm of expected runtime $O(8^{k+O(\sqrt{k})} (m+n)^{O(1)})$ . Our deterministic algorithm improves an algorithm that follows from the kernelization result of Gutin, Jones and Yeo (Theor. Comput. Sci. 412(41):5744–5751, 2011).     

Multiple signal extraction by polynomial filtering

Let {U ₁ ,?,U_n} denote stochastic processes with imbedded signals {u ₁ ,?,u_n} respectively. A mapT is said to extract {u ₁,?,u_n} without distortion provided \(\xi _i = Tu_i , i = 1,...,n\) whereξ _i , i = 1,?,n are chosen apriori. The mapT is said to be optimal whenever it minimizes \(J(T) = E\sum\limits_i {||\Xi _\iota - TU_i ||^2 } \) whereΞ _i , i = i,?,n are suitable stochastic processes. The mapT is called an optimal distortion free signal extractor if it also is causal. This paper analyses polynomic optimal distortion free signal extractors.     

Quantum search algorithm for set operation

The operations of data set, such as intersection, union and complement, are the fundamental calculation in mathematics. It’s very significant that designing fast algorithm for set operation. In this paper, the quantum algorithm for calculating intersection set ${\text{C}=\text{A}\cap \text{B}}$ is presented. Its runtime is ${O\left( {\sqrt{\left| A \right|\times \left| B \right|\times \left|C \right|}}\right)}$ for case ${\left| C \right|\neq \phi}$ and ${O\left( {\sqrt{\left| A \right|\times \left| B \right|}}\right)}$ for case ${\left| C \right|=\phi}$ (i.e. C is empty set), while classical computation needs O (|A| × |B|) steps of computation in general, where |.| denotes the size of set. The presented algorithm is the combination of Grover’s algorithm, classical memory and classical iterative computation, and the combination method decrease the complexity of designing quantum algorithm. The method can be used to design other set operations as well.     

An optimal arc consistency algorithm for a particular case of sequence constraint

The AtMostSeqCard constraint is the conjunction of a cardinality constraint on a sequence of n variables and of n???q?+?1 constraints AtMost u on each subsequence of size q. This constraint is useful in car-sequencing and crew-rostering problems. In van Hoeve et al. (Constraints 14(2):273–292, 2009), two algorithms designed for the AmongSeq constraint were adapted to this constraint with an O(2 ^q n) and O(n ³) worst case time complexity, respectively. In Maher et al. (2008), another algorithm similarly adaptable to filter the AtMostSeqCard constraint with a time complexity of O(n ²) was proposed. In this paper, we introduce an algorithm for achieving arc consistency on the AtMostSeqCard constraint with an O(n) (hence optimal) worst case time complexity. Next, we show that this algorithm can be easily modified to achieve arc consistency on some extensions of this constraint. In particular, the conjunction of a set of m AtMostSeqCard constraints sharing the same scope can be filtered in O(nm). We then empirically study the efficiency of our propagator on instances of the car-sequencing and crew-rostering problems.     

Shorthand Universal Cycles for Permutations

The set of permutations of ??n??={1,??,n} in one-line notation is ??(n). The shorthand encoding of a ₁?a _n ????(n) is a ₁?a _n?1. A shorthand universal cycle for permutations (SP-cycle) is a circular string of length n! whose substrings of length n?1 are the shorthand encodings of ??(n). When an SP-cycle is decoded, the order of ??(n) is a Gray code in which successive permutations differ by the prefix-rotation ?? _i =(1 2 ? i) for i??{n?1,n}. Thus, SP-cycles can be represented by n! bits. We investigate SP-cycles with maximum and minimum ??weight?? (number of ?? _n?1s in the Gray code). An SP-cycle n a n b?n z is ??periodic?? if its ??sub-permutations?? a,b,??,z equal ??(n?1). We prove that periodic min-weight SP-cycles correspond to spanning trees of the (n?1)-permutohedron. We provide two constructions: B(n) and C(n). In B(n) the spanning trees use ??half-hunts?? from bell-ringing, and in C(n) the sub-permutations use cool-lex order by Williams (SODA, 987?C996, 2009). Algorithmic results are: (1)?memoryless decoding of B(n) and C(n), (2)?O((n?1)!)-time generation of B(n) and C(n) using sub-permutations, (3)?loopless generation of B(n)??s binary representation n bits at a time, and (4)?O(n+??(n))-time ranking of B(n)??s permutations where ??(n) is the cost of computing a permutation??s inversion vector. Results (1)?C(4) improve on those for the previous SP-cycle construction D(n) by Ruskey and Williams (ACM Trans. Algorithms 6(3):Art.?45, 2010), which we characterize here using ??recycling??.     

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.     

Minimum Manhattan Network Problem in Normed Planes with Polygonal Balls: A Factor 2.5 Approximation Algorithm

Let ${\mathcal{B}}$ be a centrally symmetric convex polygon of ?² and ‖p?q‖ be the distance between two points p,q∈?² in the normed plane whose unit ball is ${\mathcal{B}}$ . For a set T of n points (terminals) in ?², a ${\mathcal{B}}$ -network on T is a network N(T)=(V,E) with the property that its edges are parallel to the directions of ${\mathcal{B}}$ and for every pair of terminals t _i and t _j , the network N(T) contains a shortest ${\mathcal{B}}$ -path between them, i.e., a path of length ‖t _i ?t _j ‖. A minimum ${\mathcal{B}}$ -network on T is a ${\mathcal{B}}$ -network of minimum possible length. The problem of finding minimum ${\mathcal{B}}$ -networks has been introduced by Gudmundsson, Levcopoulos, and Narasimhan (APPROX’99) in the case when the unit ball ${\mathcal{B}}$ is a square (and hence the distance ‖p?q‖ is the l ₁ or the l _∞-distance between p and q) and it has been shown recently by Chin, Guo, and Sun (Symposium on Computational Geometry, pp. 393–402, 2009) to be strongly NP-complete. Several approximation algorithms (with factors 8, 4, 3, and 2) for the minimum Manhattan problem are known. In this paper, we propose a factor 2.5 approximation algorithm for the minimum ${\mathcal{B}}$ -network problem. The algorithm employs a simplified version of the strip-staircase decomposition proposed in our paper (Chepoi et al. in Theor. Comput. Sci. 390:56–69, 2008, and APPROX-RANDOM, pp. 40–51, 2005) and subsequently used in other factor 2 approximation algorithms for the minimum Manhattan problem.     

Approximating Node-Connectivity Augmentation Problems

We consider the (undirected) Node Connectivity Augmentation (NCA) problem: given a graph J=(V,E _J ) and connectivity requirements $\{r(u,v): u,v \in V\}$ , find a minimum size set I of new edges (any edge is allowed) such that the graph J∪I contains r(u,v) internally-disjoint uv-paths, for all u,v∈V. In Rooted NCA there is s∈V such that r(u,v)>0 implies u=s or v=s. For large values of k=max? _u,v∈V r(u,v), NCA is at least as hard to approximate as Label-Cover and thus it is unlikely to admit an approximation ratio polylogarithmic in k. Rooted NCA is at least as hard to approximate as Hitting-Set. The previously best approximation ratios for the problem were O(kln?n) for NCA and O(ln?n) for Rooted NCA. In this paper we give an approximation algorithm with ratios O(kln?² k) for NCA and O(ln?² k) for Rooted NCA. This is the first approximation algorithm with ratio independent of?n, and thus is a constant for any fixed k. Our algorithm is based on the following new structural result which is of independent interest. If $\mathcal{D}$ is a set of node pairs in a graph?J, then the maximum degree in the hypergraph formed by the inclusion minimal tight sets separating at least one pair in $\mathcal{D}$ is O(? ²), where ? is the maximum connectivity in J of a pair in $\mathcal{D}$ .     

The Equivalence of Sampling and Searching

In a sampling problem, we are given an input x∈{0,1} ⁿ , and asked to sample approximately from a probability distribution \(\mathcal{D}_{x}\) over \(\operatorname{poly} ( n ) \) -bit strings. In a search problem, we are given an input x∈{0,1} ⁿ , and asked to find a member of a nonempty set A _x with high probability. (An example is finding a Nash equilibrium.) In this paper, we use tools from Kolmogorov complexity to show that sampling and search problems are “essentially equivalent.” More precisely, for any sampling problem S, there exists a search problem R _S such that, if \(\mathcal{C}\) is any “reasonable” complexity class, then R _S is in the search version of \(\mathcal{C}\) if and only if S is in the sampling version. What makes this nontrivial is that the same R _S works for every  \(\mathcal{C}\) . As an application, we prove the surprising result that SampP=SampBQP if and only if FBPP=FBQP. In other words, classical computers can efficiently sample the output distribution of every quantum circuit, if and only if they can efficiently solve every search problem that quantum computers can solve.     

A parametric algorithm for semigroup computation on mesh with buses

In this paper, we present a new parametric parallel algorithm for semigroup computation on mesh with reconfigurable buses (MRB). Givenn operands, our parallel algorithm can be performed in $O(2^{(2c^2 + 3c)/(4c + 1)} n^{1/(8c + 2)} )$ , time on a $2^{(c^2 - c)/(8c + 2)} n^{(5c + 1)/(8c + 2)} \times 2^{(c - c^2 )/(8c + 2)} n^{(3c + 1)/(8c + 2)} $ MRB ofn processors, where $0 \leqslant c \leqslant O(\sqrt {\log _2 n} )$ . Specifically, whenc=0, it takes $O(\sqrt n )$ time on the $\sqrt n \times \sqrt n $ MRB and is equal to the result on the mesh-connected computers; whenc=1, it takesO(n ^1/10) time on then ^3/5×n ^2/5 MRB and is equal to the previous result on the mesh-connected computers with segmented multiple buses; whenc=2, it takesO(n ^1/18) time on the 2^1/9 n ^11/18×2^(?1/9) n ^7/18 MRB; when $O(\sqrt {\log _2 n} )$ , it takesO(log₂ n) time and is equal to the previous result on the MRB. Consequently, our results can be viewed as a unification of some best known results on different parallel computational models.     

Average Case Analysis of Moore’s State Minimization Algorithm

We prove that the average complexity of Moore’s state minimization algorithm is $\mathcal {O}(kn\log n)$ , where n is the number of states of the input and k the size of the alphabet. This result holds for a whole family of probabilistic models on automata, including the uniform distribution over deterministic and accessible automata, as well as uniform distributions over classical subclasses, such as complete automata, acyclic automata, automata where each state is final with probability γ∈(0,1), and many other variations.