OpenRaiser/Intern-Atlas huggingface dataset:
On the Correlation Between Polarized BECs
Venue: arXiv cs.IT 2013
Year: 2013

We consider the $2^n$ channels synthesized by the $n$-fold application of Arıkan's polar transform to a binary erasure channel (BEC). The synthetic channels are BECs themselves, and we show that, asymptotically for almost all these channels, the pairwise correlations between their erasure events are extremely small: the correlation coefficients vanish faster than any exponential in $n$. Such a fast decay of correlations allows us to conclude that the union bound on the block error probability of polar codes is very tight.
Time/Computationally Optimal Network Architecture: Wireless Sensor Fusion
Venue: arXiv cs.NI 2013
Year: 2013

In this research paper, the problems dealing with sensor network architecture, sensor fusion are addressed. Time/Computationally optimal network architectures are investigated. Some novel ideas on sensor fusion are proposed.
A Packetized Direct Load Control Mechanism for Demand Side Management
Venue: arXiv cs.SY 2013
Year: 2013

Electricity peaks can be harmful to grid stability and result in additional generation costs to balance supply with demand. By developing a network of smart appliances together with a quasi-decentralized control protocol, direct load control (DLC) provides an opportunity to reduce peak consumption by directly controlling the on/off switch of the networked appliances. This paper proposes a packetized DLC (PDLC) solution that is illustrated by an application to air conditioning temperature control. Here the term packetized refers to a fixed time energy usage authorization. The consumers in each room choose their preferred set point, and then an operator of the local appliance pool will determine the comfort band around the set point. We use a thermal dynamic model to investigate the duty cycle of thermostatic appliances. Three theorems are proposed in this paper. The first two theorems evaluate the performance of the PDLC in both transient and steady state operation. The first theorem proves that the average room temperature would converge to the average room set point with fixed number of packets applied in each discrete interval. The second theorem proves that the PDLC solution guarantees to control the temperature of all the rooms within their individual comfort bands. The third theorem proposes an allocation method to link the results in theorem 1 and assumptions in theorem 2 such that the overall PDLC solution works. The direct result of the theorems is that we can reduce the consumption oscillation that occurs when no control is applied. Simulation is provided to verify theoretical results.
On a Multiple-Access in a Vector Disjunctive Channel
Venue: arXiv cs.IT 2013
Year: 2013

We address the problem of increasing the sum rate in a multiple-access system from [1] for small number of users. We suggest an improved signal-code construction in which in case of a small number of users we give more resources to them. For the resulting multiple-access system a lower bound on the relative sum rate is derived. It is shown to be very close to the maximal value of relative sum rate in [1] even for small number of users. The bound is obtained for the case of decoding by exhaustive search. We also suggest reduced-complexity decoding and compare the maximal number of users in this case and in case of decoding by exhaustive search.
Fast algorithms for ell-adic towers over finite fields
Venue: arXiv cs.SC 2013
Year: 2013

Inspired by previous work of Shoup, Lenstra-De Smit and Couveignes-Lercier, we give fast algorithms to compute in (the first levels of) the ell-adic closure of a finite field. In many cases, our algorithms have quasi-linear complexity.
Weighted Last-Step Min-Max Algorithm with Improved Sub-Logarithmic Regret
Venue: arXiv cs.LG 2013
Year: 2013

In online learning the performance of an algorithm is typically compared to the performance of a fixed function from some class, with a quantity called regret. Forster proposed a last-step min-max algorithm which was somewhat simpler than the algorithm of Vovk, yet with the same regret. In fact the algorithm he analyzed assumed that the choices of the adversary are bounded, yielding artificially only the two extreme cases. We fix this problem by weighing the examples in such a way that the min-max problem will be well defined, and provide analysis with logarithmic regret that may have better multiplicative factor than both bounds of Forster and Vovk. We also derive a new bound that may be sub-logarithmic, as a recent bound of Orabona et.al, but may have better multiplicative factor. Finally, we analyze the algorithm in a weak-type of non-stationary setting, and show a bound that is sub-linear if the non-stationarity is sub-linear as well.
A Proof of Threshold Saturation for Spatially-Coupled LDPC Codes on BMS Channels
Venue: arXiv cs.IT 2013
Year: 2013

