Tselil Schramm

According to our database, Tselil Schramm authored at least 35 papers between 2014 and 2024.

Collaborative distances:

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

2024

Discrepancy Algorithms for the Binary Perceptron.

Shuangping Li, Tselil Schramm, Kangjie Zhou

CoRR, 2024

Semidefinite Programs Simulate Approximate Message Passing Robustly.

Misha Ivkov, Tselil Schramm

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

2023

Spectral clustering in the Gaussian mixture block model.

Shuangping Li, Tselil Schramm

CoRR, 2023

Local and Global Expansion in Random Geometric Graphs.

Siqi Liu, Sidhanth Mohanty, Tselil Schramm, Elizabeth Yang

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

2022

Testing thresholds for high-dimensional sparse random geometric graphs.

Siqi Liu, Sidhanth Mohanty, Tselil Schramm, Elizabeth Yang

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics.

Afonso S. Bandeira, Ahmed El Alaoui, Samuel B. Hopkins, Tselil Schramm, Alexander S. Wein, Ilias Zadik

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

The SDP Value of Random 2CSPs.

Amulya Musipatla, Ryan O'Donnell, Tselil Schramm, Xinyu Wu

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

2021

Sherali-Adams Strikes Back.

Ryan O'Donnell, Tselil Schramm

Theory Comput., 2021

Playing unique games on certified small-set expanders.

Mitali Bafna, Boaz Barak, Pravesh K. Kothari, Tselil Schramm, David Steurer

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Robust Regression Revisited: Acceleration and Improved Estimation Rates.

Arun Jambulapati, Jerry Li, Tselil Schramm, Kevin Tian

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

The Strongish Planted Clique Hypothesis and Its Consequences.

Pasin Manurangsi, Aviad Rubinstein, Tselil Schramm

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Non-asymptotic approximations of neural networks by Gaussian processes.

Ronen Eldan, Dan Mikulincer, Tselil Schramm

Proceedings of the Conference on Learning Theory, 2021

Statistical Query Algorithms and Low Degree Tests Are Almost Equivalent.

Matthew S. Brennan, Guy Bresler, Samuel B. Hopkins, Jerry Li, Tselil Schramm

Proceedings of the Conference on Learning Theory, 2021

2020

Computational Barriers to Estimation from Low-Degree Polynomials.

Tselil Schramm, Alexander S. Wein

CoRR, 2020

Subexponential LPs Approximate Max-Cut.

Samuel B. Hopkins, Tselil Schramm, Luca Trevisan

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

The threshold for SDP-refutation of random regular NAE-3SAT.

Yash Deshpande, Andrea Montanari, Ryan O'Donnell, Tselil Schramm, Subhabrata Sen

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs.

Boaz Barak, Chi-Ning Chou, Zhixian Lei, Tselil Schramm, Yueqi Sheng

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

SOS Lower Bounds with Hard Constraints: Think Global, Act Local.

Pravesh K. Kothari, Ryan O'Donnell, Tselil Schramm

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

A Robust Spectral Algorithm for Overcomplete Tensor Decomposition.

Samuel B. Hopkins, Tselil Schramm, Jonathan Shi

Proceedings of the Conference on Learning Theory, 2019

2018

On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique.

Samuel B. Hopkins, Pravesh Kothari, Aaron Henry Potechin, Prasad Raghavendra, Tselil Schramm

ACM Trans. Algorithms, 2018

High-dimensional estimation via sum-of-squares proofs.

Prasad Raghavendra, Tselil Schramm, David Steurer

CoRR, 2018

Computing Exact Minimum Cuts Without Knowing the Graph.

Aviad Rubinstein, Tselil Schramm, S. Matthew Weinberg

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

2017

Random Matrices and the Sum-of-Squares Hierarchy.

Tselil Schramm

PhD thesis, 2017

Braess's paradox for the spectral gap in random graphs and delocalization of eigenvectors.

Ronen Eldan, Miklós Z. Rácz, Tselil Schramm

Random Struct. Algorithms, 2017

Strongly refuting random CSPs below the spectral threshold.

Prasad Raghavendra, Satish Rao, Tselil Schramm

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

The Power of Sum-of-Squares for Detecting Hidden Structures.

Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, David Steurer

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Fast and robust tensor decomposition with applications to dictionary learning.

Tselil Schramm, David Steurer

Proceedings of the 30th Conference on Learning Theory, 2017

2016

Global and Local Information in Clustering Labeled Block Models.

Varun Kanade, Elchanan Mossel, Tselil Schramm

IEEE Trans. Inf. Theory, 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

2015

Low-Rank Matrix Completion with Adversarial Missing Entries.

Tselil Schramm, Benjamin Weitz

CoRR, 2015

Tight Lower Bounds for Planted Clique in the Degree-4 SOS Program.

Prasad Raghavendra, Tselil Schramm

CoRR, 2015

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

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

CoRR, 2015

Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs.

Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, Grigory Yaroslavtsev

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

2014

Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs.

Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, Grigory Yaroslavtsev

CoRR, 2014

Gap Amplification for Small-Set Expansion via Random Walks.

Prasad Raghavendra, Tselil Schramm

Proceedings of the Approximation, 2014