OpenRaiser/Intern-Atlas huggingface dataset:
Theoretical Engineering and Satellite Comlink of a PTVD-SHAM System
Venue: arXiv cs.CE 2007
Year: 2007

This paper focuses on super helical memory system's design, 'Engineering, Architectural and Satellite Communications' as a theoretical approach of an invention-model to 'store time-data'. The current release entails three concepts: 1- an in-depth theoretical physics engineering of the chip including its, 2- architectural concept based on VLSI methods, and 3- the time-data versus data-time algorithm. The 'Parallel Time Varying & Data Super-helical Access Memory' (PTVD-SHAM), possesses a waterfall effect in its architecture dealing with the process of voltage output-switch into diverse logic and quantum states described as 'Boolean logic & image-logic', respectively. Quantum dot computational methods are explained by utilizing coiled carbon nanotubes (CCNTs) and CNT field effect transistors (CNFETs) in the chip's architecture. Quantum confinement, categorized quantum well substrate, and B-field flux involvements are discussed in theory. Multi-access of coherent sequences of 'qubit addressing' in any magnitude, gained as pre-defined, here e.g., the 'big O notation' asymptotically confined into singularity while possessing a magnitude of 'infinity' for the orientation of array displacement. Gaussian curvature of k<0 versus k'>(k<0) is debated in aim of specifying the 2D electron gas characteristics, data storage system for defining short and long time cycles for different CCNT diameters where space-time continuum is folded by chance for the particle. Precise pre/post data timing for, e.g., seismic waves before earthquake mantle-reach event occurrence, including time varying self-clocking devices in diverse geographic locations for radar systems is illustrated in the Subsections of the paper. The theoretical fabrication process, electromigration between chip's components is discussed as well.
Interpolation in Valiant's theory
Venue: arXiv cs.CC 2007
Year: 2007

We investigate the following question: if a polynomial can be evaluated at rational points by a polynomial-time boolean algorithm, does it have a polynomial-size arithmetic circuit? We argue that this question is certainly difficult. Answering it negatively would indeed imply that the constant-free versions of the algebraic complexity classes VP and VNP defined by Valiant are different. Answering this question positively would imply a transfer theorem from boolean to algebraic complexity. Our proof method relies on Lagrange interpolation and on recent results connecting the (boolean) counting hierarchy to algebraic complexity classes. As a byproduct we obtain two additional results: (i) The constant-free, degree-unbounded version of Valiant's hypothesis that VP and VNP differ implies the degree-bounded version. This result was previously known to hold for fields of positive characteristic only. (ii) If exponential sums of easy to compute polynomials can be computed efficiently, then the same is true of exponential products. We point out an application of this result to the P=NP problem in the Blum-Shub-Smale model of computation over the field of complex numbers.
TP Decoding
Venue: arXiv cs.IT 2007
Year: 2007

`Tree pruning' (TP) is an algorithm for probabilistic inference on binary Markov random fields. It has been recently derived by Dror Weitz and used to construct the first fully polynomial approximation scheme for counting independent sets up to the `tree uniqueness threshold.' It can be regarded as a clever method for pruning the belief propagation computation tree, in such a way to exactly account for the effect of loops. In this paper we generalize the original algorithm to make it suitable for decoding linear codes, and discuss various schemes for pruning the computation tree. Further, we present the outcomes of numerical simulations on several linear codes, showing that tree pruning allows to interpolate continuously between belief propagation and maximum a posteriori decoding. Finally, we discuss theoretical implications of the new method.
Detailed Network Measurements Using Sparse Graph Counters: The Theory
Venue: arXiv cs.NI 2007
Year: 2007

