OpenRaiser/Intern-Atlas huggingface dataset:
Reasoning on Schemata of Formulae
Venue: arXiv cs.LO 2012
Year: 2012

A logic is presented for reasoning on iterated sequences of formulae over some given base language. The considered sequences, or "schemata", are defined inductively, on some algebraic structure (for instance the natural numbers, the lists, the trees etc.). A proof procedure is proposed to relate the satisfiability problem for schemata to that of finite disjunctions of base formulae. It is shown that this procedure is sound, complete and terminating, hence the basic computational properties of the base language can be carried over to schemata.
Image Restoration with Signal-dependent Camera Noise
Venue: arXiv cs.CV 2012
Year: 2012

This article describes a fast iterative algorithm for image denoising and deconvolution with signal-dependent observation noise. We use an optimization strategy based on variable splitting that adapts traditional Gaussian noise-based restoration algorithms to account for the observed image being corrupted by mixed Poisson-Gaussian noise and quantization errors.
An Analytical Framework for Multi-Cell Cooperation via Stochastic Geometry and Large Deviations
Venue: arXiv cs.IT 2012
Year: 2012

Multi-cell cooperation (MCC) is an approach for mitigating inter-cell interference in dense cellular networks. Existing studies on MCC performance typically rely on either over-simplified Wyner-type models or complex system-level simulations. The promising theoretical results (typically using Wyner models) seem to materialize neither in complex simulations nor in practice. To more accurately investigate the theoretical performance of MCC, this paper models an entire plane of interfering cells as a Poisson random tessellation. The base stations (BSs) are then clustered using a regular lattice, whereby BSs in the same cluster mitigate mutual interference by beamforming with perfect channel state information. Techniques from stochastic geometry and large deviation theory are applied to analyze the outage probability as a function of the mobile locations, scattering environment, and the average number of cooperating BSs per cluster, L. For mobiles near the centers of BS clusters, it is shown that as L increases, outage probability diminishes sub-exponentially if scattering is sparse, and following a power law with an exponent proportional to the signal diversity order if scattering is rich. For randomly located mobiles, regardless of scattering, outage probability is shown to scale with increasing L following a power law with an exponent no larger than 0.5. These results confirm analytically that cluster-edge mobiles are the bottleneck for network coverage and provide a plausible analytic framework for more realistic analysis of other multi-cell techniques.
Investigating operation of the Internet in orbit: Five years of collaboration around CLEO
Venue: arXiv cs.NI 2012
Year: 2012

The Cisco router in Low Earth Orbit (CLEO) was launched into space as an experimental secondary payload onboard the UK Disaster Monitoring Constellation (UK-DMC) satellite in September 2003. The UK-DMC satellite is one of an increasing number of DMC satellites in orbit that rely on the Internet Protocol (IP) for command and control and for delivery of data from payloads. The DMC satellites, built by Surrey Satellite Technology Ltd (SSTL), have imaged the effects of Hurricane Katrina, the Indian Ocean Tsunami, and other events for disaster relief under the International Space and Major Disasters Charter. It was possible to integrate the Cisco mobile access router into the UK-DMC satellite as a result of the DMC satellites' adoption of existing commercial networking standards, using IP over Frame Relay over standard High-Level Data Link Control, or HDLC (ISO 13239) on standard serial interfaces. This approach came from work onboard SSTL's earlier UoSAT-12 satellite
Saratoga: scalable, speedy data delivery for sensor networks
Venue: arXiv cs.NI 2012
Year: 2012

A networking transport protocol, named Saratoga, has been developed at the University of Surrey for efficient delivery of imagery from Internet-Protocol-based remote-sensing satellites. Saratoga is now being implemented and evaluated for use for the high-end data-delivery needs of astronomers using large, advanced, radio telescopes. These telescopes are expected to take advantage of Internet technologies. This brief paper outlines the reasons for the creation and adoption of this protocol, discusses how it differs from and complements other protocols, and summarises the worldwide collaboration that is making this development possible.
Rateless Codes with Progressive Recovery for Layered Multimedia Delivery
Venue: arXiv cs.IT 2012
Year: 2012

This paper proposes a novel approach, based on unequal error protection, to enhance rateless codes with progressive recovery for layered multimedia delivery. With a parallel encoding structure, the proposed Progressive Rateless codes (PRC) assign unequal redundancy to each layer in accordance with their importance. Each output symbol contains information from all layers, and thus the stream layers can be recovered progressively at the expected received ratios of output symbols. Furthermore, the dependency between layers is naturally considered. The performance of the PRC is evaluated and compared with some related UEP approaches. Results show that our PRC approach provides better recovery performance with lower overhead both theoretically and numerically.
Collective Intelligence in Humans: A Literature Review
Venue: arXiv cs.CY 2012
Year: 2012

