Large Language Models (LLMs) face fundamental challenges in long-context reasoning: many documents exceed their finite context windows, while performance on texts that do fit degrades with sequence length, necessitating their augmentation with external memory frameworks. Current solutions, which have evolved from retrieval using semantic embeddings to more sophisticated structured knowledge graphs representations for improved sense-making and associativity, are tailored for fact-based retrieval and fail to build the space-time-anchored narrative representations required for tracking entities through episodic events. To bridge this gap, we propose the Generative Semantic Workspace (GSW), a neuro-inspired generative memory framework that builds structured, interpretable representations of evolving situations, enabling LLMs to reason over evolving roles, actions, and spatiotemporal contexts. Our framework comprises an Operator, which maps incoming observations to intermediate semantic structures, and a Reconciler, which integrates these into a persistent workspace that enforces temporal, spatial, and logical coherence. On the Episodic Memory Benchmark (EpBench) comprising corpora ranging from 100k to 1M tokens in length, GSW outperforms existing RAG based baselines by up to 20%. Furthermore, GSW is highly efficient, reducing query-time context tokens by 51% compared to the next most token-efficient baseline, reducing inference time costs considerably. More broadly, GSW offers a concrete blueprint for endowing LLMs with human-like episodic memory, paving the way for more capable agents that can reason over long horizons.

MOTIVATION: DNA sequence alignment, an important genomic task, involves assigning short DNA reads to the most probable locations on an extensive reference genome. Conventional methods tackle this challenge in two steps: genome indexing followed by efficient search to locate likely positions for given reads. Building on the success of Large Language Models in encoding text into embeddings, where the distance metric captures semantic similarity, recent efforts have encoded DNA sequences into vectors using Transformers and have shown promising results in tasks involving classification of short DNA sequences. Performance at sequence classification tasks does not, however, guarantee sequence alignment, where it is necessary to conduct a genome-wide search to align every read successfully, a significantly longer-range task by comparison. RESULTS: We bridge this gap by developing a "Embed-Search-Align" (ESA) framework, where a novel Reference-Free DNA Embedding (RDE) Transformer model generates vector embeddings of reads and fragments of the reference in a shared vector space; read-fragment distance metric is then used as a surrogate for sequence similarity. ESA introduces: (i) Contrastive loss for self-supervised training of DNA sequence representations, facilitating rich reference-free, sequence-level embeddings, and (ii) a DNA vector store to enable search across fragments on a global scale. RDE is 99% accurate when aligning 250-length reads onto a human reference genome of 3 gigabases (single-haploid), rivaling conventional algorithmic sequence alignment methods such as Bowtie and BWA-Mem. RDE far exceeds the performance of six recent DNA-Transformer model baselines such as Nucleotide Transformer, Hyena-DNA, and shows task transfer across chromosomes and species. AVAILABILITY AND IMPLEMENTATION: Please see https://anonymous.4open.science/r/dna2vec-7E4E/readme.md.

Imitation learning (IL) is a well-known problem in the field of Markov decision process (MDP), where one is given multiple demonstration trajectories generated by expert(s), and the goal is to replicate the hidden expert-policies so that when the MDP is run independently, it generates trajectories close to the demonstrated ones. IL is one of the most useful tools used in building versatile robots that can learn from examples. This task becomes particularly challenging when the expert exhibits a mixture of behavior modes. Prior work has introduced latent variables to model variations of the expert policy. However, our experiments show that the existing works do not exhibit appropriate imitation of individual modes. To tackle this problem, we first draw inspiration from the well-known classical technique of self-organizing maps (SOMs) and introduce an encoder-free generative model-referred to as the self-organizing generative (SOG) model-for learning multimodal data distributions from samples. We then apply SOG for behavior cloning (BC)-a framework that learns deterministic policies without considering the environment-to accurately distinguish and imitate different modes. Then, we integrate it with generative adversarial IL (GAIL)-a framework that learns policies while considering the environment-to make the learning robust toward compounding errors at unseen states. We show that our method significantly outperforms the state of the art across multiple experiments within the MuJoCo simulator, including locomotion and robotic manipulation tasks.

News reports about emerging issues often include several conflicting story lines.Individual stories can be conceptualized as samples from an underlying mixture of competing narratives.The automated identification of these distinct narratives from unstructured text is a fundamental yet difficult task in Computational Linguistics since narratives are often intertwined and only implicitly conveyed in text.In this paper, we consider a more feasible proxy task: Identify the distinct sets of aligned story actors responsible for sustaining the issue-specific narratives.Discovering aligned actors, and the groups these alignments create, brings us closer to estimating the narrative that each group represents.With the help of Large Language Models (LLM), we address this task by: (i) Introducing a corpus of text segments rich in narrative content associated with six different current issues; (ii) Introducing a novel two-step graph-based framework that (a) identifies alignments between actors (INCANT) and (b) extracts aligned actor groups using the network structure (TAMPA).Amazon Mechanical Turk evaluations demonstrate the effectiveness of our framework.Across domains, alignment relationships from INCANT are accurate (macro F 1 ≥ 0.75) and actor groups from TAMPA are preferred over 2 non-trivial baseline models (ACC ≥ 0.75).

Pavan Holur, Tianyi Wang, Shadi Shahsavari, Timothy Tangherlini, Vwani Roychowdhury. Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2022.

We propose a novel framework, On-Demand MOtion Generation (ODMO), for generating realistic and diverse long-term 3D human motion sequences conditioned only on action types with an additional capability of customization. ODMO shows improvements over SOTA approaches on all traditional motion evaluation metrics when evaluated on three public datasets (HumanAct12, UESTC, and MoCap). Furthermore, we provide both qualitative evaluations and quantitative metrics demonstrating several first-known customization capabilities afforded by our framework, including mode discovery, interpolation, and trajectory customization. These capabilities significantly widen the spectrum of potential applications of such motion generation models. The novel on-demand generative capabilities are enabled by innovations in both the encoder and decoder architectures: (i) Encoder: Utilizing contrastive learning in low-dimensional latent space to create a hierarchical embedding of motion sequences, where not only the codes of different action types form different groups, but within an action type, codes of similar inherent patterns (motion styles) cluster together, making them readily discoverable; (ii) Decoder: Using a hierarchical decoding strategy where the motion trajectory is reconstructed first and then used to reconstruct the whole motion sequence. Such an architecture enables effective trajectory control. Our code is released on the Github page: https://github.com/roychowdhuryresearch/ODMO https://github.com/roychowdhuryresearch/ODMO

