Zobrazeno 1 - 10
of 107
pro vyhledávání: '"BRIËT, JOP"'
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 algorithms)
Externí odkaz:
http://arxiv.org/abs/2306.01718
Autor:
Briët, Jop, Castro-Silva, Davi
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 gives polynomi
Externí odkaz:
http://arxiv.org/abs/2304.03234
We consider the problem of decoding corrupted error correcting codes with NC$^0[\oplus]$ circuits in the classical and quantum settings. We show that any such classical circuit can correctly recover only a vanishingly small fraction of messages, if t
Externí odkaz:
http://arxiv.org/abs/2302.02870
Autor:
Briët, Jop, Castro-Silva, Davi
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 functions, rand
Externí odkaz:
http://arxiv.org/abs/2212.13728
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 famous Groth
Externí odkaz:
http://arxiv.org/abs/2212.08559
Publikováno v:
TQC'22 Proceedings, LIPICS Vol. 232 (6), 2022
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 famous Groth
Externí odkaz:
http://arxiv.org/abs/2204.12303
Autor:
Briët, Jop, Green, Ben
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_2 d\mu$ is not
Externí odkaz:
http://arxiv.org/abs/2010.14960
Autor:
Briët, Jop, Labib, Farrokh
Publikováno v:
Forum of Mathematics, Sigma , Volume 9 , 2021 , e19
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
Externí odkaz:
http://arxiv.org/abs/2010.14956
Publikováno v:
Quantum 4, 298 (2020)
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, t
Externí odkaz:
http://arxiv.org/abs/1908.06310
Autor:
Briët, Jop
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 analytic rank $\O
Externí odkaz:
http://arxiv.org/abs/1908.04169