We stand with Ukraine  

John Wright

Orcid: 0009-0006-4071-3488

Affiliations:
  • University of California Berkeley, CA, USA
  • California Institute of Technology, CA, USA (former)
  • University of Texas at Austin, TX, USA (former)
  • Massachusetts Institute of Technology, Department of Physics, Cambridge, MA, USA (former)
  • Carnegie Mellon University, Computer Science Department, Pittsburgh, PA, USA (former)


According to our database1, John Wright authored at least 28 papers between 2011 and 2023.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2023
A one-query lower bound for unitary synthesis and breaking quantum cryptography.
[BibTeX]
[DOI]
Alex Lombardi
,
Fermi Ma
,
John Wright
IACR Cryptol. ePrint Arch., 2023

Unique Games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell's inequality.
[BibTeX]
[DOI]
Yeongwoo Hwang
,
Joe Neeman
,
Ojas Parekh
,
Kevin Thompson
,
John Wright
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

2022
Testing matrix product states.
[BibTeX]
[DOI]
Mehdi Soleimanifar
,
John Wright
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

2021
Unique Games hardness of Quantum Max-Cut, and a vector-valued Borell's inequality.
[BibTeX]
[DOI]
Yeongwoo Hwang
,
Joe Neeman
,
Ojas Parekh
,
Kevin Thompson
,
John Wright
CoRR, 2021

MIP* = RE.
[BibTeX]
[DOI]
Zhengfeng Ji
,
Anand Natarajan
,
Thomas Vidick
,
John Wright
,
Henry Yuen
Commun. ACM, 2021

Quantum soundness of testing tensor codes.
[BibTeX]
[DOI]
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.
[BibTeX]
[DOI]
Zhengfeng Ji
,
Anand Natarajan
,
Thomas Vidick
,
John Wright
,
Henry Yuen
CoRR, 2020

2019
NEEXP in MIP.
[BibTeX]
[DOI]
Anand Natarajan
,
John Wright
CoRR, 2019

Quantum state certification.
[BibTeX]
[DOI]
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.
[BibTeX]
[DOI]
Anand Natarajan
,
John Wright
Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018
Which Distribution Distances are Sublinearly Testable?
[BibTeX]
[DOI]
Constantinos Daskalakis
,
Gautam Kamath
,
John Wright
Electron. Colloquium Comput. Complex., 2018

2017
Improved NP-Inapproximability for 2-Variable Linear Equations.
[BibTeX]
[DOI]
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).
[BibTeX]
[DOI]
Ryan O'Donnell
,
John Wright
SIGACT News, 2017

Improved and simplified inapproximability for k-means.
[BibTeX]
[DOI]
Euiwoong Lee
,
Melanie Schmidt
,
John Wright
Inf. Process. Lett., 2017

Efficient quantum tomography II.
[BibTeX]
[DOI]
Ryan O'Donnell
,
John Wright
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

2016
Efficient quantum tomography.
[BibTeX]
[DOI]
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.
[BibTeX]
[DOI]
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.
[BibTeX]
[DOI]
Ryan O'Donnell
,
John Wright
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Adaptivity Helps for Testing Juntas.
[BibTeX]
[DOI]
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.
[BibTeX]
[DOI]
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.
[BibTeX]
[DOI]
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.
[BibTeX]
[DOI]
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.
[BibTeX]
[DOI]
Madhur Tulsiani
,
John Wright
,
Yuan Zhou
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

A Composition Theorem for Parity Kill Number.
[BibTeX]
[DOI]
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.
[BibTeX]
[DOI]
Andrew Wan
,
John Wright
,
Chenggang Wu
CoRR, 2013

2012
A new point of NP-hardness for unique games.
[BibTeX]
[DOI]
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.
[BibTeX]
[DOI]
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.
[BibTeX]
[DOI]
Ryan O'Donnell
,
John Wright
,
Yuan Zhou
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011


  Loading...