Csar 62 Spin Curve, 2018 Singh Center for Nanotechnology

#### Csar 62 Spin Curve, Mohsen Azadi, Georgia Griggs, Glen De Villafranca, Gerald Lopez

*Protocols and Reports*

No abstract provided.

Gene Regulatory Network Inference From Perturbed Time-Series Expression Data Via Ordered Dynamical Expansion Of Non-Steady State Actors, 2018 Stanford University

#### Gene Regulatory Network Inference From Perturbed Time-Series Expression Data Via Ordered Dynamical Expansion Of Non-Steady State Actors, Mahdi Zamanighomi, Mostafa Zamanian, Michael J. Kimber, Zhengdao Wang

*Zhengdao Wang*

The reconstruction of gene regulatory networks from gene expression data has been the subject of intense research activity. A variety of models and methods have been developed to address different aspects of this important problem. However, these techniques are narrowly focused on particular biological and experimental platforms, and require experimental data that are typically unavailable and difficult to ascertain. The more recent availability of higher-throughput sequencing platforms, combined with more precise modes of genetic perturbation, presents an opportunity to formulate more robust and comprehensive approaches to gene network inference. Here, we propose a step-wise framework for identifying gene-gene regulatory interactions ...

Joint Optimization Of Power Allocation And Training Duration For Uplink Multiuser Mimo Communications, 2018 Iowa State University

#### Joint Optimization Of Power Allocation And Training Duration For Uplink Multiuser Mimo Communications, Songtao Lu, Zhengdao Wang

*Zhengdao Wang*

In this paper, we consider a multiuser multiple-input multiple-output (MU-MIMO) communication system between a base station equipped with multiple antennas and multiple mobile users each equipped with a single antenna. The uplink scenario is considered. The uplink channels are acquired by the base station through a training phase. Two linear processing schemes are considered, namely maximum-ratio combining (MRC) and zero-forcing (ZF). We optimize the training period and optimal training energy under the average and peak power constraint so that an achievable sum rate is maximized.

A Nonconvex Splitting Method For Symmetric Nonnegative Matrix Factorization: Convergence Analysis And Optimality, 2018 Iowa State University

#### A Nonconvex Splitting Method For Symmetric Nonnegative Matrix Factorization: Convergence Analysis And Optimality, Songtao Lu, Mingyi Hong, Zhengdao Wang

*Zhengdao Wang*

Symmetric nonnegative matrix factorization (SymNMF) has important applications in data analytics problems such as document clustering, community detection, and image segmentation. In this paper, we propose a novel nonconvex variable splitting method for solving SymNMF. The proposed algorithm is guaranteed to converge to the set of Karush-Kuhn-Tucker (KKT) points of the nonconvex SymNMF problem. Furthermore, it achieves a global sublinear convergence rate. We also show that the algorithm can be efficiently implemented in parallel. Further, sufficient conditions are provided that guarantee the global and local optimality of the obtained solutions. Extensive numerical results performed on both synthetic and real datasets ...

Many Access For Small Packets Based On Precoding And Sparsity-Aware Recovery, 2018 Chinese Academy of Sciences

#### Many Access For Small Packets Based On Precoding And Sparsity-Aware Recovery, Ronggui Xie, Huarui Yin, Xiaohui Chen, Zhengdao Wang

*Zhengdao Wang*

Modern mobile terminals produce massive small data packets. For these short-length packets, it is inefficient to follow the current multiple access schemes to allocate transmission resources due to heavy signaling overhead. We propose a non-orthogonal many-access scheme that is well suited for the future communication systems equipped with many receive antennas. The system is modeled as having a block-sparsity pattern with unknown sparsity level (i.e., unknown number of transmitted messages). Block precoding is employed at each single-antenna transmitter to enable the simultaneous transmissions of many users. The number of simultaneously served active users is allowed to be even more ...

Degrees Of Freedom Region Of Wireless X Networks Based On Real Interference Alignment, 2018 Stanford University

#### Degrees Of Freedom Region Of Wireless X Networks Based On Real Interference Alignment, Mahdi Zamanighomi, Zhengdao Wang

*Zhengdao Wang*

We first consider a single hop wireless X network with K transmitters and J receivers, all with a single antenna. Each transmitter conveys an independent message for each receiver. The channel is assumed to have constant coefficients. We develop an interference alignment scheme for this setup and derive an achievable degrees of freedom (DoF) region. We show that in some cases, the derived region meets a previous outer bound, and hence, is the (exact) DoF region. For our achievability schemes, we divide each message into streams and use real interference alignment on the streams. Several previous results on the DoF ...

Rigid Object Tracking Algorithms For Low-Cost Ar Devices, 2018 Iowa State University