Measuring network flow sizes is important for tasks like accounting/billing, network forensics and security. Per-flow accounting is considered hard because it requires that many counters be updated at a very high speed; however, the large fast memories needed for storing the counters are prohibitively expensive. Therefore, current approaches aim to obtain approximate flow counts; that is, to detect large elephant flows and then measure their sizes. Recently the authors and their collaborators have developed [1] a novel method for per-flow traffic measurement that is fast, highly memory efficient and accurate. At the core of this method is a novel counter architecture called "counter braids.'' In this paper, we analyze the performance of the counter braid architecture under a Maximum Likelihood (ML) flow size estimation algorithm and show that it is optimal; that is, the number of bits needed to store the size of a flow matches the entropy lower bound. While the ML algorithm is optimal, it is too complex to implement. In [1] we have developed an easy-to-implement and efficient message passing algorithm for estimating flow sizes.
On Convergence Properties of Shannon Entropy
Venue: arXiv cs.IT 2007
Year: 2007

Convergence properties of Shannon Entropy are studied. In the differential setting, it is shown that weak convergence of probability measures, or convergence in distribution, is not enough for convergence of the associated differential entropies. A general result for the desired differential entropy convergence is provided, taking into account both compactly and uncompactly supported densities. Convergence of differential entropy is also characterized in terms of the Kullback-Liebler discriminant for densities with fairly general supports, and it is shown that convergence in variation of probability measures guarantees such convergence under an appropriate boundedness condition on the densities involved. Results for the discrete setting are also provided, allowing for infinitely supported probability measures, by taking advantage of the equivalence between weak convergence and convergence in variation in this setting.
Superrecursive Features of Interactive Computation
Venue: arXiv cs.DC 2007
Year: 2007

Functioning and interaction of distributed devices and concurrent algorithms are analyzed in the context of the theory of algorithms. Our main concern here is how and under what conditions algorithmic interactive devices can be more powerful than the recursive models of computation, such as Turing machines. Realization of such a higher computing power makes these systems superrecursive. We find here five sources for superrecursiveness in interaction. In addition, we prove that when all of these sources are excluded, the algorithmic interactive system in question is able to perform only recursive computations. These results provide computer scientists with necessary and sufficient conditions for achieving superrecursiveness by algorithmic interactive devices.
Weight Distributions of Hamming Codes (II)
Venue: arXiv cs.IT 2007
Year: 2007

In a previous paper, we derived a recursive formula determining the weight distributions of the [n=(q^m-1)/(q-1)] Hamming code H(m,q), when (m,q-1)=1. Here q is a prime power. We note here that the formula actually holds for any positive integer m and any prime power q, without the restriction (m, q-1)=1.
Approximating max-min linear programs with local algorithms
Venue: arXiv cs.DC 2007
Year: 2007

A local algorithm is a distributed algorithm where each node must operate solely based on the information that was available at system startup within a constant-size neighbourhood of the node. We study the applicability of local algorithms to max-min LPs where the objective is to maximise $\min_k \sum_v c_{kv} x_v$ subject to $\sum_v a_{iv} x_v \le 1$ for each $i$ and $x_v \ge 0$ for each $v$. Here $c_{kv} \ge 0$, $a_{iv} \ge 0$, and the support sets $V_i = \{v : a_{iv} > 0 \}$, $V_k = \{v : c_{kv}>0 \}$, $I_v = \{i : a_{iv} > 0 \}$ and $K_v = \{k : c_{kv} > 0 \}$ have bounded size. In the distributed setting, each agent $v$ is responsible for choosing the value of $x_v$, and the communication network is a hypergraph $\mathcal{H}$ where the sets $V_k$ and $V_i$ constitute the hyperedges. We present inapproximability results for a wide range of structural assumptions; for example, even if $|V_i|$ and $|V_k|$ are bounded by some constants larger than 2, there is no local approximation scheme. To contrast the negative results, we present a local approximation algorithm which achieves good approximation ratios if we can bound the relative growth of the vertex neighbourhoods in $\mathcal{H}$.
Evaluate the Word Error Rate of Binary Block Codes with Square Radius Probability Density Function
Venue: arXiv cs.IT 2007
Year: 2007