Low-density parity-check (LDPC) convolutional codes have been shown to exhibit excellent performance under low-complexity belief-propagation decoding [1], [2]. This phenomenon is now termed threshold saturation via spatial coupling. The underlying principle behind this appears to be very general and spatially-coupled (SC) codes have been successfully applied in numerous areas. Recently, SC regular LDPC codes have been proven to achieve capacity universally, over the class of binary memoryless symmetric (BMS) channels, under belief-propagation decoding [3], [4]. In [5], [6], potential functions are used to prove that the BP threshold of SC irregular LDPC ensembles saturates, for the binary erasure channel, to the conjectured MAP threshold (known as the Maxwell threshold) of the underlying irregular ensembles. In this paper, that proof technique is generalized to BMS channels, thereby extending some results of [4] to irregular LDPC ensembles. We also believe that this approach can be expanded to cover a wide class of graphical models whose message-passing rules are associated with a Bethe free energy.
Automated Design of Two-Layer Fat-Tree Networks
Venue: arXiv cs.DC 2013
Year: 2013

This paper presents an algorithm to automatically design two-level fat-tree networks, such as ones widely used in large-scale data centres and cluster supercomputers. The two levels may each use a different type of switches from design database to achieve an optimal network structure. Links between layers can run in bundles to simplify cabling. Several sample network designs are examined and their technical and economic characteristics are discussed. The characteristic feature of our approach is that real life equipment prices and values of technical characteristics are used. This allows to select an optimal combination of hardware to build the network (including semi-populated configurations of modular switches) and accurately estimate the cost of this network. We also show how technical characteristics of the network can be derived from its per-port metrics and suggest heuristics for equipment placement. The algorithm is useful as a part of a bigger design procedure that selects optimal hardware of cluster supercomputer as a whole. Therefore the article is focused on the use of fat-trees for high-performance computing, although the results are valid for any type of data centres.
Approximate Sum-Capacity of K-user Cognitive Interference Channels with Cumulative Message Sharing
Venue: arXiv cs.IT 2013
Year: 2013

This paper considers the K user cognitive interference channel with one primary and K-1 secondary/cognitive transmitters with a cumulative message sharing structure, i.e cognitive transmitter $i\in [2:K]$ knows non-causally all messages of the users with index less than i. We propose a computable outer bound valid for any memoryless channel. We first evaluate the sum-rate outer bound for the high- SNR linear deterministic approximation of the Gaussian noise channel. This is shown to be capacity for the 3-user channel with arbitrary channel gains and the sum-capacity for the symmetric K-user channel. Interestingly. for the K user channel having only the K th cognitive know all the other messages is sufficient to achieve capacity i.e cognition at transmitter 2 to K-1 is not needed. Next the sum capacity of the symmetric Gaussian noise channel is characterized to within a constant additive and multiplicative gap. The proposed achievable scheme for the additive gap is based on Dirty paper coding and can be thought of as a MIMO-broadcast scheme where only one encoding order is possible due to the message sharing structure. As opposed to other multiuser interference channel models, a single scheme suffices for both the weak and strong interference regimes. With this scheme the generalized degrees of freedom (gDOF) is shown to be a function of K, in contrast to the non cognitive case and the broadcast channel case. Interestingly, it is show that as the number of users grows to infinity the gDoF of the K-user cognitive interference channel with cumulative message sharing tends to the gDoF of a broadcast channel with a K-antenna transmitter and K single-antenna receivers. The analytical additive additive and multiplicative gaps are a function of the number of users. Numerical evaluations of inner and outer bounds show that the actual gap is less than the analytical one.
Pilot-Data: An Abstraction for Distributed Data
Venue: arXiv cs.DC 2013
Year: 2013

