3-Homogeneous latin trades

Let T be a partial latin square and L be a latin square with T subset of L. We say that T is a latin trade if there exists a partial latin square T' with T' boolean AND T = theta such that (LT) U T' is a latin square. A k-homogeneous latin trade is one which intersects each row, each column and each entry either 0 or k times. In this paper, we construct 3-homogeneous latin trades from hexagonal packings of the plane with circles. We show that 3-homogeneous latin trades of size 3 m exist for each m >= 3. This paper discusses existence results for latin trades and provides a glueing construction which is subsequently used to construct all latin trades of finite order greater than three. Crown Copyright (c) 2005 Published by Elsevier B.V. All rights reserved.

Theory of strongly correlated electron systems. II. Including correlation effects into electronic structure calculations

We have previously shown that a division of the f-shell into two subsystems gives a better understanding of the cohesive properties as well the general behavior of lanthanide systems. In this article, we present numerical computations, using the suggested method. We show that the picture is consistent with most experimental data, e.g., the equilibrium volume and electronic structure in general. Compared with standard energy band calculations and calculations based on the self-interaction correction and LIDA + U, the f-(non-f)-mixing interaction is decreased by spectral weights of the many-body states of the f-ion. (c) 2005 Wiley Periodicals, Inc.

Simple approach to estimating the van der Waals interaction between carbon nanotubes

The van der Waals (vdW) interactions between carbon nanotubes (CNTs) were studied based on the continuum Lennard-Jones model. It was found that all the vdW potentials between two arbitrary CNTs fall on the same curve when plotted in terms of certain reduced parameters, the well depth, and the equilibrium vdW gap. Based on this observation, an approximate approach is developed to obtain the vdW potential between two CNTs without time-consuming computations. The vdW potential estimated by this approach is close to that obtained from complex integrations. Therefore, the developed approach can greatly simplify the calculation of vdW interactions between CNTs.

A geometric approach to quantum circuit lower bounds

What is the minimal size quantum circuit required to exactly implement a specified n-qubit unitary operation, U, without the use of ancilla qubits? We show that a lower bound on the minimal size is provided by the length of the minimal geodesic between U and the identity, I, where length is defined by a suitable Finsler metric on the manifold SU(2(n)). The geodesic curves on these manifolds have the striking property that once an initial position and velocity are set, the remainder of the geodesic is completely determined by a second order differential equation known as the geodesic equation. This is in contrast with the usual case in circuit design, either classical or quantum, where being given part of an optimal circuit does not obviously assist in the design of the rest of the circuit. Geodesic analysis thus offers a potentially powerful approach to the problem of proving quantum circuit lower bounds. In this paper we construct several Finsler metrics whose minimal length geodesics provide lower bounds on quantum circuit size. For each Finsler metric we give a procedure to compute the corresponding geodesic equation. We also construct a large class of solutions to the geodesic equation, which we call Pauli geodesics, since they arise from isometries generated by the Pauli group. For any unitary U diagonal in the computational basis, we show that: (a) provided the minimal length geodesic is unique, it must be a Pauli geodesic; (b) finding the length of the minimal Pauli geodesic passing from I to U is equivalent to solving an exponential size instance of the closest vector in a lattice problem (CVP); and (c) all but a doubly exponentially small fraction of such unitaries have minimal Pauli geodesics of exponential length.

Hyperspace geography: Visualizing fitness landscapes beyond 4D

Human perception is finely tuned to extract structure about the 4D world of time and space as well as properties such as color and texture. Developing intuitions about spatial structure beyond 4D requires exploiting other perceptual and cognitive abilities. One of the most natural ways to explore complex spaces is for a user to actively navigate through them, using local explorations and global summaries to develop intuitions about structure, and then testing the developing ideas by further exploration. This article provides a brief overview of a technique for visualizing surfaces defined over moderate-dimensional binary spaces, by recursively unfolding them onto a 2D hypergraph. We briefly summarize the uses of a freely available Web-based visualization tool, Hyperspace Graph Paper (HSGP), for exploring fitness landscapes and search algorithms in evolutionary computation. HSGP provides a way for a user to actively explore a landscape, from simple tasks such as mapping the neighborhood structure of different points, to seeing global properties such as the size and distribution of basins of attraction or how different search algorithms interact with landscape structure. It has been most useful for exploring recursive and repetitive landscapes, and its strength is that it allows intuitions to be developed through active navigation by the user, and exploits the visual system's ability to detect pattern and texture. The technique is most effective when applied to continuous functions over Boolean variables using 4 to 16 dimensions.

Measuring and predicting the dynamics of linear monodisperse entangled polymers in rapid flow through an abrupt contraction. A small angle neutron scattering study

