Bourgain and Yehudayoff recently constructed $O(1)$-monotone bipartite expanders. By combining this result with a generalisation of the unraveling method of Kannan, we construct 3-monotone bipartite expanders, which is best possible. We then show that the same graphs admit 3-page book embeddings, 2-queue layouts, 4-track layouts, and have simple thickness 2. All these results are best possible.

Motivated by (and using tools from) communication complexity, we investigate the relationship between the following two ranks of a $0$-$1$ matrix: its nonnegative rank and its binary rank (the $\log$ of the latter being the unambiguous nondeterministic communication complexity). We prove that for partial $0$-$1$ matrices, there can be an exponential separation. For total $0$-$1$ matrices, we show that if the nonnegative rank is at most $3$ then the two ranks are equal, and we show a separation by exhibiting a matrix with nonnegative rank $4$ and binary rank $5$, as well as a family of matrices for which the binary rank is $4/3$ times the nonnegative rank.

The VP versus VNP question, introduced by Valiant, is probably the most important open question in algebraic complexity theory. Thanks to completeness results, a variant of this question, VBP versus VNP, can be succinctly restated as asking whether the permanent of a generic matrix can be written as a determinant of a matrix of polynomially bounded size. Strikingly, this restatement does not mention any notion of computational model. To get a similar restatement for the original and more fundamental question, and also to better understand the class itself, we need a complete polynomial for VP. Ad hoc constructions yielding complete polynomials were known, but not natural examples in the vein of the determinant. We give here several variants of natural complete polynomials for VP, based on the notion of graph homomorphism polynomials.

The class QMA plays a fundamental role in quantum complexity theory and it has found surprising connections to condensed matter physics and in particular in the study of the minimum energy of quantum systems. In this paper, we further investigate the class QMA and its related class QCMA by asking what makes quantum witnesses potentially more powerful than classical ones. We provide a definition of a new class, SQMA, where we restrict the possible quantum witnesses to the "simpler" subset states, i.e. a uniform superposition over the elements of a subset of $n$-bit strings. Surprisingly, we prove that this class is equal to QMA, hence providing a new characterisation of the class QMA. We also prove the analogous result for QMA(2) and describe a new complete problem for QMA and a stronger lower bound for the class $\mathrm{QMA_1 }$

First, we consider the problem of deciding whether a nonlocal game admits a perfect {finite dimensional} entangled strategy that uses projective measurements on a maximally entangled shared state. Via a polynomial-time Karp reduction, we show that independent set games are the hardest instances of this problem. Secondly, we show that if every independent set game whose entangled value is equal to one admits a perfect entangled strategy, then the same holds for all symmetric synchronous games. Finally, we identify combinatorial lower bounds on the classical and entangled values of synchronous games in terms of variants of the independence number of appropriate graphs. Our results suggest that independent set games might be representative of all nonlocal games when dealing with questions concerning perfect entangled strategies.

In this paper, we study the structure of set-multilinear arithmetic circuits and set-multilinear branching programs with the aim of showing lower bound results. We define some natural restrictions of these models for which we are able to show lower bound results. Some of our results extend existing lower bounds, while others are new and raise open questions. Specifically, our main results are the following:

• We observe that set-multilinear arithmetic circuits can be transformed into shallow set-multilinear circuits efficiently, following [VSBR83, RY08]. Hence, polynomial size set-multilinear circuits have quasi-polynomial size set-multilinear branching programs.
• We show that k-narrow set-multilinear ABPs computing the Permanent polynomial $PER_n$ (or determinant $DET_n$) require $2^{\Omega(k)}$ size. As a consequence, we show that sum of $r$ read-once oblivious ABPs computing $PER_n$ requires size $2^{\Omega(\frac{n}{r})}$.
• We also show that set-multilinear branching programs are exponentially more powerful than interval multilinear circuits (where the index sets for each gate are restricted to be an interval w.r.t. some ordering), assuming the sum-of-squares conjecture. This further underlines the power of set-multilinear branching programs.
• Finally, we show exponential lower bounds for set-multilinear circuits with restrictions on the number of parse trees of monomials and prove exponential lower bound results.

