In this paper we introduce the study of quantum boolean functions, which are unitary operators f whose square is the identity. We describe several generalisations of well-known results in the theory of boolean functions, including quantum property testing; a quantum version of the Goldreich-Levin algorithm for finding the large Fourier coefficients of boolean functions; and two quantum versions of a theorem of Friedgut, Kalai and Naor on the Fourier spectra of boolean functions. In order to obtain one of these generalisations, we prove a quantum extension of the hypercontractive inequality of Bonami, Gross and Beckner.

We also obtain an equality which relates varieties of ordered J-trivial monoids with the variety of R-trivial monoids.

A simplicial complex is d-collapsible if it can be reduced to an empty complex by repeatedly removing (collapsing) a face of dimension at most d-1 that is contained in a unique maximal face. We prove that the algorithmic question whether a given simplicial complex is d-collapsible is NP-complete for d>=4 and polynomial time solvable for d<=2.

As an intermediate step, we prove that d-collapsibility can be recognized by the greedy algorithm for d<=2, but the greedy algorithm does not work for d>=3.

A simplicial complex is d-representable if it is the nerve of a collection of convex sets in R^d. The main motivation for studying d-collapsible complexes is that every d-representable complex is d-collapsible. We also observe that known results imply that d-representability is NP-hard to decide for d >= 2.

One of the basic properties of prex-free complexity is that it is subadditive. Subadditive means that there is some constant d such that for all strings Sigma, Tau, the complexity of SigmaTau (Sigma and Tau concatenated) is less than or equal to the sum of the complexities of Sigma and Tau plus d. A fundamental question about any complexity measure is whether or not it is subadditive. In this paper we resolve this question for process complexity by proving that neither of these process complexities are subadditive.

The Tutte polynomial of a graph, also known as the partition function of the q-state Potts model, is a 2-variable polynomial graph invariant of considerable importance in both combinatorics and statistical physics. It contains several other polynomial invariants, such as the chromatic polynomial and flow polynomial as partial evaluations, and various numerical invariants, such as the number of spanning trees, as complete evaluations. We have developed the most efficient algorithm to-date for computing the Tutte polynomial of a graph. An important component of the algorithm affecting efficiency is the choice of edge to work on at each stage in the computation. In this paper, we present and discuss two edge-selection heuristics which (respectively) give good performance on sparse and dense graphs. We also present experimental data comparing these heuristics against a range of others to demonstrate their effectiveness.

In this paper we study the problem of deciding whether a given compressed string contains a square. A string x is called a square if x = zz and z = u^k implies k = 1 and u = z. A string w is said to be square-free if no substrings of w are squares. However, very little is known for testing square-freeness of a given compress ed string. In this paper, we give an O( max(n^2, n log^2 N))-time O(n^2)-spac e solution to test square-freeness of a given compressed string, where n and N are the size of a given compressed string and the corresponding decompressed string, respectively. Our input strings are compressed by balanced straight line program (BS LP). We remark that BSLP has exponential compression, that is, N = O(2^n). Hence no decompress-then-test approaches can be better than our method in the worst case.

We present a transformation from longest paths to shortest paths in sub-classes of directed acyclic graphs (DAGs). The transformation needs log-space and oracle access to reachability in the same class of graphs. As a corollary, we obtain our main result: Longest Paths in planar DAGs is in UL ∩ co-UL. The result also extends to toroidal DAGs. Further, we show that Longest Paths in max-unique DAGs where the target node is the unique sink is in UL ∩ co-UL.

We show that for planar DAGs with the promise that the number of distinct paths is bounded by a polynomial, counting paths can be done by an unambiguous pushdown automaton equipped with an auxiliary log-space worktape and running in polynomial time. This bound also holds if we want to compute the number of longest paths, or shortest paths, and this number is bounded by a polynomial (irrespective of the total number of paths). Along the way, we show that counting paths in general DAGs can be done by a deterministic pushdown automaton with an auxiliary log-space worktape and running in polynomial time, and hence is in the complexity class LogDCFL, provided the number of paths is bounded by a polynomial and the target node is the only sink.

Z is a formal specication language combining typed set theory, predicate calculus, and a schema calculus. This paper describes an extension of Z that allows transformation and reasoning rules to be written in a Z-like notation. This gives a high-level, declarative, way of specifying transformations of Z terms, which makes it easier to build new Z manipulation tools. We describe the syntax and semantics of these rules, plus some example reasoning engines that use sets of rules to manipulate Z terms. The utility of these rules is demonstrated by discussing two sets of rules. One set denes expansion of Z schema expressions. The other set is used by the ZLive animator to preprocess Z expressions into a form more suitable for animation.

A multiple quantifier is a quantifier having inference rules that introduce or eliminate arbitrary number of quantifiers by one inference. This paper introduces the lambda calculus with negation, conjunction, and multiple existential quantifiers, and the lambda calculus with implication and multiple universal quantifiers. Their type checking and type inference are proved to be undecidable. This paper also shows that the undecidability of type checking and type inference in the type-free-style lambda calculus with negation, conjunction, and existence is reduced to the undecidability of type checking and type inference in the type-free-style polymorphic lambda calculus.

This paper is concerned with the problem of Boolean approximation in the following sense: given a Boolean function class and an arbitrary Boolean function, what is the function's best proxy in the class? Specifically, what is its strongest logical consequence (or envelope) in the class of aff ine Boolean functions. We prove various properties of affine Boolean functions and their representation as ROBDDs. Using these properties, we develop an ROBDD algorithm to find the affine envelope of a Boolean function.

The data streaming model of computation processes a sequence of continuously arriving data in a single-pass over the input using sub-linear space. For efficiency purposes, it is often desirable to perform the computations in a highly distributed fashion, as are currently done in internet applications and sensor networks. The distributed computation is typically performed using a tree-topology, where the nodes are processing elements and the data resides in the leaves of the tree. A large class of interesting and practical functions are symmetric functions (i.e., invariant of the permutation of data at the leaves) of the inputs or their approximations. Flexible distributed processing refers to the class of distributed tree computations whose output remains within a pre-specified tolerance limit regardless of the permutation of the data on the leaves or the topology of the computation tree.

We consider the question: Do efficient flexible distributed computations exist corresponding to data streaming algorithms for computing the same function/approximation? The work by Jan Feldman, S. Muthukrishnan, Anastasios Sidiropoulos, Cli Stein, and Zoya Svitkina. On distributing symmetric streaming computa- tions (SODA 2008) shows that corresponding to any deterministic algorithm that computes a total symmetric function of an input stream, there exists a flexible distributed algorithm for computing the same function of the concatenation of the input streams at the leaves of the tree from left to right. Further, they present resource bounds of the distributed algorithm in terms of the resource bounds of the streaming algorithm. In this paper, we show the existence of efficient flexible distributed algorithms corresponding to a given data stream algorithm that computes an approximation to the function of the frequency vector of the stream. As opposed to the work of Feldman et al., the data stream algorithm need not compute a symmetric function of the input stream.

We study the problem of identifying an n-bit string using a single quantum query to an oracle that computes the Hamming distance between the query and hidden strings. The standard action of the oracle on a response register of dimension r is by powers of the cycle (1 . . . r), all of which, of course, commute. We introduce a new model for the action of an oracle Ñ by general permutations in Sr Ñ and explore how the success probability depends on r and on the map from Hamming distances to permutations. In particular, we prove that when r = 2, for even n the success probability is 1 with the right choice of the map, while for odd n the success probability cannot be 1 for any choice. Furthermore, for small odd n and r = 3, we demonstrate numerically that the image of the optimal map generates a non-abelian group of permutations.