OpenRaiser/Intern-Atlas huggingface dataset:
Worst-case Throughput Analysis for Parametric Rate and Parametric Actor Execution Time Scenario-Aware Dataflow Graphs
Venue: arXiv cs.PL 2014
Year: 2014

Scenario-aware dataflow (SADF) is a prominent tool for modeling and analysis of dynamic embedded dataflow applications. In SADF the application is represented as a finite collection of synchronous dataflow (SDF) graphs, each of which represents one possible application behaviour or scenario. A finite state machine (FSM) specifies the possible orders of scenario occurrences. The SADF model renders the tightest possible performance guarantees, but is limited by its finiteness. This means that from a practical point of view, it can only handle dynamic dataflow applications that are characterized by a reasonably sized set of possible behaviours or scenarios. In this paper we remove this limitation for a class of SADF graphs by means of SADF model parametrization in terms of graph port rates and actor execution times. First, we formally define the semantics of the model relevant for throughput analysis based on (max,+) linear system theory and (max,+) automata. Second, by generalizing some of the existing results, we give the algorithms for worst-case throughput analysis of parametric rate and parametric actor execution time acyclic SADF graphs with a fully connected, possibly infinite state transition system. Third, we demonstrate our approach on a few realistic applications from digital signal processing (DSP) domain mapped onto an embedded multi-processor architecture.
Quantization for Uplink Transmissions in Two-tier Networks with Femtocells
Venue: arXiv cs.NI 2014
Year: 2014

We propose two novel schemes to level up the sum--rate for a two-tier network with femtocell where the backhaul uplink and downlink connecting the Base Stations have limited capacity. The backhaul links are exploited to transport the information in order to improve the decoding of the macrocell and femtocell messages. In the first scheme, Quantize-and-Forward, the Femto Base Station (FBS) quantizes what it receives and forwards it to the Macro Base Station (MBS). Two quantization methods are considered: Elementary Quantization and Wyner-Ziv Quantization. In the second scheme, called Decode-and-Forward with Quantized Side Information (DFQSI) to be distinguished with the considered conventional Decode-and-Forward (DF) scheme. The DFQSI scheme exploits the backhaul downlink to quantize and send the information about the message in the macrocell to the FBS to help it better decode the message, cancel it and decode the message in the femtocell. The results show that there are interesting scenarios in which the proposed techniques offer considerable gains in terms of maximal sum rate and max minimal rate.
Metal-Gated Junctionless Nanowire Transistors
Venue: arXiv cs.ET 2014
Year: 2014

Junctionless Nanowire Field-Effect Transistors (JNFETs), where the channel region is uniformly doped without the need for source-channel and drain-channel junctions or lateral doping abruptness, are considered an attractive alternative to conventional CMOS FETs. Previous theoretical and experimental works [1][2] on JNFETs have considered polysilicon gates and silicon-dioxide dielectric. However, with further scaling, JNFETs will suffer from deleterious effects of doped polysilicon such as high resistance, additional capacitance due to gate-oxide interface depletion, and incompatibility with high-k dielectrics[3][4]. In this paper, novel metal- gated high-k JNFETs are investigated through detailed process and device simulations. These MJNFETs are also ideally suited for new types of nano-architectures such as N3ASICs [5] which utilize regular nanowire arrays with limited customization. In such nano- systems, the simplified device geometry in conjunction with a single-type FET circuit style [6] would imply that logic arrays could be patterned out of pre-doped SOI wafers without the need for any additional ion implantation.
Scaling laws for molecular communication
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we investigate information-theoretic scaling laws, independent from communication strategies, for point-to-point molecular communication, where it sends/receives information-encoded molecules between nanomachines. Since the Shannon capacity for this is still an open problem, we first derive an asymptotic order in a single coordinate, i.e., i) scaling time with constant number of molecules $m$ and ii) scaling molecules with constant time $t$. For a single coordinate case, we show that the asymptotic scaling is logarithmic in either coordinate, i.e., $Θ(\log t)$ and $Θ(\log m)$, respectively. We also study asymptotic behavior of scaling in both time and molecules and show that, if molecules and time are proportional to each other, then the asymptotic scaling is linear, i.e., $Θ(t)=Θ(m)$.
EEG Spatial Decoding and Classification with Logit Shrinkage Regularized Directed Information Assessment (L-SODA)
Venue: arXiv cs.IT 2014
Year: 2014