We prove a local central limit theorem for the sum of one-dimensional discrete Gaussians in $n$-dimensional space. In more detail, we analyze the distribution of $\sum_{i=1}^m v_i \mathbf{x}_i$ where $\mathbf{x}_1,\ldots,\mathbf{x}_m$ are fixed vectors from some lattice $\mathcal{L} \subset \mathbb{R}^n$ and $v_1,\ldots,v_m$ are chosen independently from a discrete Gaussian distribution over $\mathbb{Z}$. We show that under a natural constraint on $\mathbf{x}_1,\ldots,\mathbf{x}_m$, if the $v_i$ are chosen from a wide enough Gaussian, the sum is statistically close to a discrete Gaussian over $\mathcal{L}$. We also analyze the case of $\mathbf{x}_1,\ldots,\mathbf{x}_m$ that are themselves chosen from a discrete Gaussian distribution (and fixed). Our results simplify and qualitatively improve upon a recent result by Agrawal, Gentry, Halevi, and Sahai.

In this paper we study the fractional block sensitivity of Boolean functions. Recently, Tal and Gilmer, Saks, and Srinivasan independently introduced this complexity measure, denoted by fbs(f), and showed that it is equal (up to a constant factor) to the randomized certificate complexity, denoted by RC(f), which was introduced by Aaronson. In this paper, we relate the fractional block sensitivity to other complexity measures such as sensitivity $s(f)$ and approximate degree $adeg(f)$. As a consequence we obtain the following results:

1. We show that $adeg(f) = \Omega(\sqrt{RC(f)}),$ solving an open question posed by Aaronson. This also implies that $adeg(f) = \Omega(QC(f)),$ where $QC(f)$ is the quantum certificate complexity of $f.$ As both $adeg(f)$ and $QC(f)$ serve as lower bounds for the bounded error quantum query complexity, this shows that $adeg(f)$ is always a tighter lower bound compared to $QC(f).$
2. a. We show that every transitive function on $n$ variables must have $RC(f) = \Omega(n^{1/\ 2})$, $QC(f) = \Omega(n^{1/4})$ and $adeg(f) = \Omega(n^{1/4})$, and note that all these bounds are tight. This is a strengthening of the previous lower bounds give\ n by Sun et al., and Sun.

   b. We show that Chakraborty's example of a transitive function with $s(f) = O(n^{1/3})$ i\ s optimal unless there is a super-quadratic separation between the block sensitivity and t\ he sensitivity.

3. Using fractional block sensitivity, we show that the zero error randomized decision tree complexity, $R_0(f)$, is upper bounded by $O(R_\ 2(f)^2 \cdot \log R_2(f))$ where $R_2(f)$ is the two-sided bounded error randomized decision tree complexity of $f$. The previous best relation between these two complexity measures was cubic, although Midrijanis showed $R_0(f) = O(R_2(f)^2 \cdot \log n)$ (where $n$ is the number of variables).
4. We show that the (non-negative weight) adversary methods to lower bound the bounded error quantum query complexity of $f$ cannot give better bounds than $\sqrt{RC^0(f) RC^1(f)}.$ This refines the earlier bound of $\sqrt{c^0(f) c^1(f)}$ by Spalek and Szegedy and strengthens the so called certificate complexity barrier to its randomized analogue.

Given a gapped Hamiltonian of a spin chain, we give a polynomial-time algorithm for finding the degenerate ground space projector. The output is an orthonormal set of matrix product states that approximate the true ground space projector up to an inverse polynomial error in any Schatten norm, with a runtime exponential in the degeneracy. Our algorithm is an extension of the recent algorithm of Landau, Vazirani, and Vidick for the nondegenerate case, and it includes the recent improvements due to Huang. The main new idea is to incorporate the local distinguishability of ground states on the half-chain to ensure that the algorithm returns a complete set of global ground states.

By a careful analysis of the proofs of Kopparty in fields of characteristic 2, we show that the problem of powering in $\mathbb{F_{p^n}}$ requires $\mathrm{ACC}(p)$ circuits of exponential size (in $n$), for any fixed prime $p > 2$. Similar bounds hold for quadratic residuosity. As a corollary, we obtain non-trivial bounds for exponential sums that express the correlation between the quadratic character of $\mathbb{F_{p^n}}$ and $n$-variate polynomials over $\mathbb{F_p}$ of degree up to $n^{\epsilon}$ for some $0 < \epsilon < 1$.

