Jop Briët

I am a senior researcher in the Algorithms and Complexity group at CWI and am part of the Networks center and QuSoft. Contact Information Address: Phone: E-mail: Centrum Wiskunde & Informatica (CWI) Science Park 123 1098 XG Amsterdam The Netherlands +31 (0)20 5924193 j dot briet at cwi dot nl

Teaching

Publications

• On the resolution of Marton's conjecture from additive combinatorics (PDF)
  Jop Briët
  Nieuw Archief voor Wiskunde
  
  
• Discreteness of asymptotic tensor ranks (arXiv)
  Jop Briët, Matthias Christandl, Itai Leigh, Amir Shpilka and Jeroen Zuiddam
  Preprint. Accepted to ITCS 2024 and QIP 2024.
  
  
• On the threshold for Szemerédi's theorem with random differences (PDF, arXiv)
  Jop Briët and Davi Castro Silva
  Electronic Journal of Combinatorics. Extended abstract in EUROCOMB'23.
  
  
• Noisy decoding by shallow circuits with parities: classical and quantum (PDF, arXiv)
  Jop Briët, Harry Buhrman, Davi Castro Silva and Niels Neumann
  accepted to QIP 2023 and ITCS 2024
  
  
• Random restrictions of high-rank tensors and polynomial maps (PDF, arXiv)
  Jop Briët and Davi Castro Silva
  Discrete Analysis. Extended abstract in EUROCOMB'23.
  
  
• Grothendieck inequalities characterize converses to the polynomial method (PDF, arXiv)
  Jop Briët, Francisco Escudero Gutiérrez and Sander Gribling
  Quantum
  
  
• On converses to the polynomial method (PDF, arXiv)
  Jop Briët and Francisco Escudero Gutiérrez
  Proceedings of TQC 2022
  
  
• Steps towards openness and fairness in scientific publishing (PDF)
  Jop Briët, David Holmes and Ross Kang
  Nieuw Archief voor Wiskunde
  
  
• Multiple correlation sequences not approximable by nilsequences (PDF, arXiv)
  Jop Briët and Ben Green
  Ergodic Theory and Dynamical Systems
  
  
• High-entropy dual functions and locally decodable codes (PDF, arXiv)
  Jop Briët and Farrokh Labib
  Forum of Mathematics, Sigma. Extended abstract in proceedings of ITCS 2021
  
  
• Quasirandom quantum channels (PDF, arXiv)
  Tom Bannink, Jop Briët, Farrokh Labib and Hans Maassen
  Quantum. Proceedings of TQC 2020 (outstanding paper award)
  
  
• Subspaces of tensors with high analytic rank (PDF, arXiv)
  Jop Briët
  Online Journal of Analytic Combinatorics
  
  
• Failure of the trilinear operator space Grothendieck theorem (PDF, arXiv)
  Jop Briët and Carlos Palazuelos
  Discrete Analysis
  
  
• Bounding quantum-classical separations for classes of nonlocal games (PDF, arXiv)
  Tom Bannink, Jop Briët, Harry Buhrman, Troy Lee and Farrokh Labib
  Proceedings of STACS 2019
  
  
• Quantum query algorithms are completely bounded forms (PDF, arXiv)
  Srinivasan Arunachalam, Jop Briët and Carlos Palazuelos
  SIAM journal on computing (SICOMP). Preliminary version in proceedings of ITCS 2018, accepted to QIP 2019
  Accompanying note showing that Chebyshev polynomials are completely bounded: PDF
  
  
• Gaussian width bounds with applications to arithmetic progressions in random settings (PDF, arXiv)
  Jop Briët and Sivakanth Gopi
  International Mathematics Research Notices
  
  
• Outlaw distributions and locally decodable codes (PDF, arXiv)
  Jop Briët, Zeev Dvir and Sivakanth Gopi
  Theory of Computing. Preliminary version in proceedings of ITCS 2017
  
  
• Arithmetic expanders and deviation bounds for sums of random tensors (PDF, arXiv)
  Jop Briët and Shravas Rao
  Preprint.
  
  
• On the orthogonal rank of Cayley graphs and impossibility of quantum round elimination (PDF, arXiv)
  Jop Briët and Jeroen Zuiddam
  Quantum Information and Computation
  
  
• Revisiting the Sanders-Freiman-Ruzsa Theorem in \(\mathbb F_p^n\) and its Application to Non-malleable Codes (PDF, arXiv)
  Divesh Aggarwal and Jop Briët
  Proceedings of ISIT 2016
  
  
