Layered Tabu Search Algorithm for Large-MIMO Detection and a Lower Bound on ML Performance

In this paper, we are concerned with low-complexity detection in large multiple-input multiple-output (MIMO) systems with tens of transmit/receive antennas. Our new contributions in this paper are two-fold. First, we propose a low-complexity algorithm for large-MIMO detection based on a layered low-complexity local neighborhood search. Second, we obtain a lower bound on the maximum-likelihood (ML) bit error performance using the local neighborhood search. The advantages of the proposed ML lower bound are i) it is easily obtained for MIMO systems with large number of antennas because of the inherent low complexity of the search algorithm, ii) it is tight at moderate-to-high SNRs, and iii) it can be tightened at low SNRs by increasing the number of symbols in the neighborhood definition. Interestingly, the proposed detection algorithm based on the layered local search achieves bit error performances which are quite close to this lower bound for large number of antennas and higher-order QAM. For e. g., in a 32 x 32 V-BLAST MIMO system, the proposed detection algorithm performs close to within 1.7 dB of the proposed ML lower bound at 10(-3) BER for 16-QAM (128 bps/Hz), and close to within 4.5 dB of the bound for 64-QAM (192 bps/Hz).

Multiple UAV Coalitions for a Search and Prosecute Mission

Unmanned aerial vehicles (UAVs) have the potential to carry resources in support of search and prosecute operations. Often to completely prosecute a target, UAVs may have to simultaneously attack the target with various resources with different capacities. However, the UAVs are capable of carrying only limited resources in small quantities, hence, a group of UAVs (coalition) needs to be assigned that satisfies the target resource requirement. The assigned coalition must be such that it minimizes the target prosecution delay and the size of the coalition. The problem of forming coalitions is computationally intensive due to the combinatorial nature of the problem, but for real-time applications computationally cheap solutions are required. In this paper, we propose decentralized sub-optimal (polynomial time) and decentralized optimal coalition formation algorithms that generate coalitions for a single target with low computational complexity. We compare the performance of the proposed algorithms to that of a global optimal solution for which we need to solve a centralized combinatorial optimization problem. This problem is computationally intensive because the solution has to (a) provide a coalition for each target, (b) design a sequence in which targets need to be prosecuted, and (c) take into account reduction of UAV resources with usage. To solve this problem we use the Particle Swarm Optimization (PSO) technique. Through simulations, we study the performance of the proposed algorithms in terms of mission performance, complexity of the algorithms and the time taken to form the coalition. The simulation results show that the solution provided by the proposed algorithms is close to the global optimal solution and requires far less computational resources.

A simple strategy for spirocyclopentannullation of cyclic ketones. Formal total synthesis of (+/-)-acorone

A general and simple methodology for spirocyclopentannulation of cyclic ketones (or 4,4-disubstituted cyclopentenones from acyclic ketones) and its application in the synthesis of the spirodienone 7 via a prochiral precursor constituting a formal total synthesis of (+/-)-acorone (6), are described.

Genetic search: Analysis using fitness moments

Genetic Algorithms are efficient and robust search methods that are being employed in a plethora of applications with extremely large search spaces. The directed search mechanism employed in Genetic Algorithms performs a simultaneous and balanced, exploration of new regions in the search space and exploitation of already discovered regions.This paper introduces the notion of fitness moments for analyzing the working of Genetic Algorithms (GAs). We show that the fitness moments in any generation may be predicted from those of the initial population. Since a knowledge of the fitness moments allows us to estimate the fitness distribution of strings, this approach provides for a method of characterizing the dynamics of GAs. In particular the average fitness and fitness variance of the population in any generation may be predicted. We introduce the technique of fitness-based disruption of solutions for improving the performance of GAs. Using fitness moments, we demonstrate the advantages of using fitness-based disruption. We also present experimental results comparing the performance of a standard GA and GAs (CDGA and AGA) that incorporate the principle of fitness-based disruption. The experimental evidence clearly demonstrates the power of fitness based disruption.

Towards the total synthesis of tashironin related allo-cedrane natural products: further exploitation of the oxidative dearomatization-IMDA-RCM triad based strategy

Synthetic studies directed towards allo-cedrane based, tashironin sibling natural products, involving some deft functional group manipulations on a preformed tetracyclic scaffold, are delineated. (C) 2011 Elsevier Ltd. All rights reserved.

Unwinding of heterologous DNA by RecA protein during the search for homologous sequences

