In everyday conversation &quot;if&quot; is one of the most frequently used conjunctions. This dissertation investigates what meaning an everyday conditional transmits and what inferences it licenses. It is suggested that the nature of the relation between the two propositions in a conditional might play a major role for both questions. Thus, in the experiments reported here conditional statements that describe a causal relationship (e.g., &quot;If you touch that wire, you will receive an electric shock&quot;) were compared to arbitrary conditional statements in which there is no meaningful relation between the antecedent and the consequent proposition (e.g., &quot;If Napoleon is dead, then Bristol is in England&quot;).<br> Initially, central assumptions from several approaches to the meaning and the reasoning from causal conditionals will be integrated into a common model. In the model the availability of exceptional situations that have the power to generate exceptions to the rule described in the conditional (e.g., the electricity is turned off), reduces the subjective conditional probability of the consequent, given the antecedent (e.g., the probability of receiving an electric shock when touching the wire). This conditional probability determines people's degree of belief in the conditional, which in turn affects their willingness to accept valid inferences (e.g., &quot;Peter touches the wire, therefore he receives an electric shock&quot;) in a reasoning task. Additionally to this indirect pathway, the model contains a direct pathway: Cognitive availability of exceptional situations directly reduces the readiness to accept valid conclusions.<br> The first experimental series tested the integrated model for conditional statements embedded in pseudo-natural cover stories that either established a causal relation between the antecedent and the consequent event (causal conditionals) or did not connect the propositions in a meaningful way (arbitrary conditionals). The model was supported for the causal, but not for the arbitrary conditional statements. Furthermore, participants assigned lower degrees of belief to arbitrary than to causal conditionals. Is this effect due to the presence versus absence of a semantic link between antecedent and consequent in the conditionals?<br> This question was one of the starting points for the second experimental series. Here, the credibility of the conditionals was manipulated by adding explicit frequency information about possible combinations of presence or absence of antecedent and consequent events to the problems (i.e., frequencies of cases of 1. true antecedent with true consequent, 2. true antecedent with false consequent, 3. false antecedent with true consequent, 4. false antecedent with false consequent). This paradigm allows testing different approaches to the meaning of conditionals (Experiment 4) as well as theories of conditional reasoning against each other (Experiment 5).<br> The results of Experiment 4 supported mainly the conditional probability approach to the meaning of conditionals (Edgington, 1995) according to which the degree of belief a listener has in a conditional statement equals the conditional probability that the consequent is true given the antecedent (e.g., the probability of receiving an electric shock when touching the wire). Participants again assigned lower degrees of belief to the arbitrary than the causal conditionals, although the conditional probability of the consequent given the antecedent was held constant within every condition of explicit frequency information. This supports the hypothesis that the mere presence of a causal link enhances the believability of a conditional statement. In Experiment 5 participants solved conditional reasoning tasks from problems that contained explicit frequency information about possible relevant cases. The data favored the probabilistic approach to conditional reasoning advanced by Oaksford, Chater, and Larkin (2000).<br> The two experimental series reported in this dissertation provide strong support for recent probabilistic theories: for the conditional probability approach to the meaning of conditionals by Edgington (1995) and the probabilistic approach to conditional reasoning by Oaksford et al. (2000). In the domain of conditional reasoning, there was additionally support for the modified mental model approaches by Markovits and Barrouillet (2002) and Schroyens and Schaeken (2003). Probabilistic and mental model approaches could be reconciled within a dual-process-model as suggested by Verschueren, Schaeken, and d&#39;Ydewalle (2003). / Im Laufe eines Tages verwenden die meisten Menschen mehrfach Konditionalsätze: Das Wörtchen &quot;wenn&quot; gehört zu den häufigsten Konjunktionen in Alltag, Wissenschaft und Literatur. Die vorliegende Dissertation beschäftigt sich mit der Frage, welche Bedeutung ein Konditionalsatz im alltäglichen Sprachgebrauch übermittelt und welche Inferenzen er erlaubt. Es wird die Vermutung aufgestellt, dass dabei die Art der Relation zwischen den zwei Propositionen in einem Konditional eine bedeutsame Rolle spielen könnte. Daher werden in den Experimenten Konditionalsätze, die eine kausale Beziehung beschreiben (z.B. &quot;Wenn Du das Kabel berührst, bekommst Du einen elektrischen Schlag&quot;) mit arbiträren Konditionalen verglichen, in denen keinerlei sinnvolle Relation zwischen Antezedens und Konsequens besteht (z.B. &quot;Wenn Napoleon tot ist, liegt Bristol in England&quot;).<br> Als erstes werden zentrale Annahmen von mehreren Ansätzen zur Bedeutung und zum Schlußfolgern mit kausalen Konditionalsätzen in ein gemeinsames Modell integriert. In dem Modell reduziert die kognitive Verfügbarkeit von Situationen, die zu Ausnahmen von der Regel im Konditionalsatz führen können (z.B. der Strom ist abgestellt), die subjektive bedingte Wahrscheinlichkeit des Konsequens gegeben das Antezedens (z.B. die Wahrscheinlichkeit, einen Schlag zu bekommen gegeben, dass man das Kabel berührt). Diese subjektive bedingte Wahrscheinlichkeit bestimmt die Glaubwürdigkeit des Konditionals, die wiederum die Bereitwilligkeit beeinflußt, mit der gültige Schlußfolgerungen (z.B. &quot;Peter berührt das Kabel, daher erhält er einen elektrischen Schlag&quot;) in einer Schlußfolgerungsaufgabe akzeptiert werden. Zusätzlich zu dem gerade beschriebenen indirekten Pfad enthält das integrierte Modell zusätzlich einen direkten Pfad: Die kognitive Verfügbarkeit von Ausnahme-Situationen reduziert unmittelbar die Bereitschaft, gültige Schlüsse zu akzeptieren. Die erste Experimentalreihe testete das entwickelte integrierte Model für Konditionalsätze, die in pseudo-natürliche Kontextgeschichten eingebettet wurden. Die Kontextgeschichten stellten entweder eine kausale Relation zwischen Antezedens und Konsequens her (kausale Konditionale) oder stellten die Propositionen in keinerlei sinnvollen Zusammenhang (arbiträre Konditionale). Die empirischen Daten stützen das Modell für die kausalen, aber nicht für die arbiträren Konditionale. Außerdem schätzten die TeilnehmerInnen die arbiträren Konditionalsätzen als weniger glaubwürdig ein als die kausalen Konditionale. Es stellt sich die Frage, ob dieser Unterschied in der Glaubwürdigkeit auf die An- bzw. Abwesenheit einer bedeutungshaltigen Relation zwischen Antezedens und Konsequens im Konditional zurückgeführt werden kann.<br> Diese Frage war einer der Ausgangspunkte für die zweite Experimentalreihe. In dieser wurde die Glaubwürdigkeit der Konditionalsätze kontrolliert manipuliert, indem in den Kontextgeschichten explizite Häufigkeitsinformationen über die vier möglichen Kombinationen von An- bzw. Abwesenheit von Antezedens und Konsequens gegeben wurden (d.h. die Häufigkeit von Fällen mit 1. wahrem Antezedens und wahrem Konsequens, 2. wahrem Antezedens und falschem Konsequens, 3. falschem Antezedens und wahrem Konsequens, 4. falschem Antezedens und falschem Konsequens). Dieses Paradigma ermöglichte ferner, unterschiedliche Ansätze zur Bedeutung des Konditionals (Experiment 4) ebenso wie Theorien zum konditionalen Schlußfolgern gegeneinander zu testen (Experiment 5). Die Befunde aus Experiment 4 stützen im wesentlichen Edgingtons Ansatz zur Bedeutung von Konditionalen (Edgington, 1995). Nach diesem Ansatz entspricht die Glaubwürdigkeit, die ein Zuhörer einem Konditionalsatz einräumt, der bedingten Wahrscheinlichkeit, dass das Konsequens wahr ist gegeben das Antezedens (z.B. die Wahrscheinlichkeit, einen Schlag zu bekommen gegeben, dass man das Kabel berührt). Erneut schrieben die TeilnehmerInnen den arbiträren Konditionalsätzen geringere Glaubwürdigkeit zu als den kausalen Sätzen, obwohl diesmal innerhalb jeder Häufigkeitsbedingung die bedingte Wahrscheinlichkeit des Konsequens gegeben das Antezedens konstant gehalten wurde. Dieses Ergebnis stützt die Hypothese, dass die bloße Anwesenheit einer kausalen Beziehung die Glaubwürdigkeit eines Konditionalsatzes erhöht. In Experiment 5 lösten die TeilnehmerInnen konditionale Schlußfolgerungsaufgaben, dabei wurden die Kontextgeschichten um explizite Häufigkeitsangaben ergänzt. Die Ergebnisse favorisieren die probabilistische Theorie zum konditionalen Schließen, die von Oaksford, Chater, und Larkin (2000) vorgeschlagen wurde. Beide Experimentalreihen lieferten deutliche Evidenz für probabilistische Theorien: für Edgingtons Ansatz zur Bedeutung von Konditionalsätzen (Edgington, 1995) und für die probabilistische Theorie des konditionalen Schließens von Oaksford et al. (2000). Im Bereich des konditionalen Schließens stützen die Daten gleichzeitig die modifizierten mentalen Modell-Theorien von Markovits und Barrouillet (2002) und Schroyens und Schaeken (2003). Probabilistische und mentale Modell-Theorien könnten im Rahmen eines Dualen-Prozeß-Modells wie es von Verschueren, Schaeken und d&#39;Ydewalle (2003) vorgeschlagen wurde, miteinander versöhnt werden.

