OpenRaiser/Intern-Atlas huggingface dataset:
Exact recoverability from dense corrupted observations via $L_1$ minimization
Venue: arXiv cs.IT 2011
Year: 2011

This paper confirms a surprising phenomenon first observed by Wright \textit{et al.} \cite{WYGSM_Face_2009_J} \cite{WM_denseError_2010_J} under different setting: given $m$ highly corrupted measurements $y = A_{Ω\bullet} x^{\star} + e^{\star}$, where $A_{Ω\bullet}$ is a submatrix whose rows are selected uniformly at random from rows of an orthogonal matrix $A$ and $e^{\star}$ is an unknown sparse error vector whose nonzero entries may be unbounded, we show that with high probability $\ell_1$-minimization can recover the sparse signal of interest $x^{\star}$ exactly from only $m = C μ^2 k (\log n)^2$ where $k$ is the number of nonzero components of $x^{\star}$ and $μ= n \max_{ij} A_{ij}^2$, even if nearly 100% of the measurements are corrupted. We further guarantee that stable recovery is possible when measurements are polluted by both gross sparse and small dense errors: $y = A_{Ω\bullet} x^{\star} + e^{\star}+ ν$ where $ν$ is the small dense noise with bounded energy. Numerous simulation results under various settings are also presented to verify the validity of the theory as well as to illustrate the promising potential of the proposed framework.
Applying static code analysis to firewall policies for the purpose of anomaly detection
Venue: arXiv cs.PL 2011
Year: 2011

Treating modern firewall policy languages as imperative, special purpose programming languages, in this article we will try to apply static code analysis techniques for the purpose of anomaly detection. We will first abstract a policy in common firewall policy language into an intermediate language, and then we will try to apply anomaly detection algorithms to it. The contributions made by this work are: 1. An analysis of various control flow instructions in popular firewall policy languages 2. Introduction of an intermediate firewall policy language, with emphasis on control flow constructs. 3. Application of \textit{Static Code Analysis} to detect anomalies in firewall policy, expressed in intermediate firewall policy language. 4. Sample implementation of \textit{Static Code Analysis} of firewall policies, expressed in our abstract language using Datalog language.
Ensuring the boundedness of the core of games with restricted cooperation
Venue: arXiv cs.GT 2011
Year: 2011

The core of a cooperative game on a set of players $N$ is one of the most popular concept of solution. When cooperation is restricted (feasible coalitions form a subcollection $\cF$ of $2^N$), the core may become unbounded, which makes it usage questionable in practice. Our proposal is to make the core bounded by turning some of the inequalities defining the core into equalities (additional efficiency constraints). We address the following mathematical problem: can we find a minimal set of inequalities in the core such that, if turned into equalities, the core becomes bounded? The new core obtained is called the restricted core. We completely solve the question when $\cF$ is a distributive lattice, introducing also the notion of restricted Weber set. We show that the case of regular set systems amounts more or less to the case of distributive lattices. We also study the case of weakly union-closed systems and give some results for the general case.
Stable Parallel Looped Systems -- A New Theoretical Framework for the Evolution of Order
Venue: arXiv cs.NE 2011
Year: 2011

The objective of the paper is to identify laws and mechanisms that allow the creation of more order from disorder using natural means i.e., without the help of conscious beings. While this is not possible for the collection of all dynamical systems as it violates the second law of thermodynamics, I show that this is possible within a special subset called stable parallel looped (SPL) dynamical systems. I identify a new infinite family of physical and chemical dynamical SPL systems, which are (a) easy to create naturally and (b) easy to merge, link and combine to create dynamical systems of any specified complexity. Within SPL systems, I propose a special collection of designs called active material-energy looped systems using which it is possible to generate large-scale ordered chemical networks, like the metabolic networks, in a reliable, repeatable, iterative and natural manner. The resulting SPL systems provide a new theoretical framework for the problem of origin of life.
Generating Probability Distributions using Multivalued Stochastic Relay Circuits
Venue: arXiv cs.IT 2011
Year: 2011