The search for homologous sequences promoted by RecA protein in vitro involves a presynaptic filament and naked duplex DNA, the multiple contacts of which produce nucleoprotein networks or coaggregates. The single-stranded DNA within the presynaptic filaments, however, is extended to an axial spacing 1.5 times that of B-form DNA. To investigate this paradoxical difference between the spacing of bases in the RecA presynaptic filament versus the target duplex DNA, we explored the effect of heterologous contacts on the conformation of DNA, and vice versa. In the presence of wheat germ topoisomerase I, RecA presynaptic filaments induced a rapid, limited reduction in the linking number of heterologous circular duplex DNA. This limited unwinding of heterologous duplex DNA, termed heterologous unwinding, was detected within 30 seconds and reached a steady state within a few minutes. Presynaptic filaments that were formed in the presence of ATP?S and separated from free RecA protein by gel filtration also generated a ladder of topoisomers upon incubation with relaxed duplex DNA and topoisomerase. The inhibition of heterologous contacts by 60 mImage -NaCl or 5 mImage -ADP resulted in a corresponding decrease in heterologous unwinding. In reciprocal fashion, the stability or number of heterologous contacts with presynaptic filaments was inversely related to the linking number of circular duplex DNA. These observations show that heterologous contacts with the presynaptic filament cause a limited unwinding of the duplex DNA, and conversely that the ability of the DNA to unwind stabilizes transient heterologous contacts.

A new strategy for the alpha-vinylation of ketones: Application to an enantioselective synthesis of sesquiterpene (+)-alpha-elemene

A new, simple and preparatively useful protocol for the construction of a-vinyl ketones, particularly those bearing a quaternary carbon centre, from the corresponding alkenes has been devised. Our four-step strategy consists of dichloroketene addition, base catalysed ring contraction to 'push-pull' cyclopropane esters, reduction and eliminative cyclopropane fragmentation to unravel the a-vinyl ketone moiety. The generality of this approach has been demonstrated with a few representative olefins and good regio- and stereocontrol has been observed. As an application of this methodology, an enantioselective synthesis of sesquiterpene hydrocarbon (+)-alpha-elemene (42) from R-(+)-limonene (43) has been accomplished.

GyrI: a counter-defensive strategy against proteinaceous inhibitors of DNA gyrase

DNA gyrase is the target of two plasmid-encoded toxins CcdB and microcin B17, which ensure plasmid maintenance. These proteins stabilize gyrase-DNA covalent complexes leading to double-strand breaks in the genome. In contrast, the physiological role of chromosomally encoded inhibitor of DNA gyrase (Gyrl) in Escherichia coli is unclear and its mechanism of inhibition has not been established. We demonstrate that the mode of inhibition of GyrI is distinct from all other gyrase inhibitors. It inhibits DNA gyrase prior to, or at the step of, binding of DNA by the enzyme. Gyrl reduces intrinsic as well as toxin-stabilized gyrase-DNA covalent complexes. Furthermore, Gyri reduces microcin B17-mediated double-strand breaks in vivo, imparting protection to the cells against the toxin, substantiating the in vitro results. Thus, Gyrl is an antidote to DNA gyrase-specific proteinaceous poisons encoded by plasmid addiction systems.

Search for sub-mm, mm and radio continuum emission from extremely red objects

We present the results of sub-mm, mm (850 mum, 450 mum and 1250 mum) and radio (1.4 and 4.8 GHz) continuum observations of a sample of 27 K-selected Extremely Red Objects, or EROs, (14 of which form a complete sample with K < 20 and I - K > 5) aimed at detecting dusty starbursts, deriving the fraction of UltraLuminous Infrared Galaxies (ULIGs) in ERO samples, and constraining their redshifts using the radio-FIR correlation. One ERO was tentatively detected at 1250 mum and two were detected at 1.4 GHz, one of which has a less secure identification as an ERO counterpart. Limits on their redshifts and their star forming properties are derived and discussed. We stacked the observations of the undetected objects at 850 mum, 1250 mum and 4.8 GHz in order to search for possible statistical emission from the ERO population as a whole, but no significant detections were derived either for the whole sample or as a function of the average NIR colours. These results strongly suggest that the dominant population of EROs with K < 20 is not comprised of ULIGs like HR 10, but is probably made of radio-quiet ellipticals and weaker starburst galaxies with L < 10(12) L . and SFR < few hundred M. yr(-1).

A Nash Bargaining Approach to Retention Enhancing Bid Optimization in Sponsored Search Auctions with Discrete Bids

