OpenRaiser/Intern-Atlas huggingface dataset:
Time and harmonic study of strongly controllable group systems, group shifts, and group codes
Venue: arXiv cs.IT 2017
Year: 2017

In this paper we give a complementary view of some of the results on group systems by Forney and Trott. We find an encoder of a group system which has the form of a time convolution. We consider this to be a time domain encoder while the encoder of Forney and Trott is a spectral domain encoder. We study the outputs of time and spectral domain encoders when the inputs are the same, and also study outputs when the same input is used but time runs forward and backward. In an abelian group system, all four cases give the same output for the same input, but this may not be true for a nonabelian system. Moreover, time symmetry and harmonic symmetry are broken for the same reason. We use a canonic form, a set of tensors, to show how the outputs are related. These results show there is a time and harmonic theory of group systems.
The Control Complexity of $r$-Approval: from the Single-Peaked Case to the General Case
Venue: arXiv cs.GT 2017
Year: 2017

We investigate the complexity of $r$-Approval control problems in $k$-peaked elections, where at most $k$ peaks are allowed in each vote with respect to an order of the candidates. We show that most NP-hardness results in general elections also hold in k-peaked elections even for $k=2,3$. On the other hand, we derive polynomial-time algorithms for some problems for $k=2$. All our NP-hardness results apply to Approval and sincere-strategy preference-based Approval as well. Our study leads to many dichotomy results for the problems considered in this paper, with respect to the values of $k$ and $r$. In addition, we study $r$-Approval control problems from the viewpoint of parameterized complexity and achieve both fixed-parameter tractability results and W-hardness results, with respect to the solution size. Along the way exploring the complexity of control problems, we obtain two byproducts which are of independent interest. First, we prove that every graph of maximum degree 3 admits a specific 2-interval representation where every 2-interval corresponding to a vertex contains a trivial interval and, moreover, 2-intervals may only intersect at the endpoints of the intervals. Second, we develop a fixed-parameter tractable algorithm for a generalized $r$-Set Packing problem with respect to the solution size, where each element in the given universal set is allowed to occur in more than one r-subset in the solution.
On the Minimax Capacity Loss under Sub-Nyquist Universal Sampling
Venue: arXiv cs.IT 2017
Year: 2017

This paper investigates the information rate loss in analog channels when the sampler is designed to operate independent of the instantaneous channel occupancy. Specifically, a multiband linear time-invariant Gaussian channel under universal sub-Nyquist sampling is considered. The entire channel bandwidth is divided into $n$ subbands of equal bandwidth. At each time only $k$ constant-gain subbands are active, where the instantaneous subband occupancy is not known at the receiver and the sampler. We study the information loss through a capacity loss metric, that is, the capacity gap caused by the lack of instantaneous subband occupancy information. We characterize the minimax capacity loss for the entire sub-Nyquist rate regime, provided that the number $n$ of subbands and the SNR are both large. The minimax limits depend almost solely on the band sparsity factor and the undersampling factor, modulo some residual terms that vanish as $n$ and SNR grow. Our results highlight the power of randomized sampling methods (i.e. the samplers that consist of random periodic modulation and low-pass filters), which are able to approach the minimax capacity loss with exponentially high probability.
Bandits with Knapsacks
Venue: arXiv cs.DS 2017
Year: 2017

Multi-armed bandit problems are the predominant theoretical model of exploration-exploitation tradeoffs in learning, and they have countless applications ranging from medical trials, to communication networks, to Web search and advertising. In many of these application domains the learner may be constrained by one or more supply (or budget) limits, in addition to the customary limitation on the time horizon. The literature lacks a general model encompassing these sorts of problems. We introduce such a model, called "bandits with knapsacks", that combines aspects of stochastic integer programming with online learning. A distinctive feature of our problem, in comparison to the existing regret-minimization literature, is that the optimal policy for a given latent distribution may significantly outperform the policy that plays the optimal fixed arm. Consequently, achieving sublinear regret in the bandits-with-knapsacks problem is significantly more challenging than in conventional bandit problems. We present two algorithms whose reward is close to the information-theoretic optimum: one is based on a novel "balanced exploration" paradigm, while the other is a primal-dual algorithm that uses multiplicative updates. Further, we prove that the regret achieved by both algorithms is optimal up to polylogarithmic factors. We illustrate the generality of the problem by presenting applications in a number of different domains including electronic commerce, routing, and scheduling. As one example of a concrete application, we consider the problem of dynamic posted pricing with limited supply and obtain the first algorithm whose regret, with respect to the optimal dynamic policy, is sublinear in the supply.
Parallel Coordinate Descent Newton Method for Efficient $\ell_1$-Regularized Minimization
Venue: arXiv cs.LG 2017
Year: 2017

