Chicago Journal of Theoretical Computer Science

Volume 2018 Abstracts

  1. On monotone circuits with local oracles and clique lower bounds by Jan Krajíček and Igor C. Oliveira
    March 25, 2018

    We investigate monotone circuits with local oracles [Krajíček 2016] i.e., circuits containing additional inputs $y_i = y_i(\vec{x})$ that can perform unstructured computations on the input string $\vec{x}$. Let $\mu \in [0,1]$ be the locality of the circuit, a parameter that bounds the combined strength of the oracle functions $y_i(\vec{x})$, and $U_{n,k}, V_{n,k} \subseteq \{0,1\}^m$ be the set of $k$-cliques and the set of complete $(k-1)$-partite graphs, respectively (similarly to [Razborov, 1985]).} Our results can be informally stated as follows.

    The second result, which concerns monotone circuits with restricted oracles, extends and provides a matching upper bound for the exponential lower bounds on the monotone circuit size complexity of $k$-clique obtained in [Alon and Boppana, 1987].
  2. Local Maxima and Improved Exact Algorithm for MAX-2-SAT by Matthew B. Hastings
    June 19, 2018

    Given a MAX-2-SAT instance, we define a local maximum to be an assignment such that changing any single variable reduces the number of satisfied clauses. We consider the question of the number of local maxima that an instance of MAX-2-SAT can have. We give upper bounds in both the sparse and nonsparse case, where the sparse case means that ther\ e is a bound d on the average number of clauses involving any given variable. The bounds in the nonsparse case are tight up to polylogarithmic factors, while in the sparse case the bounds are tight up to a multiplicative factor in d for large d. Additionally, we generalize to the question of assignments which are maxima up to changing f k> 1 variables simultaneously; in this case, we give explicit constructions with large (in a sense explained below) numbers of such maxima in the spar\ se case. The basic idea of the upper bound proof is to consider a random assignment to some subset of the \ variables and determine the probability that some fraction of the remaining variables can be fixed \ without considering interactions between them. The bounded results hold in the case of weighted MAX-2-SAT as well. Using this technique and combining with ideas from [Golovnev and Kutzkov], we find an algorithm f\ or weighted MAX-2-SAT which is faster for large d than previous algorithms which use polynomial space; this algorithm does require additio\ nal bounds on maximum weights and degree.

  3. Universal Locally Testable Codes by Oded Goldreich and Tom Gur
    August 7, 2018

    We initiate a study of ``universal locally testable codes'' (ULTCs). These codes admit local tests for membership in numerous possible subcodes, allowing for testing properties of the encoded message. More precisely, a ULTC $C:\{0,1\}^k \to \{0,1\}^n$ for a family of functions $\mathcal{F} = \left\{ f_i : \{0,1\}^k \to \{0,1\} \right\}_{i \in [M]}$ is a code such that for every $\ i \in [M]$ the subcode $\{ C(x) \: : \: f_i(x) = 1 \}$ is locally testable. We show a ``canonical' $O(1)$-local ULTC of length $\tilde O(M\cdot s)$ for any family $\mathcal{F}$ of $M$ functions such that every $f\in\mathcal{F}$ can be computed by a circuit of size $s$, and establish a lower bound of the form $n\ =M^{1/O(k)}$, which can be strengthened to $n=M^{\Omega(1)}$ for any $\mathcal{F}$ suc\ h that every $f,f' \in\mathcal{F}$ disagree on a constant fraction of their domain

  4. Extended Nonlocal Games from Quantum-Classical Games by Vincent Russo and John Watrous
    August 7, 2018

    Several variants of nonlocal games have been considered in the study of quantum entanglement and nonlocality. This paper concerns two of these variants, called quantum-classical games and extended nonlocal games. We give a construction of an extended nonlocal game from any quantum-classical game that allows one to translate certain facts concerning quantum-classical games to extended nonlocal games. In particular, based on work of Regev and Vidick, we conclude that there exist extended nonlocal games for which no finite-dimensional entangled strategy can be optimal. While this conclusion is a direct consequence of recent work of Slofstra, who proved a stronger, analogous result for ordinary (non-extended) nonlocal games, the proof based on our construction is considerably simpler, and the construction itself might potentially have other applications in the study of entanglement and nonlocality.

  5. The border support rank of two-by-two matrix multiplication is seven by Markus Blaeser, Matthias Christandl, and Jeroen Zuiddam
    August 28, 2018

    We show that the border support rank of the tensor corresponding to two-by-two matrix multiplication is seven over the complex numbers. We do this by constructing two polynomials that vanish on all complex tensors with format four-by-four-by-four and border rank at most six, but that do not vanish simultaneously on any tensor with the same support as the two-by-two matrix multiplication tensor. This extends the work of Hauenstein, Ikenmeyer, and Landsberg. We also give two proofs that the support rank of the two-by-two matrix multiplication tensor is seven over any field: one proof using a result of De Groote saying that the decomposition of this tensor is unique up to sandwiching, and another proof via the substitution method. These results answer a question asked by Cohn and Umans. Studying the border support rank of the matrix multiplication tensor is relevant for the design of matrix multiplication algorithms, because upper bounds on the border support rank of the matrix multiplication tensor lead to upper bounds on the computational complexity of matrix multiplication, via a construction of Cohn and Umans. Moreover, support rank may be interpreted as a quantum communication complexity measure.

  6. 6. Finding Significant Fourier Coefficients: Clarifications, Simplifications, Applications and Limitations by Steven D. Galbraith, Joel Laity and Barak Shani
  7. December 20, 2018

    Ideas from Fourier analysis have been used in cryptography for the last three decades. Akavia, Goldwasser and Safra unified some of these ideas to give a complete algorithm that finds significant Fourier coefficients of functions on any finite abelian group. Their algorithm stimulated a lot of interest in the cryptography community, especially in the context of ``bit security''. This paper attempts to be a friendly and comprehensive guide to the tools and results in this field. The intended readership is cryptographers who have heard about these tools and seek an understanding of their mechanics and their usefulness and limitations. A compact overview of the algorithm is presented with emphasis on the ideas behind it. We show how these ideas can be extended to a ``modulus-switching'' variant of the algorithm. We survey some applications of this algorithm, and explain that several results should be taken in the right context. In particular, we point out that some of the most important bit security problems are still open. Our original contributions include: a discussion of the limitations on the usefulness of these tools; an answer to an open question about the modular inversion hidden number problem.

[] Volume 2017 Abstracts
[back] Volume 2018 [back] Published articles
[CJCTS home]

Janos Simon