Bid optimization is now becoming quite popular in sponsored search auctions on the Web. Given a keyword and the maximum willingness to pay of each advertiser interested in the keyword, the bid optimizer generates a profile of bids for the advertisers with the objective of maximizing customer retention without compromising the revenue of the search engine. In this paper, we present a bid optimization algorithm that is based on a Nash bargaining model where the first player is the search engine and the second player is a virtual agent representing all the bidders. We make the realistic assumption that each bidder specifies a maximum willingness to pay values and a discrete, finite set of bid values. We show that the Nash bargaining solution for this problem always lies on a certain edge of the convex hull such that one end point of the edge is the vector of maximum willingness to pay of all the bidders. We show that the other endpoint of this edge can be computed as a solution of a linear programming problem. We also show how the solution can be transformed to a bid profile of the advertisers.

Multi-agent search using?sensors with heterogeneous capabilities

In this thesis we address the problem of multi-agent search. We formulate two deploy and search strategies based on optimal deployment of agents in search space so as to maximize the search effectiveness in a single step. We show that a variation of centroidal Voronoi configuration is the optimal deployment. When the agents have sensors with different capabilities, the problem will be heterogeneous in nature. We introduce a new concept namely, generalized Voronoi partition in order to formulate and solve the heterogeneous multi-agent search problem. We address a few theoretical issues such as optimality of deployment, convergence and spatial distributedness of the control law and the search strategies. Simulation experiments are carried out to compare performances of the proposed strategies with a few simple search strategies.

Search on a Hypercubic Lattice using Quantum Random Walk

We investigate the spatial search problem on the two-dimensional square lattice, using the Dirac evolution operator discretized according to the staggered lattice fermion formalism. d=2 is the critical dimension for the spatial search problem, where infrared divergence of the evolution operator leads to logarithmic factors in the scaling behavior. As a result, the construction used in our accompanying article [ A. Patel and M. A. Rahaman Phys. Rev. A 82 032330 (2010)] provides an O(√NlnN) algorithm, which is not optimal. The scaling behavior can be improved to O(√NlnN) by cleverly controlling the massless Dirac evolution operator by an ancilla qubit, as proposed by Tulsi Phys. Rev. A 78 012310 (2008). We reinterpret the ancilla control as introduction of an effective mass at the marked vertex, and optimize the proportionality constants of the scaling behavior of the algorithm by numerically tuning the parameters.

Self Assessment-Based Decision Making for Multiagent Cooperative Search

This paper addresses a search problem with multiple limited capability search agents in a partially connected dynamical networked environment under different information structures. A self assessment-based decision-making scheme for multiple agents is proposed that uses a modified negotiation scheme with low communication overheads. The scheme has attractive features of fast decision-making and scalability to large number of agents without increasing the complexity of the algorithm. Two models of the self assessment schemes are developed to study the effect of increase in information exchange during decision-making. Some analytical results on the maximum number of self assessment cycles, effect of increasing communication range, completeness of the algorithm, lower bound and upper bound on the search time are also obtained. The performance of the various self assessment schemes in terms of total uncertainty reduction in the search region, using different information structures is studied. It is shown that the communication requirement for self assessment scheme is almost half of the negotiation schemes and its performance is close to the optimal solution. Comparisons with different sequential search schemes are also carried out. Note to Practitioners-In the futuristic military and civilian applications such as search and rescue, surveillance, patrol, oil spill, etc., a swarm of UAVs can be deployed to carry out the mission for information collection. These UAVs have limited sensor and communication ranges. In order to enhance the performance of the mission and to complete the mission quickly, cooperation between UAVs is important. Designing cooperative search strategies for multiple UAVs with these constraints is a difficult task. Apart from this, another requirement in the hostile territory is to minimize communication while making decisions. This adds further complexity to the decision-making algorithms. In this paper, a self-assessment-based decision-making scheme, for multiple UAVs performing a search mission, is proposed. The agents make their decisions based on the information acquired through their sensors and by cooperation with neighbors. The complexity of the decision-making scheme is very low. It can arrive at decisions fast with low communication overheads, while accommodating various information structures used for increasing the fidelity of the uncertainty maps. Theoretical results proving completeness of the algorithm and the lower and upper bounds on the search time are also provided.

Quantum Algorithms with Fixed Points: The Case of Database Search

The standard quantum search algorithm lacks a feature, enjoyed by many classical algorithms, of having a fixed-point, i.e. a monotonic convergence towards the solution. Here we present two variations of the quantum search algorithm, which get around this limitation. The first replaces selective inversions in the algorithm by selective phase shifts of $\frac{\pi}{3}$. The second controls the selective inversion operations using two ancilla qubits, and irreversible measurement operations on the ancilla qubits drive the starting state towards the target state. Using $q$ oracle queries, these variations reduce the probability of finding a non-target state from $\epsilon$ to $\epsilon^{2q+1}$, which is asymptotically optimal. Similar ideas can lead to robust quantum algorithms, and provide conceptually new schemes for error correction.