Stefan Tiegel

activity

20182026

most citedImproved Hardness Results for Learning Intersections of Halfspaces

1 citations · 5 across the 13 of their papers we have counts for

collaborators

Showing 2026Show all

2 papers · 1 filter

cs.DS2026

Algorithms with Polynomially-Improved Approximation Factors for the $2 \to q$ Norm, and Applications

Samuel B. Hopkins, Stefan Tiegel

The $2 \to q$ norm of a matrix $X \in R^{n \times d}$ is defined as $∥ X ∥_{2 \to q} = sup_{∥ v ∥_{2} = 1} ∥ X v ∥_{q}$ . We give…

cs.CC2026

Rigorous Implications of the Low-Degree Heuristic

Jun-Ting Hsieh, Daniel M. Kane, Pravesh K. Kothari +3

Over the past decade, the low-degree heuristic has been used to estimate the algorithmic thresholds for a wide range of average-case planted vs null distinguishing problems. Such r…

Algorithms with Polynomially-Improved Approximation Factors for the 2→q Norm, and Applications

Rigorous Implications of the Low-Degree Heuristic

Algorithms with Polynomially-Improved Approximation Factors for the $2 \to q$ Norm, and Applications