The word error rate (WER) of soft-decision-decoded binary block codes rarely has closed-form. Bounding techniques are widely used to evaluate the performance of maximum-likelihood decoding algorithm. But the existing bounds are not tight enough especially for low signal-to-noise ratios and become looser when a suboptimum decoding algorithm is used. This paper proposes a new concept named square radius probability density function (SR-PDF) of decision region to evaluate the WER. Based on the SR-PDF, The WER of binary block codes can be calculated precisely for ML and suboptimum decoders. Furthermore, for a long binary block code, SR-PDF can be approximated by Gamma distribution with only two parameters that can be measured easily. Using this property, two closed-form approximative expressions are proposed which are very close to the simulation results of the WER of interesting.
The Secrecy Capacity of the MIMO Wiretap Channel
Venue: arXiv cs.IT 2007
Year: 2007

We consider the MIMO wiretap channel, that is a MIMO broadcast channel where the transmitter sends some confidential information to one user which is a legitimate receiver, while the other user is an eavesdropper. Perfect secrecy is achieved when the the transmitter and the legitimate receiver can communicate at some positive rate, while insuring that the eavesdropper gets zero bits of information. In this paper, we compute the perfect secrecy capacity of the multiple antenna MIMO broadcast channel, where the number of antennas is arbitrary for both the transmitter and the two receivers.
Solving Infinite Kolam in Knot Theory
Venue: arXiv cs.DM 2007
Year: 2007

In south India, there are traditional patterns of line-drawings encircling dots, called ``Kolam'', among which one-line drawings or the ``infinite Kolam'' provide very interesting questions in mathematics. For example, we address the following simple question: how many patterns of infinite Kolam can we draw for a given grid pattern of dots? The simplest way is to draw possible patterns of Kolam while judging if it is infinite Kolam. Such a search problem seems to be NP complete. However, it is certainly not. In this paper, we focus on diamond-shaped grid patterns of dots, (1-3-5-3-1) and (1-3-5-7-5-3-1) in particular. By using the knot-theory description of the infinite Kolam, we show how to find the solution, which inevitably gives a sketch of the proof for the statement ``infinite Kolam is not NP complete.'' Its further discussion will be given in the final section.
Sleeping on the Job: Energy-Efficient Broadcast for Radio Networks
Venue: arXiv cs.DS 2007
Year: 2007

We address the problem of minimizing power consumption when performing reliable broadcast on a radio network under the following popular model. Each node in the network is located on a point in a two dimensional grid, and whenever a node sends a message, all awake nodes within distance r receive the message. In the broadcast problem, some node wants to successfully send a message to all other nodes in the network even when up to a 1/2 fraction of the nodes within every neighborhood can be deleted by an adversary. The set of deleted nodes is carefully chosen by the adversary to foil our algorithm and moreover, the set of deleted nodes may change periodically. This models worst-case behavior due to mobile nodes, static nodes losing power or simply some points in the grid being unoccupied. A trivial solution requires each node in the network to be awake roughly 1/2 the time, and a trivial lower bound shows that each node must be awake for at least a 1/n fraction of the time. Our first result is an algorithm that requires each node to be awake for only a 1/sqrt(n) fraction of the time in expectation. Our algorithm achieves this while ensuring correctness with probability 1, and keeping optimal values for other resource costs such as latency and number of messages sent. We give a lower-bound that shows that this reduction in power consumption is asymptotically optimal when latency and number of messages sent must be optimal. If we can increase the latency and messages sent by only a log*n factor we give a Las Vegas algorithm that requires each node to be awake for only a (log*n)/n expected fraction of the time; we give a lower-bound showing that this second algorithm is near optimal. Finally, we show how to ensure energy-efficient broadcast in the presence of Byzantine faults.
L2 norm performance index of synchronization and optimal control synthesis of complex networks
Venue: arXiv cs.NI 2007
Year: 2007

In this paper, the synchronizability problem of dynamical networks is addressed, where better synchronizability means that the network synchronizes faster with lower-overshoot. The L2 norm of the error vector e is taken as a performance index to measure this kind of synchronizability. For the equilibrium synchronization case, it is shown that there is a close relationship between the L2 norm of the error vector e and the H2 norm of the transfer function G of the linearized network about the equilibrium point. Consequently, the effect of the network coupling topology on the H2 norm of the transfer function G is analyzed. Finally, an optimal controller is designed, according to the so-called LQR problem in modern control theory, which can drive the whole network to its equilibrium point and meanwhile minimize the L2 norm of the output of the linearized network.
Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems - Report on the Workshop ICOOOLPS'2006 at ECOOP'06
Venue: arXiv cs.PF 2007
Year: 2007

