OpenRaiser/Intern-Atlas huggingface dataset:
On the Structure of Compatible Rational Functions
Venue: arXiv cs.SC 2013
Year: 2013

A finite number of rational functions are compatible if they satisfy the compatibility conditions of a first-order linear functional system involving differential, shift and q-shift operators. We present a theorem that describes the structure of compatible rational functions. The theorem enables us to decompose a solution of such a system as a product of a rational function, several symbolic powers, a hyperexponential function, a hypergeometric term, and a q-hypergeometric term. We outline an algorithm for computing this product, and present an application.
Secrecy without one-way functions
Venue: arXiv cs.CR 2013
Year: 2013

We show that some problems in information security can be solved without using one-way functions. The latter are usually regarded as a central concept of cryptography, but the very existence of one-way functions depends on difficult conjectures in complexity theory, most notably on the notorious "$P \ne NP$" conjecture. In this paper, we suggest protocols for secure computation of the sum, product, and some other functions, without using any one-way functions. A new input that we offer here is that, in contrast with other proposals, we conceal "intermediate results" of a computation. For example, when we compute the sum of $k$ numbers, only the final result is known to the parties; partial sums are not known to anybody. Other applications of our method include voting/rating over insecure channels and a rather elegant and efficient solution of Yao's "millionaires' problem". Then, while it is fairly obvious that a secure (bit) commitment between two parties is impossible without a one-way function, we show that it is possible if the number of parties is at least 3. We also show how our (bit) commitment scheme for 3 parties can be used to arrange an unconditionally secure (bit) commitment between just two parties if they use a "dummy" (e.g., a computer) as the third party. We explain how our concept of a "dummy" is different from a well-known concept of a "trusted third party". We also suggest a protocol, without using a one-way function, for "mental poker", i.e., a fair card dealing (and playing) over distance. We also propose a secret sharing scheme where an advantage over Shamir's and other known secret sharing schemes is that nobody, including the dealer, ends up knowing the shares owned by any particular player. It should be mentioned that computational cost of our protocols is negligible to the point that all of them can be executed without a computer.
Improved Approximation Algorithms for Computing k Disjoint Paths Subject to Two Constraints
Venue: arXiv cs.DS 2013
Year: 2013

For a given graph $G$ with positive integral cost and delay on edges, distinct vertices $s$ and $t$, cost bound $C\in Z^{+}$ and delay bound $D\in Z^{+}$, the $k$ bi-constraint path ($k$BCP) problem is to compute $k$ disjoint $st$-paths subject to $C$ and $D$. This problem is known NP-hard, even when $k=1$ \cite{garey1979computers}. This paper first gives a simple approximation algorithm with factor-$(2,2)$, i.e. the algorithm computes a solution with delay and cost bounded by $2*D$ and $2*C$ respectively. Later, a novel improved approximation algorithm with ratio $(1+β,\,\max\{2,\,1+\ln\frac{1}β\})$ is developed by constructing interesting auxiliary graphs and employing the cycle cancellation method. As a consequence, we can obtain a factor-$(1.369,\,2)$ approximation algorithm by setting $1+\ln\frac{1}β=2$ and a factor-$(1.567,\,1.567)$ algorithm by setting $1+β=1+\ln\frac{1}β$. Besides, by setting $β=0$, an approximation algorithm with ratio $(1,\, O(\ln n))$, i.e. an algorithm with only a single factor ratio $O(\ln n)$ on cost, can be immediately obtained. To the best of our knowledge, this is the first non-trivial approximation algorithm for the $k$BCP problem that strictly obeys the delay constraint.
Constrained Source Coding with Side Information
Venue: arXiv cs.IT 2013
Year: 2013