• On Embeddings of \(\ell_1^k\) from Locally Decodable Codes (PDF, ECCC, arXiv)
  Jop Briët
  Preprint (2015)
  
  
• Round elimination in exact quantum communication complexity (PDF, arXiv)
  Jop Briët, Harry Buhrman, Debbie Leung, Teresa Piovesan and Florian Speelman
  Proceedings of TQC 2015
  
  
• Tight Hardness of the Non-commutative Grothendieck Problem (PDF, arXiv)
  Jop Briët, Oded Regev and Rishi Saket
  Theory of Computing. A preliminary version appeared in Proceedings of FOCS 2015
  
  
• Lower bounds on approximate locally decodable codes (PDF, ECCC)
  Jop Briët, Zeev Dvir, Guangda Hu and Shubhangi Saraf
  Proceedings of ICALP 2014
  
  
• On the existence of 0/1 polytopes with high semidefinite extension complexity (PDF, arXiv)
  Jop Briët, Daniel Dadush and Sebastian Pokutta
  Mathematical Programming. Preliminary version in Proceedings of ESA 2013
  
  
• Entanglement-assisted zero-error source-channel coding (PDF, arXiv)
  Jop Briët, Harry Buhrman, Monique Laurent, Teresa Piovesan and Giannicola Scarpa
  IEEE Transactions on Information Theory. Preliminary version in proceedings of Eurocomb 2013. Presented at QIP 2014.
  
  
• Locally decodable codes and the failure of cotype for projective tensor products (PDF, arXiv)
  Jop Briët, Assaf Naor and Oded Regev
  Electronic Research Announcements in Mathematical Sciences (2012)
  
  
• Violating the Shannon capacity of metric graphs with entanglement (PDF, arXiv)
  Jop Briët, Harry Buhrman and Dion Gijswijt
  Proceedings of the National Academy of Sciences (2012)
  
  
• Explicit lower and upper bounds on the entangled value of multiplayer XOR games (PDF, arXiv)
  Jop Briët and Thomas Vidick
  Communications in Mathematical Physics (2012). Presented at QIP 2012 (contributed talk)
  
  
• Grothendieck Inequalities, Nonlocal Games and Optimization (PDF)
  Jop Briët
  PhD thesis (2011)
  Winner of the Stieltjes Prize and the Andreas Bonn medal
  
  
• All Schatten spaces endowed with the Schur product are Q-algebras (PDF)
  Jop Briët, Harry Buhrman, Troy Lee and Thomas Vidick
  Journal of Functional Analysis (2012)
  
  
• Grothendieck inequalities for semidefinite programs with rank constraints (PDF, arXiv)
  Jop Briët, Fernando Mário de Oliveira Filho and Frank Vallentin
  Theory of Computing (2014)
  
  
• Monotonicity Testing and Shortest-Path Routing on the Cube (PDF, ECCC)
  Jop Briët, David García-Soriano, Arie Matsliah and Sourav Chakraborty
  Combinatorica (2012). A preliminary version appeared in the Proceedings of APPROX-RANDOM 2010
  
  
• The Grothendieck problem with rank constraint (PDF)
  Jop Briët, Fernando Mário de Oliveira Filho and Frank Vallentin
  Proceedings of MTNS 2010
  
  
• The positive semidefinite Grothendieck problem with rank constraint (PDF, arXiv)
  Jop Briët, Fernando Mário de Oliveira Filho and Frank Vallentin
  Proceedings of ICALP 2010
  
  
• Multipartite entanglement in XOR games (PDF, arXiv)
  Jop Briët, Harry Buhrman, Troy Lee and Thomas Vidick
  Quantum Information and Computation (2013)
  
  
• Testing the equivalence of pure quantum states and graph states under SLOCC (PDF, arXiv)
  Adam D'Souza, Jop Briët and David Feder
  International Journal of Quantum Information (2010)
  
  
• A generalized Grothendieck inequality and entangled XOR games (PDF)
  Jop Briët, Harry Buhrman and Ben Toner
  Communications in Mathematical Physics (2011). Presented at QIP 2009 (long talk)
  
  
• Properties of classical and quantum Jensen-Shannon divergence (PDF, arXiv)
  Jop Briët and Peter Harremoës
  Phys. Rev. A. (2009)
  
  
• Locally decodable quantum codes (PDF, arXiv)
  Jop Briët and Ronald de Wolf
  Proceedings of STACS 2009
  
  
• Determining the Dimensionality of Spacetime by Gravitational Lensing (PDF, arXiv)
  Jop Briët and David Hobill
  Technical report