This literature review focuses on collective intelligence in humans. A keyword search was performed on the Web of Knowledge and selected papers were reviewed in order to reveal themes relevant to collective intelligence. Three levels of abstraction were identified in discussion about the phenomenon: the micro-level, the macro-level and the level of emergence. Recurring themes in the literature were categorized under the above-mentioned framework and directions for future research were identified.
Green Cellular Network Deployment To Reduce RF Pollution
Venue: arXiv cs.CY 2012
Year: 2012

As the mobile telecommunication systems are growing tremendously all over the world, the numbers of handheld and base stations are also rapidly growing and it became very popular to see these base stations distributed everywhere in the neighborhood and on roof tops which has caused a considerable amount of panic to the public in Palestine concerning wither the radiated electromagnetic fields from these base stations may cause any health effect or hazard. Recently UP High Court in India ordered for removal of BTS towers from residential area, it has created panic among cellular communication network designers too. Green cellular networks could be a solution for the above problem. This paper deals with green cellular networks with the help of multi-layer overlaid hierarchical structure (macro / micro / pico / femto cells). Macrocell for area coverage, micro for pedestrian and a slow moving traffic while pico for indoor use and femto for individual high capacity users. This could be the answer of the problem of energy conservation and enhancement of spectral density also.
Distributed Learning, Communication Complexity and Privacy
Venue: arXiv cs.LG 2012
Year: 2012

We consider the problem of PAC-learning from distributed data and analyze fundamental communication complexity questions involved. We provide general upper and lower bounds on the amount of communication needed to learn well, showing that in addition to VC-dimension and covering number, quantities such as the teaching-dimension and mistake-bound of a class play an important role. We also present tight results for a number of common concept classes including conjunctions, parity functions, and decision lists. For linear separators, we show that for non-concentrated distributions, we can use a version of the Perceptron algorithm to learn with much less communication than the number of updates given by the usual margin bound. We also show how boosting can be performed in a generic manner in the distributed setting to achieve communication with only logarithmic dependence on 1/epsilon for any concept class, and demonstrate how recent work on agnostic learning from class-conditional queries can be used to achieve low communication in agnostic settings as well. We additionally present an analysis of privacy, considering both differential privacy and a notion of distributional privacy that is especially appealing in this context.
Efficient Protocols for Distributed Classification and Optimization
Venue: arXiv cs.LG 2012
Year: 2012

In distributed learning, the goal is to perform a learning task over data distributed across multiple nodes with minimal (expensive) communication. Prior work (Daume III et al., 2012) proposes a general model that bounds the communication required for learning classifiers while allowing for $\eps$ training error on linearly separable data adversarially distributed across nodes. In this work, we develop key improvements and extensions to this basic model. Our first result is a two-party multiplicative-weight-update based protocol that uses $O(d^2 \log{1/\eps})$ words of communication to classify distributed data in arbitrary dimension $d$, $\eps$-optimally. This readily extends to classification over $k$ nodes with $O(kd^2 \log{1/\eps})$ words of communication. Our proposed protocol is simple to implement and is considerably more efficient than baselines compared, as demonstrated by our empirical results. In addition, we illustrate general algorithm design paradigms for doing efficient learning over distributed data. We show how to solve fixed-dimensional and high dimensional linear programming efficiently in a distributed setting where constraints may be distributed across nodes. Since many learning problems can be viewed as convex optimization problems where constraints are generated by individual points, this models many typical distributed learning scenarios. Our techniques make use of a novel connection from multipass streaming, as well as adapting the multiplicative-weight-update framework more generally to a distributed setting. As a consequence, our methods extend to the wide range of problems solvable using these techniques.
Markerless Motion Capture in the Crowd
Venue: arXiv cs.SI 2012
Year: 2012

This work uses crowdsourcing to obtain motion capture data from video recordings. The data is obtained by information workers who click repeatedly to indicate body configurations in the frames of a video, resulting in a model of 2D structure over time. We discuss techniques to optimize the tracking task and strategies for maximizing accuracy and efficiency. We show visualizations of a variety of motions captured with our pipeline then apply reconstruction techniques to derive 3D structure.
Visualizing Collective Discursive User Interactions in Online Life Science Communities
Venue: arXiv cs.SI 2012
Year: 2012