Small-angle neutron scattering measurements on a series of monodisperse linear entangled polystyrene melts in nonlinear flow through an abrupt 4:1 contraction have been made. Clear signatures of melt deformation and subsequent relaxation can be observed in the scattering patterns, which were taken along the centerline. These data are compared with the predictions of a recently derived molecular theory. Two levels of molecular theory are used: a detailed equation describing the evolution of molecular structure over all length scales relevant to the scattering data and a simplified version of the model, which is suitable for finite element computations. The velocity field for the complex melt flow is computed using the simplified model and scattering predictions are made by feeding these flow histories into the detailed model. The modeling quantitatively captures the full scattering intensity patterns over a broad range of data with independent variation of position within the contraction geometry, bulk flow rate and melt molecular weight. The study provides a strong, quantitative validation of current theoretical ideas concerning the microscopic dynamics of entangled polymers which builds upon existing comparisons with nonlinear mechanical stress data. Furthermore, we are able to confirm the appreciable length scale dependence of relaxation in polymer melts and highlight some wider implications of this phenomenon.

Evolving genetic regulatory networks using an artificial genome

Boolean models of genetic regulatory networks (GRNs) have been shown to exhibit many of the characteristic dynamics of real GRNs, with gene expression patterns settling to point attractors or limit cycles, or displaying chaotic behaviour, depending upon the connectivity of the network and the relative proportions of excitatory and inhibitory interactions. This range of behaviours is only apparent, however, when the nodes of the GRN are updated synchronously, a biologically implausible state of affairs. In this paper we demonstrate that evolution can produce GRNs with interesting dynamics under an asynchronous update scheme. We use an Artificial Genome to generate networks which exhibit limit cycle dynamics when updated synchronously, but collapse to a point attractor when updated asynchronously. Using a hill climbing algorithm the networks are then evolved using a fitness function which rewards patterns of gene expression which revisit as many previously seen states as possible. The final networks exhibit “fuzzy limit cycle” dynamics when updated asynchronously.

Document re-ranking by generality in bio-medical information retrieval

Document ranking is an important process in information retrieval (IR). It presents retrieved documents in an order of their estimated degrees of relevance to query. Traditional document ranking methods are mostly based on the similarity computations between documents and query. In this paper we argue that the similarity-based document ranking is insufficient in some cases. There are two reasons. Firstly it is about the increased information variety. There are far too many different types documents available now for user to search. The second is about the users variety. In many cases user may want to retrieve documents that are not only similar but also general or broad regarding a certain topic. This is particularly the case in some domains such as bio-medical IR. In this paper we propose a novel approach to re-rank the retrieved documents by incorporating the similarity with their generality. By an ontology-based analysis on the semantic cohesion of text, document generality can be quantified. The retrieved documents are then re-ranked by their combined scores of similarity and the closeness of documents’ generality to the query’s. Our experiments have shown an encouraging performance on a large bio-medical document collection, OHSUMED, containing 348,566 medical journal references and 101 test queries.

Towards effective indexing for very large video sequence database

With rapid advances in video processing technologies and ever fast increments in network bandwidth, the popularity of video content publishing and sharing has made similarity search an indispensable operation to retrieve videos of user interests. The video similarity is usually measured by the percentage of similar frames shared by two video sequences, and each frame is typically represented as a high-dimensional feature vector. Unfortunately, high complexity of video content has posed the following major challenges for fast retrieval: (a) effective and compact video representations, (b) efficient similarity measurements, and (c) efficient indexing on the compact representations. In this paper, we propose a number of methods to achieve fast similarity search for very large video database. First, each video sequence is summarized into a small number of clusters, each of which contains similar frames and is represented by a novel compact model called Video Triplet (ViTri). ViTri models a cluster as a tightly bounded hypersphere described by its position, radius, and density. The ViTri similarity is measured by the volume of intersection between two hyperspheres multiplying the minimal density, i.e., the estimated number of similar frames shared by two clusters. The total number of similar frames is then estimated to derive the overall similarity between two video sequences. Hence the time complexity of video similarity measure can be reduced greatly. To further reduce the number of similarity computations on ViTris, we introduce a new one dimensional transformation technique which rotates and shifts the original axis system using PCA in such a way that the original inter-distance between two high-dimensional vectors can be maximally retained after mapping. An efficient B+-tree is then built on the transformed one dimensional values of ViTris' positions. Such a transformation enables B+-tree to achieve its optimal performance by quickly filtering a large portion of non-similar ViTris. Our extensive experiments on real large video datasets prove the effectiveness of our proposals that outperform existing methods significantly.

Computing with elation groups

We have proved that elation groups of a certain infinite family of Roman generalized quadrangles are not isomorphic to those of associated flock generalized quadrangles. The proof is theoretical, but is based upon detailed computations. Here we elaborate on the explicit computer calculations which inspired the proof.

Studies on Wilson loops, correlators and localization in supersymmetric quantum field theories

