John Wright

53 papers A* 14A 3Journal 31Unranked 5
YearRankTypeTitle / Venue / Authors
2026 A* conf
Beating full state tomography for unentangled spectrum estimation.
SODA
Angelos Pelecanos, Xinyu Tan, Ewin Tang, John Wright
2025 J jnl
Amplitude amplification and estimation require inverses.
CoRR
Ewin Tang, John Wright
2025 J jnl
Beating full state tomography for unentangled spectrum estimation.
CoRR
Angelos Pelecanos, Xinyu Tan, Ewin Tang, John Wright
2025 J jnl
Conjugate queries can help.
CoRR
Ewin Tang, John Wright, Mark Zhandry
2025 J jnl
Haar random codes attain the quantum Hamming bound, approximately.
CoRR
Fermi Ma, Xinyu Tan, John Wright
2025 A* conf
The State Hidden Subgroup Problem and an Efficient Algorithm for Locating Unentanglement.
STOC
Adam Bouland, Tudor Giurgica-Tiron, John Wright
2024 A* conf
A One-Query Lower Bound for Unitary Synthesis and Breaking Quantum Cryptography.
STOC
Alex Lombardi, Fermi Ma, John Wright
2024 J jnl
The state hidden subgroup problem and an efficient algorithm for locating unentanglement.
CoRR
Adam Bouland, Tudor Giurgica-Tiron, John Wright
2023 J jnl
A one-query lower bound for unitary synthesis and breaking quantum cryptography.
CoRR
Alex Lombardi, Fermi Ma, John Wright
2023 J jnl
A one-query lower bound for unitary synthesis and breaking quantum cryptography.
IACR Cryptol. ePrint Arch.
Alex Lombardi, Fermi Ma, John Wright
2023 A* conf
Unique Games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell's inequality.
SODA
Yeongwoo Hwang, Joe Neeman, Ojas Parekh, Kevin Thompson, John Wright
2022 A* conf
Testing matrix product states.
SODA
Mehdi Soleimanifar, John Wright
2022 J jnl
Testing matrix product states.
CoRR
Mehdi Soleimanifar, John Wright
2021 J jnl
MIP* = RE.
Commun. ACM
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen
2021 A* conf
Quantum soundness of testing tensor codes.
FOCS
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen
2021 J jnl
Quantum soundness of testing tensor codes.
CoRR
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen
2021 J jnl
Unique Games hardness of Quantum Max-Cut, and a vector-valued Borell's inequality.
CoRR
Yeongwoo Hwang, Joe Neeman, Ojas Parekh, Kevin Thompson, John Wright
2020 J jnl
MIP*=RE.
CoRR
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen
2020 J jnl
Quantum soundness of the classical low individual degree test.
CoRR
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen
2019 J jnl
NEEXP in MIP.
CoRR
Anand Natarajan, John Wright
2019 A* conf
NEEXP is Contained in MIP.
FOCS
Anand Natarajan, John Wright
2019 A* conf
Quantum state certification.
STOC
Costin Badescu, Ryan O'Donnell, John Wright
2018 A* conf
Which Distribution Distances are Sublinearly Testable?
SODA
Constantinos Daskalakis, Gautam Kamath, John Wright
2018 J jnl
Which Distribution Distances are Sublinearly Testable?
Electron. Colloquium Comput. Complex.
Constantinos Daskalakis, Gautam Kamath, John Wright
2017 A* conf
Efficient quantum tomography II.
STOC
Ryan O'Donnell, John Wright
2017 J jnl
Guest Column: A Primer on the Statistics of Longest Increasing Subsequences and Quantum States (Shortened Version).
SIGACT News
Ryan O'Donnell, John Wright
2017 J jnl
Improved NP-Inapproximability for 2-Variable Linear Equations.
Theory Comput.
Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell, John Wright
2017 J jnl
Improved and simplified inapproximability for k-means.
Inf. Process. Lett.
Euiwoong Lee, Melanie Schmidt, John Wright
2017 J jnl
Quantum state certification.
CoRR
Costin Badescu, Ryan O'Donnell, John Wright
2017 J jnl
Which Distribution Distances are Sublinearly Testable?
CoRR
Constantinos Daskalakis, Gautam Kamath, John Wright
2016 J jnl
Efficient quantum tomography II.
CoRR
Ryan O'Donnell, John Wright
2016 A* conf
Efficient quantum tomography.
STOC
Ryan O'Donnell, John Wright
2015 A conf
Adaptivity Helps for Testing Juntas.
CCC
Rocco A. Servedio, Li-Yang Tan, John Wright
2015 — conf
Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree.
APPROX-RANDOM
Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
2015 J jnl
Beating the random assignment on constraint satisfaction problems of bounded degree.
CoRR
Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
2015 J jnl
Beating the random assignment on constraint satisfaction problems of bounded degree.
Electron. Colloquium Comput. Complex.
Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
2015 J jnl
Efficient quantum tomography.
CoRR
Ryan O'Donnell, John Wright
2015 — conf
Improved NP-Inapproximability for 2-Variable Linear Equations.
APPROX-RANDOM
Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell, John Wright
2015 J jnl
Improved and Simplified Inapproximability for k-means.
CoRR
Euiwoong Lee, Melanie Schmidt, John Wright
2015 A* conf
Quantum Spectrum Testing.
STOC
Ryan O'Donnell, John Wright
2014 A conf
A Composition Theorem for Parity Kill Number.
CCC
Ryan O'Donnell, John Wright, Yu Zhao, Xiaorui Sun, Li-Yang Tan
2014 A conf
Decision trees, protocols and the entropy-influence conjecture.
ITCS
Andrew Wan, John Wright, Chenggang Wu
2014 A* conf
Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs.
SODA
Ryan O'Donnell, John Wright, Chenggang Wu, Yuan Zhou
2014 J jnl
Hardness of robust graph isomorphism, Lasserre gaps, and asymmetry of random graphs.
CoRR
Ryan O'Donnell, John Wright, Chenggang Wu, Yuan Zhou
2014 J jnl
New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover.
ACM Trans. Comput. Theory
Per Austrin, Ryan O'Donnell, Li-Yang Tan, John Wright
2014 — conf
Optimal Strong Parallel Repetition for Projection Games on Low Threshold Rank Graphs.
ICALP (1)
Madhur Tulsiani, John Wright, Yuan Zhou
2013 J jnl
A composition theorem for parity kill number.
CoRR
Ryan O'Donnell, Xiaorui Sun, Li-Yang Tan, John Wright, Yu Zhao
2013 J jnl
Decision Trees, Protocols, and the Fourier Entropy-Influence Conjecture.
CoRR
Andrew Wan, John Wright, Chenggang Wu
2012 — conf
A New Point of NP-Hardness for 2-to-1 Label Cover.
APPROX-RANDOM
Per Austrin, Ryan O'Donnell, John Wright
2012 J jnl
A new point of NP-hardness for 2-to-1 Label Cover
CoRR
Per Austrin, Ryan O'Donnell, John Wright
2012 A* conf
A new point of NP-hardness for unique games.
STOC
Ryan O'Donnell, John Wright
2012 J jnl
New NP-hardness results for 3-Coloring and 2-to-1 Label Cover
CoRR
Per Austrin, Ryan O'Donnell, Li-Yang Tan, John Wright
2011 — conf
The Fourier Entropy-Influence Conjecture for Certain Classes of Boolean Functions.
ICALP (1)
Ryan O'Donnell, John Wright, Yuan Zhou