There is an increasing interest in studying the neural interaction mechanisms behind patterns of cognitive brain activity. This paper proposes a new approach to infer such interaction mechanisms from electroencephalographic (EEG) data using a new estimator of directed information (DI) called logit shrinkage optimized directed information assessment (L-SODA). Unlike previous directed information measures applied to neural decoding, L-SODA uses shrinkage regularization on multinomial logistic regression to deal with the high dimensionality of multi-channel EEG signals and the small sizes of many real-world datasets. It is designed to make few a priori assumptions and can handle both non-linear and non-Gaussian flows among electrodes. Our L-SODA estimator of the DI is accompanied by robust statistical confidence intervals on the true DI that make it especially suitable for hypothesis testing on the information flow patterns. We evaluate our work in the context of two different problems where interaction localization is used to determine highly interactive areas for EEG signals spatially and temporally. First, by mapping the areas that have high DI into Brodmann area, we identify that the areas with high DI are associated with motor-related functions. We demonstrate that L-SODA provides better accuracy for neural decoding of EEG signals as compared to several state-of-the-art approaches on the Brain Computer Interface (BCI) EEG motor activity dataset. Second, the proposed L-SODA estimator is evaluated on the CHB-MIT Scalp EEG database. We demonstrate that compared to the state-of-the-art approaches, the proposed method provides better performance in detecting the epileptic seizure.
Optimal Multiuser Transmit Beamforming: A Difficult Problem with a Simple Solution Structure
Venue: arXiv cs.IT 2014
Year: 2014

Transmit beamforming is a versatile technique for signal transmission from an array of $N$ antennas to one or multiple users [1]. In wireless communications, the goal is to increase the signal power at the intended user and reduce interference to non-intended users. A high signal power is achieved by transmitting the same data signal from all antennas, but with different amplitudes and phases, such that the signal components add coherently at the user. Low interference is accomplished by making the signal components add destructively at non-intended users. This corresponds mathematically to designing beamforming vectors (that describe the amplitudes and phases) to have large inner products with the vectors describing the intended channels and small inner products with non-intended user channels. While it is fairly easy to design a beamforming vector that maximizes the signal power at the intended user, it is difficult to strike a perfect balance between maximizing the signal power and minimizing the interference leakage. In fact, the optimization of multiuser transmit beamforming is generally a nondeterministic polynomial-time (NP) hard problem [2]. Nevertheless, this lecture shows that the optimal transmit beamforming has a simple structure with very intuitive properties and interpretations. This structure provides a theoretical foundation for practical low-complexity beamforming schemes. (See this lecture note for the complete abstract/introduction)
Cellular Automata and Its Applications in Bioinformatics: A Review
Venue: arXiv cs.CE 2014
Year: 2014

This paper aims at providing a survey on the problems that can be easily addressed by cellular automata in bioinformatics. Some of the authors have proposed algorithms for addressing some problems in bioinformatics but the application of cellular automata in bioinformatics is a virgin field in research. None of the researchers has tried to relate the major problems in bioinformatics and find a common solution. Extensive literature surveys were conducted. We have considered some papers in various journals and conferences for conduct of our research. This paper provides intuition towards relating various problems in bioinformatics logically and tries to attain a common frame work for addressing the same.
Self-protection and self-healing in the context of cognitive radio
Venue: arXiv cs.NI 2014
Year: 2014

Cognitive Radio (CR) operates in different fields as varied, one of these is cognitive radio networks. In this paper, we propose a new approach used CR, which aims to manage potential failures of computer systems and applications through the introduction of two aspects of autonomous networks to make systems capable of managing themselves with minimum human intervention.
Modeling contaminant intrusion in water distribution networks based on D numbers
Venue: arXiv cs.AI 2014
Year: 2014

