Bounding Run-Times of Local Adiabatic Algorithms

A common trick for designing faster quantum adiabatic algorithms is to apply the adiabaticity condition locally at every instant. However it is often difficult to determine the instantaneous gap between the lowest two eigenvalues, which is an essential ingredient in the adiabaticity condition. In this paper we present a simple linear algebraic technique for obtaining a lower bound on the instantaneous gap even in such a situation. As an illustration, we investigate the adiabatic un-ordered search of van Dam et al. [17] and Roland and Cerf [15] when the non-zero entries of the diagonal final Hamiltonian are perturbed by a polynomial (in log N, where N is the length of the unordered list) amount. We use our technique to derive a bound on the running time of a local adiabatic schedule in terms of the minimum gap between the lowest two eigenvalues.

Design of multiunit electronic exchanges through decomposition

In this paper, we exploit the idea of decomposition to match buyers and sellers in an electronic exchange for trading large volumes of homogeneous goods, where the buyers and sellers specify marginal-decreasing piecewise constant price curves to capture volume discounts. Such exchanges are relevant for automated trading in many e-business applications. The problem of determining winners and Vickrey prices in such exchanges is known to have a worst-case complexity equal to that of as many as (1 + m + n) NP-hard problems, where m is the number of buyers and n is the number of sellers. Our method proposes the overall exchange problem to be solved as two separate and simpler problems: 1) forward auction and 2) reverse auction, which turns out to be generalized knapsack problems. In the proposed approach, we first determine the quantity of units to be traded between the sellers and the buyers using fast heuristics developed by us. Next, we solve a forward auction and a reverse auction using fully polynomial time approximation schemes available in the literature. The proposed approach has worst-case polynomial time complexity. and our experimentation shows that the approach produces good quality solutions to the problem. Note to Practitioners- In recent times, electronic marketplaces have provided an efficient way for businesses and consumers to trade goods and services. The use of innovative mechanisms and algorithms has made it possible to improve the efficiency of electronic marketplaces by enabling optimization of revenues for the marketplace and of utilities for the buyers and sellers. In this paper, we look at single-item, multiunit electronic exchanges. These are electronic marketplaces where buyers submit bids and sellers ask for multiple units of a single item. We allow buyers and sellers to specify volume discounts using suitable functions. Such exchanges are relevant for high-volume business-to-business trading of standard products, such as silicon wafers, very large-scale integrated chips, desktops, telecommunications equipment, commoditized goods, etc. The problem of determining winners and prices in such exchanges is known to involve solving many NP-hard problems. Our paper exploits the familiar idea of decomposition, uses certain algorithms from the literature, and develops two fast heuristics to solve the problem in a near optimal way in worst-case polynomial time.

Kernels for large margin time-series classification

In this paper we propose a novel family of kernels for multivariate time-series classification problems. Each time-series is approximated by a linear combination of piecewise polynomial functions in a Reproducing Kernel Hilbert Space by a novel kernel interpolation technique. Using the associated kernel function a large margin classification formulation is proposed which can discriminate between two classes. The formulation leads to kernels, between two multivariate time-series, which can be efficiently computed. The kernels have been successfully applied to writer independent handwritten character recognition.

Constructing commutative semifields of square order

