Exact bounds for distributed graph colouring

A distributed system is a collection of networked autonomous processing units which must work in a cooperative manner. Currently, large-scale distributed systems, such as various telecommunication and computer networks, are abundant and used in a multitude of tasks. The field of distributed computing studies what can be computed efficiently in such systems. Distributed systems are usually modelled as graphs where nodes represent the processors and edges denote communication links between processors. This thesis concentrates on the computational complexity of the distributed graph colouring problem. The objective of the graph colouring problem is to assign a colour to each node in such a way that no two nodes connected by an edge share the same colour. In particular, it is often desirable to use only a small number of colours. This task is a fundamental symmetry-breaking primitive in various distributed algorithms. A graph that has been coloured in this manner using at most k different colours is said to be k-coloured. This work examines the synchronous message-passing model of distributed computation: every node runs the same algorithm, and the system operates in discrete synchronous communication rounds. During each round, a node can communicate with its neighbours and perform local computation. In this model, the time complexity of a problem is the number of synchronous communication rounds required to solve the problem. It is known that 3-colouring any k-coloured directed cycle requires at least ½(log* k - 3) communication rounds and is possible in ½(log* k + 7) communication rounds for all k ≥ 3. This work shows that for any k ≥ 3, colouring a k-coloured directed cycle with at most three colours is possible in ½(log* k + 3) rounds. In contrast, it is also shown that for some values of k, colouring a directed cycle with at most three colours requires at least ½(log* k + 1) communication rounds. Furthermore, in the case of directed rooted trees, reducing a k-colouring into a 3-colouring requires at least log* k + 1 rounds for some k and possible in log* k + 3 rounds for all k ≥ 3. The new positive and negative results are derived using computational methods, as the existence of distributed colouring algorithms corresponds to the colourability of so-called neighbourhood graphs. The colourability of these graphs is analysed using Boolean satisfiability (SAT) solvers. Finally, this thesis shows that similar methods are applicable in capturing the existence of distributed algorithms for other graph problems, such as the maximal matching problem.

Theory of unitarity bounds and low-energy form factors

We present a general formalism for deriving bounds on the shape parameters of the weak and electromagnetic form factors using as input correlators calculated from perturbative QCD, and exploiting analyticity and unitarily. The values resulting from the symmetries of QCD at low energies or from lattice calculations at special points inside the analyticity domain can be included in an exact way. We write down the general solution of the corresponding Meiman problem for an arbitrary number of interior constraints and the integral equations that allow one to include the phase of the form factor along a part of the unitarity cut. A formalism that includes the phase and some information on the modulus along a part of the cut is also given. For illustration we present constraints on the slope and curvature of the K-l3 scalar form factor and discuss our findings in some detail. The techniques are useful for checking the consistency of various inputs and for controlling the parameterizations of the form factors entering precision predictions in flavor physics.

Effects of Parasitics and Interface Traps on Ballistic Nanowire FET in the Ultimate Quantum Capacitance Limit

In this paper, we focus on the performance of a nanowire field-effect transistor in the ultimate quantum capacitance limit (UQCL) (where only one subband is occupied) in the presence of interface traps (D-it), parasitic capacitance (C-L), and source/drain series resistance (R-s,R-d), using a ballistic transport model and compare the performance with its classical capacitance limit (CCL) counterpart. We discuss four different aspects relevant to the present scenario, namely: 1) gate capacitance; 2) drain-current saturation; 3) subthreshold slope; and 4) scaling performance. To gain physical insights into these effects, we also develop a set of semianalytical equations. The key observations are as follows: 1) A strongly energy-quantized nanowire shows nonmonotonic multiple-peak C-V characteristics due to discrete contributions from individual subbands; 2) the ballistic drain current saturates better in the UQCL than in the CCL, both in the presence and absence of D-it and R-s,R-d; 3) the subthreshold slope does not suffer any relative degradation in the UQCL compared to the CCL, even with Dit and R-s,R-d; 4) the UQCL scaling outperforms the CCL in the ideal condition; and 5) the UQCL scaling is more immune to R-s,R-d, but the presence of D-it and C-L significantly degrades the scaling advantages in the UQCL.

Ultimate Strength of RC Wall Panels with Openings

Test results of 12 reinforced concrete (RC) wall panels with openings are presented. The panels have been subjected to in-plane vertical loads applied at an eccentricity to represent possible accidental eccentricity that occurs in practice due to constructional imperfections. The 12 specimens consist of two identical groups of six panels each. One group of panels is tested in one-way in-plane action (i.e., supported at top and bottom edges against lateral displacement). The second group of panels is tested in two-way in-plane action (i.e., supported on all the four edges against lateral displacement). Openings in the panels represent typical door and window openings. Cracking loads, ultimate loads, crack patterns, and lateral deflections of the panels are studied. Empirical methods have been developed for the prediction of ultimate load. Also, lateral deflections, cracking loads, and ultimate loads of identical loads tested under one-way and two-way action are compared.