Diese Arbeit nutzt und verfeinert Methoden der Komplexitätstheorie, um mit diesen die Komplexität dünner Instanzen zu untersuchen. Dazu gehören etwa Graphen mit wenigen Kanten oder Formeln mit wenigen Bedingungen beschränkter Weite. Dabei ergeben sich zwei natürliche Fragestellungen: (a) Gibt es einen effizienten Algorithmus, der beliebige Instanzen eines NP-schweren Problems auf äquivalente, dünne Instanzen reduziert? (b) Gibt es einen Algorithmus, der dünne Instanzen NP-schwerer Probleme bedeutend schneller löst als allgemeine Instanzen gelöst werden können? Wir formalisieren diese Fragen für verschiedene Probleme und zeigen, dass positive Antworten jeweils zu komplexitätstheoretischen Konsequenzen führen, die als unwahrscheinlich gelten. Frage (a) wird als Kommunikation modelliert, in der zwei Akteure kooperativ eine NP-schwere Sprache entscheiden möchten und dabei möglichst wenig kommunizieren. Unter der komplexitätstheoretischen Annahme, dass coNP keine Teilmenge von NP/poly ist, erhalten wir aus unseren Ergebnissen erstaunlich scharfe untere Schranken für interessante Parameter aus verschiedenen Teilgebieten der theoretischen Informatik. Im Speziellen betrifft das die Ausdünnung von Formeln, die Kernelisierung aus der parameterisierten Komplexitätstheorie, die verlustbehaftete Kompression von Entscheidungsproblemen, und die Theorie der probabilistisch verifizierbaren Beweise. Wir untersuchen Fragestellung (b) anhand der Exponentialzeitkomplexität von Zählproblemen. Unter (Varianten) der bekannten Exponentialzeithypothese (ETH) erhalten wir exponentielle untere Schranken für wichtige #P-schwere Probleme: das Berechnen der Zahl der erfüllenden Belegungen einer 2-KNF Formel, das Berechnen der Zahl aller unabhängigen Mengen in einem Graphen, das Berechnen der Permanente einer Matrix mit Einträgen 0 und 1, das Auswerten des Tuttepolynoms an festen Punkten. / In this thesis, we use and refine methods of computational complexity theory to analyze the complexity of sparse instances, such as graphs with few edges or formulas with few constraints of bounded width. Two natural questions arise in this context: (a) Is there an efficient algorithm that reduces arbitrary instances of an NP-hard problem to equivalent, sparse instances? (b) Is there an algorithm that solves sparse instances of an NP-hard problem significantly faster than general instances can be solved? We formalize these questions for different problems and show that positive answers for these formalizations would lead to consequences in complexity theory that are considered unlikely. Question (a) is modeled by a communication process, in which two players want to cooperatively decide an NP-hard language and at the same time communicate as few as possible. Under the complexity-theoretic hypothesis that coNP is not in NP/poly, our results imply surprisingly tight lower bounds for parameters of interest in several areas, namely sparsification, kernelization in parameterized complexity, lossy compression, and probabilistically checkable proofs. We study the question (b) for counting problems in the exponential time setting. Assuming (variants of) the exponential time hypothesis (ETH), we obtain asymptotically tight, exponential lower bounds for well-studied #P-hard problems: Computing the number of satisfying assignments of a 2-CNF formula, computing the number of all independent sets in a graph, computing the permanent of a matrix with entries 0 and 1, evaluating the Tutte polynomial at fixed evaluation points.

