John Wright

I am a postdoc at the Center for Theoretical Physics at MIT. I received my Ph.D. from Carnegie Mellon University, where I was advised by Ryan O'Donnell.

my email

Past teaching

      15-859BB: Quantum Computation


NEEXP ⊆ MIP* (pdf, video)
A. Natarajan, J. Wright
      FOCS '19, QIP '20
      Best paper award at FOCS '19
      Plenary talk at QIP '20
See Quanta magazine, MyCQstate, and Computational Complexity for coverage of our results. See also a short story by Henry Yuen.

Quantum State Certification (pdf, video)
C. Bădescu, R. O'Donnell, J. Wright
      STOC '19, QIP '18

Which Distribution Distances are Sublinearly Testable? (pdf)
C. Daskalakis, G. Kamath, J. Wright
      SODA '18

Efficient quantum tomography II (pdf)
R. O'Donnell, J. Wright
      STOC '17

Improved and simplified inapproximability for k-means (pdf)
E. Lee, M. Schmidt, J. Wright
      Information Processing Letters 120, pp. 40-43 (2017)

Efficient quantum tomography (pdf, video)
R. O'Donnell, J. Wright
      STOC '16, QIP '16
See also our note on the Haah et al. tomography algorithm (pdf).

Beating the random assignment on constraint satisfaction problems of bounded degree (pdf)
B. Barak, A. Moitra, R. O'Donnell, P. Raghavendra, O. Regev, D. Steurer, L. Trevisan, A. Vijayaraghavan, D. Witmer, J. Wright
      APPROX '15

Adaptivity helps for testing juntas (pdf)
R. Servedio, L.-Y. Tan, J. Wright
      CCC '15

Quantum spectrum testing (pdf)
R. O'Donnell, J. Wright
      STOC '15, QIP '15

Improved NP-inapproximability for 2-variable linear equations (pdf)
J. Håstad, S. Huang, R. Manokaran, R. O'Donnell, J. Wright
      Theory of Computing 13(19), pp. 1-51 (2017)
      Conference version: APPROX '15

Optimal strong parallel repetition for projection games on low threshold rank graphs (pdf)
M. Tulsiani, J. Wright, Y. Zhou
      ICALP '14

A composition theorem for parity kill number (pdf)
R. O'Donnell, X. Sun, L.-Y. Tan, J. Wright, Y. Zhao
      CCC '14

Hardness of robust graph isomorphism, Lasserre gaps, and asymmetry of random graphs (pdf, video)
R. O'Donnell, J. Wright, C. Wu, Y. Zhou
      SODA '14

Decision trees, protocols, and the Fourier Entropy-Influence Conjecture (pdf)
A. Wan, J. Wright, C. Wu
      ITCS '14

New NP-hardness results for 3-Coloring and 2-to-1 Label Cover (pdf)
P. Austrin, R. O'Donnell, L.-Y. Tan, J. Wright
      ACM Transactions on Computation Theory 6(1), pp. 2:1-20 (2014)
      Preliminary version: APPROX '12, A new point of NP-hardness for 2-to-1 Label Cover

A new point of NP-hardness for Unique Games (pdf)
R. O'Donnell, J. Wright
      To appear, Journal of the ACM.
      STOC '12

The Fourier Entropy-Influence Conjecture for certain classes of Boolean functions (pdf, video)
R. O'Donnell, J. Wright, Y. Zhou
      ICALP '11