The source-coding problem with side information at the decoder is studied subject to a constraint that the encoder---to whom the side information is unavailable---be able to compute the decoder's reconstruction sequence to within some distortion. For discrete memoryless sources and finite single-letter distortion measures, an expression is given for the minimal description rate as a function of the joint law of the source and side information and of the allowed distortions at the encoder and at the decoder. The minimal description rate is also computed for a memoryless Gaussian source with squared-error distortion measures. A solution is also provided to a more general problem where there are more than two distortion constraints and each distortion function may be a function of three arguments: the source symbol, the encoder's reconstruction symbol, and the decoder's reconstruction symbol.
Parametric Estimation of Handoff
Venue: arXiv cs.NI 2013
Year: 2013

The efficiency of wireless technology depends upon the seamless connectivity to the user at anywhere any time.Heterogeneous wireless networks are an integration of different networks with diversified technologies. The most essential requirement for Seamless vertical handover is that the received signal strength should always be healthy. Mobile device enabled with multiple wireless technologies makes it possible to maintain seamless connectivity in highly dynamic environment.Since the available bandwidth is limited and the number of users is growing rapidly, it is a real challenge to maintain the received signal strength in a healthy stage.In this work, the proposed, cost effective parametric estimation for vertical handover shows that the received signal strength maintains a healthy level by considering the novel concept.
Local Graph Coloring and Index Coding
Venue: arXiv cs.IT 2013
Year: 2013

We present a novel upper bound for the optimal index coding rate. Our bound uses a graph theoretic quantity called the local chromatic number. We show how a good local coloring can be used to create a good index code. The local coloring is used as an alignment guide to assign index coding vectors from a general position MDS code. We further show that a natural LP relaxation yields an even stronger index code. Our bounds provably outperform the state of the art on index coding but at most by a constant factor.
Minimal Nondeterministic Finite Automata and Atoms of Regular Languages
Venue: arXiv cs.FL 2013
Year: 2013

We examine the NFA minimization problem in terms of atomic NFA's, that is, NFA's in which the right language of every state is a union of atoms, where the atoms of a regular language are non-empty intersections of complemented and uncomplemented left quotients of the language. We characterize all reduced atomic NFA's of a given language, that is, those NFA's that have no equivalent states. Using atomic NFA's, we formalize Sengoku's approach to NFA minimization and prove that his method fails to find all minimal NFA's. We also formulate the Kameda-Weiner NFA minimization in terms of quotients and atoms.
Association between quality of clinical practice guidelines and citations given to their references
Venue: arXiv cs.DL 2013
Year: 2013

It has been suggested that bibliometric analysis of different document types may reveal new aspects of research performance. In medical research a number of study types play different roles in the research process and it has been shown, that the evidence-level of study types is associated with varying citation rates. This study focuses on clinical practice guidelines, which are supposed to gather the highest evidence on a given topic to give the best possible recommendation for practitioners. The quality of clinical practice guidelines, measured using the AGREE score, is compared to the citations given to the references used in these guidelines, as it is hypothesised, that better guidelines are based on higher cited references. AGREE scores are gathered from reviews of clinical practice guidelines on a number of diseases and treatments. Their references are collected from Web of Science and citation counts are normalised using the item-oriented z-score and the PPtop-10% indicators. A positive correlation between both citation indicators and the AGREE score of clinical practice guidelines is found. Some potential confounding factors are identified. While confounding cannot be excluded, results indicate low likelihood for the identified confounders. The results provide a new perspective to and application of citation analysis.
A simple and fast algorithm for computing exponentials of power series
Venue: arXiv cs.SC 2013
Year: 2013

As was initially shown by Brent, exponentials of truncated power series can be computed using a constant number of polynomial multiplications. This note gives a relatively simple algorithm with a low constant factor.
Counting Triangles in Massive Graphs with MapReduce
Venue: arXiv cs.SI 2013
Year: 2013