#### Rigid Object Tracking Algorithms For Low-Cost Ar Devices, Timothy Garrett, Saverio Debernardis, Rafael Radkowski, Carl K. Chang, Michele Fiorentino, Antonio E. Uva, James H. Oliver

*James H. Oliver*

Augmented reality (AR) applications rely on robust and efficient methods for tracking. Tracking methods use a computer-internal representation of the object to track, which can be either sparse or dense representations. Sparse representations use only a limited set of feature points to represent an object to track, whereas dense representations almost mimic the shape of an object. While algorithms performed on sparse representations are faster, dense representations can distinguish multiple objects. The research presented in this paper investigates the feasibility of a dense tracking method for rigid object tracking, which incorporates the both object identification and object tracking steps. We ...

Comparison Of Natural Feature Descriptors For Rigid-Object Tracking For Real-Time Augmented Reality, 2018 Inter American University of Puerto Rico

#### Comparison Of Natural Feature Descriptors For Rigid-Object Tracking For Real-Time Augmented Reality, France Franco Bermudez, Sheneeka Ward, Christian Santana Diaz, Rafael Radkowski, Timothy Garrett, James H. Oliver

*James H. Oliver*

This paper presents a comparison of natural feature descrip- tors for rigid object tracking for augmented reality (AR) applica- tions. AR relies on object tracking in order to identify a physical object and to superimpose virtual object on an object. Natu- ral feature tracking (NFT) is one approach for computer vision- based object tracking. NFT utilizes interest points of a physcial object, represents them as descriptors, and matches the descrip- tors against reference descriptors in order to identify a phsical object to track. In this research, we investigate four different nat- ural feature descriptors (SIFT, SURF, FREAK, ORB) and their ...

Randomized Routing On Fat-Trees, 2018 Loyola University Chicago

#### Randomized Routing On Fat-Trees, Ronald I. Greenberg, Charles E. Leiserson

*Ronald Greenberg*

Fat-trees are a class of routing networks for hardware-efficient parallel computation. This paper presents a randomized algorithm for routing messages on a fat-tree. The quality of the algorithm is measured in terms of the load factor of a set of messages to be routed, which is a lower bound on the time required to deliver the messages. We show that if a set of messages has load factor lambda on a fat-tree with n processors, the number of delivery cycles (routing attempts) that the algorithm requires is O(lambda + lg n lg lg n) with probability 1-O(1/n). The ...

The Fat-Pyramid And Universal Parallel Computation Independent Of Wire Delay, 2018 Loyola University Chicago

#### The Fat-Pyramid And Universal Parallel Computation Independent Of Wire Delay, Ronald I. Greenberg

*Ronald Greenberg*

This paper shows that a fat-pyramid of area Θ(A) requires only O(log A) slowdown to simulate any competing network of area A under very general conditions. The result holds regardless of the processor size (amount of attached memory) and number of processors in the competing networks as long as the limitation on total area is met. Furthermore, the result is valid regardless of the relationship between wire length and wire delay. We especially focus on elimination of the common simplifying assumption that unit time suffices to traverse a wire regardless of its length, since the assumption becomes more ...

Randomized Routing On Fat-Trees, 2018 Selected Works

#### Randomized Routing On Fat-Trees, Ronald I. Greenberg

*Ronald Greenberg*

