From the 1 of 12 linked papers with an AI index.
12 papers
A Subsampling Theorem for Constraint Satisfaction Problems with Large Arity
Martino Bernasconi, Matteo Castiglioni, Andrea Celli +2
Subsampling theorems for constraint satisfaction problems (CSPs) guarantee that the value of the CSP is approximately preserved after restricting it to small random subsets of vari…
A Unifying Framework for Quasi-Polynomial Optimization of Fixed-degree Polynomials
Martino Bernasconi, Matteo Castiglioni, Andrea Celli +1
The paper presents a method to construct ε‑covers for the joint value sets of constant-degree polynomials over convex domains, enabling quasi‑polynomial time approximation schemes…
Theoretical Foundations of @ Reinforcement Learning
Riccardo Poiani, Martino Bernasconi, Andrea Celli
Reinforcement Learning is a cornerstone technique for modern large reasoning models. Usually, for difficult tasks such as code generation and theorem proving, the agent is evaluate…
The Complexity of Min-Max Optimization for Quadratic Polynomials
Martino Bernasconi, Matteo Castiglioni, Andrea Celli +1
We prove that computing approximate stationary points of min-max optimization over the hypercube is PPAD-hard for quadratic polynomials. This holds even when the polynomials are mu…
Regret Minimization in Single-Dimensional Contract-Design with Binary Actions
Riccardo Poiani, Martino Bernasconi, Andrea Celli
We study principal-agent problems in which a principal commits to an outcome-dependent payment scheme (i.e., a contract) in order to induce an agent to take a costly action leading…
Optimal Rates for Feasible Payoff Set Estimation in Games
Annalisa Barbara, Riccardo Poiani, Martino Bernasconi +1
We study a setting in which two players play a (possibly approximate) Nash equilibrium of a bimatrix game, while a learner observes only their actions and has no knowledge of the e…