One of the main criticisms of previously studied label noise models in the PAC-learning framework is the inability of such models to represent the noise in real world data. In this thesis, we study this problem by introducing a framework for modeling label noise and suggesting four new label noise models. We prove positive learnability results for these noise models in learning simple concept classes and discuss the difficulty of the problem of learning other interesting concept classes under these new models. In addition, we study the previous general learning algorithm, called the minimum pn-disagreement strategy, that is used to prove learnability results in the PAC-learning framework both in the absence and presence of noise. Because of limitations of the minimum pn-disagreement strategy, we propose a new general learning algorithm called the minimum nn-disagreement strategy. Finally, for both minimum pn-disagreement strategy and minimum nn-disagreement strategy, we investigate some properties of label noise models that provide sufficient conditions for the learnability of specific concept classes.

This research pursues the use of powerful BDD-based functional circuit analysis to evaluate some approaches to test set generation. Functional representations of the circuit allow the measurement of information about faults that is not directly available through circuit simulation methods, such as probability of random detection and test-space overlap between faults. I have created a software tool that performs experiments to make such measurements and augments existing test generation strategies with this new information. Using this tool, I explored the relationship of fault model difficulty to test set length through fortuitous detection, and I experimented with the application of function-based methods to help reconcile the traditionally opposed goals of making test sets that are both smaller and more effective.

While the characteristic dimensions of electronic systems scale down to micro- or nano-world, their performance is greatly influenced. Micro-fabrication process or variations of the operating situation such as temperature, humidity or pressure are usual cause of dispersion. Therefore, it seems essential to co-integrate self-testing or self-adjustment routines for these microdevices. For this feature, most existing system parameter estimation methods are based on the implementation of high-resolution digital measurements of the system's output. Thus, long design time and large silicon areas are needed, which increases the cost of the micro-fabricated devices. The parameter estimation problems based on binary outputs can be introduced as alternative self-test identification methods, requiring only a 1-bit Analog-to-Digital Converter (ADC) and a 1-bit Digital-to-Analog Converter (DAC).In this thesis, we propose a novel recursive identification method to the problem of system parameter estimation from binary observations. An online identification algorithm with low-storage requirements and small computational complexity is derived. We prove the asymptotic convergence of this method under some assumptions. We show by Monte Carlo simulations that these assumptions do not necessarily have to be met in practice in order to obtain an appropriate performance of the method. Furthermore, we present the first experimental application of this method dedicated to the self-test of integrated micro-electro-mechanical systems (MEMS). The proposed online Built-In Self-Test method is very amenable to integration for the self-testing of systems relying on resistive sensors and actuators, because it requires low memory storage, only a 1-bit ADC and a 1-bit DAC which can be easily implemented in a small silicon area with minimal energy consumption.

Diese Doktorarbeit behandelt neue Methoden der numerischen Evolution von Systemen mit binären Schwarzen Löchern. Wir analysieren und vergleichen Evolutionen von verschiedenen physikalisch motivierten Anfangsdaten und zeigen Resultate der ersten Evolution von so genannten 'Thin Sandwich' Daten, die von der Gruppe in Meudon entwickelt wurden. <br /> Zum ersten Mal wurden zwei verschiedene Anfangsdaten anhand von dreidimensionalen Evolutionen verglichen: die Puncture-Daten und die Thin-Sandwich Daten. Diese zwei Datentypen wurden im Hinblick auf die physikalischen Eigenschaften während der Evolution verglichen. <br /> Die Evolutionen zeigen, dass die Meudon Daten im Vergleich zu Puncture Daten wesentlich mehr Zeit benötigen bevor sie kollidieren. Dies deutet auf eine bessere Abschätzung der Parameter hin. Die Kollisionszeiten der numerischen Evolutionen sind konsistent mit unabhängigen Schätzungen basierend auf Post-Newtonschen Näherungen die vorhersagen, dass die Schwarzen Löcher ca. 60% eines Orbits rotieren bevor sie kollidieren. / This thesis presents new approaches to evolutions of binary black hole systems in numerical relativity. We analyze and compare evolutions from various physically motivated initial data sets, in particular presenting the first evolutions of Thin Sandwich data generated by the Meudon group. <br /> For the first time two different quasi-circular orbit initial data sequences are compared through fully 3d numerical evolutions: Puncture data and Thin Sandwich data (TSD) based on a helical killing vector ansatz. The two different sets are compared in terms of the physical quantities that can be measured from the numerical data, and in terms of their evolutionary behavior. <br /> The evolutions demonstrate that for the latter, "Meudon" datasets, the black holes do in fact orbit for a longer amount of time before they merge, in comparison with Puncture data from the same separation. This indicates they are potentially better estimates of quasi-circular orbit parameters. The merger times resulting from the numerical simulations are consistent with independent Post-Newtonian estimates that the final plunge phase of a black hole inspiral should take 60% of an orbit.

<p>Our main results are that splay trees are faster for sorted insertion, where AVL trees are faster for random insertion. For searching, skip lists are faster than single class top-down splay trees, but two-class and multi-class top-down splay trees can behave better than skip lists.</p>

