Konstantinos Stavropoulos

Konstantinos Stavropoulos

Auto-generated profile, based on publicly available information

Konstantinos Stavropoulos

University of Texas at Austin, Austin, USA

Research Focus & Metrics

Academic Career Length

1Year (2026-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
9 June 2026
Verified
Conference Paper
Open access
GCGautam Chandrasekaran
Gautam Chandrasekaran
AKAdam R. Klivans
Adam R. Klivans
KSKonstantinos Stavropoulos
Konstantinos Stavropoulos
AVArsen Vasilyan
Arsen Vasilyan

9 June 2026
Verified
Conference Paper
Open access
GCGautam Chandrasekaran
Gautam Chandrasekaran
RMRaghu Meka
Raghu Meka
KSKonstantinos Stavropoulos
Konstantinos Stavropoulos

9 June 2026
Verified
Conference Paper
Open access
PGParikshit Gopalan
Parikshit Gopalan
KSKonstantinos Stavropoulos
Konstantinos Stavropoulos
KTKunal Talwar
Kunal Talwar
PTPranay Tankala
Pranay Tankala

3 September 2026 in TheoretiCS
Verified
Journal Article
Open access
PDF file
GCGautam Chandrasekaran
Gautam Chandrasekaran
AKAdam Klivans
Adam Klivans
VKVasilis Kontonis
Vasilis Kontonis
RMRaghu Meka
Raghu Meka
KSKonstantinos Stavropoulos
Konstantinos Stavropoulos
In traditional models of supervised learning, the goal of a learner-- given examples from an arbitrary joint distribution on $\mathbb{R}^d \times \{\pm 1\}$-- is to output a hypothesis that is competitive (to within $ε$) of the best fitting concept from some class. In order to escape strong hardness results for learning even simple concept classes, we introduce a smoothed-analysis framework that requires a learner to compete only with the best classifier that is robust to small random Gaussian perturbation. This subtle change allows us to give a wide array of learning results for any concept that (1) depends on a low-dimensional subspace (aka multi-index model) and (2) has a bounded Gaussian surface area. This class includes functions of halfspaces and (low-dimensional) convex sets, cases that are only known to be learnable in non-smoothed settings with respect to highly structured distributions such as Gaussians. Our definition of smoothed agnostic learning is an interpolation between the case where the instance distribution $D$ and the optimal classifier can be arbitrarily coupled (which corresponds to agnostic learning and $σ= 0$) and completely decoupled (when $σ= \infty$). This decoupling allows us to avoid worst-case concepts that can encode complexity-theoretic primitives. Surprisingly, our analysis also yields new results for traditional non-smoothed frameworks such as learning with margin. In particular, we obtain the first algorithm for agnostically learning intersections of $k$-halfspaces in time $k^{\mathrm{poly}(\frac{\log k}{εγ}) }$ where $γ$ is the margin parameter. Before our work, the best-known runtime was exponential in $k$ (Arriaga and Vempala, FOCS' 99). 50 pages. This is the TheoretiCS journal version