Fat-trees are a class of routing networks for hardware-efficient parallel computation. This paper presents a randomized algorithm for routing messages on a fat-tree. The quality of the algorithm is measured in terms of the *load factor* of a set of messages to be routed, which is a lower bound on the time required to deliver the messages. We show that if a set of messages has load factor *lambda* on a fat-tree with *n* processors, the number of delivery cycles (routing attempts) that the algorithm requires is *O*(*lambda*+lg*n*lglg*n*) with probability 1-*O*(1/*n*). The ...

Universal Wormhole Routing, 2018 Selected Works

#### Universal Wormhole Routing, Ronald I. Greenberg, Hyeong-Cheol Oh

*Ronald Greenberg*

In this paper, we examine the wormhole routing problem in terms of the “congestion” c and “dilation” d for a set of packet paths. We show, with mild restrictions, that there is a simple randomized algorithm for routing any set of P packets in O(cdη+cLηlogP) time with high probability, where L is the number of flits in a packet, and η=min{d,L}; only a constant number of flits are stored in each queue at any time. Using this result, we show that a fat-tree network of area Θ(A) can simulate wormhole routing on any network ...

Single-Layer Channel Routing And Placement With Single-Sided Nets, 2018 Selected Works

#### Single-Layer Channel Routing And Placement With Single-Sided Nets, Ronald I. Greenberg, Jau-Der Shih

*Ronald Greenberg*

This paper considers the optimal offset, feasible offset, and optimal placement problems for a more general form of single-layer VLSI channel routing than has usually been considered in the past. Most prior works require that every net has exactly one terminal on each side of the channel. As long as only one side of the channel contains multiple terminals of the same net, we provide linear-time solutions to all three problems. Such results are implausible if the placement of terminals is entirely unrestricted; in fact, the size of the output for the feasible offset problem may be Ω(n^2 ...

Retrospective Data Filter, 2018 Loyola University Chicago

#### Retrospective Data Filter, Richard J. Prengaman, Robert E. Thurber, Joe Phipps, Ronald I. Greenberg, Wai L. Hom, James F. Jaworski, Guy W. Riffle

*Ronald Greenberg*

In a target detection communication system, apparatus and method for determining the presence of probable targets based on contacts (which can indicate the presence of a target, noise, chatter, or objects not of interest) detected within a predefined position sector or sectors over a specified number of scans. The position of each detected contact, as a contact of interest, is compared with the positions of contacts detected at previous times or scans. Velocity profiles indicate which previous contacts support the likelihood that the contact of interest represents a target having a velocity within a defined band. The likelihood, which can ...

On The Difficulty Of Manhattan Channel Routing, 2018 Loyola University Chicago

#### On The Difficulty Of Manhattan Channel Routing, Ronald I. Greenberg, Joseph Jaja, Sridhar Krishnamurthy

*Ronald Greenberg*

We show that channel routing in the Manhattan model remains difficult even when all nets are single-sided. Given a set of n single-sided nets, we consider the problem of determining the minimum number of tracks required to obtain a dogleg-free routing. In addition to showing that the decision version of the problem isNP-complete, we show that there are problems requiring at least d+Omega(sqrt(n)) tracks, where d is the density. This existential lower bound does not follow from any of the known lower bounds in the literature.

On The Area Of Hypercube Layouts, 2018 Selected Works

#### On The Area Of Hypercube Layouts, Ronald I. Greenberg, Lee Guan

*Ronald Greenberg*

This paper precisely analyzes the wire density and required area in standard styles for the hypercube. It shows that the most natural, regular layout of a hypercube of N^2 nodes in the plane, in a NxN grid arrangement, uses floor(2N/3)+1 horizontal wiring tracks for each row of nodes. (In the process, we see that the number of tracks per row can be reduced by 1 with a less regular design, as can also be seen from an independent argument of Bezrukov et al.) This paper also gives a simple formula for the wire density at any ...

Minimum Separation For Single-Layer Channel Routing, 2018 Loyola University Chicago

#### Minimum Separation For Single-Layer Channel Routing, Ronald I. Greenberg, F. Miller Maley

*Ronald Greenberg*

We present a linear-time algorithm for determining the minimum height of a single-layer routing channel. The algorithm handles single-sided connections and multiterminal nets. It yields a simple routability test for single-layer switchboxes, correcting an error in the literature.

Mulch: A Multi-Layer Channel Router Using One, Two, And Three Layer Partitions, 2018 Loyola University Chicago

#### Mulch: A Multi-Layer Channel Router Using One, Two, And Three Layer Partitions, Ronald I. Greenberg, Alex T. Ishii, Alberto L. Sangiovanni-Vincentelli

*Ronald Greenberg*

Chameleon, a channel router for three layers of interconnect, has been implemented to accept specification of an arbitrary number of layers. Chameleon is based on a strategy of decomposing the multilayer problem into two- and three-layer problems in which one of the layers is reserved primarily for vertical wire runs and the other layer(s) for horizontal runs. In some situations, however, it is advantageous to consider also layers that allow the routing of entire nets, using both horizontal and vertical wires. MulCh is a multilayer channel router that extends the algorithms of Chameleon in this direction. MulCh can route ...

Minimizing Channel Density With Movable Terminals, 2018 Loyola University Chicago

#### Minimizing Channel Density With Movable Terminals, Ronald I. Greenberg, Jau-Der Shih

*Ronald Greenberg*

We give algorithms to minimize density for channels with terminals that are movable subject to certain constraints. The main cases considered are channels with linear order constraints, channels with linear order constraints and separation constraints, channels with movable modules containing fixed terminals, and channels with movable modules and terminals. In each case, previous results for running time and space are improved by a factor of L/lg n and L , respectively, where L is the channel length and n is the number of terminals.

Minimizing Channel Density With Movable Terminals, 2018 Selected Works

#### Minimizing Channel Density With Movable Terminals, Ronald I. Greenberg, Jau-Der Shih

*Ronald Greenberg*

We give algorithms to minimize density for VLSI channel routing problems with terminals that are movable subject to certain constraints. The main cases considered are channels with linear order constraints, channels with linear order constraints and separation constraints, channels with movable modules containing fixed terminals, and channels with movable modules and terminals. In each case, we improve previous results for running time and space by a factor of L/\lgn and L, respectively, where L is the channel length, and n is the number of terminals.