Scientific problems that depend on processing large amounts of data require overcoming challenges in multiple areas: managing large-scale data distribution, controlling co-placement and scheduling of data with compute resources, and storing, transferring, and managing large volumes of data. Although there exist multiple approaches to addressing each of these challenges, an integrative approach is missing; furthermore, extending existing functionality or enabling interoperable capabilities remains difficult at best. We propose the concept of Pilot-Data to address the fundamental challenges of co-placement and scheduling of data and compute in heterogeneous and distributed environments with interoperability and extensibility as first-order concerns. Pilot-Data is an extension of the Pilot-Job abstraction for supporting the management of data in conjunction with compute tasks. Pilot-Data separates logical data units from physical storage, thereby providing the basis for efficient compute/data placement and scheduling. In this paper, we discuss the design and implementation of the Pilot-Data prototype, demonstrate its use by data-intensive applications on multiple production distributed cyberinfrastructure and illustrate the advantages arising from flexible execution modes enabled by Pilot-Data. Our experiments utilize an implementation of Pilot-Data in conjunction with a scalable Pilot-Job (BigJob) to establish the application performance that can be enabled by the use of Pilot-Data. We demonstrate how the concept of Pilot-Data also provides the basis upon which to build tools and support capabilities like affinity which in turn can be used for advanced data-compute co-placement and scheduling.
A Secure Submission System for Online Whistleblowing Platforms
Venue: arXiv cs.CR 2013
Year: 2013

Whistleblower laws protect individuals who inform the public or an authority about governmental or corporate misconduct. Despite these laws, whistleblowers frequently risk reprisals and sites such as WikiLeaks emerged to provide a level of anonymity to these individuals. However, as countries increase their level of network surveillance and Internet protocol data retention, the mere act of using anonymizing software such as Tor, or accessing a whistleblowing website through an SSL channel might be incriminating enough to lead to investigations and repercussions. As an alternative submission system we propose an online advertising network called AdLeaks. AdLeaks leverages the ubiquity of unsolicited online advertising to provide complete sender unobservability when submitting disclosures. AdLeaks ads compute a random function in a browser and submit the outcome to the AdLeaks infrastructure. Such a whistleblower's browser replaces the output with encrypted information so that the transmission is indistinguishable from that of a regular browser. Its back-end design assures that AdLeaks must process only a fraction of the resulting traffic in order to receive disclosures with high probability. We describe the design of AdLeaks and evaluate its performance through analysis and experimentation.
Quasi-Equiangular Frame (QEF) : A New Flexible Configuration of Frame
Venue: arXiv cs.IT 2013
Year: 2013

Frame theory is a powerful tool in the domain of signal processing and communication. Among its numerous configurations, the ones which have drawn much attention recently are Equiangular Tight Frame (ETF) and Grassmannian Frame. These frames both have some kind of optimality in coherence, thus bring robustness or optimal performance in applications such as digital fingerprint, erasure channels, and Compressive Sensing. However, too strict constraint on existence and construction of ETF and Grassmannian Frame became the main obstacle for widespread use. In this paper, we propose a new configuration of frame: Quasi-Equiangular Frame, as a compromise but more convenient and flexible approximation of ETF and Grassmannian Frame. We will give formal definition of Quasi-Equiangular Frame and analyze its relationship with ETF and Grassmannian frame. Furthermore, for popularity of ETF and Grassmannian frame in Compressive Sensing, we utilize the technique of random matrices to obtain asymptotical concentration estimation of the Restricted Isometry Constant (RIC) of Quasi-Equiangular Frame with respect to its key parameter.
Optimal Locally Repairable Codes via Rank-Metric Codes
Venue: arXiv cs.IT 2013
Year: 2013