The recent years have witnessed advances in parallel algorithms for large scale optimization problems. Notwithstanding demonstrated success, existing algorithms that parallelize over features are usually limited by divergence issues under high parallelism or require data preprocessing to alleviate these problems. In this work, we propose a Parallel Coordinate Descent Newton algorithm using multidimensional approximate Newton steps (PCDN), where the off-diagonal elements of the Hessian are set to zero to enable parallelization. It randomly partitions the feature set into $b$ bundles/subsets with size of $P$, and sequentially processes each bundle by first computing the descent directions for each feature in parallel and then conducting $P$-dimensional line search to obtain the step size. We show that: (1) PCDN is guaranteed to converge globally despite increasing parallelism; (2) PCDN converges to the specified accuracy $ε$ within the limited iteration number of $T_ε$, and $T_ε$ decreases with increasing parallelism (bundle size $P$). Using the implementation technique of maintaining intermediate quantities, we minimize the data transfer and synchronization cost of the $P$-dimensional line search. For concreteness, the proposed PCDN algorithm is applied to $\ell_1$-regularized logistic regression and $\ell_2$-loss SVM. Experimental evaluations on six benchmark datasets show that the proposed PCDN algorithm exploits parallelism well and outperforms the state-of-the-art methods in speed without losing accuracy.
Instruction sequence expressions for the secure hash algorithm SHA-256
Venue: arXiv cs.PL 2017
Year: 2017

The secure hash function SHA-256 is a function on bit strings. This means that its restriction to the bit strings of any given length can be computed by a finite instruction sequence that contains only instructions to set and get the content of Boolean registers, forward jump instructions, and a termination instruction. We describe such instruction sequences for the restrictions to bit strings of the different possible lengths by means of uniform terms from an algebraic theory.
Asymptotically Optimal Power Allocation for Energy Harvesting Communication Networks
Venue: arXiv cs.IT 2017
Year: 2017

For a general energy harvesting (EH) communication network, i.e., a network where the nodes generate their transmit power through EH, we derive the asymptotically optimal online power allocation solution which optimizes a general utility function when the number of transmit time slots, $N$, and the battery capacities of the EH nodes, $B_{\rm max}$, satisfy $N\to\infty$ and $B_{\rm max}\to\infty$. The considered family of utility functions is general enough to include the most important performance measures in communication theory such as the average data rate, outage probability, average bit error probability, and average signal-to-noise ratio. The proposed power allocation solution is very simple. Namely, the asymptotically optimal power allocation for the EH network is identical to the optimal power allocation for an equivalent non-EH network whose nodes have infinite energy available but their average transmit power is constrained to be equal to the average harvested power and/or the maximum average transmit power of the corresponding nodes in the EH network. Moreover, the maximum average performance of a general EH network converges to the maximum average performance of the corresponding equivalent non-EH network, when $N\to\infty$ and $B_{\rm max}\to\infty$. Although the proposed solution is asymptotic in nature, it is applicable to EH systems transmitting in a large but finite number of time slots and having a battery capacity much larger than the average harvested power and/or the maximum average transmit power.
The Quest for Sustainable Smart Grids
Venue: arXiv cs.SY 2017
Year: 2017

