The paper "What Energy Functions Can Be Minimized via Graph Cuts?" by Vladimir Kolmogorov and Ramin Zabih characterizes the energy functions that can be minimized using graph cuts, a technique widely used in computer vision for solving energy minimization problems. The authors focus on binary-valued variables and define two classes of energy functions: $\mathcal{F}^2$, which can be written as a sum of functions of up to two variables at a time, and $\mathcal{F}^3$, which can be written as a sum of functions of up to three variables at a time. They provide necessary and sufficient conditions for these classes to be graph-representable, meaning that the minimum cut on a constructed graph minimizes the energy function. The main results include: 1. A necessary condition for any energy function to be graph-representable. 2. A sufficient condition for energy functions in $\mathcal{F}^3$. 3. A general-purpose construction to minimize energy functions in $\mathcal{F}^3$. The paper also discusses the application of these results to various vision problems, such as stereo, motion, image restoration, and scene reconstruction. The authors show that their results generalize many previous constructions and provide a significant generalization of energy minimization methods used in various applications.The paper "What Energy Functions Can Be Minimized via Graph Cuts?" by Vladimir Kolmogorov and Ramin Zabih characterizes the energy functions that can be minimized using graph cuts, a technique widely used in computer vision for solving energy minimization problems. The authors focus on binary-valued variables and define two classes of energy functions: $\mathcal{F}^2$, which can be written as a sum of functions of up to two variables at a time, and $\mathcal{F}^3$, which can be written as a sum of functions of up to three variables at a time. They provide necessary and sufficient conditions for these classes to be graph-representable, meaning that the minimum cut on a constructed graph minimizes the energy function. The main results include: 1. A necessary condition for any energy function to be graph-representable. 2. A sufficient condition for energy functions in $\mathcal{F}^3$. 3. A general-purpose construction to minimize energy functions in $\mathcal{F}^3$. The paper also discusses the application of these results to various vision problems, such as stereo, motion, image restoration, and scene reconstruction. The authors show that their results generalize many previous constructions and provide a significant generalization of energy minimization methods used in various applications.