ICOOOLPS'2006 was the first edition of ECOOP-ICOOOLPS workshop. It intended to bring researchers and practitioners both from academia and industry together, with a spirit of openness, to try and identify and begin to address the numerous and very varied issues of optimization. This succeeded, as can be seen from the papers, the attendance and the liveliness of the discussions that took place during and after the workshop, not to mention a few new cooperations or postdoctoral contracts. The 22 talented people from different groups who participated were unanimous to appreciate this first edition and recommend that ICOOOLPS be continued next year. A community is thus beginning to form, and should be reinforced by a second edition next year, with all the improvements this first edition made emerge.
Automatic Methods for Analyzing Non-Repudiation Protocols with an Active Intruder
Venue: arXiv cs.LO 2007
Year: 2007

Non-repudiation protocols have an important role in many areas where secured transactions with proofs of participation are necessary. Formal methods are clever and without error, therefore using them for verifying such protocols is crucial. In this purpose, we show how to partially represent non-repudiation as a combination of authentications on the Fair Zhou-Gollmann protocol. After discussing its limits, we define a new method based on the handling of the knowledge of protocol participants. This method is very general and is of natural use, as it consists in adding simple annotations, like for authentication problems. The method is very easy to implement in tools able to handle participants knowledge. We have implemented it in the AVISPA Tool and analyzed the optimistic Cederquist-Corin- Dashti protocol, discovering two unknown attacks. This extension of the AVISPA Tool for handling non-repudiation opens a highway to the specification of many other properties, without any more change in the tool itself.
On the Capacity of Interference Channels with One Cooperating Transmitter
Venue: arXiv cs.IT 2007
Year: 2007

Inner and outer bounds are established on the capacity region of two-sender, two-receiver interference channels where one transmitter knows both messages. The transmitter with extra knowledge is referred to as being cognitive. The inner bound is based on strategies that generalize prior work, and include rate-splitting, Gel'fand-Pinsker coding and cooperative transmission. A general outer bound is based on the Nair-El Gamal outer bound for broadcast channels. A simpler bound is presented for the case in which one of the decoders can decode both messages. The bounds are evaluated and compared for Gaussian channels.
A Note on Comparison of Error Correction Codes
Venue: arXiv cs.IT 2007
Year: 2007

Use of an error correction code in a given transmission channel can be regarded as the statistical experiment. Therefore, powerful results from the theory of comparison of experiments can be applied to compare the performances of different error correction codes. We present results on the comparison of block error correction codes using the representation of error correction code as a linear experiment. In this case the code comparison is based on the Loewner matrix ordering of respective code matrices. Next, we demonstrate the bit-error rate code performance comparison based on the representation of the codes as dichotomies, in which case the comparison is based on the matrix majorization ordering of their respective equivalent code matrices.
Optimized Design of Survivable MPLS over Optical Transport Networks. Optical Switching and Networking
Venue: arXiv cs.NI 2007
Year: 2007

In this paper we study different options for the survivability implementation in MPLS over Optical Transport Networks in terms of network resource usage and configuration cost. We investigate two approaches to the survivability deployment: single layer and multilayer survivability and present various methods for spare capacity allocation (SCA) to reroute disrupted traffic. The comparative analysis shows the influence of the traffic granularity on the survivability cost: for high bandwidth LSPs, close to the optical channel capacity, the multilayer survivability outperforms the single layer one, whereas for low bandwidth LSPs the single layer survivability is more cost-efficient. For the multilayer survivability we demonstrate that by mapping efficiently the spare capacity of the MPLS layer onto the resources of the optical layer one can achieve up to 22% savings in the total configuration cost and up to 37% in the optical layer cost. Further savings (up to 9 %) in the wavelength use can be obtained with the integrated approach to network configuration over the sequential one, however, at the increase in the optimization problem complexity. These results are based on a cost model with actual technology pricing and were obtained for networks targeted to a nationwide coverage.
Hardware Support for Arbitrarily Complex Loop Structures in Embedded Applications
Venue: arXiv cs.AR 2007
Year: 2007