Recently, analog compute-in-memory (CIM) architectures based on emerging analog non-volatile memory (NVM) technologies have been explored for deep neural networks (DNNs) to improve scalability, speed, and energy efficiency. Such architectures, however, leverage charge conservation, an operation with infinite resolution, and thus are susceptible to errors. Thus, the inherent stochasticity in any analog NVM used to execute DNNs, will compromise performance. Several reports have demonstrated the use of analog NVM for CIM in a limited scale. It is unclear whether the uncertainties in computations will prohibit large-scale DNNs. To explore this critical issue of scalability, this article first presents a simulation framework to evaluate the feasibility of large-scale DNNs based on CIM architecture and analog NVM. Simulation results show that DNNs trained for high-precision digital computing engines are not resilient against the uncertainty of the analog NVM devices. To avoid such catastrophic failures, this article introduces the analog bi-scale representation for the DNN, and the Hessian-aware Stochastic Gradient Descent training algorithm to enhance the inference accuracy of trained DNNs. As a result of such enhancements, DNNs such as Wide ResNets for CIFAR-100 image recognition problem are demonstrated to have significant performance improvements in accuracy without adding cost to the inference hardware .

We analyze access statistics of 150 blog entries and news articles for periods of up to 3 years. Access rate falls as an inverse power of time passed since publication. The power law holds for periods of up to 1,000 days. The exponents are different for different blogs and are distributed between 0.6 and 3.2. We argue that the decay of attention to a web article is caused by the link to it first dropping down the list of links on the website's front page and then disappearing from the front page and its subsequent movement further into background. The other proposed explanations that use a decaying with time novelty factor, or some intricate theory of human dynamics, cannot explain all of the experimental observations.

We consider the min-cost multicast problem (under network coding) with multiple correlated sources where each terminal wants to losslessly reconstruct all the sources. We study the inefficiency brought forth by the selfish behavior of the terminals in this scenario by modeling it as a noncooperative game among the terminals. The degradation in performance due to the lack of regulation is measured by the Price of Anarchy (POA), which is defined as the ratio between the cost of the worst possible Wardrop equilibrium and the socially optimum cost. Our main result is that in contrast with the case of independent sources, the presence of source correlations can significantly increase the price of anarchy. Toward establishing this result, we first characterize the socially optimal flow and rate allocation in terms of four intuitive conditions. Next, we show that the Wardrop equilibrium is a socially optimal solution for a different set of (related) cost functions. Using this, we construct explicit examples that demonstrate that the POA >; 1 and determine near-tight upper bounds on the POA as well. The main techniques in our analysis are Lagrangian duality theory and the usage of the supermodularity of conditional entropy.

In ensemble (or bulk) quantum computation, all computations are performed on an ensemble of computers rather than on a single computer. Measurements of qubits in an individual computer cannot be performed; instead, only expectation values (over the complete ensemble of computers) can be measured. As a result of this limitation on the model of computation, many algorithms cannot be processed directly on such computers, and must be modified, as the common strategy of delaying the measurements usually does not resolve this ensemble-measurement problem. Here we present several new strategies for resolving this problem. Based on these strategies we provide new versions of some of the most important quantum algorithms, versions that are suitable for implementing on ensemble quantum computers, e.g., on liquid NMR quantum computers. These algorithms are Shor's factorization algorithm, Grover's search algorithm (with several marked items), and an algorithm for quantum fault-tolerant computation. The first two algorithms are simply modified using a randomizing and a sorting strategies. For the last algorithm, we develop a classical-quantum hybrid strategy for removing measurements. We use it to present a novel quantum fault-tolerant scheme. More explicitly, we present schemes for fault-tolerant measurement-free implementation of Toffoli and σ(z)(¼) as these operations cannot be implemented "bitwise", and their standard fault-tolerant implementations require measurement.

We consider the min-cost multicast problem (under network coding) with multiple correlated sources where each terminal wants to losslessly reconstruct all the sources. This can be considered as the network generalization of the classical distributed source coding (Slepian-Wolf) problem. We study the inefficiency brought forth by the selfish behavior of the terminals in this scenario by modeling it as a noncooperative game among the terminals. The solution concept that we adopt for this game is the popular local Nash equilibrium (Waldrop equilibrium) adapted for the scenario with multiple sources. The degradation in performance due to the lack of regulation is measured by the price of anarchy (POA), which is defined as the ratio between the cost of the worst possible Waldrop equilibrium and the socially optimum cost. Our main result is that in contrast with the case of independent sources, the presence of source correlations can significantly increase the price of anarchy. Towards establishing this result we make several contributions. We characterize the socially optimal flow and rate allocation in terms of four intuitive conditions. This result is a key technical contribution of this paper and is of independent interest as well. Next, we show that the Waldrop equilibrium is a socially optimal solution for a different set of (related) cost functions. Using this, we construct explicit examples that demonstrate that the POA > 1 and determine near- tight upper bounds on the POA as well. The main techniques in our analysis are Lagrangian duality theory and the usage of the supermodularity of conditional entropy. Finally, all the techniques and results in this paper will naturally extend to a large class of network information flow problems where the Slepian-Wolf polytope is replaced by any contra-polymatroid (or more generally polymatroid-like set), leading to a nice class of succinct multi-player games and allow the investigation of other practical and meaningful scenarios beyond network coding as well.

