BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Jop Briët appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
We show that for infinitely many primes $p$, there exist dual functions of order $k$ over $\mathbb{F}_p^n$ that cannot be approximated in $L_\infty$-distance by polynomial phase functions of degree $k-1$. This answers in the negative a natural finite-field analog of a problem of Frantzikinakis on $L_\infty$-approximations of dual functions over $\mathbb{N}$ (a.k.a. multiple correlation sequences) by nilsequences.
We prove a characterization of $t$-query quantum algorithms in terms of the unit ball of a space of degree-$2t$ polynomials. Based on this, we obtain a refined notion of approximate polynomial degree that equals the quantum query complexity, answering a question of Aaronson et al. (CCC'16). Our proof is based on a fundamental result of Christensen and Sinclair (J. Funct. Anal., 1987) that generalizes the well-known Stinespring representation for quantum channels to multilinear forms. Using our characterization, we show that many polynomials of degree four are far from those coming from two-query quantum algorithms. We also give a simple and short proof of one of the results of Aaronson et al. showing an equivalence between one-query quantum algorithms and bounded quadratic polynomials. Revision note: A mistake was found in the proof of the second result on degree-4 polynomials far from 2-query quantum algorithms. An explanation of the issue, a corrected proof and stronger examples are presented in work of Escudero Gutiérrez and the second author.
$\newcommand{\eps}{\varepsilon} $We prove that for any $\eps > 0$ it is $\textsf{NP}$-hard to approximate the non-commutative Grothendieck problem to within a factor $1/2 + \eps$, which matches the approximation ratio of the algorithm of Naor, Regev, and Vidick (STOC'13). Our proof uses an embedding of $\ell_2$ into the space of matrices endowed with the trace norm with the property that the image of standard basis vectors is longer than that of unit vectors with no large coordinates. We also observe that one can obtain a tight $\textsf{NP}$-hardness result for the commutative Little Grothendieck problem; previously, this was only known based on the Unique Games Conjecture (Khot and Naor, Mathematika 2009).
Mixing (or quasirandom) properties of the natural transition matrix associated to a graph can be quantified by its distance to the complete graph. Different mixing properties correspond to different norms to measure this distance. For dense graphs, two such properties known as spectral expansion and uniformity were shown to be equivalent in seminal 1989 work of Chung, Graham and Wilson. Recently, Conlon and Zhao extended this equivalence to the case of sparse vertex transitive graphs using the famous Grothendieck inequality. Here we generalize these results to the non-commutative, or `quantum', case, where a transition matrix becomes a quantum channel. In particular, we show that for irreducibly covariant quantum channels, expansion is equivalent to a natural analog of uniformity for graphs, generalizing the result of Conlon and Zhao. Moreover, we show that in these results, the non-commutative and commutative (resp.) Grothendieck inequalities yield the best-possible constants.
We prove hypergraph variants of the celebrated Alon-Roichman theorem on spectral expansion of sparse random Cayley graphs. One of these variants implies that for every prime $p\geq 3$ and any $\varepsilon > 0$, there exists a set of directions $D\subseteq \mathbb{F}_p^n$ of size $O_{p,\varepsilon}(p^{(1-1/p +o(1))n})$ such that for every set $A\subseteq \mathbb{F}_p^n$ of density $α$, the fraction of lines in $A$ with direction in $D$ is within $\varepsilonα$ of the fraction of all lines in $A$. Our proof uses new deviation bounds for sums of independent random multi-linear forms taking values in a generalization of the Birkhoff polytope. The proof of our deviation bound is based on Dudley's integral inequality and a probabilistic construction of $\varepsilon$-nets. Using the polynomial method we prove that a Cayley hypergraph with edges generated by a set~$D$ as above requires $|D| \geq Ω_p(n^{p-1})$ for (our notion of) spectral expansion for hypergraphs.
We show that any $q$-query locally decodable code (LDC) gives a copy of $\ell_1^k$ with small distortion in the Banach space of $q$-linear forms on $\ell_{p_1}^N\times\cdots\times\ell_{p_q}^N$, provided $1/p_1 + \cdots + 1/p_q \leq 1$ and where $k$, $N$, and the distortion are simple functions of the code parameters. We exhibit the copy of $\ell_1^k$ by constructing a basis for it directly from "smooth" LDC decoders. Based on this, we give alternative proofs for known lower bounds on the length of 2-query LDCs. Using similar techniques, we reprove known lower bounds for larger $q$. We also discuss the relation with an alternative proof, due to Pisier, of a result of Naor, Regev, and the author on cotype properties of projective tensor products of $\ell_p$ spaces.
Non-malleable codes (NMCs) protect sensitive data against degrees of corruption that prohibit error detection, ensuring instead that a corrupted codeword decodes correctly or to something that bears little relation to the original message. The split-state model, in which codewords consist of two blocks, considers adversaries who tamper with either block arbitrarily but independently of the other. The simplest construction in this model, due to Aggarwal, Dodis, and Lovett (STOC'14), was shown to give NMCs sending k-bit messages to $O(k^7)$-bit codewords. It is conjectured, however, that the construction allows linear-length codewords. Towards resolving this conjecture, we show that the construction allows for code-length $O(k^5)$. This is achieved by analysing a special case of Sanders's Bogolyubov-Ruzsa theorem for general Abelian groups. Closely following the excellent exposition of this result for the group $\mathbb{F}_2^n$ by Lovett, we expose its dependence on $p$ for the group $\mathbb{F}_p^n$, where $p$ is a prime.
We study the use of quantum entanglement in the zero-error source-channel coding problem. Here, Alice and Bob are connected by a noisy classical one-way channel, and are given correlated inputs from a random source. Their goal is for Bob to learn Alice's input while using the channel as little as possible. In the zero-error regime, the optimal rates of source codes and channel codes are given by graph parameters known as the Witsenhausen rate and Shannon capacity, respectively. The Lovász theta number, a graph parameter defined by a semidefinite program, gives the best efficiently-computable upper bound on the Shannon capacity and it also upper bounds its entanglement-assisted counterpart. At the same time it was recently shown that the Shannon capacity can be increased if Alice and Bob may use entanglement. Here we partially extend these results to the source-coding problem and to the more general source-channel coding problem. We prove a lower bound on the rate of entanglement-assisted source-codes in terms Szegedy's number (a strengthening of the theta number). This result implies that the theta number lower bounds the entangled variant of the Witsenhausen rate. We also show that entanglement can allow for an unbounded improvement of the asymptotic rate of both classical source codes and classical source-channel codes. Our separation results use low-degree polynomials due to Barrington, Beigel and Rudich, Hadamard matrices due to Xia and Liu and a new application of remote state preparation.
We study an approximate version of $q$-query LDCs (Locally Decodable Codes) over the real numbers and prove lower bounds on the encoding length of such codes. A $q$-query $(α,δ)$-approximate LDC is a set $V$ of $n$ points in $\mathbb{R}^d$ so that, for each $i \in [d]$ there are $Ω(δn)$ disjoint $q$-tuples $(\vec{u}_1,\ldots,\vec{u}_q) $ in $V$ so that $\text{span}(\vec{u}_1,\ldots,\vec{u}_q)$ contains a unit vector whose $i$'th coordinate is at least $α$. We prove exponential lower bounds of the form $n \geq 2^{Ω(αδ\sqrt{d})}$ for the case $q=2$ and, in some cases, stronger bounds (exponential in $d$).
In Rothvoß it was shown that there exists a 0/1 polytope (a polytope whose vertices are in \{0,1\}^{n}) such that any higher-dimensional polytope projecting to it must have 2^{Ω(n)} facets, i.e., its linear extension complexity is exponential. The question whether there exists a 0/1 polytope with high PSD extension complexity was left open. We answer this question in the affirmative by showing that there is a 0/1 polytope such that any spectrahedron projecting to it must be the intersection of a semidefinite cone of dimension~2^{Ω(n)} and an affine space. Our proof relies on a new technique to rescale semidefinite factorizations.
A set of necessary and sufficient conditions are derived for the equivalence of an arbitrary pure state and a graph state on n qubits under stochastic local operations and classical communication (SLOCC), using the stabilizer formalism. Because all stabilizer states are equivalent to a graph state by local unitary transformations, these conditions constitute a classical algorithm for the determination of SLOCC-equivalence of pure states and stabilizer states. This algorithm provides a distinct advantage over the direct solution of the SLOCC-equivalence condition for an unknown invertible local operator S, as it usually allows for easy detection of states that are not SLOCC-equivalent to graph states.