Tselil Schramm
where else to find them
no profile links on file
what they talk about
where they keep going back
no series more than once — all 9 in the filters
on a stage with
- Aviad Rubinsteinonce
- Pasin Manurangsionce
who talks about the same things
nobody close enough yet
| title | conference | date |
|---|---|---|
| Something about new average-case hard problems? | Obfuscation | 2025-06-23 |
Tutorial-style exposition of the low-degree polynomials model uses the sum of squared low-degree Fourier/Hermite coefficients — called the low-degree… | ||
| Some Easy Optimization Problems Have the Overlap-Gap Property | Joint IFML/MPG Symposium 2024 | 2024-11-19 |
Shows that some easy problems like S–T shortest path in Gn,Θ(log n)/n nevertheless satisfy an ensemble OGP: correlated graph sequences force near-optimal paths… | ||
| Higher-dimensional Expansion of Random Geometric Complexes | Structural Results 2023 | 2023-07-20 |
Shows that triangles in a random geometric graph on the D-sphere produce a sparse 2D spectral expander: pick C log n dimensions and edge probability p =… | ||
| Computational Barriers to Estimation from Low-Degree Polynomials | Rigorous Evidence for Information-Computation Trade-offs | 2021-09-13 |
Considers the spiked Gaussian matrix model with K = N^alpha nonzeros and SNR lambda = N^{beta-alpha}, and shows a concrete lower bound: against no… | ||
| The Strongish Planted Clique Hypothesis and Its Consequences | ITCS 2021 | 2021-01-06 |
Postulates that for kappa = N^{0.1} planted clique cannot be solved in time N^{o(log N)} and uses a randomized graph product that samples N random L‑vertex… | ||
| Graph Matching in Correlated Random Graphs via Small Subgraph Statistics | Concentration of Measure Phenomena | 2020-10-19 |
Gives a quasi-polynomial-time algorithm that recovers the planted permutation between two correlated G(n,p) graphs when gamma is constant (example gamma ≈… | ||
| Pedagogical Talk: Frameworks for Information-Computation Tradeoffs | Computational Phase Transitions (Simons Institute, 2020) | 2020-09-21 |
Shows concrete reductions: if a degree-d sum-of-squares relaxation distinguishes a noise‑robust planted hypothesis, then an explicit degree‑O(d) spectral test… | ||
| Max Cut with Linear Programs: Sherali-Adams Strikes Back | Hyperbolic Polynomials and Hyperbolic Programming | 2019-04-30 |
Claim: linear programs from Sherali‑Adams level D can certify max‑cut ≲ 1/2+ε on graphs whose random‑walk eigenvalues are ≤ 1/√δ by using random‑walk spider… | ||
| Fast Spectral Algorithms from Sum-of-Squares Analyses | Hierarchies, Extended Formulations and Matrix-Analytic Techniques (2017) | 2017-11-06 |
Shows how to turn a degree-6 SOS guarantee for robust order‑4 symmetric tensor decomposition into a near‑linear spectral procedure: assume the square‑reshaping… | ||
| nothing matches | ||