Jop Briët
YOU?
Author Swipe
View article: Clifford testing: algorithms and lower bounds
Clifford testing: algorithms and lower bounds Open
We consider the problem of Clifford testing, which asks whether a black-box $n$-qubit unitary is a Clifford unitary or at least $\varepsilon$-far from every Clifford unitary. We give the first 4-query Clifford tester, which decides this pr…
View article: Grothendieck inequalities characterize converses to the polynomial method
Grothendieck inequalities characterize converses to the polynomial method Open
A surprising 'converse to the polynomial method' of Aaronson et al. (CCC'16) shows that any bounded quadratic polynomial can be computed exactly in expectation by a 1-query algorithm up to a universal multiplicative factor r…
View article: On the Threshold for Szemerédi's Theorem with Random Differences
On the Threshold for Szemerédi's Theorem with Random Differences Open
Using recent developments on the theory of locally decodable codes, we prove that the critical size for Szemerédi's theorem with random differences is bounded from above by $N^{1-\frac{2}{k} + o(1)}$ for length-$k$ progressions. This impro…
View article: Noisy Decoding by Shallow Circuits with Parities: Classical and Quantum (Extended Abstract)
Noisy Decoding by Shallow Circuits with Parities: Classical and Quantum (Extended Abstract) Open
We consider the problem of decoding corrupted error correcting codes with NC⁰[⊕] circuits in the classical and quantum settings. We show that any such classical circuit can correctly recover only a vanishingly small fraction of messages, i…
View article: Discreteness of Asymptotic Tensor Ranks (Extended Abstract)
Discreteness of Asymptotic Tensor Ranks (Extended Abstract) Open
Tensor parameters that are amortized or regularized over large tensor powers, often called "asymptotic" tensor parameters, play a central role in several areas including algebraic complexity theory (constructing fast matrix multiplication …
View article: Discreteness of Asymptotic Tensor Ranks (Extended Abstract)
Discreteness of Asymptotic Tensor Ranks (Extended Abstract) Open
Tensor parameters that are amortized or regularized over large tensor powers, often called "asymptotic" tensor parameters, play a central role in several areas including algebraic complexity theory (constructing fast matrix multiplication …
View article: Orthogonal schedules in single round robin tournaments
Orthogonal schedules in single round robin tournaments Open
A measure for the flexibility of a Home-Away Pattern set (HAP-set) is the width. The width of a HAP-set equals the size of the largest set of schedules compatible with the HAP-set, for which no match is scheduled in the same round in any t…
View article: On the threshold for Szemerédi's theorem with random differences
On the threshold for Szemerédi's theorem with random differences Open
Using recent developments on the theory of locally decodable codes, we prove that the critical size for Szemerédi's theorem with random differences is bounded from above by $N^{1-\frac{2}{k} + o(1)}$ for length-$k$ progressions. This gives…
View article: Raising the roof on the threshold for Szemerédi's theorem with random differences
Raising the roof on the threshold for Szemerédi's theorem with random differences Open
Using recent developments on the theory of locally decodable codes, we prove that the critical size for Szemer\'edi's theorem with random differences is bounded from above by $N^{1-\frac{2}{k} + o(1)}$ for length-$k$ progressions. This imp…
View article: Random restrictions of high-rank tensors and polynomial maps
Random restrictions of high-rank tensors and polynomial maps Open
Motivated by a problem in computational complexity, we consider the behavior of rank functions for tensors and polynomial maps under random coordinate restrictions. We show that, for a broad class of rank functions called \emph{natural ran…
View article: Random restrictions of high-rank tensors and polynomial maps
Random restrictions of high-rank tensors and polynomial maps Open
Motivated by a problem in computational complexity, we consider the behavior of rank functions for tensors and polynomial maps under random coordinate restrictions. We show that, for a broad class of rank functions called natural rank func…
View article: Grothendieck inequalities characterize converses to the polynomial method
Grothendieck inequalities characterize converses to the polynomial method Open
A surprising 'converse to the polynomial method' of Aaronson et al. (CCC'16) shows that any bounded quadratic polynomial can be computed exactly in expectation by a 1-query algorithm up to a universal multiplicative factor related to the f…
View article: On converses to the polynomial method
On converses to the polynomial method Open
A surprising 'converse to the polynomial method' of Aaronson et al. (CCC'16) shows that any bounded quadratic polynomial can be computed exactly in expectation by a 1-query algorithm up to a universal multiplicative factor related to the f…
View article: Multiple correlation sequences not approximable by nilsequences
Multiple correlation sequences not approximable by nilsequences Open
We show that there is a measure-preserving system $(X,\mathscr {B}, \mu , T)$ together with functions $F_0, F_1, F_2 \in L^{\infty }(\mu )$ such that the correlation sequence $C_{F_0, F_1, F_2}(n) = \int _X F_0 \cdot T^n F_1 \cdot T^{2n} F…
View article: High-Entropy Dual Functions and Locally Decodable Codes (Extended Abstract)
High-Entropy Dual Functions and Locally Decodable Codes (Extended Abstract) Open
Locally decodable codes (LDCs) allow any single encoded message symbol to be retrieved from a codeword with good probability by reading only a tiny number of codeword symbols, even if the codeword is partially corrupted. LDCs have surprisi…
View article: High-entropy dual functions over finite fields and locally decodable codes
High-entropy dual functions over finite fields and locally decodable codes Open
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 nat…
View article: High-Entropy Dual Functions and Locally Decodable Codes (Extended Abstract)
High-Entropy Dual Functions and Locally Decodable Codes (Extended Abstract) Open
Locally decodable codes (LDCs) allow any single encoded message symbol to be retrieved from a codeword with good probability by reading only a tiny number of codeword symbols, even if the codeword is partially corrupted. LDCs have surprisi…
View article: Multiple correlation sequences not approximable by nilsequences
Multiple correlation sequences not approximable by nilsequences Open
We show that there is a measure-preserving system $(X,\mathscr{B}, μ, T)$ together with functions $F_0, F_1, F_2 \in L^{\infty}(μ)$ such that the correlation sequence $C_{F_0, F_1, F_2}(n) = \int_X F_0 \cdot T^n F_1 \cdot T^{2n} F_2 dμ$ is…
View article: Quasirandom quantum channels
Quasirandom quantum channels Open
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 dens…
View article: Subspaces of tensors with high analytic rank
Subspaces of tensors with high analytic rank Open
It is shown that for any subspace $V\subseteq \mathbb{F}_p^{n\times\cdots\times n}$ of $d$-tensors, if $\dim(V) \geq tn^{d-1}$, then there is subspace $W\subseteq V$ of dimension at least $t/(dr) - 1$ whose nonzero elements all have analyt…
View article: Bounding Quantum-Classical Separations for Classes of Nonlocal Games
Bounding Quantum-Classical Separations for Classes of Nonlocal Games Open
We bound separations between the entangled and classical values for several classes of nonlocal t-player games. Our motivating question is whether there is a family of t-player XOR games for which the entangled bias is 1 but for which the …
View article: Quantum Query Algorithms Are Completely Bounded Forms
Quantum Query Algorithms Are Completely Bounded Forms Open
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,…
View article: Bounding Quantum-Classical Separations for Classes of Nonlocal Games
Bounding Quantum-Classical Separations for Classes of Nonlocal Games Open
We bound separations between the entangled and classical values for several classes of nonlocal t-player games. Our motivating question is whether there is a family of t-player XOR games for which the entangled bias is 1 but for which the …
View article: Round elimination in exact communication complexity
Round elimination in exact communication complexity Open
We study two basic graph parameters, the chromatic number and the orthogonal rank, in the context of classical and quantum exact communication complexity. In particular, we consider two types of communication problems that we call promise …
View article: Gaussian Width Bounds with Applications to Arithmetic Progressions in Random Settings
Gaussian Width Bounds with Applications to Arithmetic Progressions in Random Settings Open
Motivated by problems on random differences in Szemer\'{e}di's theorem and on large deviations for arithmetic progressions in random sets, we prove upper bounds on the Gaussian width of point sets that are formed by the image of the $n$-di…
View article: Quantum Query Algorithms are Completely Bounded Forms
Quantum Query Algorithms are Completely Bounded Forms Open
We prove a characterization of quantum query algorithms in terms of polynomials satisfying a certain (completely bounded) norm constraint. Based on this, we obtain a refined notion of approximate polynomial degree that equals the quantum q…
View article: Grafentheorie en communicatie
Grafentheorie en communicatie Open
View article: Outlaw Distributions and Locally Decodable Codes
Outlaw Distributions and Locally Decodable Codes Open
Locally decodable codes (LDCs) are error correcting codes that allow for decoding of a single message bit using a small number of queries to a corrupted encoding. Despite decades of study, the optimal trade-off between query complexity and…