Ultimate Strength of R.C. Wall Panels in Two-Way In-Plane Action

Test results of 24 reinforced concrete wall panels in two-way action (i.e., supported on all the four sides) and subjected to in-plane vertical load are presented. The load is applied at an eccentricity to represent possible accidental eccentricity that occurs in practice due to constructional imperfections. Influences of aspect ratio, thinness ratio, slendemess ratio, vertical steel, and horizontal steel on the ultimate load are studied. Two equations are proposed to predict the ultimate load carried by the panels. The first equation is empirical and is arrived at from trial and error fitting with test data. The second equation is semi-empirical and is developed from a modification of the buckling strength of thin rectangular plates. Both the equations are formulated so as to give a safe prediction of a large portion of ultimate strength test results. Also, ultimate load cracking load and lateral deflections of identical panels in two-way action (all four sides supported) and oneway action (top and bottom sides only supported) are compared.

Bounds on the Lifetime of Wireless Sensor Networks Employing Multiple Data Sinks

Employing multiple base stations is an attractive approach to enhance the lifetime of wireless sensor networks. In this paper, we address the fundamental question concerning the limits on the network lifetime in sensor networks when multiple base stations are deployed as data sinks. Specifically, we derive upper bounds on the network lifetime when multiple base stations are employed, and obtain optimum locations of the base stations (BSs) that maximize these lifetime bounds. For the case of two BSs, we jointly optimize the BS locations by maximizing the lifetime bound using a genetic algorithm based optimization. Joint optimization for more number of BSs is complex. Hence, for the case of three BSs, we optimize the third BS location using the previously obtained optimum locations of the first two BSs. We also provide simulation results that validate the lifetime bounds and the optimum locations of the BSs.

Bounds on fourth generation induced lepton flavour violating double insertions in supersymmetry

We derive bounds on leptonic double mass insertions of the type delta(l)(i4)delta(l)(4j) in four generational MSSM, using the present limits on l(i) -> l(j) + gamma. Two main features distinguish the rates of these processes in MSSM4 from MSSM3: (a) tan beta is restricted to be very small less than or similar to 3 and (b) the large masses for the fourth generation leptons. In spite of small tan beta, there is an enhancement in amplitudes with LLRR (4 delta(ll)(i4)delta(rr)(4j)) type insertions which pick up the mass of the fourth generation lepton, m(tau'). We find these bounds to be at least two orders of magnitude more stringent than those in MSSM3. (C) 2011 Elsevier B.V. All rights reserved.

Bounds on Defect Level and Fault Coverage in Linear Analog Circuit Testing

Transfer function coefficients (TFC) are widely used to test linear analog circuits for parametric and catastrophic faults. This paper presents closed form expressions for an upper bound on the defect level (DL) and a lower bound on fault coverage (FC) achievable in TFC based test method. The computed bounds have been tested and validated on several benchmark circuits. Further, application of these bounds to scalable RC ladder networks reveal a number of interesting characteristics. The approach adopted here is general and can be extended to find bounds of DL and FC of other parametric test methods for linear and non-linear circuits.

Cramer-Rao bounds for source localization in shallow ocean with generalized Gaussian noise

Localization of underwater acoustic sources is a problem of great interest in the area of ocean acoustics. There exist several algorithms for source localization based on array signal processing.It is of interest to know the theoretical performance limits of these estimators. In this paper we develop expressions for the Cramer-Rao-Bound (CRB) on the variance of direction-of-arrival(DOA) and range-depth estimators of underwater acoustic sources in a shallow range-independent ocean for the case of generalized Gaussian noise. We then study the performance of some of the popular source localization techniques,through simulations, for DOA/range-depth estimation of underwater acoustic sources in shallow ocean by comparing the variance of the estimators with the corresponding CRBs.

Bounds on Probability of Error in Decision Feedback Equalizers

Evaluation of the probability of error in decision feedback equalizers is difficult due to the presence of a hard limiter in the feedback path. This paper derives the upper and lower bounds on the probability of a single error and multiple error patterns. The bounds are fairly tight. The bounds can also be used to select proper tap gains of the equalizer.

Bounds on Probability of Error Due to Co-Channel Interference

Upper bounds on the probability of error due to co-channel interference are proposed in this correspondence. The bounds are easy to compute and can be fairly tight.

Minimal unsatisfiable sets: Classification and bounds

Proving the unsatisfiability of propositional Boolean formulas has applications in a wide range of fields. Minimal Unsatisfiable Sets (MUS) are signatures of the property of unsatisfiability in formulas and our understanding of these signatures can be very helpful in answering various algorithmic and structural questions relating to unsatisfiability. In this paper, we explore some combinatorial properties of MUS and use them to devise a classification scheme for MUS. We also derive bounds on the sizes of MUS in Horn, 2-SAT and 3-SAT formulas.