Graphs and networks are used to model interactions in a variety of contexts. There is a growing need to quickly assess the characteristics of a graph in order to understand its underlying structure. Some of the most useful metrics are triangle-based and give a measure of the connectedness of mutual friends. This is often summarized in terms of clustering coefficients, which measure the likelihood that two neighbors of a node are themselves connected. Computing these measures exactly for large-scale networks is prohibitively expensive in both memory and time. However, a recent wedge sampling algorithm has proved successful in efficiently and accurately estimating clustering coefficients. In this paper, we describe how to implement this approach in MapReduce to deal with massive graphs. We show results on publicly-available networks, the largest of which is 132M nodes and 4.7B edges, as well as artificially generated networks (using the Graph500 benchmark), the largest of which has 240M nodes and 8.5B edges. We can estimate the clustering coefficient by degree bin (e.g., we use exponential binning) and the number of triangles per bin, as well as the global clustering coefficient and total number of triangles, in an average of 0.33 seconds per million edges plus overhead (approximately 225 seconds total for our configuration). The technique can also be used to study triangle statistics such as the ratio of the highest and lowest degree, and we highlight differences between social and non-social networks. To the best of our knowledge, these are the largest triangle-based graph computations published to date.
Computing bounded-width tree and branch decompositions of k-outerplanar graphs
Venue: arXiv cs.DS 2013
Year: 2013

By a well known result the treewidth of k-outerplanar graphs is at most 3k-1. This paper gives, besides a rigorous proof of this fact, an algorithmic implementation of the proof, i.e. it is shown that, given a k-outerplanar graph G, a tree decomposition of G of width at most 3k-1 can be found in O(kn) time and space. Similarly, a branch decomposition of a k-outerplanar graph of width at most 2k+1 can be also obtained in O(kn) time, the algorithm for which is also analyzed.
Resource Allocation and Interference Mitigation Techniques for Cooperative Multi-Antenna and Spread Spectrum Wireless Networks
Venue: arXiv cs.IT 2013
Year: 2013

This chapter presents joint interference suppression and power allocation algorithms for DS-CDMA and MIMO networks with multiple hops and amplify-and-forward and decode-and-forward (DF) protocols. A scheme for joint allocation of power levels across the relays and linear interference suppression is proposed. We also consider another strategy for joint interference suppression and relay selection that maximizes the diversity available in the system. Simulations show that the proposed cross-layer optimization algorithms obtain significant gains in capacity and performance over existing schemes.
BaPu: Efficient and Practical Bunching of Access Point Uplinks
Venue: arXiv cs.NI 2013
Year: 2013

Today's increasing demand for wirelessly uploading a large volume of User Generated Content (UGC) is still significantly limited by the throttled backhaul of residential broadband (typically between 1 and 3Mbps). We propose BaPu, a carefully designed system with implementation for bunching WiFi access points' backhaul to achieve a high aggregated throughput. BaPu is inspired by a decade of networking design principles and techniques to enable efficient TCP over wireless links and multipath. BaPu aims to achieve two major goals:1) requires no client modification for easy incremental adoption; 2) supports not only UDP, but also TCP traffic to greatly extend its applicability to a broad class of popular applications such as HD streaming or large file transfer. We prototyped BaPu with commodity hardware. Our extensive experiments shows that despite TCP's sensitivity to typical channel factors such as high wireless packet loss, out-of-order packets arrivals due to multipath, heterogeneous backhaul capacity, and dynamic delays, BaPu achieves a backhaul aggregation up to 95% of the theoretical maximum throughput for UDP and 88% for TCP. We also empirically estimate the potential idle bandwidth that can be harnessed from residential broadband.
A Tight Lower Bound on the Mutual Information of a Binary and an Arbitrary Finite Random Variable in Dependence of the Variational Distance
Venue: arXiv cs.IT 2013
Year: 2013

In this paper a numerical method is presented, which finds a lower bound for the mutual information between a binary and an arbitrary finite random variable with joint distributions that have a variational distance not greater than a known value to a known joint distribution. This lower bound can be applied to mutual information estimation with confidence intervals.
Confidence Intervals for the Mutual Information
Venue: arXiv cs.IT 2013
Year: 2013

By combining a bound on the absolute value of the difference of mutual information between two joint probablity distributions with a fixed variational distance, and a bound on the probability of a maximal deviation in variational distance between a true joint probability distribution and an empirical joint probability distribution, confidence intervals for the mutual information of two random variables with finite alphabets are established. Different from previous results, these intervals do not need any assumptions on the distribution and the sample size.
Computer Poker Research at LIACC
Venue: arXiv cs.AI 2013
Year: 2013

