<p>In this thesis we are concerned with the complexity of formalizing reasoning in Combinatorial Matrix Theory (CMT). We are interested in the strength of the bounded arithmetic theories necessary in order to prove the fundamental results of this field. Bounded Arithmetic can be seen as the uniform counterpart of Propositional Proof Complexity.</p> <p>Perhaps the most famous and fundamental theorem in CMT is the K{\"o}nig's Min-Max Theorem $(\KMM)$ which arises naturally in all areas of combinatorial algorithms. As far as we know, in this thesis we give the first feasible proof of $\KMM$. Our results show that Min-Max reasoning can be formalized with uniform Extended Frege.</p> <p>We show, by introducing new proof techniques, that the first order theory $\LA$ with induction restricted to $\Sigma_1^B$ formulas---i.e., restricted to bounded existential matrix quantification---is sufficient to formalize a large portion of CMT, in particular $\KMM$. $\Sigma_1^B$-$\LA$ corresponds to polynomial time reasoning, also known as $\ELA$.</p> <p>While we consider matrices over $\{0,1\}$, the underlying ring is $\mathbb{Z}$, since we require that $\Sigma A$ compute the number of 1s in the matrix $A$ (which for a 0-1 matrix is simply the sum of all entries---meaning $\Sigma A$). Thus, over $\mathbb{Z}$, $\LA$ translates to $\TC^0$-Frege, while, as mentioned before, $\ELA$ translates into Extended Frege.</p> <p>In order to prove $\KMM$ in $\ELA$, we need to restrict induction to $\Sigma_1^B$ formulas. The main technical contribution is presented in Claim~4.3.4, ~Section~4.3.3. Basically, we introduce a polynomial time procedure, whose proof of correctness can be shown with $\ELA$, that works as follow: given a matrix of size $e \times f$ such that $e\leq f$, where the minimum cover is of size $e$, our procedure computes a maximum selection of size $e$, row by row.</p> <p>Furthermore, we show that Menger's Theorem, Hall's Theorem, and Dilworth's Theorem---theorems related to $\KMM$---can also be proven feasibly; in fact, all these theorems are equivalent to KMM, and the equivalence can be shown in $\LA$. We believe that this captures the proof complexity of Min-Max reasoning rather completely.</p> <p>We also present a new Permutation-Based algorithm for computing a Minimum Vertex Cover from a Maximum Matching in a bipartite graph. Our algorithm is linear-time and computationally very simple: it permutes the rows and columns of the matrix representation of the bipartite graph in order to extract the vertex cover from a maximum matching in a recursive fashion. Our Permutation-Based algorithm uses properties of $\KMM$ Theorem and it is interesting for providing a new permutation---and CMT---perspective on a well-known problem.</p> / Doctor of Philosophy (PhD)

Dans cette thèse, nous étudions un principe général de convexification permettant de traiter certainsproblèmes variationnels non convexes sur Rd. Grâce à ce principe nous pouvons mettre en oeuvre lespuissantes techniques de dualité et ramener de tels problèmes à des formulations de type primal–dualdans Rd+1, rendant ainsi efficace la recherche numérique de minima globaux. Une théorie de ladualité et des champs de calibration est reformulée dans le cas de fonctionnelles à croissance linéaire.Sous certaines hypothèses, cela nous permet de généraliser un principe d’exclusion découvert parVisintin dans les années 1990 et de réduire le problème initial à la minimisation d’une fonctionnelleconvexe sur Rd. Ce résultat s’applique notamment à une classe de problèmes à frontière libre oumulti-phasique donnant lieu à des tests numériques très convaincants au vu de la qualité des interfacesobtenues. Ensuite nous appliquons la théorie des calibrations à un problème classique de surfacesminimales avec frontière libre et établissons de nouveaux résultats de comparaison avec sa varianteoù la fonctionnelle des surfaces minimales est remplacée par la variation totale. Nous généralisonsla notion de calibrabilité introduite par Caselles-Chambolle et Al. et construisons explicitementune solution duale pour le problème associé à la seconde fonctionnelle en utilisant un potentiellocalement Lipschitzien lié à la distance au cut-locus. La dernière partie de la thèse est consacrée auxalgorithmes d’optimisation de type primal-dual pour la recherche de points selle, en introduisant denouvelles variantes plus efficaces en précision et temps calcul. Nous avons en particulier introduit unevariante semi-implicite de la méthode d’Arrow-Hurwicz qui permet de réduire le nombre d’itérationsnécessaires pour obtenir une qualité satisfaisante des interfaces. Enfin nous avons traité la nondifférentiabilité structurelle des Lagrangiens utilisés à l’aide d’une méthode géométrique de projectionsur l’épigraphe offrant ainsi une alternative aux méthodes classiques de régularisation. / In this thesis, we study a general principle of convexification to treat certain non convex variationalproblems in Rd. Thanks to this principle we are able to enforce the powerful duality techniques andbring back such problems to primal-dual formulations in Rd+1, thus making efficient the numericalsearch of a global minimizer. A theory of duality and calibration fields is reformulated in the caseof linear-growth functionals. Under suitable assumptions, this allows us to revisit and extend anexclusion principle discovered by Visintin in the 1990s and to reduce the original problem to theminimization of a convex functional in Rd. This result is then applied successfully to a class offree boundary or multiphase problems that we treat numerically obtaining very accurate interfaces.On the other hand we apply the theory of calibrations to a classical problem of minimal surfaceswith free boundary and establish new results related to the comparison with its variant where theminimal surfaces functional is replaced by the total variation. We generalize the notion of calibrabilityintroduced by Caselles-Chambolle and Al. and construct explicitly a dual solution for the problemassociated with the second functional by using a locally Lipschitzian potential related to the distanceto the cut-locus. The last part of the thesis is devoted to primal-dual optimization algorithms forthe search of saddle points, introducing new more efficient variants in precision and computationtime. In particular, we experiment a semi-implicit variant of the Arrow-Hurwicz method whichallows to reduce drastically the number of iterations necessary to obtain a sharp accuracy of theinterfaces. Eventually we tackle the structural non-differentiability of the Lagrangian arising fromour method by means of a geometric projection method on the epigraph, thus offering an alternativeto all classical regularization methods.