Efficient modeling on uncertain information plays an important role in estimating the risk of contaminant intrusion in water distribution networks. Dempster-Shafer evidence theory is one of the most commonly used methods. However, the Dempster-Shafer evidence theory has some hypotheses including the exclusive property of the elements in the frame of discernment, which may not be consistent with the real world. In this paper, based on a more effective representation of uncertainty, called D numbers, a new method that allows the elements in the frame of discernment to be non-exclusive is proposed. To demonstrate the efficiency of the proposed method, we apply it to the water distribution networks to estimate the risk of contaminant intrusion.
Waterfilling Theorems in the Time-Frequency Plane for the Heat Channel and a Related Source
Venue: arXiv cs.IT 2014
Year: 2014

The capacity of the heat channel, a linear time-varying (LTV) filter with additive white Gaussian noise (AWGN), is characterized by waterfilling in the time-frequency plane. Similarly, the rate distortion function for a related nonstationary source is characterized by reverse waterfilling in the time-frequency plane. The source is formed by the white Gaussian noise response of the same LTV filter as before. The proofs of both waterfilling theorems rely on a specific Szego theorem for a positive definite operator associated with the filter. An essentially self-contained proof of the Szego theorem is given. The waterfilling theorems compare well with classical results of Gallager and Berger. In case of the nonstationary source it is observed that the part of the classical power spectral density (PSD) is taken by the Wigner-Ville spectrum (WVS).
Privacy-Preserving Social Network with Multigrained and Multilevel Access Control
Venue: arXiv cs.SI 2014
Year: 2014

I study two privacy-preserving social network graphs to dis- close the types of relationships of connecting edges and provide flexible multigrained access control. To create such graphs, my schemes employ the concept of secretaries and types of relationships. It is significantly more efficient than those that using expensive cryptographic primitives. I also show how these schemes can be used for multigrained access control with various options. In addition, I describe how much these schemes are resilient to infer the types of connecting edges.
Thermodynamic Hypothesis as Social Choice: An Impossibility Theorem for Protein Folding
Venue: arXiv cs.CE 2014
Year: 2014

Protein Folding is concerned with the reasons and mechanism behind a protein's tertiary structure. The thermodynamic hypothesis of Anfinsen postulates an universal energy function (UEF) characterizing the tertiary structure, defined consistently across proteins, in terms of their aminoacid sequence. We consider the approach of examining multiple protein structure descriptors in the PDB (Protein Data Bank), and infer individual preferences, biases favoring particular classes of aminoacid interactions in each of them, later aggregating these individual preferences into a global preference. This 2-step process would ideally expose intrinsic biases on classes of aminoacid interactions in the UEF itself. The intuition is that any intrinsic biases in the UEF are expressed within each protein in a specific manner consistent with its specific aminoacid sequence, size, and fold (consistently with Anfinsen's thermodynamic hypothesis), making a 1-step, holistic aggregation less desirable. Our intention is to illustrate how some impossibility results from voting theory would apply in this setting, being possibly applicable to other protein folding problems as well. We consider concepts and results from voting theory and unveil methodological difficulties for the approach mentioned above. With our observations, we intend to highlight how key theoretical barriers, already exposed by economists, can be relevant for the development of new methods, new algorithms, for problems related to protein folding.
Information Flow Decomposition in Feedback Systems: General Case Study
Venue: arXiv cs.IT 2014
Year: 2014

We derive three fundamental decompositions on relevant information quantities in feedback systems. The feedback systems considered in this paper are only restricted to be causal in time domain and the channels are allowed to be subject to arbitrary distribution. These decompositions comprise the well-known mutual information and the directed information, and indicate a law of conservation of information flows in the closed-loop network.
Expectations or Guarantees? I Want It All! A crossroad between games and MDPs
Venue: arXiv cs.GT 2014
Year: 2014

