Physical Sciences and Mathematics Commons^™

Semantics Vs. Syntax Vs. Computations Machine Models For Type-2 Polynomial-Time Bounded Functionals (Preliminary Draft), James S. Royer

Electrical Engineering and Computer Science - Technical Reports

This paper investigates analogs of the Kreisel-Lacombe-Shoenfield Theorem in the context of the type-2 basic feasible functionals, a.k.a. the Mehlhorn-Cook class of type-2 polynomial-time functionals. We develop a direct, polynomial-time analog of effective operation, where the time bound on computations is modeled after Kapron and Cook's scheme for their basic polynomial-time functionals. We show that (i) if P = NP, these polynomial-time effective operations are strictly more powerful on R (the class of recursive functions) than the basic feasible functions, and (ii) there is an oracle relative to which these polynomial-time effective operations and the basic feasible functionals have the …

Multiprocessor Document Allocation: A Neural Network Approach, Abdulaziz Sultan Al-Sehibani, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka

Electrical Engineering and Computer Science - Technical Reports

We consider the problem of distributing the documents to a given set of processors so that the load on each processor is as equal as possible and the amount of communication is as small as possible. This is an NP-Complete problem. We apply continuous as well as discrete Hopfield neural networks to obtain suboptimal solutions for the problem. These networks perform better than a genetic algorithm for this task proposed by Frieder et al. [4]; in particular, the continuous Hopfield network performs extremely well.

Characterization Of A Class Of Sigmoid Functions With Applications To Neural Networks, Anil Ravindran Menon, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka

Electrical Engineering and Computer Science - Technical Reports

Sigmoid functions, whose graphs are "S-shaped" curves, appear in a great variety of contexts, such as the transfer functions in many neural networks. Their ubiquity is no accident; these curves are the among the simplest non-linear curves, striking a graceful balance between linear and non-linear behavior.

Covering Radius 1985-1994, G. D. Cohen, S. N. Litsyn, Antoine C. Lobstein, H. F. Mattson Jr

Electrical Engineering and Computer Science - Technical Reports

We survey important developments in the theory of covering radius during the period 1985-1994. We present lower bounds, constructions and upper bounds, the linear and nonlinear cases, density and asymptotic results, normality, specific classes of codes, covering radius and dual distance, tables, and open problems.

Application Of Fractals And Kinetic Equation In Modelling Cluster And Ultrafine Particle Size Distributions, Joseph Chaiken, Jerry Goodisman

Chemistry - All Scholarship

We briefly describe a model which seems to be applicable to a variety of coalescence growth systems. Spanning cluster growth, particle growth and hillock formation in thin metal films, this model is based on the Smoluchowski kinetic equations and fractals. We describe how this model has been able to suggest the effect of translational to internal energy conversion in coalescing systems in determining the shape of particle size distributions. We also suggest how this model can be employed to account for the behavior of hillocks in supersaturated alloy films under thermal annealing conditions.

Particle Conjugation And The 1/N_C Corrections To G_A, Joseph Schechter, H. Weigel

Physics - All Scholarship

We impose the requirement that the isovector axial vector current for the soliton sector of the chiral quark model transforms correctly under particle conjugation. This forces us to choose an otherwise arbitrary ordering of collective space operators in such a way that the next--to--leading 1/N_C correction to g_A vanishes.

Excited Heavy Baryons In The Bound State Picture, Joseph Schechter, Anand Subbaraman

Physics - All Scholarship

The orbitally excited heavy quark baryons are studied in the Callan Klebanov bound state model with heavy spin symmetry. First, a compact description of the large N_c, infinite heavy quark mass bound state wavefunctions and the collective quantization is given. In order to study the kinematical corrections due to finite masses we motivate an approximate Schrodinger-like equation for the bound state. The effective potential in this equation is compared with the quadratic approximation (spherical harmonic oscillator) to it. This oscillator approximation is seen to be not very accurate. It is noted that the present experimental information cannot be even qualitatively …

Fluted Formulas And The Limits Of Decidability, William C. Purdy

Electrical Engineering and Computer Science - Technical Reports