The problem of random number generation dates back to von Neumann's work in 1951. Since then, many algorithms have been developed for generating unbiased bits from complex correlated sources as well as for generating arbitrary distributions from unbiased bits. An equally interesting, but less studied aspect is the structural component of random number generation as opposed to the algorithmic aspect. That is, given a network structure imposed by nature or physical devices, how can we build networks that generate arbitrary probability distributions in an optimal way? In this paper, we study the generation of arbitrary probability distributions in multivalued relay circuits, a generalization in which relays can take on any of N states and the logical 'and' and 'or' are replaced with 'min' and 'max' respectively. Previous work was done on two-state relays. We generalize these results, describing a duality property and networks that generate arbitrary rational probability distributions. We prove that these networks are robust to errors and design a universal probability generator which takes input bits and outputs arbitrary binary probability distributions.
Security Embedding Codes
Venue: arXiv cs.IT 2011
Year: 2011

This paper considers the problem of simultaneously communicating two messages, a high-security message and a low-security message, to a legitimate receiver, referred to as the security embedding problem. An information-theoretic formulation of the problem is presented. A coding scheme that combines rate splitting, superposition coding, nested binning and channel prefixing is considered and is shown to achieve the secrecy capacity region of the channel in several scenarios. Specifying these results to both scalar and independent parallel Gaussian channels (under an average individual per-subchannel power constraint), it is shown that the high-security message can be embedded into the low-security message at full rate (as if the low-security message does not exist) without incurring any loss on the overall rate of communication (as if both messages are low-security messages). Extensions to the wiretap channel II setting of Ozarow and Wyner are also considered, where it is shown that "perfect" security embedding can be achieved by an encoder that uses a two-level coset code.
Joint Decoding of LDPC Codes and Finite-State Channels via Linear-Programming
Venue: arXiv cs.IT 2011
Year: 2011

This paper considers the joint-decoding (JD) problem for finite-state channels (FSCs) and low-density parity-check (LDPC) codes. In the first part, the linear-programming (LP) decoder for binary linear codes is extended to JD of binary-input FSCs. In particular, we provide a rigorous definition of LP joint-decoding pseudo-codewords (JD-PCWs) that enables evaluation of the pairwise error probability between codewords and JD-PCWs in AWGN. This leads naturally to a provable upper bound on decoder failure probability. If the channel is a finite-state intersymbol interference channel, then the joint LP decoder also has the maximum-likelihood (ML) certificate property and all integer-valued solutions are codewords. In this case, the performance loss relative to ML decoding can be explained completely by fractional-valued JD-PCWs. After deriving these results, we discovered some elements were equivalent to earlier work by Flanagan on LP receivers. In the second part, we develop an efficient iterative solver for the joint LP decoder discussed in the first part. In particular, we extend the approach of iterative approximate LP decoding, proposed by Vontobel and Koetter and analyzed by Burshtein, to this problem. By taking advantage of the dual-domain structure of the JD-LP, we obtain a convergent iterative algorithm for joint LP decoding whose structure is similar to BCJR-based turbo equalization (TE). The result is a joint iterative decoder whose per-iteration complexity is similar to that of TE but whose performance is similar to that of joint LP decoding. The main advantage of this decoder is that it appears to provide the predictability of joint LP decoding and superior performance with the computational complexity of TE. One expected application is coding for magnetic storage where the required block-error rate is extremely low and system performance is difficult to verify by simulation.
Peer-to-Peer Multimedia Sharing based on Social Norms
Venue: arXiv cs.MM 2011
Year: 2011