In this article, we introduce an exploratory framework for learning patterns of conditional co-expression in gene expression data. The main idea behind the proposed approach consists of estimating how the information content shared by a set of M nodes in a network (where each node is associated to an expression profile) varies upon conditioning on a set of L conditioning variables (in the simplest case represented by a separate set of expression profiles). The method is non-parametric and it is based on the concept of statistical co-information, which, unlike conventional correlation based techniques, is not restricted in scope to linear conditional dependency patterns. Moreover, such conditional co-expression relationships can potentially indicate regulatory interactions that do not manifest themselves when only pair-wise relationships are considered. A moment based approximation of the co-information measure is derived that efficiently gets around the problem of estimating high-dimensional multi-variate probability density functions from the data, a task usually not viable due to the intrinsic sample size limitations that characterize expression level measurements. By applying the proposed exploratory method, we analyzed a whole genome microarray assay of the eukaryote Saccharomices cerevisiae and were able to learn statistically significant patterns of conditional co-expression. A selection of such interactions that carry a meaningful biological interpretation are discussed.

In this paper, we propose a distributed parallel support vector machine (DPSVM) training mechanism in a configurable network environment for distributed data mining. The basic idea is to exchange support vectors among a strongly connected network (SCN) so that multiple servers may work concurrently on distributed data set with limited communication cost and fast training speed. The percentage of servers that can work in parallel and the communication overhead may be adjusted through network configuration. The proposed algorithm further speeds up through online implementation and synchronization. We prove that the global optimal classifier can be achieved iteratively over an SCN. Experiments on a real-world data set show that the computing time scales well with the size of the training data for most networks. Numerical results show that a randomly generated SCN may achieve better performance than the state of the art method, cascade SVM, in terms of total training time.

Determining transcriptional regulatory networks has been one of the most important goals in the field of functional genomics. Despite the recent advances in experimental techniques, complementary computational techniques have lagged behind. We introduce a novel computational methodology that uses DNA microarray data and known regulatory interactions to predict unknown regulatory interactions. Our method involves three steps: in the training stage, we utilize network component analysis (NCA) (Liao et al., 2003; Kao et al., 2004; Boscolo et al., 2005) to reconstruct the hidden activity profiles of transcriptional factors (TF); then we cluster TFs into functional modules according to the similarities of their reconstructed activity profiles; in the prediction stage, we infer additional TF-gene regulatory links by selecting TF profiles that best interpret genes expression profiles via a linear model. We applied the methodology to a gene expression dataset of bacterium Escherichia coli, whose partial TF-gene regulatory structure is obtained from RegulonDB (Salgado et al., 2004). Cross-validation results show that when the profiles of all TFs regulating a gene are reconstructed from NCA, we could identify 36% of the TF-gene interactions, and the prediction accuracy is 89%. And when the profiles of partial (50% or more) TFs regulating a gene can be reconstructed, we can identify 14% of the TF-gene interactions, and the accuracy rate is 69%. These represent some of the best known accuracy and coverage statistics reported in the literature so far

Current P2P systems employ tit-for-tat strategies, where peers only upload when they are simultaneously downloading, to avoid free riding. We derive optimal tit-for-tat strategies and obtain theoretical bounds on the performance of any P2P network employing such strategies. These are fundamental limitations that stem from peers unwillingness to cooperate without getting something in return. We show that the number of cooperating peers in a tit-for-tat strategy can, at best, grow linearly in time, as opposed to exponentially for a fully cooperative strategy. However, tit-for-tat strategies are fairer than a fully cooperative strategy. Our results show that there exists a seed capacity threshold for tit-for-tat strategies. Increasing seed capacity beyond this threshold brings significantly reduced marginal gains.

Abstract Recently we proposed a model in which when a scientist writes a manuscript, he picks up several random papers, cites them, and also copies a fraction of their references. The model was stimulated by our finding that a majority of scientific citations are copied from the lists of references used in other papers. It accounted quantitatively for several properties of empirically observed distribution of citations; however, important features such as power‐law distributions of citations to papers published during the same year and the fact that the average rate of citing decreases with aging of a paper were not accounted for by that model. Here, we propose a modified model: When a scientist writes a manuscript, he picks up several random recent papers, cites them, and also copies some of their references. The difference with the original model is the word recent . We solve the model using methods of the theory of branching processes, and find that it can explain the aforementioned features of citation distribution, which our original model could not account for. The model also can explain “ sleeping beauties in science ;” that is, papers that are little cited for a decade or so and later “awaken” and get many citations. Although much can be understood from purely random models, we find that to obtain a good quantitative agreement with empirical citation data, one must introduce Darwinian fitness parameter for the papers.

We present a novel framework, called balanced overlay networks (BON), that provides scalable, decentralized load balancing for distributed computing using large-scale pools of heterogeneous computers. Fundamentally, BON encodes the information about each node's available computational resources in the structure of the links connecting the nodes in the network. This distributed encoding is self-organized, with each node managing its in-degree and local connectivity via random-walk sampling. Assignment of incoming jobs to nodes with the most free resources is also accomplished by sampling the nodes via short random walks. Extensive simulations show that the resulting highly dynamic and self-organized graph structure can efficiently balance computational load throughout large-scale networks. These simulations cover a wide spectrum of cases, including significant heterogeneity in available computing resources and high burstiness in incoming load. Prior analytical results show BON's scalability for truly large-scale networks; under certain ideal conditions, the network structure converges to Erdos-Renyi (ER) random graphs. Our simulation results, however, show that the algorithm does much better, and the structures seem to approach the ideal case of d-regular random graphs. We also make a connection between highly-loaded BON and the well-known ball-bin randomized load balancing framework.

In recent years, many DHT-based P2P systems have been proposed, analyzed, and certain deployments have reached a global scale with nearly one million nodes. One is thus faced with the question of which particular DHT system to choose, and whether some are inherently more robust and scalable. Toward developing such a comparative framework, we present the reachable component method (RCM) for analyzing the performance of different DHT routing systems subject to random failures. We apply RCM to five DHT systems and obtain analytical expressions that characterize their routability as a continuous function of system size and node failure probability. An important consequence is that in the large-network limit, the routability of certain DHT systems go to zero for any non-zero probability of node failure. These DHT routing algorithms are therefore unscalable, while some others, including Kademlia, which powers the popular eDonkey P2P system, are found to be scalable