In the predicate calculus, variables provide a flexible indexing service that selects the actual arguments to a predicate letter from among possible arguments that precede the predicate letter (in the parse of the formula). In the process of selection, the possible arguments can be permuted, repeated (used more than once), and skipped. If this service is withheld, so that arguments must be the immediately preceding ones, taken in the order in which they occur, the formula is said to be fluted. Quine showed that if a fluted formula contains only homogeneous conjunction (conjoins only subformulas of equal arity), then the …

A Domain-Specific Parallel Programming System I: Design And Application To Ecological Modelling, Elaine Wenderholm, Micah Beck

Electrical Engineering and Computer Science - Technical Reports

The goal of the εm project is to make parallel programming easily accessible to a broad community of scientists. Previous approaches such as the use of general parallel programming languages and parallelizing compilers for sequential languages have fallen short in this respect. The approach is to design a special purpose programming language which is oriented towards a specific area of application. The result is a specialized and effective scientific tool. εm is a high-level programming system which puts parallelism into the hands of scientists who are not sophisticated programmers. By restricting and simplifying the programming interface, εm eases both the …

Interface Motion In Random Media At Finite Temperature, Lee-Wen Chen, M. Cristina Marchetti

Physics - All Scholarship

We have studied numerically the dynamics of a driven elastic interface in a random medium, focusing on the thermal rounding of the depinning transition and on the behavior in the

T = 0 pinned phase. Thermal effects are quantitatively more important than expected from simple dimensional estimates. For sufficient low temperature the creep velocity at a driving force equal to the T = 0 depinning force exhibits a power-law dependence on T, in agreement with earlier theoretical and numerical predictions for CDW’s. We have also examined the dynamics in the T = 0 pinned phase resulting from slowly increasing the …

Non-Perturbative Renormalization Group Flows In Two-Dimensional Quantum Gravity, Simon Catterall, Ray L. Renken, John B. Kogut

Physics - All Scholarship

Recently a block spin renormalization group approach was proposed for the dynamical triangulation formulation of two-dimensional quantum gravity. We use this approach to examine non-perturbatively a particular class of higher derivative actions for pure gravity.

Self-Organized Criticality In Non-Conserved Systems, Alan Middleton, Chao Tang

Physics - All Scholarship

The origin of self-organized criticality in a model without conservation law (Olami, Feder, and Christensen, Phys. Rev. Lett. {\bf 68}, 1244 (1992)) is studied. The homogeneous system with periodic boundary condition is found to be periodic and neutrally stable. A change to open boundaries results in the invasion of the interior by a ``self-organized'' region. The mechanism for the self-organization is closely related to the synchronization or phase-locking of the individual elements with each other. A simplified model of marginal oscillator locking on a directed lattice is used to explain many of the features in the non-conserved model: in particular, …

Twin-Boundary Pinning Of Superconducting Vortex Arrays, M. Cristina Marchetti, Valerii M. Vinokur

Physics - All Scholarship

We discuss the low-temperature dynamics of magnetic flux lines in high-temperature superconductors in the presence of a family of parallel twin planes that contain the $c$ axis. A current applied along the twin planes drives flux motion in the direction transverse to the planes and acts like an electric field applied to {\it one-dimensional} carriers in disordered semiconductors. As in flux arrays with columnar pins, there is a regime where the dynamics is dominated by superkink excitations that correspond to Mott variable range hopping (VRH) of carriers. In one dimension, however, rare events, such as large regions void of twin …

Heavy Meson Radiative Decays And Light Vector Meson Dominance, Joseph Schechter, Pankaj Jain, Arshad Momen

Physics - All Scholarship

Electromagnetic interactions are introduced in the effective chiral Lagrangian for heavy mesons which includes light vector particles. A suitable notion of vector meson dominance is formulated. The constraints on the heavy meson -light vector and heavy meson-light pseudoscalar coupling constants are obtained using experimental D^* \ra D \, \gamma branching ratios. These constraints are compared with values estimated from semi-leptonic transition amplitudes as well as from extension of the light meson coupling pattern. Application to the heavy baryon spectrum in the ``bound state " model is made.

Analysis Of Myoelectrical Signals For Building A Dextrous Hand, Christopher T. Creel, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka

Electrical Engineering and Computer Science - Technical Reports

We analyze techniques for myoelectrical signals classification for the purpose of designing a multifunctional prosthetic device for human amputees. The main advantage of our system over existing models is that it is more robust, easier to work with, more general, and efficient enough to run in real time. We achieve this with the help of "Supervised Growing Cell Structures." an artificial neural network model designed by Fritzke [10]. The current paper focuses on the flexion of the index, middle and ring fingers, as these are the most difficult movements to tackle.