When reasoning about the strategic capabilities of an agent, it is important to consider the nature of its adversaries. In the particular context of controller synthesis for quantitative specifications, the usual problem is to devise a strategy for a reactive system which yields some desired performance, taking into account the possible impact of the environment of the system. There are at least two ways to look at this environment. In the classical analysis of two-player quantitative games, the environment is purely antagonistic and the problem is to provide strict performance guarantees. In Markov decision processes, the environment is seen as purely stochastic: the aim is then to optimize the expected payoff, with no guarantee on individual outcomes. In this expository work, we report on recent results introducing the beyond worst-case synthesis problem, which is to construct strategies that guarantee some quantitative requirement in the worst-case while providing an higher expected value against a particular stochastic model of the environment given as input. This problem is relevant to produce system controllers that provide nice expected performance in the everyday situation while ensuring a strict (but relaxed) performance threshold even in the event of very bad (while unlikely) circumstances. It has been studied for both the mean-payoff and the shortest path quantitative measures.
Reasoning about Knowledge and Strategies: Epistemic Strategy Logic
Venue: arXiv cs.LO 2014
Year: 2014

In this paper we introduce Epistemic Strategy Logic (ESL), an extension of Strategy Logic with modal operators for individual knowledge. This enhanced framework allows us to represent explicitly and to reason about the knowledge agents have of their own and other agents' strategies. We provide a semantics to ESL in terms of epistemic concurrent game models, and consider the corresponding model checking problem. We show that the complexity of model checking ESL is not worse than (non-epistemic) Strategy Logic
A Resolution Prover for Coalition Logic
Venue: arXiv cs.LO 2014
Year: 2014

We present a prototype tool for automated reasoning for Coalition Logic, a non-normal modal logic that can be used for reasoning about cooperative agency. The theorem prover CLProver is based on recent work on a resolution-based calculus for Coalition Logic that operates on coalition problems, a normal form for Coalition Logic. We provide an overview of coalition problems and of the resolution-based calculus for Coalition Logic. We then give details of the implementation of CLProver and present the results for a comparison with an existing tableau-based solver.
Efficient Decomposition of Bimatrix Games (Extended Abstract)
Venue: arXiv cs.GT 2014
Year: 2014

Exploiting the algebraic structure of the set of bimatrix games, a divide-and-conquer algorithm for finding Nash equilibria is proposed. The algorithm is fixed-parameter tractable with the size of the largest irreducible component of a game as parameter. An implementation of the algorithm is shown to yield a significant performance increase on inputs with small parameters.
Automata Techniques for Epistemic Protocol Synthesis
Venue: arXiv cs.LO 2014
Year: 2014

In this work we aim at applying automata techniques to problems studied in Dynamic Epistemic Logic, such as epistemic planning. To do so, we first remark that repeatedly executing ad infinitum a propositional event model from an initial epistemic model yields a relational structure that can be finitely represented with automata. This correspondence, together with recent results on uniform strategies, allows us to give an alternative decidability proof of the epistemic planning problem for propositional events, with as by-products accurate upper-bounds on its time complexity, and the possibility to synthesize a finite word automaton that describes the set of all solution plans. In fact, using automata techniques enables us to solve a much more general problem, that we introduce and call epistemic protocol synthesis.
Map Route Ranking with Weighted Distance using Environmental Factors
Venue: arXiv cs.HC 2014
Year: 2014

When users search for the routes between two places using map based services, these services compute and provide the top candidate routes based on shortest geometric distances or ideal time consuming. However, other real factors like physical exertion and practical time consuming will influence user experience, and the environmental factors like steep slope and traffic jam that result in these real factors need to be considered. For example, when users travel on foot or by bicycle, if there are many steep slopes on the routes, it will be difficult or easy to be tired. In this paper, we propose an approach computing weighted distance considering these environmental factors. We rank the candidate route results generated by Google Map using elevation information. We integrate the elevation information in the route results to assist users to make decision. The solution can also be used in other scenarios that need to consider environmental factors.
Distributed Hypothesis Testing with Social Learning and Symmetric Fusion
Venue: arXiv cs.IT 2014
Year: 2014

