Chicago Journal of Theoretical Computer Science

Volume 2013 Abstracts


  1. Improved Soundness for QMA with Multiple Provers by Alessandro Chiesa and Michael A. Forbes.
    January 13, 2013.

    We present three contributions to the understanding of QMAs with multiple provers :

  2. Few Product Gates but Many Zeroes by Bernd Borchert, Pierre McKenzie and Klaus Reinhardt.
    March 10, 2013.

    A d-gem is a $\{+,-,\times\}$-circuit having very few $\times$-gates and computing from $\{x\}\cup Z$ a univariate polynomial of degree $d$ having $d$ distinct integer roots. We introduce $d$-gems because they offer the remote possibility of being helpful for factoring integers, and because their exiatence for infinitely many $d$ would disprove a form of the Blum-Cucker-Shub-Smale conjecture (strengthened to allow arbitrary constants). A natural step towards a better understanding of the BCSS conjecture thus would be to construct $d$-gems or to rule out their existence. Ruling out $d$-gems for large $d$ is currently totally out of reach. Here the best we can do towards that goal is to prove that skew $2^n$-gems if they exist require $n$ $\{+,-\}$-gates and that skew $2^n$-gems or any $n\geq5$ would provide new solutions to the Prouhet-Tarry-Escott problem in number theory (skew meaning the further restriction that each $\{+,-\}$-gate merely adds an integer to a polynomial). In the opposite direction, here we do manage to construct skew $d$-gems for several values of $d$ up to $55$.

  3. A Turing Machine Resisting Isolated Bursts Of Faults by Ilir Çapuni and Peter Gács.
    March 27, 2013.

    We consider computations of a Turing machine under noise that causes violations of the transition function. Given an upper bound \( \beta \) on the size of bursts of faults, we construct a Turing machine \( M(\beta) \) subject to faults that can simulate any fault-free machine under the condition that the time between bursts is lowerbounded by \( O(\beta^2) \).

  4. Quantum Adversary (Upper) Bound by Shelby Kimmel
    April 5, 2013

    We describe a method to upper bound the quantum query complexity of Boolean formula evaluation problems, using fundamental theorems about the general adversary bound. This nonconstructive method can give an upper bound on query complexity without producing an algorithm. For example, we describe an oracle problem which we prove (non-constructively) can be solved in $O(1)$ queries, where the previous best quantum algorithm uses a polylogarithmic number of queries. We then give an explicit $O(1)$-query algorithm for this problem based on span programs.

  5. Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic by Eric Allender, George Davie, Luke Friedman, Samuel B. Hopkins, and Iddo Tzameret}<
    April 23, 2013

    Can complexity classes be characterized in terms of efficient reducibility to the (undecidable) set of Kolmogorov-random strings? Although this might seem improbable, a series of papers has recently provided evidence that this may be the case. In particular, it is known that there is a class of problems $\cal C$ defined in terms of polynomial-time truth-table reducibility to $RK$ (the set of Kolmogorov-random strings) that lies between $BPP$ and $PSPACE$.

    The results in this paper were obtained, as part of an investigation of whether this upper bound can be improved, to show $$ BPP \subseteq {\cal C} \subseteq PSPACE \cap Ppoly. \quad\quad\quad(*)$$ In fact, we conjecture that ${\cal C} = BPP = Polytime$, and we close this paper with a discussion of the possibility this might be an avenue for trying to prove the equality of $BPP$ and $Polytime$.

    In this paper, we present a collection of true statements in the language of arithmetic, (each provable in ZF) and show that if these statements can be proved in certain extensions of Peano arithmetic ($PA$), then (*) holds. Although it was subsequently proved (by Allender, Buhrman, Friedman and Loff) that infinitely many of these statements are, in fact, independent of those extensions of $PA$, we present these results in the hope that related ideas may yet contribute to a proof of ${\cal C} = BPP$, and because this work did serve as a springboard for subsequent work in the area.

  6. The non-adaptive query complexity of testing k-parities by Harry Buhrman, David García-Soriano, Arie Matsliah, and Ronald de Wolf

    We prove tight bounds of $\Theta(k \log k)$ queries for non-adaptively testing whether a function $f: \{ 0,1 \}^n \to \{ 0,1 \}$ is a $k$-parity or far from any $k$-parity. The lower bound combines a recent method of Blais, Brody and Matulef to get lower bounds for testing from communication complexity with an $\Omega(k\log k)$ lower bound for the one-way communication complexity of $k$-disjointness.

  7. Interactive proofs with competing teams of no-signaling provers by Gus Gutoski

    This paper studies a generalization of multi-prover interactive proofs in which a verifier interacts with two competing teams of provers: one team attempts to convince the verifier to accept while the other attempts to convince the verifier to reject. Each team consists of two provers who jointly implement a no-signaling strategy. No-signaling strategies are a curious class of joint strategy that cannot in general be implemented without communication between the provers, yet cannot be used as a black box to establish communication between them. Attention is restricted in this paper to two-turn interactions in which the verifier asks questions of each of the four provers and decides whether to accept or reject based on their responses. We prove that the complexity class of decision problems that admit two-turn interactive proofs with competing teams of no-signaling provers is a subset of PSPACE. This upper bound matches existing PSPACE lower bounds on the following two disparate and weaker classes of interactive proof:

    Our result implies that the complexity of these two models is unchanged by the addition of a second competing team of no-signaling provers in the first case and by the addition of a second no-signaling prover to each team in the second case. Moreover, our result unifies and subsumes prior PSPACE upper bounds on these classes.
  8. Simpler semidefinite programs for completely bounded norms by John Watrous

    The completely bounded trace and spectral norms, for finite-dimensional spaces, are known to be efficiently expressible by semidefinite programs (J. Watrous, Theory of Computing 5: 11, 2009). This paper presents two new, and arguably simpler, semidefinite programming formulations of these norms.

  9. Complexity of the homomorphism extension problem in the random case by Alexandr Kazda

    We prove that if A is a large random relational structure (with at least one relation of arity at least 2) then the homomorphism extension problem Ext(A) is almost surely NP-complete.

  10. On the complexity of solving linear congruences and computing nullspaces modulo a constant by Niel de Beaudrap

    We consider the problems of determining the feasibility of a linear congruence, producing a solution to a linear congruence, and finding a spanning set for the nullspace of an integer matrix, where each problem is considered modulo an arbitrary constant $k \geqslant 2$. These problems are known to be complete for the logspace modular counting classes $\mathrm{Mod_k L = coMod_k L}$ in the special case when $k$ is prime (Buntrock et al 1992). By considering variants of standard logspace function classes -- related to $\mathrm{\#L}$ and functions computable by $\mathrm{UL}$ machines, but which only characterize the number of accepting paths modulo $k$ -- we show that these problems of linear algebra are also complete for $\mathrm{coMod_k L}$ for any constant $k \geqslant 2$.

    Our results are obtained by defining a class of functions $\mathrm{FUL_k}$ which are low for $\mathrm{Mod_k L}$ and $\mathrm{coMod_k L}$ for $k \geqslant 2$, using ideas similar to those used in the case of k prime in (Buntrock et al 1992) to show closure of $\mathrm{Mod_k L}$ under $\mathrm{NC^1}$ reductions (including $\mathrm{Mod_k L}$ oracle reductions). In addition to the results above, we briefly consider the relationship of the class $\mathrm{FUL_k}$ for arbitrary moduli $k$ to the class $\mathrm{F \cdot coMod_k L}$ of functions whose output symbols are verifiable by $\mathrm{coMod_k L}$ algorithms; and consider what consequences such a comparison may have for oracle closure results of the form $\mathrm{Mod_k L^{Mod_k L} = Mod_k L}$ for composite $k$.

  11. Coherent state exchange in multi-prover quantum interactive proof systems by Debbie Leung, Ben Toner, and John Watrous

    We show that any number of parties can coherently exchange any one pure quantum state for another, without communication, given prior shared entanglement. Two applications of this fact to the study of multi-prover quantum interactive proof systems are given. First, we prove that there exists a one-round two-prover quantum interactive proof system for which no finite amount of shared entanglement allows the provers to implement an optimal strategy. More specifically, for every fixed input string, there exists a sequence of strategies for the provers, with each strategy requiring more entanglement than the last, for which the probability for the provers to convince the verifier to accept approaches one. It is not possible, however, for the provers to convince the verifier to accept with certainty with a finite amount of shared entanglement. The second application is a simple proof that multi-prover quantum interactive proofs can be transformed to have near-perfect completeness by the addition of one round of communication.

  12. A Lower Bound for Fourier Transform Computation in a Linear Model Over 2x2 Unitary Gates Using Matrix Entropy by Nir Ailon

    Obtaining a non-trivial (super-linear) lower bound for computation of the Fourier transform in the linear circuit model has been a long standing open problem. All lower bounds so far have made strong restrictions on the computational model. One of the best known results, by Morgenstern from 1973, provides an $\Omega(n \log n)$ lower bound for the unnormalized FFT when the constants used in the computation are bounded. The proof uses a potential function related to a determinant. The determinant of the unnormalized Fourier transform is $n^{n/2}$, and thus by showing that it can grow by at most a constant factor after each step yields the result. This classic result, however, does not explain why the normalized Fourier transform, which has a unit determinant, should take $\Omega(n\log n)$ steps to compute. In this work we show that in a layered linear circuit model restricted to unitary $2\times 2$ gates, one obtains an $\Omega(n\log n)$ lower bound. The well known FFT works in this model. The main conclusion from this work is that a potential function that might eventually help proving the $\Omega(n\log n)$ conjectured lower bound for computation of Fourier transform is not related to matrix determinant, but rather to a notion of matrix entropy.

  13. Graph Pricing Problem on Bounded Treewidth, Bounded Genus and k-Partite Graphs by Parinya Chalermsook, Shiva Kintali, Richard J. Lipton, and Danupon Nanongkai

    Consider the following problem. A seller has infinite copies of $n$ products represented by nodes in a graph. There are $m$ consumers, each has a budget and wants to buy two products. Consumers are represented by weighted edges. Given the prices of products, each consumer will buy both products she wants, at the given price, if she can afford to. Our objective is to help the seller price the products to maximize her profit.

    This problem is called graph vertex pricing (GVP) problem and has resisted several recent attempts despite its current simple solution. This motivates the study of this problem on special classes of graphs. In this paper, we study this problem on a large class of graphs such as graphs with bounded treewidth, bounded genus and $k$-partite graphs.

    We show that there exists an FPTAS for GVP on graphs with bounded treewidth. This result is also extended to an FPTAS for the more general single-minded pricing problem. On bounded genus graphs we present a PTAS and show that GVP is NP-hard even on planar graphs.

    We study the Sherali-Adams hierarchy applied to a natural Integer Program formulation that $(1+\epsilon)$-approximates the optimal solution of GVP. Sherali-Adams hierarchy has gained much interest recently as a possible approach to develop new approximation algorithms. We show that, when the input graph has bounded treewidth or bounded genus, applying a constant number of rounds of Sherali-Adams hierarchy makes the integrality gap of this natural LP arbitrarily small, thus giving a $(1+\epsilon)$-approximate solution to the original GVP instance.

    On $k$-partite graphs, we present a constant-factor approximation algorithm. We further improve the approximation factors for paths, cycles and graphs with degree at most three.

  14. Testing Booleanity and the Uncertainty Principle by Tom Gur and Omer Tamuz

    Let $f:\{-1,1\}^n \to$ R be a real function on the hypercube, given by its discrete Fourier expansion, or, equivalently, represented as a multilinear polynomial. We say that it is Boolean if its image is in $\{-1,1\}$.

    We show that every function on the hypercube with a sparse Fourier expansion must either be Boolean or far from Boolean. In particular, we show that a multilinear polynomial with at most $k$ terms must either be Boolean, or output values different than $-1$ or $1$ for a fraction of at least $2/(k+2)^2$ of its domain.

    It follows that given oracle access to $f$, together with the guarantee that its representation as a multilinear polynomial has at most $k$ terms, one can test Booleanity using $O(k^2)$ queries. We show an $\Omega(k)$ queries lower bound for this problem.

    Our proof crucially uses Hirschman's entropic version of Heisenberg's uncertainty principle.


[] Volume 2012 Abstracts
[back] Volume 2013 [back] Published articles
[CJCTS home]


Janos Simon