We use a recently discovered constrained de Finetti reduction (aka “Post-Selection Lemma”) to study the parallel repetition of multi-player non-local games under no-signalling strategies. Since the technique allows us to reduce general strategies to independent plays, we obtain parallel repetition (corresponding to winning all rounds) in the same way as exponential concentration of the probability to win a fraction larger than the value of the game. Our proof technique leads us naturally to a relaxation of no-signalling (NS) strategies, which we dub sub-no-signalling (SNOS). While for two players the two concepts coincide, they differ for three or more players. Our results are most complete and satisfying for arbitrary number of sub-no-signalling players, where we get universal parallel repetition and concentration for any game, while the no-signalling case is obtained as a corollary, but only for games with “full support”.

In this note, we study the relationship between the parity decision tree complexity of a boolean function $f$, denoted by ${\mathrm D}_{\oplus} (f)$, and the $k$-party number-in-hand multiparty communication complexity of the XOR-functions $F_k(x_1,\ldots, x_k) {\stackrel{{\mathsf{def}}}{=}} f(x_1\oplus\cdots\oplus x_k)$, denoted by ${\rm CC}^{(k)}(F_k )$. It is known that ${\rm CC}^{(k)}(F_k )\leq k\cdot {\mathrm {D}}_{\oplus} (f)$ because the players can simulate the parity decision tree that computes $f$. In this note, we show that \[{\mathrm D}_{\oplus} (f)= O ({\rm CC}^{(4)}(F_k)^5 .\] Our main tool is a recent result from additive combinatorics due to Sanders. As ${\rm CC}^{(k)}(F_k )$ is non-decreasing as $k$ grows, the parity decision tree complexity of $f$ and the communication complexity of the corresponding $k$-argument XOR-functions are polynomially equivalent whenever $k\geq 4$.
Remark: After a first version of this paper was finished, we were informed that Hatami and Lovett had already discovered the same result a few years ago, without writing it up.

Oblivious transfer is a fundamental cryptographic primitive in which Bob transfers one of two bits to Alice in such a way that Bob cannot know which of the two bits Alice has learned.
We present an optimal security bound for quantum oblivious transfer protocols, in the information theoretic setting, under a natural and {arguably} demanding definition of what it means for Alice to cheat.
Our lower bound is a smooth tradeoff between the probability $P^*_{Bob}$ with which Bob can guess Alice's bit choice and the probability $P^*_{Alice}$ with which Alice can guess both of Bob's bits given that she learns one of the bits with certainty.
We prove that $2 P^*_{Bob} + P^*_{Alice} \geq 2$ in any quantum protocol for oblivious transfer, from which it follows that one of the two parties must be able to cheat with probability at least $2/3$.
We prove that this bound is optimal by exhibiting a family of protocols whose cheating probabilities can be made arbitrarily close to any point on the tradeoff curve.

The Friedgut--Kalai--Naor theorem, a basic result in the field of analysis of Boolean functions, states that if a Boolean function on the Boolean cube $\{0,1\}^n$ is close to a function of the form $c_0 + \sum_i c_i x_i$, then it is close to a dictatorship (a function depending on a single coordinate). We prove an analogous theorem for functions defined on the slice $\binom{[n]}{k} = \{ (x_1,\ldots,x_n) \in \{0,1\}^n : \sum_i x_i = k \}$.

When $k/n$ is bounded away from $0$ and $1$, our theorem states that if a function on the slice is close to a function of the form $\sum_i c_i x_i$ then it is close to a dictatorship. When $k/n$ is close to $0$ or to $1$, we can only guarantee being close to a junta (a function depending on a small number of coordinates); this deterioration in the guarantee is unavoidable, since for small $p$ a maximum of a small number of variables is close to their sum.

Kindler and Safra proved an FKN theorem for the biased Boolean cube, in which the un\ derlying measure is the product measure $\mu_p(x) = p^{\sum_i x_i} (1-p)^{\sum_i (1-\ x_i)}$. As a corollary of our FKN theorem for the slice, we deduce a uniform version\ of the FKN theorem for the biased Boolean cube, in which the error bounds depend un\ iformly on $p$. Mirroring the situation on the slice, when $p$ is very close to $0$ \ or to $1$, we can only guarantee closeness to a junta.