In this thesis we study at perturbative level correlation functions of Wilson loops (and local operators) and their relations to localization, integrability and other quantities of interest as the cusp anomalous dimension and the Bremsstrahlung function. First of all we consider a general class of 1/8 BPS Wilson loops and chiral primaries in N=4 Super Yang-Mills theory. We perform explicit two-loop computations, for some particular but still rather general configuration, that confirm the elegant results expected from localization procedure. We find notably full consistency with the multi-matrix model averages, obtained from 2D Yang-Mills theory on the sphere, when interacting diagrams do not cancel and contribute non-trivially to the final answer. We also discuss the near BPS expansion of the generalized cusp anomalous dimension with L units of R-charge. Integrability provides an exact solution, obtained by solving a general TBA equation in the appropriate limit: we propose here an alternative method based on supersymmetric localization. The basic idea is to relate the computation to the vacuum expectation value of certain 1/8 BPS Wilson loops with local operator insertions along the contour. Also these observables localize on a two-dimensional gauge theory on S^2, opening the possibility of exact calculations. As a test of our proposal, we reproduce the leading Luscher correction at weak coupling to the generalized cusp anomalous dimension. This result is also checked against a genuine Feynman diagram approach in N=4 super Yang-Mills theory. Finally we study the cusp anomalous dimension in N=6 ABJ(M) theory, identifying a scaling limit in which the ladder diagrams dominate. The resummation is encoded into a Bethe-Salpeter equation that is mapped to a Schroedinger problem, exactly solvable due to the surprising supersymmetry of the effective Hamiltonian. In the ABJ case the solution implies the diagonalization of the U(N) and U(M) building blocks, suggesting the existence of two independent cusp anomalous dimensions and an unexpected exponentation structure for the related Wilson loops.

Natural language processing as a foundation of the semantic Web

The main argument of this paper is that Natural Language Processing (NLP) does, and will continue to, underlie the Semantic Web (SW), including its initial construction from unstructured sources like the World Wide Web (WWW), whether its advocates realise this or not. Chiefly, we argue, such NLP activity is the only way up to a defensible notion of meaning at conceptual levels (in the original SW diagram) based on lower level empirical computations over usage. Our aim is definitely not to claim logic-bad, NLP-good in any simple-minded way, but to argue that the SW will be a fascinating interaction of these two methodologies, again like the WWW (which has been basically a field for statistical NLP research) but with deeper content. Only NLP technologies (and chiefly information extraction) will be able to provide the requisite RDF knowledge stores for the SW from existing unstructured text databases in the WWW, and in the vast quantities needed. There is no alternative at this point, since a wholly or mostly hand-crafted SW is also unthinkable, as is a SW built from scratch and without reference to the WWW. We also assume that, whatever the limitations on current SW representational power we have drawn attention to here, the SW will continue to grow in a distributed manner so as to serve the needs of scientists, even if it is not perfect. The WWW has already shown how an imperfect artefact can become indispensable.

Threshold-induced phase transitions in perceptrons

Error rates of a Boolean perceptron with threshold and either spherical or Ising constraint on the weight vector are calculated for storing patterns from biased input and output distributions derived within a one-step replica symmetry breaking (RSB) treatment. For unbiased output distribution and non-zero stability of the patterns, we find a critical load, α p, above which two solutions to the saddlepoint equations appear; one with higher free energy and zero threshold and a dominant solution with non-zero threshold. We examine this second-order phase transition and the dependence of α p on the required pattern stability, κ, for both one-step RSB and replica symmetry (RS) in the spherical case and for one-step RSB in the Ising case.

Advanced mean field methods:theory and practice

A major problem in modern probabilistic modeling is the huge computational complexity involved in typical calculations with multivariate probability distributions when the number of random variables is large. Because exact computations are infeasible in such cases and Monte Carlo sampling techniques may reach their limits, there is a need for methods that allow for efficient approximate computations. One of the simplest approximations is based on the mean field method, which has a long history in statistical physics. The method is widely used, particularly in the growing field of graphical models. Researchers from disciplines such as statistical physics, computer science, and mathematical statistics are studying ways to improve this and related methods and are exploring novel application areas. Leading approaches include the variational approach, which goes beyond factorizable distributions to achieve systematic improvements; the TAP (Thouless-Anderson-Palmer) approach, which incorporates correlations by including effective reaction terms in the mean field theory; and the more general methods of graphical models. Bringing together ideas and techniques from these diverse disciplines, this book covers the theoretical foundations of advanced mean field methods, explores the relation between the different approaches, examines the quality of the approximation obtained, and demonstrates their application to various areas of probabilistic modeling.

Public key cryptography and error correcting codes as Ising models

We employ the methods of statistical physics to study the performance of Gallager type error-correcting codes. In this approach, the transmitted codeword comprises Boolean sums of the original message bits selected by two randomly-constructed sparse matrices. We show that a broad range of these codes potentially saturate Shannon's bound but are limited due to the decoding dynamics used. Other codes show sub-optimal performance but are not restricted by the decoding dynamics. We show how these codes may also be employed as a practical public-key cryptosystem and are of competitive performance to modern cyptographical methods.