We study the utility of social learning in a distributed detection model with agents sharing the same goal: a collective decision that optimizes an agreed upon criterion. We show that social learning is helpful in some cases but is provably futile (and thus essentially a distraction) in other cases. Specifically, we consider Bayesian binary hypothesis testing performed by a distributed detection and fusion system, where all decision-making agents have binary votes that carry equal weight. Decision-making agents in the team sequentially make local decisions based on their own private signals and all precedent local decisions. It is shown that the optimal decision rule is not affected by precedent local decisions when all agents observe conditionally independent and identically distributed private signals. Perfect Bayesian reasoning will cancel out all effects of social learning. When the agents observe private signals with different signal-to-noise ratios, social learning is again futile if the team decision is only approved by unanimity. Otherwise, social learning can strictly improve the team performance. Furthermore, the order in which agents make their decisions affects the team decision.
Compressed Sensing Bayes Risk Minimization for Under-determined Systems via Sphere Detection
Venue: arXiv cs.IT 2014
Year: 2014

The application of Compresses Sensing is a promising physical layer technology for the joint activity and data detection of signals. Detecting the activity pattern correctly has severe impact on the system performance and is therefore of major concern. In contrast to previous work, in this paper we optimize joint activity and data detection in under-determined systems by minimizing the Bayes-Risk for erroneous activity detection. We formulate a new Compressed Sensing Bayes-Risk detector which directly allows to influence error rates at the activity detection dynamically by a parameter that can be controlled at higher layers. We derive the detector for a general linear system and show that our detector outperforms classical Compressed Sensing approaches by investigating an overloaded CDMA system.
Parallel Support Vector Machines in Practice
Venue: arXiv cs.LG 2014
Year: 2014

In this paper, we evaluate the performance of various parallel optimization methods for Kernel Support Vector Machines on multicore CPUs and GPUs. In particular, we provide the first comparison of algorithms with explicit and implicit parallelization. Most existing parallel implementations for multi-core or GPU architectures are based on explicit parallelization of Sequential Minimal Optimization (SMO)---the programmers identified parallelizable components and hand-parallelized them, specifically tuned for a particular architecture. We compare these approaches with each other and with implicitly parallelized algorithms---where the algorithm is expressed such that most of the work is done within few iterations with large dense linear algebra operations. These can be computed with highly-optimized libraries, that are carefully parallelized for a large variety of parallel platforms. We highlight the advantages and disadvantages of both approaches and compare them on various benchmark data sets. We find an approximate implicitly parallel algorithm which is surprisingly efficient, permits a much simpler implementation, and leads to unprecedented speedups in SVM training.
Competitive Algorithms from Competitive Equilibria: Non-Clairvoyant Scheduling under Polyhedral Constraints
Venue: arXiv cs.DS 2014
Year: 2014

We introduce and study a general scheduling problem that we term the Packing Scheduling problem. In this problem, jobs can have different arrival times and sizes; a scheduler can process job $j$ at rate $x_j$, subject to arbitrary packing constraints over the set of rates ($\vec{x}$) of the outstanding jobs. The PSP framework captures a variety of scheduling problems, including the classical problems of unrelated machines scheduling, broadcast scheduling, and scheduling jobs of different parallelizability. It also captures scheduling constraints arising in diverse modern environments ranging from individual computer architectures to data centers. More concretely, PSP models multidimensional resource requirements and parallelizability, as well as network bandwidth requirements found in data center scheduling. In this paper, we design non-clairvoyant online algorithms for PSP and its special cases -- in this setting, the scheduler is unaware of the sizes of jobs. Our two main results are, 1) a constant competitive algorithm for minimizing total weighted completion time for PSP and 2)a scalable algorithm for minimizing the total flow-time on unrelated machines, which is a special case of PSP.