Jonathan Shi

List of research outcomes

This list is not complete and representing at the moment only items from zbMATH Open and arXiv. We are working on additional sources - please check back here soon!

Publication	Date of Publication	Type
Polynomial-time tensor decompositions with sum-of-squares	2025-08-06	Paper
Random Max-CSPs inherit algorithmic hardness from spin glasses	2024-09-25	Paper
Cut sparsification of the Clique beyond the Ramanujan bound: a separation of cut versus spectral sparsification	2024-07-19	Paper
Limitations of local quantum algorithms on random MAX-k-XOR and beyond	2024-06-24	Paper
Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses	2022-10-06	Paper
Cut Sparsification of the Clique Beyond the Ramanujan Bound: A Separation of Cut Versus Spectral Sparsification	2020-08-12	Paper
Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors Proceedings of the forty-eighth annual ACM symposium on Theory of Computing	2017-09-29	Paper
Sparse Quantum Codes From Quantum Circuits IEEE Transactions on Information Theory	2017-07-27	Paper
Sparse quantum codes from quantum circuits Proceedings of the forty-seventh annual ACM symposium on Theory of Computing	2015-08-21	Paper
Efficient computation of the Kauffman bracket Journal of Knot Theory and its Ramifications	2014-09-04	Paper

Research outcomes over time

This page was built for person: Jonathan Shi