The projection construction has been used to construct semifields of odd characteristic using a field and a twisted semifield [Commutative semi-fields from projection mappings, Designs, Codes and Cryptography, 61 (2011), 187{196]. We generalize this idea to a projection construction using two twisted semifields to construct semifields of odd characteristic. Planar functions and semifields have a strong connection so this also constructs new planar functions.

Global lopsided instability in a purely stellar galactic disc

It is shown that pure exponential discs in spiral galaxies are capable of supporting slowly varying discrete global lopsided modes, which can explain the observed features of lopsidedness in the stellar discs. Using linearized fluid dynamical equations with the softened self-gravity and pressure of the perturbation as the collective effect, we derive self-consistently a quadratic eigenvalue equation for the lopsided perturbation in the galactic disc. On solving this, we find that the ground-state mode shows the observed characteristics of the lopsidedness in a galactic disc, namely the fractional Fourier amplitude A(1), increases smoothly with the radius. These lopsided patterns precess in the disc with a very slow pattern speed with no preferred sense of precession. We show that the lopsided modes in the stellar disc are long-lived because of a substantial reduction (approximately a factor of 10 compared to the local free precession rate) in the differential precession. The numerical solution of the equations shows that the groundstate lopsided modes are either very slowly precessing stationary normal mode oscillations of the disc or growing modes with a slow growth rate depending on the relative importance of the collective effect of the self-gravity. N-body simulations are performed to test the spontaneous growth of lopsidedness in a pure stellar disc. Both approaches are then compared and interpreted in terms of long-lived global m = 1 instabilities, with almost zero pattern speed.

Isoperimetric Problem and Meta-fibonacci Sequences

Let G = (V,E) be a simple, finite, undirected graph. For S ⊆ V, let $\delta(S,G) = \{ (u,v) \in E : u \in S \mbox { and } v \in V-S \}$ and $\phi(S,G) = \{ v \in V -S: \exists u \in S$ , such that (u,v) ∈ E} be the edge and vertex boundary of S, respectively. Given an integer i, 1 ≤ i ≤ ∣ V ∣, the edge and vertex isoperimetric value at i is defined as b e (i,G) =  min S ⊆ V; |S| = i |δ(S,G)| and b v (i,G) =  min S ⊆ V; |S| = i |φ(S,G)|, respectively. The edge (vertex) isoperimetric problem is to determine the value of b e (i, G) (b v (i, G)) for each i, 1 ≤ i ≤ |V|. If we have the further restriction that the set S should induce a connected subgraph of G, then the corresponding variation of the isoperimetric problem is known as the connected isoperimetric problem. The connected edge (vertex) isoperimetric values are defined in a corresponding way. It turns out that the connected edge isoperimetric and the connected vertex isoperimetric values are equal at each i, 1 ≤ i ≤ |V|, if G is a tree. Therefore we use the notation b c (i, T) to denote the connected edge (vertex) isoperimetric value of T at i. Hofstadter had introduced the interesting concept of meta-fibonacci sequences in his famous book “Gödel, Escher, Bach. An Eternal Golden Braid”. The sequence he introduced is known as the Hofstadter sequences and most of the problems he raised regarding this sequence is still open. Since then mathematicians studied many other closely related meta-fibonacci sequences such as Tanny sequences, Conway sequences, Conolly sequences etc. Let T 2 be an infinite complete binary tree. In this paper we related the connected isoperimetric problem on T 2 with the Tanny sequences which is defined by the recurrence relation a(i) = a(i − 1 − a(i − 1)) + a(i − 2 − a(i − 2)), a(0) = a(1) = a(2) = 1. In particular, we show that b c (i, T 2) = i + 2 − 2a(i), for each i ≥ 1. We also propose efficient polynomial time algorithms to find vertex isoperimetric values at i of bounded pathwidth and bounded treewidth graphs.

On the Average Case Communication Complexity for Detection in Sensor Networks

The problem of sensor-network-based distributed intrusion detection in the presence of clutter is considered. It is argued that sensing is best regarded as a local phenomenon in that only sensors in the immediate vicinity of an intruder are triggered. In such a setting, lack of knowledge of intruder location gives rise to correlated sensor readings. A signal-space viewpoint is introduced in which the noise-free sensor readings associated to intruder and clutter appear as surfaces $\mathcal{S_I}$ and $\mathcal{S_C}$ and the problem reduces to one of determining in distributed fashion, whether the current noisy sensor reading is best classified as intruder or clutter. Two approaches to distributed detection are pursued. In the first, a decision surface separating $\mathcal{S_I}$ and $\mathcal{S_C}$ is identified using Neyman-Pearson criteria. Thereafter, the individual sensor nodes interactively exchange bits to determine whether the sensor readings are on one side or the other of the decision surface. Bounds on the number of bits needed to be exchanged are derived, based on communication complexity (CC) theory. A lower bound derived for the two-party average case CC of general functions is compared against the performance of a greedy algorithm. The average case CC of the relevant greater-than (GT) function is characterized within two bits. In the second approach, each sensor node broadcasts a single bit arising from appropriate two-level quantization of its own sensor reading, keeping in mind the fusion rule to be subsequently applied at a local fusion center. The optimality of a threshold test as a quantization rule is proved under simplifying assumptions. Finally, results from a QualNet simulation of the algorithms are presented that include intruder tracking using a naive polynomial-regression algorithm.

Dielectric, Ferroelectric and Relaxor Behavior of BaLaxBi4-xTi4O15 Ceramics

Monophasic BaLaxBi4-xTi4O15 (x = 0, 0.2, 0.4, 0.6 and 0.8) ceramics, fabricated from the powders synthesized via the solid-state reaction route exhibited relaxor behavior. Dielectric properties of the well sintered ceramics were measured in a wide frequency range (1 kHz-1 MHz) at different temperatures (300-750 K). The temperature of dielectri maximum (T-m) was found to decrease significantly from 696 K for an undoped sample (x = 0) to 395 K for the sample corresponding to the composition x = 0.8 accompanied by a decrease in the magnitude ofdielectric maximum (epsilon(m)). The temperature variation of the dielectric constant on the high temperature slope of the peak (T > T-m) was analyzed by using the Lorentz-ype quadratic law and the diffuseness of the peak was found to increase with increasing x. Vogel-Fulcher modelling of dielectric relaxation showed a decrease in freezing temperature (T-VF) (from 678 to 340 K) and an increase in the activation energy (5 to 24 meV) for the frequency dispersion with increase in x (La-3 divided by content). Strength of frequency dispersion of the phase transition increased with lanthanum content. Polarization (P)-electric field (E) hysteresis loops recorded at 373 showed a transition from a nearly squarish to slim loop hysteresis behavior with increasing lanthanum content.

A unified construction of space-time codes with optimal rate-diversity tradeoff

The problem of constructing space-time (ST) block codes over a fixed, desired signal constellation is considered. In this situation, there is a tradeoff between the transmission rate as measured in constellation symbols per channel use and the transmit diversity gain achieved by the code. The transmit diversity is a measure of the rate of polynomial decay of pairwise error probability of the code with increase in the signal-to-noise ratio (SNR). In the setting of a quasi-static channel model, let n(t) denote the number of transmit antennas and T the block interval. For any n(t) <= T, a unified construction of (n(t) x T) ST codes is provided here, for a class of signal constellations that includes the familiar pulse-amplitude (PAM), quadrature-amplitude (QAM), and 2(K)-ary phase-shift-keying (PSK) modulations as special cases. The construction is optimal as measured by the rate-diversity tradeoff and can achieve any given integer point on the rate-diversity tradeoff curve. An estimate of the coding gain realized is given. Other results presented here include i) an extension of the optimal unified construction to the multiple fading block case, ii) a version of the optimal unified construction in which the underlying binary block codes are replaced by trellis codes, iii) the providing of a linear dispersion form for the underlying binary block codes, iv) a Gray-mapped version of the unified construction, and v) a generalization of construction of the S-ary case corresponding to constellations of size S-K. Items ii) and iii) are aimed at simplifying the decoding of this class of ST codes.