Shape description is an important problem in computer vision because most vision tasks that require comparing or matching visual entities rely on shape descriptors. In this thesis, two novel shape descriptors are proposed, namely Intersection Consistency Histogram (ICH) and Global Binary Patterns (GBP). The former is based on a local regularity measure called Intersection Consistency (IC), which determines whether edge pixels in an image patch point towards the center or not. The second method, called Global Binary Patterns, represents the shape in binary along horizontal, vertical, diagonal or principal directions. These two methods are extensively analyzed on several databases, and retrieval and running time performances are presented. Moreover, these methods are compared with methods such as Shape Context, Histograms of Oriented Gradients, Local Binary Patterns and Fourier Descriptors. We report that our descriptors perform comparable to these methods.

Wireless Sensor Networks (WSNs) have enticed a strong attention in the research community due to the broad range of applications and services they support. WSNs are composed of intelligent sensor nodes that have the capabilities to monitor different types of environmental phenomena or critical activities. Sensor nodes operate under stringent requirements of scarce power resources, limited storage capacities, limited processing capabilities, and hostile environmental surroundings. However, conserving sensor nodes’ power resources is the top priority requirement in the design of a WSN as it has a direct impact on its lifetime. The IEEE 802.15.4 standard defines a set of specifications for both the PHY layer and the MAC sub-layer that abide by the distinguished requirements of WSNs. The standard’s MAC protocol employs an intelligent backoff algorithm, called the Binary Exponent Backoff (BEB), that minimizes the drainage of power in these networks. In this thesis we present an in-depth study of the IEEE 802.15.4 MAC protocol to highlight both its strong and weak aspects. We show that we have enticing opportunities to improve the performance of this protocol in the context of WSNs. We propose three new backoff algorithms, namely, the Standby-BEB (SB-BEB), the Adaptive Backoff Algorithm (ABA), and the Priority-Based BEB (PB-BEB), to replace the standard BEB. The main contribution of the thesis is that it develops a new design concept that drives the design of efficient backoff algorithms for the IEEE 802.15.4-based WSNs. The concept dictates that controlling the algorithms parameters probabilistically has a direct impact on enhancing the backoff algorithm’s performance. We provide detailed discrete-time Markov-based models (for AB-BEB and ABA) and extensive simulation studies (for the three algorithms) to prove the superiority of our new algorithms over the standard BEB.

In this thesis, contributions are presented in the areas of shape parsing for view-based object recognition and spatio-temporal feature description for action recognition. A probabilistic model for parsing shapes into several distinguishable parts for accurate shape recognition is presented. This approach is based on robust geometric features that permit high recognition accuracy. As the second contribution in this thesis, a binary spatio-temporal feature descriptor is presented. Recent work shows that binary spatial feature descriptors are effective for increasing the efficiency of object recognition, while retaining comparable performance to state of the art descriptors. An extension of these approaches to action recognition is presented, facilitating huge gains in efficiency due to the computational advantage of computing a bag-of-words representation with the Hamming distance. A scene's motion and appearance is encoded with a short binary string. Exploiting the binary makeup of this descriptor greatly increases the efficiency while retaining competitive recognition performance.

As Field-Programmable Gate Array (FPGA) capacity can now support several processors on a single device, the scalability of FPGA design tools and methods has emerged as a major obstacle for the wider use of FPGAs. For example, logic synthesis, which has traditionally been the fastest step in the FPGA Computer-Aided Design (CAD) flow, now takes several hours to complete in a typical FPGA compile. In this work, we address this problem by focusing on two areas. First, we revisit FPGA logic synthesis and attempt to improve its scalability. Specifically, we look at a binary decision diagram (BDD) based logic synthesis flow, referred to as FBDD, where we improve its runtime by several fold with a marginal impact to the resulting circuit area. We do so by speeding up the classical cut generation problem by an order-of-magnitude which enables its application directly at the logic synthesis level. Following this, we introduce a guided partitioning technique using a fast global budgeting formulation, which enables us to optimize individual “pockets” within the circuit without degrading the overall circuit performance. By using partitioning we can significantly reduce the solution space of the logic synthesis problem and, furthermore, open up the possibility of parallelizing the logic synthesis step. The second area we look at is the area of Engineering Change Orders (ECOs). ECOs are incremental modifications to a design late in the design flow. This is beneficial since it is minimally disruptive to the existing circuit which preserves much of the engineering effort invested previously in the design. In a design flow where most of the steps are fully automated, ECOs still remain largely a manual process. This can often tie up a designer for weeks leading to missed project deadlines which is very detrimental to products whose life-cycle can span only a few months. As a solution to this, we show how we can leverage existing logic synthesis techniques to automatically modify a circuit in a minimally disruptive manner. This can significantly reduce the turn-around time when applying ECOs.

This essay examines commitment and abandonment structured as two binary opposites informing For Whom the Bell Tolls. The intention behind this structuring is to highlight Hemingway’s message of the novel, set forth by the epigraph by Donne; everyone is part of mankind and every death diminishes everyone equally. The consistent structuring of characters can be seen by the fact that everyone who is committed, loyal and honest is punished while the reverse is true for people who abandon, desert and betray. The one exception to this is Pilar who, because of the role as a liberated woman given to her by Hemingway, is not included in this general categorization.