This letter is my comment about the opinion paper: Transdisciplinary electric power grid science (PNAS, 2013 - http://www.pnas.org/content/110/30/12159.full). [arXiv:1307.7305].
Finite-Length Analyses for Source and Channel Coding on Markov Chains
Venue: arXiv cs.IT 2017
Year: 2017

We study finite-length bounds for source coding with side information for Markov sources and channel coding for channels with conditional Markovian additive noise. For this purpose, we propose two criteria for finite-length bounds. One is the asymptotic optimality and the other is the efficient computability of the bound. Then, we derive finite-length upper and lower bounds for coding length in both settings so that their computational complexity is efficient. To discuss the first criterion, we derive the large deviation bounds, the moderate deviation bounds, and second order bounds for these two topics, and show that these finite-length bounds achieves the asymptotic optimality in these senses. For this discussion, we introduce several kinds of information measure for transition matrices.
Approaches to Maintain Bi-connectivity for Resilience in Overlaid Multicasting
Venue: arXiv cs.NI 2017
Year: 2017

Application layer multicast (ALM) also called Overlay Multicast, is an attractive alternative solution to most of the problems associated with IP multicast. In ALM, multicast-related functionalities are moved to end-hosts. Application layer multicast builds a peer-to-peer (P2P) overlay topology consisting of end-to-end unicast connections between end-hosts. The key advantages, overlays offer, are flexibility, adaptability and ease of deployment [1]. The general approach to build an application layer multicast architecture involves tracking network characteristics and building appropriate topologies by allowing the end users to self organize into logical overlay networks for efficient data delivery. The major concern in designing ALM protocol is the mechanism to build and maintain a topology and to route data efficiently and reliably in this topology. We propose here a two-fold dynamic overlay tree construction and maintenance scheme in which a mesh-like topology is first built, where an arriving host connects to two already connected hosts. This ensures that two node and link disjoint paths are always maintained between every possible pair of nodes. Once the mesh is formed, on top of it, a single or multiple data delivery tree(s) are built using a suitable protocol. An algorithm is run in the nodes of the overlay topology to maintain the biconnectivity by inserting new links and deleting the redundant links as a continuous process.
Temporal stability in human interaction networks
Venue: arXiv cs.SI 2017
Year: 2017

This paper reports on stable (or invariant) properties of human interaction networks, with benchmarks derived from public email lists. Activity, recognized through messages sent, along time and topology were observed in snapshots in a timeline, and at different scales. Our analysis shows that activity is practically the same for all networks across timescales ranging from seconds to months. The principal components of the participants in the topological metrics space remain practically unchanged as different sets of messages are considered. The activity of participants follows the expected scale-free trace, thus yielding the hub, intermediary and peripheral classes of vertices by comparison against the Erdös-Rényi model. The relative sizes of these three sectors are essentially the same for all email lists and the same along time. Typically, $<15\%$ of the vertices are hubs, 15-45\% are intermediary and $>45\%$ are peripheral vertices. Similar results for the distribution of participants in the three sectors and for the relative importance of the topological metrics were obtained for 12 additional networks from Facebook, Twitter and ParticipaBR. These properties are consistent with the literature and may be general for human interaction networks, which has important implications for establishing a typology of participants based on quantitative criteria.
Intermittent Communication
Venue: arXiv cs.IT 2017
Year: 2017

We formulate a model for intermittent communication that can capture bursty transmissions or a sporadically available channel, where in either case the receiver does not know a priori when the transmissions will occur. Focusing on the point-to-point case, we develop a decoding structure, decoding from pattern detection, and its achievable rate for such communication scenarios. Decoding from pattern detection first detects the locations of codeword symbols and then uses them to decode. We introduce the concept of partial divergence and study some of its properties in order to obtain stronger achievability results. As the system becomes more intermittent, the achievable rates decrease due to the additional uncertainty about the positions of the codeword symbols at the decoder. Additionally, we provide upper bounds on the capacity of binary noiseless intermittent communication with the help of a genie-aided encoder and decoder. The upper bounds imply a tradeoff between the capacity and the intermittency rate of the communication system, even if the receive window scales linearly with the codeword length.
BigOP: Generating Comprehensive Big Data Workloads as a Benchmarking Framework
Venue: arXiv cs.DC 2017
Year: 2017

Big Data is considered proprietary asset of companies, organizations, and even nations. Turning big data into real treasure requires the support of big data systems. A variety of commercial and open source products have been unleashed for big data storage and processing. While big data users are facing the choice of which system best suits their needs, big data system developers are facing the question of how to evaluate their systems with regard to general big data processing needs. System benchmarking is the classic way of meeting the above demands. However, existent big data benchmarks either fail to represent the variety of big data processing requirements, or target only one specific platform, e.g. Hadoop. In this paper, with our industrial partners, we present BigOP, an end-to-end system benchmarking framework, featuring the abstraction of representative Operation sets, workload Patterns, and prescribed tests. BigOP is part of an open-source big data benchmarking project, BigDataBench. BigOP's abstraction model not only guides the development of BigDataBench, but also enables automatic generation of tests with comprehensive workloads. We illustrate the feasibility of BigOP by implementing an automatic test generation tool and benchmarking against three widely used big data processing systems, i.e. Hadoop, Spark and MySQL Cluster. Three tests targeting three different application scenarios are prescribed. The tests involve relational data, text data and graph data, as well as all operations and workload patterns. We report results following test specifications.
Quantifying literature quality using complexity criteria
Venue: arXiv cs.CL 2017
Year: 2017

We measured entropy and symbolic diversity for English and Spanish texts including literature Nobel laureates and other famous authors. Entropy, symbol diversity and symbol frequency profiles were compared for these four groups. We also built a scale sensitive to the quality of writing and evaluated its relationship with the Flesch's readability index for English and the Szigriszt's perspicuity index for Spanish. Results suggest a correlation between entropy and word diversity with quality of writing. Text genre also influences the resulting entropy and diversity of the text. Results suggest the plausibility of automated quality assessment of texts.
Using Entropy Estimates for DAG-Based Ontologies
Venue: arXiv cs.CL 2017
Year: 2017

Motivation: Entropy measurements on hierarchical structures have been used in methods for information retrieval and natural language modeling. Here we explore its application to semantic similarity. By finding shared ontology terms, semantic similarity can be established between annotated genes. A common procedure for establishing semantic similarity is to calculate the descriptiveness (information content) of ontology terms and use these values to determine the similarity of annotations. Most often information content is calculated for an ontology term by analyzing its frequency in an annotation corpus. The inherent problems in using these values to model functional similarity motivates our work. Summary: We present a novel calculation for establishing the entropy of a DAG-based ontology, which can be used in an alternative method for establishing the information content of its terms. We also compare our IC metric to two others using semantic and sequence similarity.
E-Generalization Using Grammars
Venue: arXiv cs.LO 2017
Year: 2017

We extend the notion of anti-unification to cover equational theories and present a method based on regular tree grammars to compute a finite representation of E-generalization sets. We present a framework to combine Inductive Logic Programming and E-generalization that includes an extension of Plotkin's lgg theorem to the equational case. We demonstrate the potential power of E-generalization by three example applications: computation of suggestions for auxiliary lemmas in equational inductive proofs, computation of construction laws for given term sequences, and learning of screen editor command sequences.
Derivatives of Parsing Expression Grammars
Venue: arXiv cs.FL 2017
Year: 2017

This paper introduces a new derivative parsing algorithm for recognition of parsing expression grammars. Derivative parsing is shown to have a polynomial worst-case time bound, an improvement on the exponential bound of the recursive descent algorithm. This work also introduces asymptotic analysis based on inputs with a constant bound on both grammar nesting depth and number of backtracking choices; derivative and recursive descent parsing are shown to run in linear time and constant space on this useful class of inputs, with both the theoretical bounds and the reasonability of the input class validated empirically. This common-case constant memory usage of derivative parsing is an improvement on the linear space required by the packrat algorithm.
Low-Autocorrelation Binary Sequences: On Improved Merit Factors and Runtime Predictions to Achieve Them
Venue: arXiv cs.DS 2017
Year: 2017

The search for binary sequences with a high figure of merit, known as the low autocorrelation binary sequence ($labs$}) problem, represents a formidable computational challenge. To mitigate the computational constraints of the problem, we consider solvers that accept odd values of sequence length $L$ and return solutions for skew-symmetric binary sequences only -- with the consequence that not all best solutions under this constraint will be optimal for each $L$. In order to improve both, the search for best merit factor $and$ the asymptotic runtime performance, we instrumented three stochastic solvers, the first two are state-of-the-art solvers that rely on variants of memetic and tabu search ($lssMAts$ and $lssRRts$), the third solver ($lssOrel$) organizes the search as a sequence of independent contiguous self-avoiding walk segments. By adapting a rigorous statistical methodology to performance testing of all three combinatorial solvers, experiments show that the solver with the best asymptotic average-case performance, $lssOrel\_8 = 0.000032*1.1504^L$, has the best chance of finding solutions that improve, as $L$ increases, figures of merit reported to date. The same methodology can be applied to engineering new $labs$ solvers that may return merit factors even closer to the conjectured asymptotic value of 12.3248.
Fast Separable Non-Local Means
Venue: arXiv cs.CV 2017
Year: 2017

We propose a simple and fast algorithm called PatchLift for computing distances between patches (contiguous block of samples) extracted from a given one-dimensional signal. PatchLift is based on the observation that the patch distances can be efficiently computed from a matrix that is derived from the one-dimensional signal using lifting; importantly, the number of operations required to compute the patch distances using this approach does not scale with the patch length. We next demonstrate how PatchLift can be used for patch-based denoising of images corrupted with Gaussian noise. In particular, we propose a separable formulation of the classical Non-Local Means (NLM) algorithm that can be implemented using PatchLift. We demonstrate that the PatchLift-based implementation of separable NLM is few orders faster than standard NLM, and is competitive with existing fast implementations of NLM. Moreover, its denoising performance is shown to be consistently superior to that of NLM and some of its variants, both in terms of PSNR/SSIM and visual quality.