Empirical data shows that in the absence of incentives, a peer participating in a Peer-to-Peer (P2P) network wishes to free-riding. Most solutions for providing incentives in P2P networks are based on direct reciprocity, which are not appropriate for most P2P multimedia sharing networks due to the unique features exhibited by such networks: large populations of anonymous agents interacting infrequently, asymmetric interests of peers, network errors, and multiple concurrent transactions. In this paper, we design and rigorously analyze a new family of incentive protocols that utilizes indirect reciprocity which is based on the design of efficient social norms. In the proposed P2P protocols, the social norms consist of a social strategy, which represents the rule prescribing to the peers when they should or should not provide content to other peers, and a reputation scheme, which rewards or punishes peers depending on whether they comply or not with the social strategy. We first define the concept of a sustainable social norm, under which no peer has an incentive to deviate. We then formulate the problem of designing optimal social norms, which selects the social norm that maximizes the network performance among all sustainable social norms. Hence, we prove that it becomes in the self-interest of peers to contribute their content to the network rather than to free-ride. We also investigate the impact of various punishment schemes on the social welfare as well as how should the optimal social norms be designed if altruistic and malicious peers are active in the network. Our results show that optimal social norms are capable of providing significant improvements in the sharing efficiency of multimedia P2P networks.
Multiuser Diversity in Downlink Channels: When does the Feedback Cost Outweigh the Spectral Efficiency Gain?
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we perform a cost-benefit analysis of multiuser diversity in single antenna broadcast channels. It is well known that multiuser diversity can be beneficial but there is a significant cost associated with acquiring instantaneous CSI. We perform a cost-benefit analysis of multiuser diversity for 2 types of CSI feedback methods, dedicated feedback and SNR dependent feedback, quantifying how many users should feedback CSI from a net throughput perspective. Dedicated feedback, in which orthogonal resources are allocated to each user, has significant feedback cost and this limits the amount of available multiuser diversity that can be used. SNR dependent feedback method, in which only users with SNR above a threshold attempt to feedback, has relatively much smaller feedback cost and this allows for all of the available multiuser diversity to be used. Next, we study the effect of single user multiantenna techniques, which reduce the SNR variation, on the number of feedback users neccessary. It is seen that a broadcast channel using single user multiantenna techniques should reduce the number of feedback users with the spatial dimension.
ATC Taskload Inherent to the Geometry of Stochastic 4-D Trajectory Flows with Flight Technical Errors
Venue: arXiv cs.SY 2011
Year: 2011

A method to quantify the probabilistic controller taskload inherent to maintaining aircraft adherence to 4-D trajectories within flow corridors is presented. An Ornstein-Uhlenbeck model of the aircraft motion and a Poisson model of the flow scheduling are introduced along with reasonable numerical values of the model parameters. Analytic expressions are derived for the taskload probability density functions for basic functional elements of the flow structure. Monte Carlo simulations are performed for these basic functional elements and the controller taskload probabilities are exhibited.
Applying weighted PageRank to author citation networks
Venue: arXiv cs.DL 2011
Year: 2011

This paper aims to identify whether different weighted PageRank algorithms can be applied to author citation networks to measure the popularity and prestige of a scholar from a citation perspective. Information Retrieval (IR) was selected as a test field and data from 1956-2008 were collected from Web of Science (WOS). Weighted PageRank with citation and publication as weighted vectors were calculated on author citation networks. The results indicate that both popularity rank and prestige rank were highly correlated with the weighted PageRank. Principal Component Analysis (PCA) was conducted to detect relationships among these different measures. For capturing prize winners within the IR field, prestige rank outperformed all the other measures.
Proposing LT based Search in PDM Systems for Better Information Retrieval
Venue: arXiv cs.IR 2011
Year: 2011