Given some of the recent advances in distributed hash table (DHT) based peer-to-peer (P2P) systems we ask the following questions: are there applications where unstructured queries are still necessary (i.e., the underlying queries do not efficiently map onto any structured framework), and are there unstructured P2P systems that can deliver the high bandwidth and computing performance necessary to support such applications. Toward this end, we consider an image search application which supports queries based on image similarity metrics, such as color histogram intersection, and discuss why in this setting, standard DHT approaches are not directly applicable. We then study the feasibility of implementing such an image search system on two different unstructured P2P systems: power-law topology with percolation search, and an optimized super-node topology using structured broadcasts. We examine the average and maximum values for node bandwidth, storage and processing requirements in the percolation and super-node models, and show that current high-end computers and high-speed links have sufficient resources to enable deployments of large-scale complex image search systems

It is now widely accepted that the CMOS technology implementing irreversible logic may hit a scaling limit beyond 2016, and that the increased power dissipation is a major limiting factor. Reversible computing can potentially require arbitrarily small amounts of energy. Recently several nano-scale devices which have the potential to scale, and which naturally perform reversible logic, have emerged. This paper addresses several fundamental issues that need to be addressed before any nano-scale reversible computing systems can be realized, including reliability and performance trade-offs and architecture optimization. Many nano-scale devices are limited to only near neighbor interactions, requiring careful optimization of circuits. We provide efficient fault-tolerant (FT) circuits when restricted to both 2D and 1D. Finally, we compute bounds on the entropy (and hence, heat) generated by our FT circuits and provide quantitative estimates on how large can we make our circuits before we lose any advantage over irreversible computing.

The authors recently introduced a framework, named Network Component Analysis (NCA), for the reconstruction of the dynamics of transcriptional regulators' activities from gene expression assays. The original formulation had certain shortcomings that limited NCA's application to a wide class of network dynamics reconstruction problems, either because of limitations in the sample size or because of the stringent requirements imposed by the set of identifiability conditions. In addition, the performance characteristics of the method for various levels of data noise or in the presence of model inaccuracies were never investigated. In this article, the following aspects of NCA have been addressed, resulting in a set of extensions to the original framework: 1) The sufficient conditions on the a priori connectivity information (required for successful reconstructions via NCA) are made less stringent, allowing easier verification of whether a network topology is identifiable, as well as extending the class of identifiable systems. Such a result is accomplished by introducing a set of identifiability requirements that can be directly tested on the regulatory architecture, rather than on specific instances of the system matrix. 2) The two-stage least square iterative procedure used in NCA is proven to identify stationary points of the likelihood function, under Gaussian noise assumption, thus reinforcing the statistical foundations of the method. 3) A framework for the simultaneous reconstruction of multiple regulatory subnetworks is introduced, thus overcoming one of the critical limitations of the original formulation of the decomposition, for example, occurring for poorly sampled data (typical of microarray experiments). A set of monte carlo simulations we conducted with synthetic data suggests that the approach is indeed capable of accurately reconstructing regulatory signals when these are the input of large-scale networks that satisfy the suggested identifiability criteria, even under fairly noisy conditions. The sensitivity of the reconstructed signals to inaccuracies in the hypothesized network topology is also investigated. We demonstrate the feasibility of our approach for the simultaneous reconstruction of multiple regulatory subnetworks from the same data set with a successful application of the technique to gene expression measurements of the bacterium Escherichia coli.

In ensemble (or bulk) quantum computation, all computations are performed on an ensemble of computers rather than on a single computer. Measurements of qubits in an individual computer cannot be performed; instead, only expectation values (over the complete ensemble of computers) can be measured. As a result of this limitation on the model of computation, many algorithms cannot be processed directly on such computers, and must be modified. We provide modification of the fault tolerant quantum computation protocols to enable processing on ensemble quantum computers.

We introduce a scalable searching protocol for locating and retrieving content in random networks with power-law (PL) and heavy-tailed degree distributions. The proposed algorithm is capable of finding any content in the network with probability one in time O(logN), with a total traffic that provably scales sub-linearly with the network size, N. Unlike other proposed solutions, there is no need to assume that the network has multiple copies of contents; the protocol finds all contents reliably, even if every node in the network starts with a unique content. The scaling behavior of the size of the giant connected component of a random graph with heavy tailed degree distributions under bond percolation is at the heart of our results. The percolation search algorithm can be directly applied to make unstructured peer-to-peer (P2P) networks, such as Gnutella, Limewire and other file-sharing systems (which naturally display heavy-tailed degree distributions and scale-free network structures), scalable. For example, simulations of the protocol on the limewire crawl number 5 network, consisting of over 65,000 links and 10,000 nodes, shows that even for this snapshot network, the traffic can be reduced by a factor of at least 100, and yet achieve a hit-rate greater than 90%.

In this paper, we introduce a novel independent component analysis (ICA) algorithm, which is truly blind to the particular underlying distribution of the mixed signals. Using a nonparametric kernel density estimation technique, the algorithm performs simultaneously the estimation of the unknown probability density functions of the source signals and the estimation of the unmixing matrix. Following the proposed approach, the blind signal separation framework can be posed as a nonlinear optimization problem, where a closed form expression of the cost function is available, and only the elements of the unmixing matrix appear as unknowns. We conducted a series of Monte Carlo simulations, involving linear mixtures of various source signals with different statistical characteristics and sample sizes. The new algorithm not only consistently outperformed all state-of-the-art ICA methods, but also demonstrated the following properties: 1) Only a flexible model, capable of learning the source statistics, can consistently achieve an accurate separation of all the mixed signals. 2) Adopting a suitably designed optimization framework, it is possible to derive a flexible ICA algorithm that matches the stability and convergence properties of conventional algorithms. 3) A nonparametric approach does not necessarily require large sample sizes in order to outperform methods with fixed or partially adaptive contrast functions.

