Search

We develop upper and lower bound arguments for counting acceptance modes of communication protocols. A number of separation results for counting communication complexity classes is established. This extends the investigation of the complexity of communication between two processors in terms of complexity classes initiated by Babai et al. (Proceedings of the 27th IEEE FOCS, 1986, pp. 337–347) and continued in several papers (e.g., J. Comput. System Sci. 41 (1990) 402; 49 (1994) 247; Proceedings of the 36th IEEE FOCS, 1995, pp. 6–15).In particular, it will be shown that for all pairs of distinct primes p and q the communication complexity classes MODpPcc and MODqPcc are incomparable with regard to inclusion. The same is true for PPcc and MODmPcc, for any number m⩾2. Moreover, non-determinism and modularity are incomparable to a large extend. On the other hand, if m=p1ℓ1·…·prℓr is the prime decomposition of m⩾2, then the complexity classes MODmPcc and MODρ(m)Pcc coincide, where ρ(m)=p1·…·pr.The results are obtained by characterizing the modular and probabilistic communication complexity in terms of the minimum rank of matrices ranging over certain equivalence classes. Methods from algebra and analytic geometry are used.This paper is the completely revised and strongly extended version of the conference paper Damm et al. (Proc. 9th Ann. STACS, pp. 281–291) where a subset of the results was presented. [Copyright &y& Elsevier]