PDM Systems contain and manage heavy amount of data but the search mechanism of most of the systems is not intelligent which can process user"s natural language based queries to extract desired information. Currently available search mechanisms in almost all of the PDM systems are not very efficient and based on old ways of searching information by entering the relevant information to the respective fields of search forms to find out some specific information from attached repositories. Targeting this issue, a thorough research was conducted in fields of PDM Systems and Language Technology. Concerning the PDM System, conducted research provides the information about PDM and PDM Systems in detail. Concerning the field of Language Technology, helps in implementing a search mechanism for PDM Systems to search user"s needed information by analyzing user"s natural language based requests. The accomplished goal of this research was to support the field of PDM with a new proposition of a conceptual model for the implementation of natural language based search. The proposed conceptual model is successfully designed and partially implementation in the form of a prototype. Describing the proposition in detail the main concept, implementation designs and developed prototype of proposed approach is discussed in this paper. Implemented prototype is compared with respective functions of existing PDM systems .i.e., Windchill and CIM to evaluate its effectiveness against targeted challenges.
Generalized companion matrix for approximate GCD
Venue: arXiv cs.SC 2011
Year: 2011

We study a variant of the univariate approximate GCD problem, where the coefficients of one polynomial f(x)are known exactly, whereas the coefficients of the second polynomial g(x)may be perturbed. Our approach relies on the properties of the matrix which describes the operator of multiplication by gin the quotient ring C[x]=(f). In particular, the structure of the null space of the multiplication matrix contains all the essential information about GCD(f; g). Moreover, the multiplication matrix exhibits a displacement structure that allows us to design a fast algorithm for approximate GCD computation with quadratic complexity w.r.t. polynomial degrees.
The structure of the Arts & Humanities Citation Index: A mapping on the basis of aggregated citations among 1,157 journals
Venue: arXiv cs.DL 2011
Year: 2011

Using the Arts & Humanities Citation Index (A&HCI) 2008, we apply mapping techniques previously developed for mapping journal structures in the Science and Social Science Citation Indices. Citation relations among the 110,718 records were aggregated at the level of 1,157 journals specific to the A&HCI, and the journal structures are questioned on whether a cognitive structure can be reconstructed and visualized. Both cosine-normalization (bottom up) and factor analysis (top down) suggest a division into approximately twelve subsets. The relations among these subsets are explored using various visualization techniques. However, we were not able to retrieve this structure using the ISI Subject Categories, including the 25 categories which are specific to the A&HCI. We discuss options for validation such as against the categories of the Humanities Indicators of the American Academy of Arts and Sciences, the panel structure of the European Reference Index for the Humanities (ERIH), and compare our results with the curriculum organization of the Humanities Section of the College of Letters and Sciences of UCLA as an example of institutional organization.
Distributed Uplink Resource Allocation in Cognitive Radio Networks -- Part I: Equilibria and Algorithms for Power Allocation
Venue: arXiv cs.IT 2011
Year: 2011

Spectrum management has been identified as a crucial step towards enabling the technology of a cognitive radio network (CRN). Most of the current works dealing with spectrum management in the CRN focus on a single task of the problem, e.g., spectrum sensing, spectrum decision, spectrum sharing or spectrum mobility. In this two-part paper, we argue that for certain network configurations, jointly performing several tasks of the spectrum management improves the spectrum efficiency. Specifically, our aim is to study the uplink resource management problem in a CRN where there exist multiple cognitive users (CUs) and access points (APs). The CUs, in order to maximize their uplink transmission rates, have to associate to a suitable AP (spectrum decision), and to share the channels used by this AP with other CUs (spectrum sharing). These tasks are clearly interdependent, and the problem of how they should be carried out efficiently and in a distributed manner is still open in the literature.
What Stops Social Epidemics?
Venue: arXiv cs.SI 2011
Year: 2011

Theoretical progress in understanding the dynamics of spreading processes on graphs suggests the existence of an epidemic threshold below which no epidemics form and above which epidemics spread to a significant fraction of the graph. We have observed information cascades on the social media site Digg that spread fast enough for one initial spreader to infect hundreds of people, yet end up affecting only 0.1% of the entire network. We find that two effects, previously studied in isolation, combine cooperatively to drastically limit the final size of cascades on Digg. First, because of the highly clustered structure of the Digg network, most people who are aware of a story have been exposed to it via multiple friends. This structure lowers the epidemic threshold while moderately slowing the overall growth of cascades. In addition, we find that the mechanism for social contagion on Digg points to a fundamental difference between information spread and other contagion processes: despite multiple opportunities for infection within a social group, people are less likely to become spreaders of information with repeated exposure. The consequences of this mechanism become more pronounced for more clustered graphs. Ultimately, this effect severely curtails the size of social epidemics on Digg.
Parsing Reflective Grammars
Venue: arXiv cs.PL 2011
Year: 2011