Recent studies showed that conventional approaches being used to solve problems imposed by hard-wired metal interconnects will eventually encounter fundamental limits and may impede the advance of future ultralarge-scale integrated circuits (ULSls). To surpass these fundamental limits, we introduce a novel RF/wireless interconnect concept for future inter- and intra-ULSI communications. Unlike the traditional "passive" metal interconnect, the "active" RF/wireless interconnect is based on low loss and dispersion-free microwave signal transmission, near-field capacitive coupling, and modem multiple-access algorithms. In this paper we address issues relevant to the signal channeling of the RF/wireless interconnect and discuss its advantages in speed, signal integrity, and channel reconfiguration. The electronic overhead required in the RF/wireless-interconnect system and its compatibility with the future ULSI and MCM (multi-chip-module) will be discussed as well.

We show that Nechiporuk's method [I. Wegener, The Complexity of Boolean Functions, Teubner-Wiley, New York, 1987] for proving lower bounds for Boolean formulas can be extended to the quantum case. This leads to an $\Omega(n^2/\log^2 n)$ lower bound for quantum formulas computing an explicit function. The only known previous explicit lower bound for quantum formulas [A. Yao, Proceedings of 34th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1993, pp. 352--361] states that the majority function does not have a linear-size quantum formula. We also show that quantum formulas can be simulated by Boolean circuits of almost the same size.

Upper bounds are given for the weight distribution of binary weakly self-dual codes. To get these new bounds, we introduce a novel method of utilizing unitary operations on Hilbert spaces. This method is motivated by recent progress on quantum computing. This new approach leads to much simpler proofs for such genre of bounds on the weight distributions of certain classes of codes. Moreover, in some cases, our bounds are improvements on the earlier bounds. These improvements are achieved either by extending the range of the weights over which the bounds apply or by extending the class of codes subjected to these bounds.

Article Free Access Share on A proof of the security of quantum key distribution (extended abstract) Authors: Eli Biham Computer Science Department, Technion, Haifa 32000, Israel Computer Science Department, Technion, Haifa 32000, IsraelView Profile , Michel Boyer DIRO, Université de Montréal, Montréal, Canada DIRO, Université de Montréal, Montréal, CanadaView Profile , P. Oscar Boykin Dept. of Electrical Engineering, UCLA, Los Angeles, CA Dept. of Electrical Engineering, UCLA, Los Angeles, CAView Profile , Tal Mor Dept. of Electrical Engineering, UCLA, Los Angeles, CA and Dept. of Electrical Engineering, College of Judea and Samaria, Ariel, Israel Dept. of Electrical Engineering, UCLA, Los Angeles, CA and Dept. of Electrical Engineering, College of Judea and Samaria, Ariel, IsraelView Profile , Vwani Roychowdhury Dept. of Electrical Engineering, College of Judea and Samaria, Ariel, Israel Dept. of Electrical Engineering, College of Judea and Samaria, Ariel, IsraelView Profile Authors Info & Claims STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computingMay 2000 Pages 715–724https://doi.org/10.1145/335305.335406Published:01 May 2000Publication History 38citation1,057DownloadsMetricsTotal Citations38Total Downloads1,057Last 12 Months95Last 6 weeks17 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We derive and discuss new adaptive algorithms for principal component analysis (PCA) that are shown to converge faster than the traditional PCA algorithms due to Oja, Sanger, and Xu. It is well known that traditional PCA algorithms that are derived by using gradient descent on an objective function are slow to converge. Furthermore, the convergence of these algorithms depends on appropriate choices of the gain sequences. Since online applications demand faster convergence and an automatic selection of gains, we present new adaptive algorithms to solve these problems. We first present an unconstrained objective function, which can be minimized to obtain the principal components. We derive adaptive algorithms from this objective function by using: 1) gradient descent; 2) steepest descent; 3) conjugate direction; and 4) Newton-Raphson methods. Although gradient descent produces Xu's LMSER algorithm, the steepest descent, conjugate direction, and Newton-Raphson methods produce new adaptive algorithms for PCA. We also provide a discussion on the landscape of the objective function, and present a global convergence proof of the adaptive gradient descent PCA algorithm using stochastic approximation theory. Extensive experiments with stationary and nonstationary multidimensional Gaussian sequences show faster convergence of the new algorithms over the traditional gradient descent methods.We also compare the steepest descent adaptive algorithm with state-of-the-art methods on stationary and nonstationary sequences.