Computer Poker's unique characteristics present a well-suited challenge for research in artificial intelligence. For that reason, and due to the Poker's market increase in popularity in Portugal since 2008, several members of LIACC have researched in this field. Several works were published as papers and master theses and more recently a member of LIACC engaged on a research in this area as a Ph.D. thesis in order to develop a more extensive and in-depth work. This paper describes the existing research in LIACC about Computer Poker, with special emphasis on the completed master's theses and plans for future work. This paper means to present a summary of the lab's work to the research community in order to encourage the exchange of ideas with other labs / individuals. LIACC hopes this will improve research in this area so as to reach the goal of creating an agent that surpasses the best human players.
Autocorrelation and Linear Complexity of Quaternary Sequences of Period 2p Based on Cyclotomic Classes of Order Four
Venue: arXiv cs.IT 2013
Year: 2013

We examine the linear complexity and the autocorrelation properties of new quaternary cyclotomic sequences of period 2p. The sequences are constructed via the cyclotomic classes of order four.
A Probabilistic Approach to Analysis of Reliability in n-D Meshes with Interconnect Router Failures
Venue: arXiv cs.DC 2013
Year: 2013

The routing algorithms for parallel computers, on-chip networks, multi-core processors, and multiprocessors system-on-chip (MP-SoCs) exhibit router failures must be able to handle interconnect router failures that render a symmetrical mesh non-symmetrically. When developing a routing methodology, the time complexity of calculation should be minimal, and thus complicated routing strategies to introduce profitable paths may not be appropriate. Several reports have been released in the literature on using the concept of fault rings to provide detour paths to messages blocked by faults and to route messages around the fault regions. In order to analyze the performance of such algorithms, it is required to investigate the characteristics of fault rings. In this paper, we introduce a novel performance index of network reliability presenting the probability of message facing fault rings, and evaluating the performance-related reliability of adaptive routing schemes in n-D mesh-based interconnection networks with a variety of common cause fault patterns. Sufficient simulation results of Monte-Carlo method are conducted to demonstrate the correctness of the proposed analytical model.
A Framework for Intelligent Medical Diagnosis using Rough Set with Formal Concept Analysis
Venue: arXiv cs.AI 2013
Year: 2013

Medical diagnosis process vary in the degree to which they attempt to deal with different complicating aspects of diagnosis such as relative importance of symptoms, varied symptom pattern and the relation between diseases them selves. Based on decision theory, in the past many mathematical models such as crisp set, probability distribution, fuzzy set, intuitionistic fuzzy set were developed to deal with complicating aspects of diagnosis. But, many such models are failed to include important aspects of the expert decisions. Therefore, an effort has been made to process inconsistencies in data being considered by Pawlak with the introduction of rough set theory. Though rough set has major advantages over the other methods, but it generates too many rules that create many difficulties while taking decisions. Therefore, it is essential to minimize the decision rules. In this paper, we use two processes such as pre process and post process to mine suitable rules and to explore the relationship among the attributes. In pre process we use rough set theory to mine suitable rules, whereas in post process we use formal concept analysis from these suitable rules to explore better knowledge and most important factors affecting the decision making.
Flaglets: Exact Wavelets on the Ball
Venue: arXiv cs.IT 2013
Year: 2013

We summarise the construction of exact axisymmetric scale-discretised wavelets on the sphere and on the ball. The wavelet transform on the ball relies on a novel 3D harmonic transform called the Fourier-Laguerre transform which combines the spherical harmonic transform with damped Laguerre polynomials on the radial half-line. The resulting wavelets, called flaglets, extract scale-dependent, spatially localised features in three-dimensions while treating the tangential and radial structures separately. Both the Fourier-Laguerre and the flaglet transforms are theoretically exact thanks to a novel sampling theorem on the ball. Our implementation of these methods is publicly available and achieves floating-point accuracy when applied to band-limited signals.
Automated Design of Torus Networks
Venue: arXiv cs.DC 2013
Year: 2013