Existing technology can parse arbitrary context-free grammars, but only a single, static grammar per input. In order to support more powerful syntax-extension systems, we propose reflective grammars, which can modify their own syntax during parsing. We demonstrate and prove the correctness of an algorithm for parsing reflective grammars. The algorithm is based on Earley's algorithm, and we prove that it performs asymptotically no worse than Earley's algorithm on ordinary context-free grammars.
Synthesis of Mechanism for single- and hybrid-tasks using Differential Evolution
Venue: arXiv cs.CE 2011
Year: 2011

The optimal dimensional synthesis for planar mechanisms using differential evolution (DE) is demonstrated. Four examples are included: in the first case, the synthesis of a mechanism for hybrid-tasks, considering path generation, function generation, and motion generation, is carried out. The second and third cases pertain to path generation, with and without prescribed timing. Finally, the synthesis of an Ackerman mechanism is reported. Order defect problem is solved by manipulating individuals instead of penalizing or discretizing the search space for the parameters. A technique that consists in applying a transformation in order to satisfy the Grashof and crank conditions to generate an initial elitist population is introduced. As a result, the evolutionary algorithm increases its efficiency.
Noise-based information processing: Noise-based logic and computing: what do we have so far?
Venue: arXiv cs.ET 2011
Year: 2011

We briefly introduce noise-based logic. After describing the main motivations we outline classical, instantaneous (squeezed and non-squeezed), continuum, spike and random-telegraph-signal based schemes with applications such as circuits that emulate the brain functioning and string verification via a slow communication channel.
The best possible upper bound on the probability of undetected error for linear codes of full support
Venue: arXiv cs.IT 2011
Year: 2011

There is a known best possible upper bound on the probability of undetected error for linear codes. The $[n,k;q]$ codes with probability of undetected error meeting the bound have support of size $k$ only. In this note, linear codes of full support ($=n$) are studied. A best possible upper bound on the probability of undetected error for such codes is given, and the codes with probability of undetected error meeting this bound are characterized.
Universal Learning Theory
Venue: arXiv cs.LG 2011
Year: 2011

This encyclopedic article gives a mini-introduction into the theory of universal learning, founded by Ray Solomonoff in the 1960s and significantly developed and extended in the last decade. It explains the spirit of universal learning, but necessarily glosses over technical subtleties.
A Framework Based Approach for the Development of Web Based Applications
Venue: arXiv cs.CY 2011
Year: 2011

The sole goal of E-Governance is to allow interaction of government with their citizens in a comfortable & transparent manner. Uniqueness of J2EE makes it a perfect technology for development of any online portal. These involve constancy, easy to replant, construct speedily etc. In this paper we present a procedural approach to develop a web application using the J2EE Struts Framework.
Co-ordering and Type 2 co-ordering
Venue: arXiv cs.LO 2011
Year: 2011

In [arXiv:1006.4939] the enumeration order reducibility is defined on natural numbers. For a c.e. set A, [A] denoted the class of all subsets of natural numbers which are co-order with A. In definition 5 we redefine co-ordering for rational numbers. One of the main questions there, was: "For a specific c.e. set A, consider set of all enumerations of it which is generated by some Turing machine {TM_A} what are the associated order types in [A]?" Here, we propose the same question for rational numbers, and we try to investigate the varieties of c.e. sets on Q. The theories here are hold for R_c and we could repeat the same theories in this domain, in a parallel way.