A novel universal and fault-tolerant basis (set of gates) for quantum computation is described. Such a set is necessary to perform quantum computation in a realistic noisy environment. The new basis consists of two single-qubit gates (Hadamard and /spl sigma//sub z//sup 1/4 /) and one double-qubit gate (Controlled-NOT). Since the set consisting of Controlled-NOT and Hadamard gates is not universal, the new basis achieves universality by including only one additional elementary (in the sense that it does not include angles that are irrational multiples of /spl pi/) single-qubit gate, and hence, is potentially the simplest universal basis that one can construct. We also provide an alternative proof of universality for the only other known class of universal and fault-tolerant basis proposed by P.W. Shor (1996) and A.Y. Kitaev (1997).

We derive and discuss new adaptive algorithms for principal component analysis (PCA) that are shown to converge faster than the traditional PCA algorithms due to Oja, Sanger and Xu. Since online applications demand faster convergence and an automatic selection of gains, we employ nonlinear optimization techniques to present new algorithms to solve these problems. We first present an unconstrained objective function, which can be minimized to obtain the principal components. We derive adaptive algorithms from this objective function by using: (1) gradient descent, (2) steepest descent, (3) conjugate direction, and (4) Newton-Raphson methods. We also provide a discussion on the landscape of the objective function, and present a convergence proof of the adaptive gradient descent PCA algorithm using stochastic approximation theory. Extensive experiments with stationary and nonstationary multidimensional Gaussian sequences show the faster convergence of the new algorithms over the traditional gradient descent methods.

We explore the design of quantum error-correcting codes for cases where the decoherence events of qubits are correlated. In particular, we consider the case where only spatially contiguous qubits decohere, which is analogous to the case of burst errors in classical coding theory. We present several different efficient schemes for constructing families of such codes. For example, one can find one-dimensional quantum codes of length n=13 and 15 that correct burst errors of width b<3; as a comparison, a random-error correcting quantum code that corrects t=3 errors must have length n/spl ges/17. In general, we show that it is possible to build quantum burst-correcting codes that have near optimal dimension. For example, we show that for any constant b, there exist b-burst-correcting quantum codes with length n, and dimension k=n-log n-O(1); as a comparison, the Hamming bound for the case with t (constant) random errors yields k/spl les/n-tlog n+O(1).

We investigate the convergence properties of two different stochastic approximation algorithms for principal component analysis, and analytically explain some commonly observed experimental results. In our analysis, we use the theory of stochastic approximation, and in particular the results of Fabian, to explore the asymptotic mean square errors (AMSE's) of the algorithms. This study reveals the conditions under which the algorithms produce smaller AMSE's, and also the conditions under which one algorithm has a smaller AMSE than the other. Experimental study with multidimensional Gaussian data corroborate our analytical findings. We next explore the convergence rates of the two algorithms. Our experiments and an analytical explanation reveals the conditions under which the algorithms converge faster to the solution, and also the conditions under which one algorithm converges faster than the other. Finally, we observe that although one algorithm has a larger computation in each iteration, it leads to a smaller AMSE and converges faster for the minor eigenvectors when compared to the other algorithm.

The past decade has seen tremendous experimental and theoretical progress in the field of mesoscopic devices and molecular self assembly techniques, leading to laboratory demonstration of many new device concepts. While these studies have been important from a fundamental physics perspective, it has been recognized by many that they may offer new insights into building a future generation of computing machines. This has recently led to a number of proposals for computing machines which use these new and novel device concepts. In this paper, we explain the physical principles behind the operation of one of these proposals, namely the ground state computing model. These computational models share some of the characteristics of the well-known systolic type processor arrays, namely spatial locality, and functional uniformity. In particular, we study the effect of metastable states on the relaxation process (and hence information propagation) in locally coupled and boundary-driven structures. We first give a general argument to show that metastable states are inevitable even in the simplest of structures, a wire. At finite temperatures, the relaxation mechanism is a thermally assisted random walk. The time required to reach the ground state and its life time are determined by the coupling parameters. These time scales are studied in a model based on an array of quantum dots.

We describe an adaptive algorithm based on stochastic approximation theory for the simultaneous diagonalization of the expectations of two random matrix sequences. Although there are several conventional approaches to solving this problem, there are many applications in pattern analysis and signal detection that require an online (i.e., real-time) procedure for this computation. In these applications, we are given two sequences of random matrices {A/sub k/} and {B/sub k/} as online observations, with lim/sub k/spl rarr//spl infin//E[A/sub k/]=A and lim/sub k/spl rarr//spl infin//E[B/sub k/]=B, where A and B are real, symmetric and positive definite. For every sample (A/sub k/, B/sub k/), we need the current estimates /spl Phi//sub k/ and /spl Lambda//sub k/, respectively of the eigenvectors /spl Phi/ and eigenvalues /spl Lambda/ of A/sup -1/ B. We have described such an algorithm where /spl Phi//sub k/ and /spl Lambda//sub k/ converge provably with probability one to /spl Phi/ and /spl Lambda/ respectively. A novel computational procedure used in the algorithm is the adaptive computation of A/sup - 1/2 /. Besides its use in the generalized eigen-decomposition problem, this procedure can be used on its own in several feature extraction problems. The performance of the algorithm is demonstrated with an example of detecting a high-dimensional signal in the presence of interference and noise, in a digital mobile communications problem. Experiments comparing computational complexity and performance demonstrate the effectiveness of the algorithm in this real-time application.

A nanoelectronic implementation of Boolean logic circuits is described where logic functionality is realized through charge interactions between metallic dots self-assembled on the surface of a double-barrier resonant tunneling diode (RTD) structure. The primitive computational cell in this architecture consists of a number of dots with nearest neighbor (resistive) interconnections. Specific logic functionality is provided by appropriate rectifying connections between cells. We show how basic logic gates, leading to combinational and sequential circuits, can be realized in this architecture. Additionally, architectural issues including directionality, fault tolerance, and power dissipation are discussed. Estimates based on the current-voltage characteristics of RTD's and the capacitance and resistance values of the interdot connections indicate that static power dissipation as small as 0.1 nW/gate and switching delay as small as a few picoseconds can be expected. We also present a strategy for fabricating/synthesizing such systems using chemical self-organizing/self-assembly phenomena. The proposed synthesis procedure utilizes several chemical self-assembly techniques which have been demonstrated recently, including self-assembly of uniform arrays of close-packed metallic dots with nanometer diameters, controlled resistive linking of nearest neighbor dots with conjugated organic molecules and organic rectifiers.

We describe self-organizing learning algorithms and associated neural networks to extract features that are effective for preserving class separability. As a first step, an adaptive algorithm for the computation of Q(-1/2) (where Q is the correlation or covariance matrix of a random vector sequence) is described. Convergence of this algorithm with probability one is proven by using stochastic approximation theory, and a single-layer linear network architecture for this algorithm is described, which we call the Q(-1/2) network. Using this network, we describe feature extraction architectures for: 1) unimodal and multicluster Gaussian data in the multiclass case; 2) multivariate linear discriminant analysis (LDA) in the multiclass case; and 3) Bhattacharyya distance measure for the two-class case. The LDA and Bhattacharyya distance features are extracted by concatenating the Q (-1/2) network with a principal component analysis network, and the two-layer network is proven to converge with probability one. Every network discussed in the study considers a flow or sequence of inputs for training. Numerical studies on the performance of the networks for multiclass random data are presented.

We discuss a new approach to self-organization that leads to novel adaptive algorithms for generalized eigen-decomposition and its variance for a single-layer linear feedforward neural network. First, we derive two novel iterative algorithms for linear discriminant analysis (LDA) and generalized eigen-decomposition by utilizing a constrained least-mean-squared classification error cost function, and the framework of a two-layer linear heteroassociative network performing a one-of-m classification. By using the concept of deflation, we are able to find sequential versions of these algorithms which extract the LDA components and generalized eigenvectors in a decreasing order of significance. Next, two new adaptive algorithms are described to compute the principal generalized eigenvectors of two matrices (as well as LDA) from two sequences of random matrices. We give a rigorous convergence analysis of our adaptive algorithms by using stochastic approximation theory, and prove that our algorithms converge with probability one.