Low-Temperatures Vortex Dynamics In Twinned Superconductors, M. Cristina Marchetti, Valerii M. Vinokur

Physics - All Scholarship

We discuss the low-temperature dynamics of magnetic flux lines in samples with a family of parallel twin planes. A current applied along the twin planes drives flux motion in the direction transverse to the planes and acts like an electric field applied to {\it one-dimensional} carriers in disordered semiconductors. As in flux arrays with columnar pins, there is a regime where the dynamics is dominated by superkink excitations that correspond to Mott variable range hopping (VRH) of carriers. In one dimension, however, rare events, such as large regions void of twin planes, can impede VRH and dominate transport in samples …

Ac Response Of The Flux-Line Liquid In High-Tc Superconductors, Lee-Wen Chen, M. Cristina Marchetti

Physics - All Scholarship

We use a hydrodynamics theory to discuss the response of a viscous flux-line liquid to an ac perturbation applied at the surface of the sample. The theory incorporates viscoelastic effects and describes the crossover between liquid-like and solid-like response of the vortex array as the frequency of the perturbation increases. A large viscosity from flux-line interactions and entanglement leads to viscous screening of surface fields. As a result, two frequency-dependent length scales are needed to describe the penetration of an ac field. For large viscosities the imaginary part of the ac permeability can exihibit, in addition to the well-know peak …

Knowledge-Based Nonuniform Crossover, Harpal Maini, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka

Electrical Engineering and Computer Science - Technical Reports

