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.
IACR Cryptol. ePrint Arch., 2023

Unique Games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell's inequality.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

2022
Testing matrix product states.
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.
CoRR, 2021

MIP* = RE.
Commun. ACM, 2021

Quantum soundness of testing tensor codes.
Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020
Quantum soundness of the classical low individual degree test.
CoRR, 2020

2019
NEEXP in MIP.
CoRR, 2019

Quantum state certification.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

NEEXP is Contained in MIP.
Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018
Which Distribution Distances are Sublinearly Testable?
Electron. Colloquium Comput. Complex., 2018

2017
Improved NP-Inapproximability for 2-Variable Linear Equations.
Theory Comput., 2017

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

Improved and simplified inapproximability for k-means.
Inf. Process. Lett., 2017

Efficient quantum tomography II.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

2016
Efficient quantum tomography.
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.
Electron. Colloquium Comput. Complex., 2015

Quantum Spectrum Testing.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Adaptivity Helps for Testing Juntas.
Proceedings of the 30th Conference on Computational Complexity, 2015

2014
New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover.
ACM Trans. Comput. Theory, 2014

Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Decision trees, protocols and the entropy-influence conjecture.
Proceedings of the Innovations in Theoretical Computer Science, 2014

Optimal Strong Parallel Repetition for Projection Games on Low Threshold Rank Graphs.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

A Composition Theorem for Parity Kill Number.
Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

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

2012
A new point of NP-hardness for unique games.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

A New Point of NP-Hardness for 2-to-1 Label Cover.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011
The Fourier Entropy-Influence Conjecture for Certain Classes of Boolean Functions.
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011


  Loading...