1 |
Formalizing Combinatorial Matrix TheoryFernandez, Ariel German G. 10 1900 (has links)
<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)
|
2 |
Do trained actors learn strategic behaviour or are they selected into their positions?Berger, Roger 22 July 2014 (has links) (PDF)
This paper studies if the Minimax theorem holds for the behaviour of trained and untrained actors in the field. This is explored with data from 1043 football penalty kicks from professionals of the German Bundesliga and for 268 penalty kicks from untrained players. Minimax makes good predictions about the collective patterns emerging from the behaviour of experienced actors, as well as about their individual strategic actions. However, this is not true for untrained actors. In the
next step it is explored if, the professional players learned their behaviour, or if they were selected into their roles because they had the required abilities. The data suggests that the professionals were selected by the competitive conditions of professional sports.
|
3 |
Do trained actors learn strategic behaviour or are they selected into their positions?: empirical evidence from penalty kickingBerger, Roger January 2013 (has links)
This paper studies if the Minimax theorem holds for the behaviour of trained and untrained actors in the field. This is explored with data from 1043 football penalty kicks from professionals of the German Bundesliga and for 268 penalty kicks from untrained players. Minimax makes good predictions about the collective patterns emerging from the behaviour of experienced actors, as well as about their individual strategic actions. However, this is not true for untrained actors. In the
next step it is explored if, the professional players learned their behaviour, or if they were selected into their roles because they had the required abilities. The data suggests that the professionals were selected by the competitive conditions of professional sports.
|
Page generated in 0.0176 seconds