Jonathan Shi

According to our database, Jonathan Shi authored at least 15 papers between 2009 and 2024.

Collaborative distances:

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

2024

A Sum-of-Squares Hierarchy in the Absence of Pointwise Proofs I: Energy Certificates.

Juspreet Singh Sandhu, Jonathan Shi

CoRR, 2024

2023

Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses.

Chris Jones, Kunal Marwaha, Juspreet Singh Sandhu, Jonathan Shi

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

2022

Cut Sparsification of the Clique Beyond the Ramanujan Bound: A Separation of Cut Versus Spectral Sparsification.

Antares Chen, Jonathan Shi, Luca Trevisan

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Limitations of Local Quantum Algorithms on Random MAX-k-XOR and Beyond.

Chi-Ning Chou, Peter J. Love, Juspreet Singh Sandhu, Jonathan Shi

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

2021

Limitations of Local Quantum Algorithms on Maximum Cuts of Sparse Hypergraphs and Beyond.

Chi-Ning Chou, Peter J. Love, Juspreet Singh Sandhu, Jonathan Shi

CoRR, 2021

2020

Cut Sparsification of the Clique Beyond the Ramanujan Bound.

Antares Chen, Jonathan Shi, Luca Trevisan

CoRR, 2020

2019

Tensor rank decompositions via the pseudo-moment method.

Jonathan Shi

PhD thesis, 2019

A Robust Spectral Algorithm for Overcomplete Tensor Decomposition.

Samuel B. Hopkins, Tselil Schramm, Jonathan Shi

Proceedings of the Conference on Learning Theory, 2019

2017

Sparse Quantum Codes From Quantum Circuits.

Dave Bacon, Steven T. Flammia, Aram W. Harrow, Jonathan Shi

IEEE Trans. Inf. Theory, 2017

2016

Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors.

Samuel B. Hopkins, Tselil Schramm, Jonathan Shi, David Steurer

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

Polynomial-Time Tensor Decompositions with Sum-of-Squares.

Tengyu Ma, Jonathan Shi, David Steurer

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015

Speeding up sum-of-squares for tensor decomposition and planted sparse vectors.

Samuel B. Hopkins, Tselil Schramm, Jonathan Shi, David Steurer

CoRR, 2015

Tensor principal component analysis via sum-of-squares proofs.

Samuel B. Hopkins, Jonathan Shi, David Steurer

CoRR, 2015

Tensor principal component analysis via sum-of-square proofs.

Samuel B. Hopkins, Jonathan Shi, David Steurer

Proceedings of The 28th Conference on Learning Theory, 2015

2009

A tractable time-cost tradeoff algorithm for project activity management.

Kun-Jung Hsu, Jonathan Shi

Proceedings of the 2009 Spring Simulation Multiconference, SpringSim 2009, 2009