School of Electrical Engineering and Computer Science
http://hdl.handle.net/1957/7302
Sun, 31 Aug 2014 03:43:12 GMT2014-08-31T03:43:12ZCovering Nearly Surface-Embedded Graphs with a Fixed Number of Balls
http://hdl.handle.net/1957/51764
Covering Nearly Surface-Embedded Graphs with a Fixed Number of Balls
Borradaile, Glencora; Chambers, Erin Wolf
A recent result of Chepoi, Estellon and Vaxes [Disc. Comp. Geom. '07] states that any planar graph
of diameter at most 2R can be covered by a constant number of balls of size R; put another way, there
are a constant-sized subset of vertices within which every other vertex is distance half the diameter.
We generalize this result to graphs embedded on surfaces of fixed genus with a fixed number of apices,
making progress toward the conjecture that graphs excluding a fixed minor can also be covered by a
constant number of balls. To do so, we develop two tools which may be of independent interest. The first
gives a bound on the density of graphs drawn on a surface of genus g having a limit on the number of
pairwise-crossing edges. The second bounds the size of a non-contractible cycle in terms of the Euclidean
norm of the degree sequence of a graph embedded on surface.
This is an author's peer-reviewed final manuscript, as accepted by the publisher. The published article is copyrighted by Springer and can be found at: http://link.springer.com/journal/454.
Sun, 01 Jun 2014 00:00:00 GMThttp://hdl.handle.net/1957/517642014-06-01T00:00:00ZAmorphous metal thin films as a platform for solution processing
http://hdl.handle.net/1957/51704
Amorphous metal thin films as a platform for solution processing
Landau, Nicholas P.
The research presented herein represents an effort to combine the ultra-smooth surface of an amorphous metal thin ﬁlm (AMTF) with a solution-processed dielectric synthesized via prompt inorganic condensation (PIC). Analysis of dielectric ﬁlm quality is carried out via electrical measurements of metal-insulator-metal (MIM) diodes. Anneals at 500 and 700 °C for PIC Al₂O₃ deposited onto TaWSi AMTFs are conducted under vacuum with forming gas in order to maintain PIC ﬁlm structural integrity. Conduction through PIC Al₂O₃ in TaWSi-based MIM diodes is argued to be space-charge limited current (SCLC) with trapping and is facilitated by pinhole shunts. In contrast, PIC Al₂O₃ deposited onto highly-doped n-type silicon substrates, which are processed in parallel to the TaWSi diodes, exhibit Fowler-Nordheim tunneling. A 10 nm layer of ALD-deposited Al₂O₃ prior to PIC Al₂O₃ deposition is shown to reduce the high leakage previously seen in TaWSi-based diodes fabricated without an ALD layer from 2.2 × 10⁻² A/cm² to 2.6 × 10⁻⁹ A/cm² measured at 1 MV/cm. This is attributed to a lack of pinhole formation. Power-law ﬁtting of current density versus electric ﬁeld (J-ξ)data is presented as an eﬃcient tool to detect the presence of pinholes in a PIC insulator and can be readily distinguished from Poole-Frenkel conduction and Fowler-Nordheim tunneling common in MIM diodes with ultra-thin insulators.
Graduation date: 2015
Thu, 21 Aug 2014 00:00:00 GMThttp://hdl.handle.net/1957/517042014-08-21T00:00:00ZEstablishing Flight Software Reliability: Testing, Model Checking, Constraint-Solving, Monitoring and Learning
http://hdl.handle.net/1957/51437
Establishing Flight Software Reliability: Testing, Model Checking, Constraint-Solving, Monitoring and Learning
Groce, Alex; Havelund, Klaus; Holzmann, Gerard; Joshi, Rajeev; Xu, Ru-Gang
In this paper we discuss the application of a range of techniques to the
verification of mission-critical flight software at NASA’s Jet Propulsion Laboratory.
For this type of application we want to achieve a higher level of confidence than can
be achieved through standard software testing. Unfortunately, given the current state
of the art, especially when efforts are constrained by the tight deadlines and resource
limitations of a flight project, it is not feasible to produce a rigorous formal proof of
correctness of even a well-specified stand-alone module such as a file system (much less
more tightly coupled or difficult-to-specify modules). This means that we must look for
a practical alternative in the area between traditional testing and proof, as we attempt
to optimize rigor and coverage. The approaches we describe here are based on testing,
model checking, constraint-solving, monitoring, and finite-state machine learning, in
addition to static code analysis. The results we have obtained in the domain of file systems
are encouraging, and suggest that for more complex properties of programs with
complex data structures, it is possibly more beneficial to use constraint solvers to guide
and analyze execution (i.e., as in testing, even if performed by a model checking tool)
than to translate the program and property into a set of constraints, as in abstraction-based
and bounded model checkers. Our experience with non-file-system flight software
modules shows that methods even further removed from traditional static formal methods
can be assisted by formal approaches, yet readily adopted by test engineers and
software developers, even as the key problem shifts from test generation and selection
to test evaluation.
This is an author's peer-reviewed final manuscript, as accepted by the publisher. The published article is copyrighted by Springer and can be found at: http://link.springer.com/journal/10472.
Tue, 01 Apr 2014 00:00:00 GMThttp://hdl.handle.net/1957/514372014-04-01T00:00:00ZParameter estimation of Gaussian hierarchical model using Gibbs sampling
http://hdl.handle.net/1957/51386
Parameter estimation of Gaussian hierarchical model using Gibbs sampling
Mbuthia, Juliana
Gibbs sampling method is an important tool used in parameter estimation for many probabilistic models. Specifically, for many scenarios, it is difficult to generate high-dimensional data samples from its joint distribution. The Gibbs sampling provides a way to draw high-dimensional data via the conditional distributions which are typically easier to sample. In this thesis, we study a simple generative model called Hierarchical Gaussian and an efficient method for computing its parameters using Gibbs sampling. In particular, we show that the Hierarchical Gaussian model admits closed form conditional distributions such that Gibbs sampling can be used effectively to draw the samples from the joint distribution, and perform parameter estimation.
Graduation date: 2015
Wed, 04 Jun 2014 00:00:00 GMThttp://hdl.handle.net/1957/513862014-06-04T00:00:00Z