3 papers
cs.CC2026
Multiple Planted Structures Below : An SoS Integrality Gap and an SQ Lower Bound
Matvey Mosievskiy, Lev Reyzin
We study computational limitations in \emph{multi-plant} average-case inference problems, in which disjoint planted structures of size are embedded in a random background o…
cs.LG2025
On the Hardness of Learning Regular Expressions
Idan Attias, Lev Reyzin, Nathan Srebro +1
Despite the theoretical significance and wide practical use of regular expressions, the computational complexity of learning them has been largely unexplored. We study the computat…
cs.DS2025
Learning-Augmented Algorithms for Boolean Satisfiability
Idan Attias, Xing Gao, Lev Reyzin
Learning-augmented algorithms are a prominent recent development in beyond worst-case analysis. In this framework, a problem instance is provided with a prediction (``advice'') fro…