Chicago Journal of Theoretical Computer Science

Volume 2010 Abstracts

  1. Quantum Boolean Functions by Ashley Montanaro and Tobias J. Osborne.
    January 13, 2010.

    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.

  2. Varieties Generated by Certain Models of Reversible Finite Automata by Marats Golovkins and Jean-Eric Pin.
    June 20, 2010.
    Reversible finite automata with halting states (RFA) were first considered by Ambainis and Freivalds to facilitate the research of Kondacs-Watrous quantum finite automata. In this paper we consider some of the algebraic properties of RFA, namely the varieties these automata generate. Consequently, we obtain a characterization of the Boolean closure of the classes of languages recognized by these models.

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

  3. d-collapsibility is NP-complete for d>=4 by Martin Tancer.
    June 21, 2010.

    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.

  4. On Process Complexity by Adam R. Day.
    June 22, 2010.
    Process complexity is one of the basic variants of Kolmogorov complexity. Unlike plain Kolmogorov complexity, process complexity provides a simple characterization of randomness for real numbers in terms of initial segment complexity. Process complexity was first developed in [11]. Schnorr's defi nition of a process, while simple, can be difficult to work with. In many situations, a preferable de nition of a process is that given in [9]. In this paper we de ne a variant of process complexity based on Levin and Zvonkin's de nition of a process. We call this variant strict process complexity. Strict process complexity retains the main desirable properties of process complexity. In particular, it provides simple characterizations of Martin- Löf random real numbers, and of computable real numbers. However, we will prove that strict process complexity does not agree within an additive constant with Schnorr's original process complexity.

    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.

  5. On the Structure of Classes of Random Graphs by András Faragó.
    June 22, 2010.
    Many different random graph constructions are used to model large real life graphs, i.e., graphs that describe the structure of real systems. Often it is not clear, however, how the strength of the different models compare to each other, e.g., when does it hold that a certain model class contains another. We are particularly interested in random graph models that arise via abstract geometric constructions, motivated by the fact that these graphs can model wireless communication networks. We set up a general framework to compare the strength of random graph models, and present some results about the equality, inequality and proper containment of certain model classes, as well as some open problems.

  6. Edge-Selection Heuristics for Computing Tutte Polynomials by David J. Pearce, Gary Haggard and Gordon Royle.
    June 22, 2010.

    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.

  7. An Efficient Algorithm
    to Test Square-Freeness of Strings
    Compressed by Balanced Straight Line Programs
    by Wataru Matsubara, Shunsuke Inenaga and Ayumi Shinohara.
    June 22, 2010.

    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.

  8. Longest Paths in Planar DAGs in Unambiguous Log-Space by Nutan Limaye, Meena Mahajan and Prajakta Nimbhorkar.
    June 22, 2010.

    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.

  9. Transformation Rules for Z by Mark Utting, Petra Malik and Ian Toyn.
    June 22, 2010.

    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.

  10. Type Checking and Inference
    for Polymorphic and Existential Types
    in Multiple-Quantifier and Type-Free Systems
    by Koji Nakazawa and Makoto Tatsuta.
    June 22, 2010.

    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.

  11. An Algorithm for Affine Approximation of Binary Decision Diagrams by Kevin Henshall, Peter Schachte, Harald Søndergaard and Leigh Whiting.
    June 22, 2010.

    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.

  12. Distributing Frequency-Dependent Data Stream Computations by Sumit Ganguly.
    June 22, 2010.

    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.

  13. Single-Query Learning from Abelian and Non-Abelian Hamming Distance Oracles by David A. Meyer and James Pommersheim.
    August 5, 2010.

    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.

[] Volume 2009 Abstracts
[back] Volume 2010 [back] Published articles
[CJCTS home]

Janos Simon