John Wright

I am a fourth-year Ph.D. student at CMU. My advisor is Ryan O'Donnell.

my email address

Publications

Improved NP-inapproximability for 2-variable linear equations
J. Håstad, S. Huang, R. Manokaran, R. O'Donnell, J. Wright
      Manuscript

Optimal strong parallel repetition for projection games on low threshold rank graphs
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 (arXiv, 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), Article 2 (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
      STOC '12

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