This paper presents an algorithm to automatically design networks with torus topologies, such as ones widely used in large-scale supercomputers. The characteristic feature of our approach is that real life equipment prices and values of technical characteristics are used. As a result, we also have the opportunity to compare costs of torus and fat-tree networks. The algorithm is useful as a part of a bigger design procedure that selects optimal hardware of cluster supercomputer as a whole.
Multi-Trial Guruswami--Sudan Decoding for Generalised Reed--Solomon Codes
Venue: arXiv cs.IT 2013
Year: 2013

An iterated refinement procedure for the Guruswami--Sudan list decoding algorithm for Generalised Reed--Solomon codes based on Alekhnovich's module minimisation is proposed. The method is parametrisable and allows variants of the usual list decoding approach. In particular, finding the list of \emph{closest} codewords within an intermediate radius can be performed with improved average-case complexity while retaining the worst-case complexity.
Information Loss due to Finite Block Length in a Gaussian Line Network: An Improved Bound
Venue: arXiv cs.IT 2013
Year: 2013

A bound on the maximum information transmission rate through a cascade of Gaussian links is presented. The network model consists of a source node attempting to send a message drawn from a finite alphabet to a sink, through a cascade of Additive White Gaussian Noise links each having an input power constraint. Intermediate nodes are allowed to perform arbitrary encoding/decoding operations, but the block length and the encoding rate are fixed. The bound presented in this paper is fundamental and depends only on the design parameters namely, the network size, block length, transmission rate, and signal-to-noise ratio.
Nested Lattice Codes for Gaussian Two-Way Relay Channels
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we consider a Gaussian two-way relay channel (GTRC), where two sources exchange messages with each other through a relay. We assume that there is no direct link between sources, and all nodes operate in full-duplex mode. By utilizing nested lattice codes for the uplink (i.e., MAC phase), and structured binning for the downlink (i.e., broadcast phase), we propose two achievable schemes. Scheme 1 is based on compute and forward scheme of [1] while scheme 2 utilizes two different lattices for source nodes based on a three-stage lattice partition chain. We show that scheme 2 can achieve capacity region at the high signal-to-noise ratio (SNR). Regardless all channel parameters, the achievable rate of scheme 2 is within 0.2654 bit from the cut-set outer bound for user 1. For user 2, the proposed scheme achieves within 0.167 bit from the outer bound if channel coefficient is larger than one, and achieves within 0.2658 bit from the outer bound if channel coefficient is smaller than one. Moreover, sum rate of the proposed scheme is within 0.334 bits from the sum capacity. These gaps for GTRC are the best gap-to-capacity results to date.
Safety of Deferred Update in Transactional Memory
Venue: arXiv cs.DC 2013
Year: 2013

Transactional memory allows the user to declare sequences of instructions as speculative \emph{transactions} that can either \emph{commit} or \emph{abort}. If a transaction commits, it appears to be executed sequentially, so that the committed transactions constitute a correct sequential execution. If a transaction aborts, none of its instructions can affect other transactions. The popular criterion of \emph{opacity} requires that the views of aborted transactions must also be consistent with the global sequential order constituted by committed ones. This is believed to be important, since inconsistencies observed by an aborted transaction may cause a fatal irrecoverable error or waste of the system in an infinite loop. Intuitively, an opaque implementation must ensure that no intermediate view a transaction obtains before it commits or aborts can be affected by a transaction that has not started committing yet, so called \emph{deferred-update} semantics. In this paper, we intend to grasp this intuition formally. We propose a variant of opacity that explicitly requires the sequential order to respect the deferred-update semantics. We show that our criterion is a safety property, i.e., it is prefix- and limit-closed. Unlike opacity, our property also ensures that a serialization of a history implies serializations of its prefixes. Finally, we show that our property is equivalent to opacity if we assume that no two transactions commit identical values on the same variable, and present a counter-example for scenarios when the "unique-write" assumption does not hold.