The limiter function is used in many learning and retrieval models as the constraint controlling the magnitude of the weight or state vectors. In this paper, we developed a new method to relate the set of saturated fixed points to the set of system parameters of the models that use the limiter function, and then, as a case study, applied this method to Linsker's Hebbian learning network. We derived a necessary and sufficient condition to test whether a given saturated weight or state vector is stable or not for any given set of system parameters, and used this condition to determine the whole regime in the parameter space over which the given state is stable. This approach allows us to investigate the relative stability of the major receptive fields reported in Linsker's simulations, and to demonstrate the crucial role played by the synaptic density functions.

We consider the problem of scheduling tasks on multiprocessor architectures in the presence of communication delays. Given a set of dependent tasks, the scheduling problem is to allocate the tasks to processors such that the pre-specified precedence constraints among the tasks are obeyed and certain cost-measures (such as the computation time) are minimized. Several cases of the scheduling problem have been proven to be NP-complete. Nevertheless, there are polynomial time algorithms for interesting special cases of the general scheduling problem. Most of these results, however, do not take into consideration the delays due to message passing among processors. In this paper we study the increase in time complexity of scheduling problems due to the introduction of communication delays. In particular, we address the open problem of scheduling Out-forests (In-forests) in a multiprocessor system of m identical processors when communication delays are considered. The corresponding problem of scheduling Out-forests (In-forests) without communication delays admits an elegant polynomial time solution as presented first by Hu in 1961; however, the problem in the presence of communication delays has remained unsolved. We present here first known polynomial time algorithms for the computation of the optimal schedule when the number of available processors is given and bounded and both computation and communication delays are assumed to take one unit of time. Furthermore, we present a linear-time algorithm for computing a near-optimal schedule for unit-delay out-forests. The schedule's length exceeds the optimum by no more than (m-2) time units, where m is the number of processors. Hence for two processors the computed schedule is strictly optimum.

Learning and convergence properties of linear threshold elements or perceptrons are well understood for the case where the input vectors (or the training sets) to the perceptron are linearly separable. Little is known, however, about the behavior of the perceptron learning algorithm when the training sets are linearly nonseparable. We present the first known results on the structure of linearly nonseparable training sets and on the behavior of perceptrons when the set of input vectors is linearly nonseparable. More precisely, we show that using the well known perceptron learning algorithm, a linear threshold element can learn the input vectors that are provably learnable, and identify those vectors that cannot be learned without committing errors. We also show how a linear threshold element can be used to learn large linearly separable subsets of any given nonseparable training set. In order to develop our results, we first establish formal characterizations of linearly nonseparable training sets and define learnable structures for such patterns. We also prove computational complexity results for the related learning problems. Next, based on such characterizations, we show that a perceptron does the best one can expect for linearly nonseparable sets of input vectors and learns as much as is theoretically possible.

We propose a novel rigorous approach for the analysis of Linsker's unsupervised Hebbian learning network. The behavior of this model is determined by the underlying nonlinear dynamics which are parameterized by a set of parameters originating from the Heb(cid:173) bian rule and the arbor density of the synapses. These parameters determine the presence or absence of a specific receptive field (also referred to as a 'connection pattern') as a saturated fixed point attractor of the model. In this paper, we perform a qualitative analysis of the underlying nonlinear dynamics over the parameter space, determine the effects of the system parameters on the emer(cid:173) gence of various receptive fields, and predict precisely within which parameter regime the network will have the potential to develop a specially designated connection pattern. In particular, this ap(cid:173) proach exposes, for the first time, the crucial role played by the synaptic density functions, and provides a complete precise picture of the parameter space that defines the relationships among the different receptive fields. Our theoretical predictions are confirmed by numerical simulations. 320 lian/eng Feng, H. Pan, V. P. Roychowdhury

Let $\widehat{LT}_d $ denote the class of functions that can be computed by depth-d threshold circuits with polynomial size and polynomially bounded integer weights. Using the results in [M. Goldman, J. Håstad, and A. Razborov, in Proc. 7th Annual Conference on Structure in Complexity Theory], [M. Goldman and M. Karpinski, Constructing depth$d+1$majority circuits that simulate depth d threshold circuits, unpublished] we show that multiple sum is in $\widehat{LT}_2 $, and multiplication and division are in $\widehat{LT}_3 $. Moreover, it follows from the lower-bound results in [A. Hajnal et al., IEEE Sympos. Foundations of Comput. Sci., 28 (1987), pp. 99–110], [T. Hofmeister and P. Pudlák, Forschungbericht Nr. 477 Uni Dortmund, 1992] that these threshold circuits are optimal in circuit depth. The authors also indicate that these techniques can be applied to construct polynomial-size depth-3 threshold circuits for powering and depth-4 threshold circuits for multiple product.

Using communication complexity concepts and techniques, we derive linear (/spl Omega/(n)) and almost-linear (/spl Omega/(n/logn)) lower bounds on the size of circuits implementing certain functions. Our approach utilizes only basic features of the gates used, hence the bounds hold for general families of gates of which the symmetric and threshold gates are special cases. Each of the bounds derived is shown to be tight for some functions and some applications to threshold circuit complexity are indicated. The results generalize and in some cases strengthen recent results.>

