3 papers
cs.CC2025
Negations are powerful even in small depth
Bruno Cavalar, Théo Borém Fabris, Partha Mukhopadhyay +2
We study the power of negation in the Boolean and algebraic settings and show the following results. * We construct a family of polynomials in variables, all of whose mon…
cs.CC2025
The Algebraic Cost of a Boolean Sum
Ian Orzel, Srikanth Srinivasan, Sébastien Tavenas +1
It is a well-known fact that the permanent polynomial is complete for the complexity class VNP, and it is largely suspected that the determinant does not share this property, despi…
cs.LG2023
The Sample Complexity Of ERMs In Stochastic Convex Optimization
Daniel Carmon, Roi Livni, Amir Yehudayoff
Stochastic convex optimization is one of the most well-studied models for learning in modern machine learning. Nevertheless, a central fundamental question in this setup remained u…