Conformal Field Theory Methods for Variants of Schramm-Loewner Evolutions

This thesis consists of an introduction, four research articles and an appendix. The thesis studies relations between two different approaches to continuum limit of models of two dimensional statistical mechanics at criticality. The approach of conformal field theory (CFT) could be thought of as the algebraic classification of some basic objects in these models. It has been succesfully used by physicists since 1980's. The other approach, Schramm-Loewner evolutions (SLEs), is a recently introduced set of mathematical methods to study random curves or interfaces occurring in the continuum limit of the models. The first and second included articles argue on basis of statistical mechanics what would be a plausible relation between SLEs and conformal field theory. The first article studies multiple SLEs, several random curves simultaneously in a domain. The proposed definition is compatible with a natural commutation requirement suggested by Dubédat. The curves of multiple SLE may form different topological configurations, ``pure geometries''. We conjecture a relation between the topological configurations and CFT concepts of conformal blocks and operator product expansions. Example applications of multiple SLEs include crossing probabilities for percolation and Ising model. The second article studies SLE variants that represent models with boundary conditions implemented by primary fields. The most well known of these, SLE(kappa, rho), is shown to be simple in terms of the Coulomb gas formalism of CFT. In the third article the space of local martingales for variants of SLE is shown to carry a representation of Virasoro algebra. Finding this structure is guided by the relation of SLEs and CFTs in general, but the result is established in a straightforward fashion. This article, too, emphasizes multiple SLEs and proposes a possible way of treating pure geometries in terms of Coulomb gas. The fourth article states results of applications of the Virasoro structure to the open questions of SLE reversibility and duality. Proofs of the stated results are provided in the appendix. The objective is an indirect computation of certain polynomial expected values. Provided that these expected values exist, in generic cases they are shown to possess the desired properties, thus giving support for both reversibility and duality.

Pilot-scale cellulosic ethanol production using eucalyptus biomass pre-treated by dilute acid and steam explosion

