John Wright

According to our database, John Wright authored at least 24 papers between 2011 and 2021.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2021

MIP* = RE.

Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen

Commun. ACM, 2021

Quantum soundness of testing tensor codes.

Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

Quantum soundness of the classical low individual degree test.

Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen

CoRR, 2020

2019

NEEXP in MIP.

Anand Natarajan, John Wright

CoRR, 2019

Quantum state certification.

Costin Badescu, Ryan O'Donnell, John Wright

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

NEEXP is Contained in MIP.

Anand Natarajan, John Wright

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

Which Distribution Distances are Sublinearly Testable?

Constantinos Daskalakis, Gautam Kamath, John Wright

Electron. Colloquium Comput. Complex., 2018

2017

Improved NP-Inapproximability for 2-Variable Linear Equations.

Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell, John Wright

Theory Comput., 2017

Guest Column: A Primer on the Statistics of Longest Increasing Subsequences and Quantum States (Shortened Version).

Ryan O'Donnell, John Wright

SIGACT News, 2017

Improved and simplified inapproximability for k-means.

Euiwoong Lee, Melanie Schmidt, John Wright

Inf. Process. Lett., 2017

Efficient quantum tomography II.

Ryan O'Donnell, John Wright

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

2016

Efficient quantum tomography.

Ryan O'Donnell, John Wright

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

2015

Beating the random assignment on constraint satisfaction problems of bounded degree.

Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright

Electron. Colloquium Comput. Complex., 2015

Quantum Spectrum Testing.

Ryan O'Donnell, John Wright

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Adaptivity Helps for Testing Juntas.

Rocco A. Servedio, Li-Yang Tan, John Wright

Proceedings of the 30th Conference on Computational Complexity, 2015

2014

New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover.

Per Austrin, Ryan O'Donnell, Li-Yang Tan, John Wright

ACM Trans. Comput. Theory, 2014

Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs.

Ryan O'Donnell, John Wright, Chenggang Wu, Yuan Zhou

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Decision trees, protocols and the entropy-influence conjecture.

Andrew Wan, John Wright, Chenggang Wu

Proceedings of the Innovations in Theoretical Computer Science, 2014

Optimal Strong Parallel Repetition for Projection Games on Low Threshold Rank Graphs.

Madhur Tulsiani, John Wright, Yuan Zhou

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

A Composition Theorem for Parity Kill Number.

Ryan O'Donnell, John Wright, Yu Zhao, Xiaorui Sun, Li-Yang Tan

Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

2013

Decision Trees, Protocols, and the Fourier Entropy-Influence Conjecture.

Andrew Wan, John Wright, Chenggang Wu

CoRR, 2013

2012

A new point of NP-hardness for unique games.

Ryan O'Donnell, John Wright

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

A New Point of NP-Hardness for 2-to-1 Label Cover.

Per Austrin, Ryan O'Donnell, John Wright

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

The Fourier Entropy-Influence Conjecture for Certain Classes of Boolean Functions.

Ryan O'Donnell, John Wright, Yuan Zhou

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011