This paper presents a new explicit construction for locally repairable codes (LRCs) for distributed storage systems which possess all-symbols locality and maximal possible minimum distance, or equivalently, can tolerate the maximal number of node failures. This construction, based on maximum rank distance (MRD) Gabidulin codes, provides new optimal vector and scalar LRCs. In addition, the paper also discusses mechanisms by which codes obtained using this construction can be used to construct LRCs with efficient repair of failed nodes by combination of LRC with regenerating codes.
Subjective Reality and Strong Artificial Intelligence
Venue: arXiv cs.AI 2013
Year: 2013

The main prospective aim of modern research related to Artificial Intelligence is the creation of technical systems that implement the idea of Strong Intelligence. According our point of view the path to the development of such systems comes through the research in the field related to perceptions. Here we formulate the model of the perception of external world which may be used for the description of perceptual activity of intelligent beings. We consider a number of issues related to the development of the set of patterns which will be used by the intelligent system when interacting with environment. The key idea of the presented perception model is the idea of subjective reality. The principle of the relativity of perceived world is formulated. It is shown that this principle is the immediate consequence of the idea of subjective reality. In this paper we show how the methodology of subjective reality may be used for the creation of different types of Strong AI systems.
A Two Level Feedback System Design to Regulation Service Provision
Venue: arXiv cs.SY 2013
Year: 2013

Demand side management has gained increasing importance as the penetration of renewable energy grows. Based on a Markov jump process modelling of a group of thermostatic loads, this paper proposes a two level feedback system design between the independent system operator (ISO) and the regulation service provider such that two objectives are achieved: (1) the ISO can optimally dispatch regulation signals to multiple providers in real time in order to reduce the requirement for expensive spinning reserves, and (2) each regulation provider can control its thermostatic loads to respond the ISO signal. It is also shown that the amount of regulation service that can be provided is implicitly restricted by a few fundamental parameters of the provider itself, such as the allowable set point choice and its thermal constant. An interesting finding is that the regulation provider's ability to provide a large amount of long term accumulated regulation and short term signal tracking restrict each other. Simulation results are presented to verify and illustrate the performance of the proposed framework.
Engineering Small Space Dictionary Matching
Venue: arXiv cs.DS 2013
Year: 2013

The dictionary matching problem is to locate occurrences of any pattern among a set of patterns in a given text. Massive data sets abound and at the same time, there are many settings in which working space is extremely limited. We introduce dictionary matching software for the space-constrained environment whose running time is close to linear. We use the compressed suffix tree as the underlying data structure of our algorithm, thus, the working space of our algorithm is proportional to the optimal compression of the dictionary. We also contribute a succinct tool for performing constant-time lowest marked ancestor queries on a tree that is succinctly encoded as a sequence of balanced parentheses, with linear time preprocessing of the tree. This tool should be useful in many other applications. Our source code is available at http://www.sci.brooklyn.cuny.edu/~sokol/dictmatch.html
Nearly Optimal Private Convolution
Venue: arXiv cs.DS 2013
Year: 2013

We study computing the convolution of a private input $x$ with a public input $h$, while satisfying the guarantees of $(ε, δ)$-differential privacy. Convolution is a fundamental operation, intimately related to Fourier Transforms. In our setting, the private input may represent a time series of sensitive events or a histogram of a database of confidential personal information. Convolution then captures important primitives including linear filtering, which is an essential tool in time series analysis, and aggregation queries on projections of the data. We give a nearly optimal algorithm for computing convolutions while satisfying $(ε, δ)$-differential privacy. Surprisingly, we follow the simple strategy of adding independent Laplacian noise to each Fourier coefficient and bounding the privacy loss using the composition theorem of Dwork, Rothblum, and Vadhan. We derive a closed form expression for the optimal noise to add to each Fourier coefficient using convex programming duality. Our algorithm is very efficient -- it is essentially no more computationally expensive than a Fast Fourier Transform. To prove near optimality, we use the recent discrepancy lowerbounds of Muthukrishnan and Nikolov and derive a spectral lower bound using a characterization of discrepancy in terms of determinants.
Optimal Nonstationary Reproduction Distribution for Nonanticipative RDF on Abstract Alphabets
Venue: arXiv cs.IT 2013
Year: 2013