In this paper, the program control unit of an embedded RISC processor is enhanced with a novel zero-overhead loop controller (ZOLC) supporting arbitrary loop structures with multiple-entry/exit nodes. The ZOLC has been incorporated to an open RISC processor core to evaluate the performance of the proposed unit for alternative configurations of the selected processor. It is proven that speed improvements of 8.4% to 48.2% are feasible for the used benchmarks.
UML 2.0 - Overview and Perspectives in SoC Design
Venue: arXiv cs.SE 2007
Year: 2007

The design productivity gap requires more efficient design methods. Software systems have faced the same challenge and seem to have mastered it with the introduction of more abstract design methods. The UML has become the standard for software systems modeling and thus the foundation of new design methods. Although the UML is defined as a general purpose modeling language, its application to hardware and hardware/software codesign is very limited. In order to successfully apply the UML at these fields, it is essential to understand its capabilities and to map it to a new domain.
Cycle Accurate Binary Translation for Simulation Acceleration in Rapid Prototyping of SoCs
Venue: arXiv cs.AR 2007
Year: 2007

In this paper, the application of a cycle accurate binary translator for rapid prototyping of SoCs will be presented. This translator generates code to run on a rapid prototyping system consisting of a VLIW processor and FPGAs. The generated code is annotated with information that triggers cycle generation for the hardware in parallel to the execution of the translated program. The VLIW processor executes the translated program whereas the FPGAs contain the hardware for the parallel cycle generation and the bus interface that adapts the bus of the VLIW processor to the SoC bus of the emulated processor core.
Locality-Aware Process Scheduling for Embedded MPSoCs
Venue: arXiv cs.AR 2007
Year: 2007

Utilizing on-chip caches in embedded multiprocessor-system-on-a-chip (MPSoC) based systems is critical from both performance and power perspectives. While most of the prior work that targets at optimizing cache behavior are performed at hardware and compilation levels, operating system (OS) can also play major role as it sees the global access pattern information across applications. This paper proposes a cache-conscious OS process scheduling strategy based on data reuse. The proposed scheduler implements two complementary approaches. First, the processes that do not share any data between them are scheduled at different cores if it is possible to do so. Second, the processes that could not be executed at the same time (due to dependences) but share data among each other are mapped to the same processor core so that they share the cache contents. Our experimental results using this new data locality aware OS scheduling strategy are promising, and show significant improvements in task completion times.
A Fast Diagnosis Scheme for Distributed Small Embedded SRAMs
Venue: arXiv cs.AR 2007
Year: 2007

This paper proposes a diagnosis scheme aimed at reducing diagnosis time of distributed small embedded SRAMs (e-SRAMs). This scheme improves the one proposed in [A parallel built-in self-diagnostic method for embedded memory buffers, A parallel built-in self-diagnostic method for embedded memory arrays]. The improvements are mainly two-fold. On one hand, the diagnosis of time-consuming Data Retention Faults (DRFs), which is neglected by the diagnosis architecture in [A parallel built-in self-diagnostic method for embedded memory buffers, A parallel built-in self-diagnostic method for embedded memory arrays], is now considered and performed via a DFT technique referred to as the "No Write Recovery Test Mode (NWRTM)". On the other hand, a pair comprising a Serial to Parallel Converter (SPC) and a Parallel to Serial Converter (PSC) is utilized to replace the bi-directional serial interface, to avoid the problems of serial fault masking and defect rate dependent diagnosis. Results from our evaluations show that the proposed diagnosis scheme achieves an increased diagnosis coverage and reduces diagnosis time compared to those obtained in [A parallel built-in self-diagnostic method for embedded memory buffers, A parallel built-in self-diagnostic method for embedded memory arrays], with neglectable extra area cost.