This paper highlights the rationale for the development of BioViz, a tool to help visualize the existence of collective user interactions in online life science communities. The first community studied has approximately 22,750 unique users and the second has 35,000. Making sense of the number of interactions between actors in these networks in order to discern patterns of collective organization and intelligent behavior is challenging. One of the complications is that forums - our object of interest - can vary in their purpose and remit (e.g. the role of gender in the life sciences to forums of praxis such as one exploring the cell line culturing) and this shapes the structure of the forum organization itself. Our approach took a random sample of 53 forums which were manually analyzed by our research team and interactions between actors were recorded as arcs between nodes. The paper focuses on a discussion of the utility of our approach, but presents some brief results to highlight the forms of knowledge that can be gained in identifying collective group formations. Specifically, we found that by using a matrix-based visualization approach, we were able to see patterns of collective behavior which we believe is valuable both to the study of collective intelligence and the design of virtual organizations.
Jar Decoding: Non-Asymptotic Converse Coding Theorems, Taylor-Type Expansion, and Optimality
Venue: arXiv cs.IT 2012
Year: 2012

Recently, a new decoding rule called jar decoding was proposed; under jar decoding, a non-asymptotic achievable tradeoff between the coding rate and word error probability was also established for any discrete input memoryless channel with discrete or continuous output (DIMC). Along the path of non-asymptotic analysis, in this paper, it is further shown that jar decoding is actually optimal up to the second order coding performance by establishing new non-asymptotic converse coding theorems, and determining the Taylor expansion of the (best) coding rate $R_n (ε)$ of finite block length for any block length $n$ and word error probability $ε$ up to the second order. Finally, based on the Taylor-type expansion and the new converses, two approximation formulas for $R_n (ε)$ (dubbed "SO" and "NEP") are provided; they are further evaluated and compared against some of the best bounds known so far, as well as the normal approximation of $R_n (ε)$ revisited recently in the literature. It turns out that while the normal approximation is all over the map, i.e. sometime below achievable bounds and sometime above converse bounds, the SO approximation is much more reliable as it is always below converses; in the meantime, the NEP approximation is the best among the three and always provides an accurate estimation for $R_n (ε)$. An important implication arising from the Taylor-type expansion of $R_n (ε)$ is that in the practical non-asymptotic regime, the optimal marginal codeword symbol distribution is not necessarily a capacity achieving distribution.
Non-asymptotic Equipartition Properties for Independent and Identically Distributed Sources
Venue: arXiv cs.IT 2012
Year: 2012

Given an independent and identically distributed source $X = \{X_i \}_{i=1}^{\infty}$ with finite Shannon entropy or differential entropy (as the case may be) $H(X)$, the non-asymptotic equipartition property (NEP) with respect to $H(X)$ is established, which characterizes, for any finite block length $n$, how close $-{1\over n} \ln p(X_1 X_2...X_n)$ is to $H(X)$ by determining the information spectrum of $X_1 X_2...X_n $, i.e., the distribution of $-{1\over n} \ln p(X_1 X_2...X_n)$. Non-asymptotic equipartition properties (with respect to conditional entropy, mutual information, and relative entropy) in a similar nature are also established. These non-asymptotic equipartition properties are instrumental to the development of non-asymptotic coding (including both source and channel coding) results in information theory in the same way as the asymptotic equipartition property to all asymptotic coding theorems established so far in information theory. As an example, the NEP with respect to $H(X)$ is used to establish a non-asymptotic fixed rate source coding theorem, which reveals, for any finite block length $n$, a complete picture about the tradeoff between the minimum rate of fixed rate coding of $X_1...X_n$ and error probability when the error probability is a constant, or goes to 0 with block length $n$ at a sub-polynomial, polynomial or sub-exponential speed. With the help of the NEP with respect to other information quantities, non-asymptotic channel coding theorems of similar nature will be established in a separate paper.
Thermodynamic Principles in Social Collaborations
Venue: arXiv cs.SI 2012
Year: 2012

A thermodynamic framework is presented to characterize the evolution of efficiency, order, and quality in social content production systems, and this framework is applied to the analysis of Wikipedia. Contributing editors are characterized by their (creative) energy levels in terms of number of edits. We develop a definition of entropy that can be used to analyze the efficiency of the system as a whole, and relate it to the evolution of power-law distributions and a metric of quality. The concept is applied to the analysis of eight years of Wikipedia editing data and results show that (1) Wikipedia has become more efficient during its evolution and (2) the entropy-based efficiency metric has high correlation with observed readership of Wikipedia pages.
E-Health Initiative and Customer's Expectation: Case Brunei
Venue: arXiv cs.OH 2012
Year: 2012

This paper is to determine the dimension of e-health services in Brunei Darussalam (Brunei) from customers' perspective. It is to identify, understand, analyze and evaluate public's expectation on e-health in Brunei. A questionnaire was designed to gather quantitative and qualitative data to survey patients, patient's family, and health practitioners at hospitals, clinics, or home care centers in Brunei starting from February to March, 2011. A 25-item Likert-type survey instrument was specifically developed for this study and administered to a sample of 366 patients. The data were analyzed to provide initial ideas and recommendation to policy makers on how to move forward with the e-health initiative as a mean to improve healthcare services. The survey revealed that there exists a high demand and expectation from people in Brunei to have better healthcare services accessible through an e-health system in order to improve health literacy as well as quality and efficiency of healthcare. Regardless of the limitations of the survey, the general public has responded with a great support for the capabilities of an e-health system listed from the questionnaires. The results of the survey provide a solid foundation for our on going research project to proceed further to develop a model of e-health and subsequently develop a system prototype that incorporate expectations from the people.
On the Blind Interference Alignment over Homogeneous Block Fading Channels
Venue: arXiv cs.IT 2012
Year: 2012