We present a new "knowledge-based non-uniform crossover" (KNUX) operator for genetic algorithms (GA's) that generalizes uniform crossover. We extend this to "Dynamic KNUX" (DKNUX), which constantly updates the knowledge extracted so far from the environment's feedback on previously generated chromosomes. KNUX can improve on good solutions previously obtained by using other algorithms. The modifications made by KNUX are orthogonal to other changes in parameters of GA's, and can be pursued together with any other proposed improvements. Whereas most genetic search methods focus on improving the move-selection procedures, after having chosen a fixed move-generation mechanism, KNUX and DKNUX make the move-generation …

Possible Extension Of The Chiral Perturbation Theory Program, Joseph Schechter

Physics - All Scholarship

After a brief discussion of how chiral dynamics has evolved from the ``universal V-A theory of weak interactions'', we present some evidence that symmetry breaking for the vector meson multiplet is not simpler than but rather analogous to that for the pseudoscalar multiplet. This provides a motivation for speculating on how to extend in a systematic way the chiral perturbation theory program to include vectors.

On The Absence Of An Exponential Bound In Four Dimensional Simplicial Gravity, Simon Catterall, John B. Kogut, R. Renken

Physics - All Scholarship

We have studied a model which has been proposed as a regularisation for four dimensional quantum gravity. The partition function is constructed by performing a weighted sum over all triangulations of the four sphere. Using numerical simulation we find that the number of such triangulations containing V simplices grows faster than exponentially with V. This property ensures that the model has no thermodynamic limit.

Decoding Linear Block Codes Using A Priority-First Search: Performance Analysis And Suboptimal Version, Yunghsiang S. Han, Carlos R.P. Hartmann, Kishan Mehrotra

Electrical Engineering and Computer Science - Technical Reports

An efficient maximum-likelihood soft-decision decoding algorithm for linear block codes using a generalized Dijkstra's Algorithm was proposed by Han, Hartmann, and Chen. In this report we prove that this algorithm is efficient for most practical communication systems where the probability of error is less than 10-3 by finding an upper bound of the computation performance of the algorithm. A suboptimal decoding algorithm is also proposed. The performance of this suboptimal decoding algorithm is within 0.25 dB and 0.5 dB of the performance of an optimal decoding algorithm for the (104, 52) binary extended quadratic residue code and the (128, 64) …

Can The World Industrialization Project Be Sustained?, Isidor Wallimann

Program for the Advancement of Research on Conflict and Collaboration

No abstract provided.

Phase Structure Of Four Dimensional Simplicial Quantum Gravity, Simon Catterall, John B. Kogut, R. Renken

Physics - All Scholarship

We present the results of a high statistics Monte Carlo study of a model for four dimensional euclidean quantum gravity based on summing over triangulations. We show evidence for two phases; in one there is a logarithmic scaling on the mean linear extent with volume, whilst the other exhibits power law behaviour with exponent 1/2. We are able to extract a finite size scaling exponent governing the growth of the susceptibility peak

Heavy Quark Solitons: Strangeness And Symmetry Breaking, Joseph Schechter, Arshad Momen, Anand Subbaraman

Physics - All Scholarship

We discuss the generalization of the Callan-Klebanov model to the case of heavy quark baryons. The light flavor group is considered to be SU(3) and the limit of heavy spin symmetry is taken. The presence of the Wess-Zumino-Witten term permits the neat development of a picture , at the collective level, of a light diquark bound to a ``heavy" quark with decoupled spin degree of freedom. The consequences of SU(3) symmetry breaking are discussed in detail. We point out that the SU(3) mass splittings of the heavy baryons essentially measure the ``low energy" physics once more and that the comparison …

Gravity And Electromagnetism In Noncommutative Geometry, Giovanni Landi, Nguyen Ai Viet, Kameshwar C. Wali

Physics - All Scholarship

We present a unified description of gravity and electromagnetism in the framework of a Z 2 non-commutative differential calculus. It can be considered as a “discrete version” of Kaluza-Klein theory, where the fifth continuous dimension is replaced by two discrete points. We derive an action which coincides with the dimensionally reduced one of the ordinary Kaluza-Klein theory.

Group Cohomology, Modular Theory And Space-Time Symmetries, R. Brunetti, D. Guido, R. Longo

Physics - All Scholarship

The Bisognano-Wichmann property on the geometric behavior of the modular group of the von Neumann algebras of local observables associated to wedge regions in Quantum Field Theory is shown to provide an intrinsic sufficient criterion for the existence of a covariant action of the (universal covering of) the Poincar'e group. In particular this gives, together with our previous results, an intrinsic characterization of positive-energy conformal pre-cosheaves of von Neumann algebras. To this end we adapt to our use Moore theory of central extensions of locally compact groups by polish groups, selecting and making an analysis of a wider class of …

A Data Parallel Algorithm For Solving The Region Growing Problem On The Connection Machine, Nawal Copty, Sanjay Ranka, Geoffrey C. Fox, Ravi V. Shankar

College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects

Region growing is a general technique for image segmentation, where image characteristics are used to group adjacent pixels together to form regions. This paper presents a parallel algorithm for solving the region growing problem based on the split and merge approach, and uses it to test and compare various parallel architectures and programming models. The implementations were done on the Connection Machine, models CM-2 and CM-5, in the data parallel and message passing programming models. Randomization was introduced in breaking ties during merging to increase the degree of parallelism, and only one and two-dimensional arrays of data were used in …

The Complexity Of Local Stratification, Peter Cholak, Howard A. Blair

College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects

The class of locally stratified logic programs is shown to be Π 1 1-complete by the construction of a reducibility of the class of infinitely branching nondeterministic finite register machines.

Genetic Algorithms For Graph Partitioning And Incremental Graph Partitioning, Harpal Maini, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka

College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects

Partitioning graphs into equally large groups of nodes, minimizing the number of edges between different groups, is an extremely important problem in parallel computing. This paper presents genetic algorithms for suboptimal graph partitioning, with new crossover operators (KNUX, DKNUX) that lead to orders of magnitude improvement over traditional genetic operators in solution quality and speed. Our method can improve on good solutions previously obtained by using other algorithms or graph theoretic heuristics in minimizing the total communication cost or the worst case cost of communication for a single processor. We also extend our algorithm to Incremental Graph Partitioning problems, in …

The Transportation Primitive, Ravi V. Shankar, Khaled A. Alsabti, Sanjay Ranka

College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects

This paper presents algorithms for implementing the transportation primitive on a distributed memory parallel architecture. The transportation primitive performs many-to-many personalized communication with bounded incoming and outgoing traffic. We present a two-stage deterministic algorithm that decomposes the communication with possibly high variance in message size into two communication stages with low message size variance. If the maximum outgoing or incoming traffic at any processor is t, transportation can be done in 2t¯ time (+ lower order terms) when t O(p 2 + pø=¯) (¯ is the inverse of the data transfer rate, ø is the startup overhead). If the maximum …