Artificial neural networks are comprised of an interconnected collection of certain nonlinear devices; examples of commonly used devices include linear threshold elements, sigmoidal elements, and radial-basis elements. We employ results from harmonic analysis and the theory of rational approximation to obtain almost tight lower bounds on the size (i.e., number of elements) of neural networks. The class of neural networks to which our techniques can be applied is quite general it includes any feedforward network in which each element can be piecewise approximated by a low degree rational function. For example, we prove that any depth-d+1 network of sigmoidal units or linear threshold elements computing the parity function of n variables must have R(dn/sup 1//d-/spl epsiv/) size, for any fixed /spl epsiv/>0. In addition, we prove that this lower bound is almost tight by showing that the parity function can be computed with O(dn/sup 1/d/) sigmoidal units or linear threshold elements in a depth-(d+1) network. These almost tight bounds are the first known complexity results on the size of neural networks with depth more than two. Our lower bound techniques yield a unified approach to the complexity analysis of various models of neural networks with feedforward structures. Moreover, our results indicate that the in the context of computing highly oscillating symmetric Boolean functions, networks of continuous-output units such as sigmoidal elements do not offer significant reduction in size compared with networks of linear threshold elements of binary outputs.>

An algorithm for camera calibration is presented. It is a significant improvement in mathematical simplicity, accuracy and computational efficiency in the solution of all extrinsic (external camera geometric) and intrinsic (internal camera geometric and camera optics) parameters. The method involves a direct transformation from the three-dimensional (3-D) object world to the two-dimensional (2-D) image or sensor plane in terms of homogeneous vector forms for both coplanar and noncoplanar distributions of object points. A strong robust property of the proposed algorithm is demonstrated by proving that if the camera is calibrated with image data not compensated for image center displacement and scale factor, the proposed algorithm yields parameters that cause no error in the computation of both image and world coordinates.>

A polynomial time algorithm for solving the combinatorial problem that underlies the reconfiguration issues in the m1/2-track-m-spare model, for any arbitrary m, is discussed. The following combinatorial problem is solved: Given a set of points in a two-dimensional grid, find a set of noninteracting straight lines such that every line starts at a point and connects to one of the boundaries of the grid, there are no more than m lines overlapping in any row or column of the grid, and there are no near-miss situations. The time complexity of the algorithm is shown to be O(m mod F mod /sup 2/), where mod F is the number of faulty processors.>

Present new results on systematic procedures for reconfiguring processor arrays in the presence of faulty processors. In particular, the authors consider models that use multiple tracks along every channel and a single spare row (or column) of processing elements (PEs) along each boundary of the array. In the presence of faulty PEs the general methodology for reconfiguration involves replacing every faulty PE logically (rather than physically) by a spare PE through a sequence of logical substitutions; these sequences of substitutions are referred to as compensation paths. The authors show that if there exists a set of compensation paths subjected only to the constraints of continuity and nonintersection, then routing channels with three tracks are enough for the reconfiguration of the array. They refer to the underlying model as a S-track-l-spare model; this is done to distinguish it from other models that not only use multiple tracks but also multiple spare rows (or columns) along each boundary. An efficient algorithm for reconfiguration in our 3-track-1-spare model is presented and its performance evaluated. Experimental results show that the 3-track-1-spare model has much higher reconfiguration probability than other models that use considerably more spare processors.>

Novel problems concerning routing in a segmented routing channel are introduced. These problems are fundamental to routing and design automation for field programmable gate arrays (FPGAs), a new type of electrically programmable VLSI. The first known theoretical results on the combinatorial complexity and algorithm design for segmented channel routing are presented. It is shown that the segmented channel routing problem is in general NP-complete. Efficient polynomial time algorithms for a number of important special cases are presented.>

The tradeoffs between the depth (i.e., the time for parallel computation) and the size (i.e., the number of threshold gates) in neural networks are studied. The authors focus the study on the neural computations of symmetric Boolean functions and some arithmetic functions. It is shown that a significant reduction in the size is possible for symmetric functions and some arithmetic functions, at the expense of a small constant increase in depth. In the process, several neural networks which have the minimum size among all the known constructions have been developed. Results on implementing symmetric functions can be used to improve results about arbitrary Boolean functions. In particular, it is shown that any Boolean function can be computed in a depth-3 neural network with O(2/sup n/ /sup 2/) threshold gates; it is also proven that at least Omega (2/sup n/ /sup 3/) threshold gates are required.>

Routing channels in a field-programmable gate array contain predefined wiring segments of various lengths. These may be connected to the pins of the gates or joined end-to-end to form longer segments by programmable switches. The segmented channel routing problem is formulated, and polynomial time algorithms are given for certain special cases. The general problem is NP-complete, but it can be adequately solved in practice. Experiments indicate that a segmented channel with judiciously chosen segment lengths may near the efficiency of a conventional channel.

The study of Regular Iterative Algorithms (RIAs), which was introduced in a seminal pa.per by Knrp, Miller, and Winograd in 1967, forms the basis for systematic design and analysis of regular processor arrays, including the class of systolic arrays.The RIAs have also been studied under different contexts and different names (on the last count RIAs were reintroduced, as late as 1987, under the name of dynamic graphs).In spite of the interest such algorithms have received over the years, many important issues that were left unresolved in the original paper by Karp e2 al., have remained unanswered.In this paper we answer many such questions, particularly those relating to parallel scheduling and implementation of RIAs.Based on the analysis of a simple graph that captures the dependence structure of a given RIA, we are able to determine linear subspaces in the index space of a given RIA such that all variables lying on the same subspace can be scheduled at the same time; this generalizes the so-called hyperplanar scheduling which was shown by Karp et.al. to work for only a subclass of RIAs.This geometric scheduling scheme is shown to be asymptotically optimal and is used to completely characterize the extent of parallelism in any RIA.Moreover, we develop procedures to determine explicit schedules (;.e, a closed form expression for the schedule of every computation in the algorithm) that correspond to the geometric schedules, and also show that every RIA can be automatically mapped onto regular processor arrays.

The issue of developing efficient algorithms for reconfiguring processor arrays in the presence of faulty processors and fixed hardware resources is discussed. The models discussed consist of a set of identical processors embedded in a flexible interconnection structure that is configured in the form of a rectangular grid. An array grid model based on single-track switches is considered. An efficient polynomial time algorithm is proposed for determining feasible reconfigurations for an array with a given distribution of faulty processors. In the process, it is shown that the set of conditions in the reconfigurability theorem is not necessary. A polynomial time algorithm is developed for finding feasible reconfigurations in an augmented single-track model and in array grid models with multiple-track switches.>

The outer-product method for programming the Hopfield model is discussed. The method can result in many spurious stable states-exponential in the number of vectors that are to be stored-even in the case when the vectors are orthogonal.>