Arsen Vasilyan

Arsen Vasilyan

Auto-generated profile, based on publicly available information

Arsen Vasilyan

University of Texas at Austin, Austin, USA

Research Focus & Metrics

Academic Career Length

2Years (2025-Present)

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

Representative Publications

View All Publications
23 January 2025 in SIAM Journal on Computing
Verified
Journal Article
Closed access
JLJane Lange
Jane Lange
AVArsen Vasilyan
Arsen Vasilyan
We give the first agnostic, efficient, proper learning algorithm for monotone Boolean functions. Given [Formula: see text] uniformly random examples of an unknown function [Formula: see text], our algorithm outputs a hypothesis [Formula: see text] that is monotone and [Formula: see text]-close to [Formula: see text], where [Formula: see text] is the distance from [Formula: see text] to the closest monotone function. The running time of the algorithm (and consequently the size and evaluation time of the hypothesis) is also [Formula: see text], nearly matching the lower bound of [E. Blais et al., Proceedings of the 19 th International Workshop on Randomness and Computation, 2015, pp. 512–527]. We also give an algorithm for estimating up to additive error [Formula: see text] the distance of an unknown function [Formula: see text] to monotone using a run-time of [Formula: see text]. Previously, for both of these problems, sample-efficient algorithms were known, but these algorithms were not run-time efficient. Our work thus closes this gap in our knowledge between the run-time and sample complexity. This work builds upon the improper learning algorithm of [N. H. Bshouty and C. Tamon, J. ACM, 43 (1996), pp. 747–770] and the proper semiagnostic learning algorithm of [J. Lange, R. Rubinfeld, and A. Vasilyan, Proceedings of the 63 rd Annual Symposium on Foundations of Computer Science, IEEE, 2022, pp. 75–86], which obtains a nonmonotone Boolean-valued hypothesis, then “corrects” it to monotone using query-efficient local computation algorithms on graphs. This black-box correction approach can achieve no error better than [Formula: see text] information-theoretically; we bypass this barrier by (a) augmenting the improper learner with a convex optimization step, and (b) learning and correcting a real-valued function before rounding its values to Boolean. Our real-valued correction algorithm solves the “poset sorting” problem of Lange, Rubinfeld, and Vasilyan for functions over general posets with non-Boolean labels.

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