John Wright

Publication Activity (10 Years)

Years Active: 2011-2024
Publications (10 Years): 28

Top Topics

Constraint Satisfaction

Graph Isomorphism

Linear Equations

Top Venues

Publications

Alex Lombardi, Fermi Ma, John Wright
A One-Query Lower Bound for Unitary Synthesis and Breaking Quantum Cryptography. STOC (2024)
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen
Quantum soundness of testing tensor codes. FOCS (2022)
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen
MIP* = RE. Commun. ACM 64 (11) (2021)
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen
Quantum soundness of testing tensor codes. CoRR (2021)
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen
Quantum soundness of testing tensor codes. FOCS (2021)
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen
MIP*=RE. CoRR (2020)
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen
Quantum soundness of the classical low individual degree test. CoRR (2020)
Costin Badescu, Ryan O'Donnell, John Wright
Quantum state certification. STOC (2019)
Anand Natarajan, John Wright
NEEXP in MIP. CoRR (2019)
Anand Natarajan, John Wright
NEEXP is Contained in MIP. FOCS (2019)
Constantinos Daskalakis, Gautam Kamath, John Wright
Which Distribution Distances are Sublinearly Testable? Electron. Colloquium Comput. Complex. 25 (2018)
Constantinos Daskalakis, Gautam Kamath, John Wright
Which Distribution Distances are Sublinearly Testable? SODA (2018)
Constantinos Daskalakis, Gautam Kamath, John Wright
Which Distribution Distances are Sublinearly Testable? CoRR (2017)
Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell, John Wright
Improved NP-Inapproximability for 2-Variable Linear Equations. Theory Comput. 13 (1) (2017)
Euiwoong Lee, Melanie Schmidt, John Wright
Improved and simplified inapproximability for k-means. Inf. Process. Lett. 120 (2017)
Costin Badescu, Ryan O'Donnell, John Wright
Quantum state certification. CoRR (2017)
Ryan O'Donnell, John Wright
Guest Column: A Primer on the Statistics of Longest Increasing Subsequences and Quantum States (Shortened Version). SIGACT News 48 (3) (2017)
Ryan O'Donnell, John Wright
Efficient quantum tomography II. STOC (2017)
Ryan O'Donnell, John Wright
Efficient quantum tomography. STOC (2016)
Ryan O'Donnell, John Wright
Efficient quantum tomography II. CoRR (2016)
Ryan O'Donnell, John Wright
Quantum Spectrum Testing. STOC (2015)
Ryan O'Donnell, John Wright
Efficient quantum tomography. CoRR (2015)
Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
Beating the random assignment on constraint satisfaction problems of bounded degree. CoRR (2015)
Euiwoong Lee, Melanie Schmidt, John Wright
Improved and Simplified Inapproximability for k-means. CoRR (2015)
Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree. APPROX-RANDOM (2015)
Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
Beating the random assignment on constraint satisfaction problems of bounded degree. Electron. Colloquium Comput. Complex. 22 (2015)
Rocco A. Servedio, Li-Yang Tan, John Wright
Adaptivity Helps for Testing Juntas. Computational Complexity Conference (2015)
Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell, John Wright
Improved NP-Inapproximability for 2-Variable Linear Equations. APPROX-RANDOM (2015)
Ryan O'Donnell, John Wright, Chenggang Wu, Yuan Zhou
Hardness of robust graph isomorphism, Lasserre gaps, and asymmetry of random graphs. CoRR (2014)
Andrew Wan, John Wright, Chenggang Wu
Decision trees, protocols and the entropy-influence conjecture. ITCS (2014)
Per Austrin, Ryan O'Donnell, Li-Yang Tan, John Wright
New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover. ACM Trans. Comput. Theory 6 (1) (2014)
Ryan O'Donnell, John Wright, Chenggang Wu, Yuan Zhou
Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs. SODA (2014)
Ryan O'Donnell, John Wright, Yu Zhao, Xiaorui Sun, Li-Yang Tan
A Composition Theorem for Parity Kill Number. Computational Complexity Conference (2014)
Madhur Tulsiani, John Wright, Yuan Zhou
Optimal Strong Parallel Repetition for Projection Games on Low Threshold Rank Graphs. ICALP (1) (2014)
Ryan O'Donnell, Xiaorui Sun, Li-Yang Tan, John Wright, Yu Zhao
A composition theorem for parity kill number. CoRR (2013)
Andrew Wan, John Wright, Chenggang Wu
Decision Trees, Protocols, and the Fourier Entropy-Influence Conjecture. CoRR (2013)
Per Austrin, Ryan O'Donnell, John Wright
A new point of NP-hardness for 2-to-1 Label Cover CoRR (2012)
Per Austrin, Ryan O'Donnell, John Wright
A New Point of NP-Hardness for 2-to-1 Label Cover. APPROX-RANDOM (2012)
Per Austrin, Ryan O'Donnell, Li-Yang Tan, John Wright
New NP-hardness results for 3-Coloring and 2-to-1 Label Cover CoRR (2012)
Ryan O'Donnell, John Wright
A new point of NP-hardness for unique games. STOC (2012)
Ryan O'Donnell, John Wright, Yuan Zhou
The Fourier Entropy-Influence Conjecture for Certain Classes of Boolean Functions. ICALP (1) (2011)