A number of recent papers on approximation algorithms have used the square roots of unity, −1 and 1, to represent binary decision variables for problems in combinatorial optimization, and have relaxed these to unit vectors in real space using semidefinite programming in order to obtain near optimum solutions to these problems. In this paper, we consider using the cube roots of unity, 1, ei2π/3, and ei4π/3, to represent ternary decision variables for problems in combinatorial optimization. Here the natural relaxation is that of unit vectors in complex space. We use an extension of semidefinite programming to complex space to solve the natural relaxation, and use a natural extension of the random hyperplane technique introduced by the authors in Goemans and Williamson (J. ACM 42 (1995) 1115–1145) to obtain near-optimum solutions to the problems. In particular, we consider the problem of maximizing the total weight of satisfied equations xu−xv≡c (mod 3) and inequations xu−xv≢c (mod 3), where xu∈{0,1,2} for all u. This problem can be used to model the Max-3-Cut problem and a directed variant we call Max-3-Dicut. For the general problem, we obtain a 0.793733-approximation algorithm. If the instance contains only inequations (as it does for Max-3-Cut), we obtain a performance guarantee of 7/12+3/4π2arccos2(−1/4)−ϵ>0.836008. This compares with proven performance guarantees of 0.800217 for Max-3-Cut (by Frieze and Jerrum (Algorithmica 18 (1997) 67–81) and 1/3+3/4π2arccos2(−1/4)−ϵ>0.836008. This compares with proven performance guarantees of 0.800217 for Max-3-Cut (by Frieze and Jerrum (Algorithmica 18 (1997) 67–81) and 1/3 arccos2(−1/4)−ϵ>0.836008. This compares with proven performance guarantees of 0.800217 for Max-3-Cut (by Frieze and Jerrum (Algorithmica 18 (1997) 67–81) and 1/3+10−8 for the general problem (by Andersson et al. (J. Algorithms 39 (2001) 162–204)). It matches the guarantee of 0.836008 for Max-3-Cut found independently by de Klerk et al. (On approximate graph colouring and Max-k-Cut algorithms based on the ϑ-function, Manuscript, October 2000). We show that all these algorithms are in fact equivalent in the case of Max-3-Cut, and that our algorithm is the same as that of Andersson et al. in the more general case. [Copyright &y& Elsevier]

Unreliable failure detectors are oracles that give information about process failures. Chandra and Toueg were first to study such failure detectors for distributed systems, and they identified a number that enabled the solution of the Consensus problem in asynchronous distributed systems. This paper focuses on two of these, denoted S (strong) and ⋄S (eventually strong). The characteristics of a given unreliable failure detector are usually described by its completeness and accuracy properties. Completeness is a requirement on the actual detection of failures, while accuracy limits the mistakes a failure detector can make. Let the scope of the accuracy property of an unreliable failure detector be the minimum number (k) of processes that may not erroneously suspect a correct process to have crashed. Usual failure detectors implicitly consider a scope equal to n (the total number of processes). Accuracy properties with limited scope give rise to the classes of failure detectors that we call Sk and ⋄Sk. This paper investigates the following question: “Given Sk and ⋄Sk, under which condition is it possible to transform their failure detectors into their counterparts with unlimited accuracy, i.e., S and ⋄S?”. The paper answers this question in the following way. It first presents a particularly simple protocol that realizes such a transformation when f (where f is the maximum number of processes that may crash). Then, it shows that there is no reduction protocol when f⩾k. [Copyright &y& Elsevier]

Abstract: Quantum finite automata have been studied intensively since their introduction in late 1990s as a natural model of a quantum computer working with finite-dimensional quantum memory space. This paper seeks their direct application to interactive proof systems in which a mighty quantum prover communicates with a quantum-automaton verifier through a common communication cell. Our quantum interactive proof systems are juxtaposed to Dwork–Stockmeyer''s classical interactive proof systems whose verifiers are two-way probabilistic finite automata. We demonstrate strengths and weaknesses of our systems by studying how various restrictions on the behaviors of quantum-automaton verifiers affect the power of quantum interactive proof systems. [Copyright &y& Elsevier]

Abstract: In Gori [An abstract interpretation framework to reason on finite failure and other properties of finite and infinite computations, Theoret. Comput. Sci. 290(1) (2003) 863–936] a new fixpoint semantics which correctly models finite failure has been defined. This semantics is And-compositional, compositional w.r.t. instantiation and is based on a co-continuous operator. Based on this fixpoint semantics a new inductive method able to verify a program w.r.t. the property of finite failure can be defined. In this paper we show how Ferrand''s approach, using both a least fixpoint and greatest fixpoint semantics, can be adapted to finite failure. The verification method is not effective. Therefore, we consider an approximation from above and an approximation from below of our semantics, which give two different finite approximations. These approximations are used for effective program verification. [Copyright &y& Elsevier]

Abstract: Bryant [On the complexity of VLSI implementations and graph representations of boolean functions with applications to integer multiplication, IEEE Trans. Comput. 40 (1991) 205–213] has shown that any for the function , i.e. the middle bit of the n-bit multiplication, requires at least nodes. In this paper a stronger lower bound of essentially is proven by a new technique, using a universal family of hash functions. As a consequence, one cannot hope anymore to verify e.g. 128-bit multiplication circuits using -techniques because the representation of the middle bit of such a multiplier requires more than -nodes. Further, a first non-trivial upper bound of for the -size of is provided. [Copyright &y& Elsevier]

Abstract: A mere bounded number of random bits judiciously employed by a probabilistically correct algorithmic coordinator is shown to increase the power of learning to coordinate compared to deterministic algorithmic coordinators. Furthermore, these probabilistic algorithmic coordinators are provably not characterized in power by teams of deterministic ones. An insightful, enumeration technique based, normal form characterization of the classes that are learnable by total computable coordinators is given. These normal forms are for insight only since it is shown that the complexity of the normal form of a total computable coordinator can be infeasible compared to the original coordinator. Montagna and Osherson showed that the competence class of a total coordinator cannot be strictly improved by another total coordinator. It is shown in the present paper that the competencies of any two total coordinators are the same modulo isomorphism. Furthermore, a completely effective, index set version of this competency isomorphism result is given, where all the coordinators are total computable. We also investigate the competence classes of total coordinators from the points of view of topology and descriptive set theory. [Copyright &y& Elsevier]

Resource-bounded dimension is a complexity-theoretic extension of classical Hausdorff dimension introduced by Lutz (in: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000, pp. 158–169) in order to investigate the fractal structure of sets that have resource-bounded measure 0. For example, while it has long been known that the Boolean circuit-size complexity class SIZE(α2n/n) has measure 0 in ESPACE for all 0⩽α⩽1, we now know that SIZE(α2n/n) has dimension α in ESPACE for all 0⩽α⩽1. The present paper furthers this program by developing a natural hierarchy of “rescaled” resource-bounded dimensions. For each integer i and each set X of decision problems, we define the ith-order dimension of X in suitable complexity classes. The zeroth-order dimension is precisely the dimension of Hausdorff (Math. Ann. 79 (1919) 157–179) and Lutz (2000). Higher and lower orders are useful for various sets X. For example, we prove the following for 0⩽α⩽1 and any polynomial q(n)⩾n2: [Copyright &y& Elsevier]

Parikh matrices recently introduced give much more information about a word than just the number of occurrences of each letter. In this paper we introduce the closely related notion of a subword history and obtain a sequence of general results: elimination of products, decidability of equivalence, and normal form. We also investigate overall methods for proving the validity of such results. A general inequality of “Cauchy type” for subword occurrences is established. [Copyright &y& Elsevier]

Consider a forest of k trees and n nodes together with a (partial) function σ mapping leaves of the trees to non-root nodes of other trees. Define the shadow of a leaf ℓ to be the subtree rooted at σ(ℓ). The shadow problem asks whether there is a set S of leaves exactly one from each tree such that none of these leaves lies in the shadow of another leaf in S. This graph theoretical problem as shown in Franco et al. (Discrete Appl. Math. 96 (1999) 89) is equivalent to the falsifiability problem for pure implicational Boolean formulas over n variables with k occurences of the constant false as introduced in: Heusch J. Wiedermann, P. Hajek (Eds.), Proceedings of the Twentieth International Symposium on Mathematical Foundations of Computer Science (MFCS’95), Prague, Czech Republic, Lecture Notes in Computer Science, Vol. 969, Springer, Berlin, 1995, pp. 221–226, where its NP-completeness is shown for arbitrary values of k and a time bound of O(nk) for fixed k was obtained. In Franco et al. (1999) this bound is improved to O(n2kk) showing the problem''s fixed parameter tractability (Congr. Numer. 87 (1992) 161). In this paper the bound O(n33k) is achieved by dynamic programming techniques thus significantly improving the fixed parameter part. [Copyright &y& Elsevier]

In this paper, a complex-valued wavelet network (CWN) is proposed. The network has complex inputs, outputs, connection weights, dilation and translation parameters, but the nonlinearity of the hidden nodes remains a real-valued function (real-valued wavelet function). This kind of network is able to approximate an arbitrary nonlinear function in complex multi-dimensional space, and it provides a powerful tool for nonlinear signal processing involving complex signals. A complex algorithm is derived for the training of the proposed CWN. A numerical example on nonlinear communication channel identification is presented for illustration. [Copyright &y& Elsevier]

In this paper we introduce a new notion of traversal sequences that we call exploration sequences. Exploration sequences share many properties with the traversal sequences defined in Aleliunas et al. (Proceedings on the 20th Annual Symposium of Foundations of Computer Science, 1979, pp. 218–223), but they also exhibit some new properties. In particular, they have an ability to backtrack, and their random properties are robust under choice of the probability distribution on labels.Further, we present simple constructions of polynomial-length universal exploration sequences for some previously studied classes of graphs (e.g., 2-regular graphs, cliques, expanders), and we also present universal exploration sequences for trees. These constructions do not obey previously known lower bounds on the length of universal traversal sequences; thus, they highlight another difference between exploration and traversal sequences. [Copyright &y& Elsevier]

The main mathematical result of this paper may be stated as follows: Given a matrix M∈{−1,1}n×n and any matrix M˜∈Rn×n such that sign(M˜i,j)=Mi,j for all i,j, then rank(M˜)⩾n/||M||. Here ||M|| denotes the spectral norm of the matrix M.This implies a general lower bound on the complexity of unbounded error probabilistic communication protocols. As a simple consequence, we obtain the first linear lower bound on the complexity of unbounded error probabilistic communication protocols for the functions defined by Hadamard matrices. This solves a long-standing open problem stated by Paturi and Simon (J. Comput. System Sci. 33 (1986) 106).We also give an upper bound on the margin of any embedding of a concept class in half spaces. Such bounds are of interest to problems in learning theory. [Copyright &y& Elsevier]

In this paper, we introduce a new model for computing polynomials—a depth-2 circuit with a symmetric gate at the top and plus gates at the bottom, i.e. the circuit computes a symmetric function in linear functions—Smd(ℓ1,ℓ2,…,ℓm) (Smd is the dth elementary symmetric polynomial in m variables, and the ℓi''s are linear functions). We refer to this model as the symmetric model. This new model is related to standard models of arithmetic circuits, especially to depth-3 circuits. In particular, we show that in order to improve the results of Shpilka and Wigderson (in: CCC, Vol. 14, 1999, pp. 87–96), i.e. to prove super-quadratic lower bounds for depth-3 circuits, one must first prove a super-linear lower bound for the symmetric model.We prove two non-trivial linear lower bounds for our model. The first lower bound is for computing the determinant, and the second is for computing the sum of two monomials. The main technical contribution relates the maximal dimension of linear subspaces on which Smd vanishes to lower bounds in the symmetric model. In particular, we show that an answer of the following problem (which is very natural, and of independent interest) will imply lower bounds on symmetric circuits for many polynomials:What is the maximal dimension of a linear subspace of Cm, on which Smd vanishes?We give two partial solutions to the problem above, each enables us to prove a different lower bound. Using our techniques we also prove quadratic lower bounds for depth-3 circuits computing the elementary symmetric polynomials of degree αn (where 0<α<1 is a constant), thus extending the result of Shpilka and Wigderson (in: CCC, Vol. 14, 1999, pp. 87–96). These are the best lower bounds known for depth-3 circuits over fields of characteristic zero. [Copyright &y& Elsevier]