The widespread deployment of commercial-scale cellulosic ethanol currently hinges on developing and evaluating scalable processes whilst broadening feedstock options. This study investigates whole Eucalyptus grandis trees as a potential feedstock and demonstrates dilute acid pre-treatment (with steam explosion) followed by pre-saccharification simultaneous saccharification fermentation process (PSSF) as a suitable, scalable strategy for the production of bioethanol. Biomass was pre-treated in dilute H2SO4 at laboratory scale (0.1 kg) and pilot scale (10 kg) to evaluate the effect of combined severity factor (CSF) on pre-treatment effectiveness. Subsequently, pilot-scale pre-treated residues (15 wt.%) were converted to ethanol in a PSSF process at 2 L and 300 L scales. Good polynomial correlations (n = 2) of CSF with hemicellulose removal and glucan digestibility with a minimum R2 of 0.91 were recorded. The laboratory-scale 72 h glucan digestibility and glucose yield was 68.0% and 51.3%, respectively, from biomass pre-treated at 190 °C /15 min/ 4.8 wt.% H2SO4. Pilot-scale pre-treatment (180 °C/ 15 min/2.4 wt.% H2SO4 followed by steam explosion) delivered higher glucan digestibility (71.8%) and glucose yield (63.6%). However, the ethanol yields using PSSF were calculated at 82.5 and 113 kg/ton of dry biomass for the pilot and the laboratory scales, respectively. © 2016 Society of Chemical Industry and John Wiley & Sons, Ltd

Measurement of air leakage in air-handling units and air conditioning ducts

The purpose of this article is to report the experience of design and testing of orifice plate-based flow measuring systems for evaluation of air leakages in components of air conditioning systems. Two of the flow measuring stations were designed with a beta value of 0.405 and 0.418. The third was a dual path unit with orifice plates of beta value 0.613 and 0.525. The flow rates covered with all the four were from 4-94 l/s and the range of Reynolds numbers is from 5600 to 76,000. The coefficients of discharge were evaluated and compared with the Stolz equation. Measured C-d values are generally higher than those obtained from the equation, the deviations being larger in the low Reynolds number region. Further, it is observed that a second-degree polynomial is inadequate to relate the pressure drop and flow rate. The lower Reynolds number limits set by standards appear to be somewhat conservative.

Fracture analysis of stiffened panels under combined tensile, bending, and shear loads

The objective is to present the formulation of numerically integrated modified virtual crack closure integral technique for concentrically and eccentrically stiffened panels for computation of strain-energy release rate and stress intensity factor based on linear elastic fracture mechanics principles. Fracture analysis of cracked stiffened panels under combined tensile, bending, and shear loads has been conducted by employing the stiffened plate/shell finite element model, MQL9S2. This model can be used to analyze plates with arbitrarily located concentric/eccentric stiffeners, without increasing the total number of degrees of freedom, of the plate element. Parametric studies on fracture analysis of stiffened plates under combined tensile and moment loads have been conducted. Based on the results of parametric,studies, polynomial curve fitting has been carried out to get best-fit equations corresponding to each of the stiffener positions. These equations can be used for computation of stress intensity factor for cracked stiffened plates subjected to tensile and moment loads for a given plate size, stiffener configuration, and stiffener position without conducting finite element analysis.

Approximate methods for step function response of undamped non-linear spring mass systems with arbitrary hardening type spring characteristic

The possibility of applying two approximate methods for determining the salient features of response of undamped non-linear spring mass systems subjected to a step input, is examined. The results obtained on the basis of these approximate methods are compared with the exact results that are available for some particular types of spring characteristics. The extension of the approximate methods for non-linear systems with general polynomial restoring force characteristics is indicated.

Theory of laminar flame propagation with non-normal diffusion.

A study has been made of the problem of steady, one-dimensional, laminar flame propagation in premixed gases, with the Lewis number differing from (and equal to) unity. Analytical solutions, using the method of matched asymptotic expansions, have been obtained for large activation energies. Numerical solutions have been obtained for a wide range of the reduced activation temperature parameter (n {geometrically equal to} E/RTb), and the Lewis number δ. The studies reveal that the flame speed eigenvalue is linear in Lewis number for first order and quadratic in Lewis number for second order reactions. For a quick determination of flame speeds, with reasonable accuracy, a simple rule, expressing the flame speed eigenvalue as a function of the Lewis number and the centroid of the reaction rate function, is proposed. Comparisons have been made with some of the earlier works, for both first and second order reactions.