Staggered fading pattern between different users is crucial to interference alignment without CSIT, or so-called blind interference alignment (BIA). This special fading structure naturally arises from heterogeneous block fading setting, in which different users experience independent block fading with different coherent times. Jafar et al. prove that BIA can be applied in some special heterogeneous block fading channels, which are formed naturally or constructed artificially. In this paper, we show that in the context of a 2-user 2x1 broadcasting (BC) channel, staggered fading pattern can also be found in homogeneous block fading setting, in which both users experience independent fading with the same coherent time; and we propose a scheme to achieve the optimal 4/3 DoF for the homogenous setting by using BIA. Applying the proposed scheme, we further study a 2x1 BC network with K users undergoing homogeneous block fading. When K>=4, we show it is almost guaranteed that the transmitter can find two users among the K users to form a 2-user 2x1 BC channel which can apply BIA.
GPS Information and Rate Tolerance - Clarifying Relationship between Rate Distortion and Complexity Distortion
Venue: arXiv cs.IT 2012
Year: 2012

I proposed rate tolerance and discussed its relation to rate distortion in my book "A Generalized Information Theory" published in 1993. Recently, I examined the structure function and the complexity distortion based on Kolmogorov's complexity theory. It is my understanding now that complexity-distortion is only a special case of rate tolerance while constraint sets change from fuzzy sets into clear sets that look like balls with the same radius. It is not true that the complexity distortion is generally equivalent to rate distortion as claimed by the researchers of complexity theory. I conclude that a rate distortion function can only be equivalent to a rate tolerance function and both of them can be described by a generalized mutual information formula where P(Y|X) is equal to P(Y|Tolerance). The paper uses GPS as an example to derive generalized information formulae and proves the above conclusions using mathematical analyses and a coding example. The similarity between the formula for measuring GPS information and the formula for rate distortion function can deepen our understanding the generalized information measure.
Indus script corpora, archaeo-metallurgy and Meluhha (Mleccha)
Venue: arXiv cs.CL 2012
Year: 2012

Jules Bloch's work on formation of the Marathi language has to be expanded further to provide for a study of evolution and formation of Indian languages in the Indian language union (sprachbund). The paper analyses the stages in the evolution of early writing systems which began with the evolution of counting in the ancient Near East. A stage anterior to the stage of syllabic representation of sounds of a language, is identified. Unique geometric shapes required for tokens to categorize objects became too large to handle to abstract hundreds of categories of goods and metallurgical processes during the production of bronze-age goods. About 3500 BCE, Indus script as a writing system was developed to use hieroglyphs to represent the 'spoken words' identifying each of the goods and processes. A rebus method of representing similar sounding words of the lingua franca of the artisans was used in Indus script. This method is recognized and consistently applied for the lingua franca of the Indian sprachbund. That the ancient languages of India, constituted a sprachbund (or language union) is now recognized by many linguists. The sprachbund area is proximate to the area where most of the Indus script inscriptions were discovered, as documented in the corpora. That hundreds of Indian hieroglyphs continued to be used in metallurgy is evidenced by their use on early punch-marked coins. This explains the combined use of syllabic scripts such as Brahmi and Kharoshti together with the hieroglyphs on Rampurva copper bolt, and Sohgaura copper plate from about 6th century BCE.Indian hieroglyphs constitute a writing system for meluhha language and are rebus representations of archaeo-metallurgy lexemes. The rebus principle was employed by the early scripts and can legitimately be used to decipher the Indus script, after secure pictorial identification.
Macroscopes: models for collective decision making
Venue: arXiv cs.SI 2012
Year: 2012

We introduce a new model of collective decision making, when a global decision needs to be made but the parties only possess partial information, and are unwilling (or unable) to first create a globalcomposite of their local views. Our macroscope model captures two key features of many real-world problems: allotment structure (how access to local information is apportioned between parties, including overlaps between the parties) and the possible presence of meta-information (what each party knows about the allotment structure of the overall problem). Using the framework of communication complexity, we formalize the efficient solution of a macroscope. We present general results about the macroscope model, and also results that abstract the essential computational operations underpinning practical applications, including in financial markets and decentralized sensor networks. We illustrate the computational problem inherent in real-world collective decision making processes using results for specific functions, involving detecting a change in state (constant and step functions), and computing statistical properties (the mean).