The task of 6D object pose estimation, i.e. of estimating an object position (three degrees of freedom) and orientation (three degrees of freedom) from images is an essential building block of many modern applications, such as robotic grasping, autonomous driving, or augmented reality. Automatic pose estimation systems have to overcome a variety of visual ambiguities, including texture-less objects, clutter, and occlusion. Since many applications demand real time performance the efficient use of computational resources is an additional challenge. In this thesis, we will take a probabilistic stance on trying to overcome said issues. We build on a highly successful automatic pose estimation framework based on predicting pixel-wise correspondences between the camera coordinate system and the local coordinate system of the object. These dense correspondences are used to generate a pool of hypotheses, which in turn serve as a starting point in a final search procedure. We will present three systems that each use probabilistic modeling and sampling to improve upon different aspects of the framework. The goal of the first system, System I, is to enable pose tracking, i.e. estimating the pose of an object in a sequence of frames instead of a single image. By including information from previous frames tracking systems can resolve many visual ambiguities and reduce computation time. System I is a particle filter (PF) approach. The PF represents its belief about the pose in each frame by propagating a set of samples through time. Our system uses the process of hypothesis generation from the original framework as part of a proposal distribution that efficiently concentrates samples in the appropriate areas. In System II, we focus on the problem of evaluating the quality of pose hypotheses. This task plays an essential role in the final search procedure of the original framework. We use a convolutional neural network (CNN) to assess the quality of an hypothesis by comparing rendered and observed images. To train the CNN we view it as part of an energy-based probability distribution in pose space. This probabilistic perspective allows us to train the system under the maximum likelihood paradigm. We use a sampling approach to approximate the required gradients. The resulting system for pose estimation yields superior results in particular for highly occluded objects. In System III, we take the idea of machine learning a step further. Instead of learning to predict an hypothesis quality measure, to be used in a search procedure, we present a way of learning the search procedure itself. We train a reinforcement learning (RL) agent, termed PoseAgent, to steer the search process and make optimal use of a given computational budget. PoseAgent dynamically decides which hypothesis should be refined next, and which one should ultimately be output as final estimate. Since the search procedure includes discrete non-differentiable choices, training of the system via gradient descent is not easily possible. To solve the problem, we model behavior of PoseAgent as non-deterministic stochastic policy, which is ultimately governed by a CNN. This allows us to use a sampling-based stochastic policy gradient training procedure. We believe that some of the ideas developed in this thesis, such as the sampling-driven probabilistically motivated training of a CNN for the comparison of images or the search procedure implemented by PoseAgent have the potential to be applied in fields beyond pose estimation as well.