In this paper we introduce a definition for nonanticipative Rate Distortion Function (RDF) on abstract alphabets, and we invoke weak convergence of probability measures to show various of its properties, such as, existence of the optimal reproduction conditional distribution, compactness of the fidelity set, lower semicontinuity of the RDF functional, etc. Further, we derive the closed form expression of the optimal nonstationary reproduction distribution. This expression is computed recursively backward in time. Throughout the paper we point out an operational meaning of the nonanticipative RDF by recalling the coding theorem derive in \cite{tatikonda2000}, and we state relations to Gorbunov-Pinsker's nonanticipatory $ε-$entropy \cite{gorbunov-pinsker}.
Weighted Sum Rate Maximization for Downlink OFDMA with Subcarrier-pair based Opportunistic DF Relaying
Venue: arXiv cs.SY 2013
Year: 2013

This paper addresses a weighted sum rate (WSR) maximization problem for downlink OFDMA aided by a decode-and-forward (DF) relay under a total power constraint. A novel subcarrier-pair based opportunistic DF relaying protocol is proposed. Specifically, user message bits are transmitted in two time slots. A subcarrier in the first slot can be paired with a subcarrier in the second slot for the DF relay-aided transmission to a user. In particular, the source and the relay can transmit simultaneously to implement beamforming at the subcarrier in the second slot. Each unpaired subcarrier in either the first or second slot is used for the source's direct transmission to a user. A benchmark protocol, same as the proposed one except that the transmit beamforming is not used for the relay-aided transmission, is also considered. For each protocol, a polynomial-complexity algorithm is developed to find at least an approximately optimum resource allocation (RA), by using continuous relaxation, the dual method, and Hungarian algorithm. Instrumental to the algorithm design is an elegant definition of optimization variables, motivated by the idea of regarding the unpaired subcarriers as virtual subcarrier pairs in the direct transmission mode. The effectiveness of the RA algorithm and the impact of relay position and total power on the protocols' performance are illustrated by numerical experiments. The proposed protocol always leads to a maximum WSR equal to or greater than that for the benchmark one, and the performance gain of using the proposed one is significant especially when the relay is in close proximity to the source and the total power is low. Theoretical analysis is presented to interpret these observations.
A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time
Venue: arXiv cs.DS 2013
Year: 2013

In this paper, we present a simple combinatorial algorithm that solves symmetric diagonally dominant (SDD) linear systems in nearly-linear time. It uses very little of the machinery that previously appeared to be necessary for a such an algorithm. It does not require recursive preconditioning, spectral sparsification, or even the Chebyshev Method or Conjugate Gradient. After constructing a "nice" spanning tree of a graph associated with the linear system, the entire algorithm consists of the repeated application of a simple (non-recursive) update rule, which it implements using a lightweight data structure. The algorithm is numerically stable and can be implemented without the increased bit-precision required by previous solvers. As such, the algorithm has the fastest known running time under the standard unit-cost RAM model. We hope that the simplicity of the algorithm and the insights yielded by its analysis will be useful in both theory and practice.
Possibilistic logic bases and possibilistic graphs
Venue: arXiv cs.AI 2013
Year: 2013

Possibilistic logic bases and possibilistic graphs are two different frameworks of interest for representing knowledge. The former stratifies the pieces of knowledge (expressed by logical formulas) according to their level of certainty, while the latter exhibits relationships between variables. The two types of representations are semantically equivalent when they lead to the same possibility distribution (which rank-orders the possible interpretations). A possibility distribution can be decomposed using a chain rule which may be based on two different kinds of conditioning which exist in possibility theory (one based on product in a numerical setting, one based on minimum operation in a qualitative setting). These two types of conditioning induce two kinds of possibilistic graphs. In both cases, a translation of these graphs into possibilistic bases is provided. The converse translation from a possibilistic knowledge base into a min-based graph is also described.