OpenRaiser/Intern-Atlas huggingface dataset:
Marvin: A Heuristic Search Planner with Online Macro-Action Learning
Venue: arXiv cs.AI 2011
Year: 2011

This paper describes Marvin, a planner that competed in the Fourth International Planning Competition (IPC 4). Marvin uses action-sequence-memoisation techniques to generate macro-actions, which are then used during search for a solution plan. We provide an overview of its architecture and search behaviour, detailing the algorithms used. We also empirically demonstrate the effectiveness of its features in various planning domains; in particular, the effects on performance due to the use of macro-actions, the novel features of its search behaviour, and the native support of ADL and Derived Predicates.
Cutset Sampling for Bayesian Networks
Venue: arXiv cs.AI 2011
Year: 2011

The paper presents a new sampling methodology for Bayesian networks that samples only a subset of variables and applies exact inference to the rest. Cutset sampling is a network structure-exploiting application of the Rao-Blackwellisation principle to sampling in Bayesian networks. It improves convergence by exploiting memory-based inference algorithms. It can also be viewed as an anytime approximation of the exact cutset-conditioning algorithm developed by Pearl. Cutset sampling can be implemented efficiently when the sampled variables constitute a loop-cutset of the Bayesian network and, more generally, when the induced width of the networks graph conditioned on the observed sampled variables is bounded by a constant w. We demonstrate empirically the benefit of this scheme on a range of benchmarks.
Separation Theorems for Phase-Incoherent Multiple-User Channels
Venue: arXiv cs.IT 2011
Year: 2011

We study the transmission of two correlated and memoryless sources $(U,V)$ over several multiple-user phase asynchronous channels. Namely, we consider a class of phase-incoherent multiple access relay channels (MARC) with both non-causal and causal unidirectional cooperation between encoders, referred to as phase-incoherent unidirectional non-causal cooperative MARC (PI-UNCC-MARC), and phase-incoherent unidirectional causal cooperative MARC (PI-UCC-MARC) respectively. We also consider phase-incoherent interference channels (PI-IC), and interference relay channel (PI-IRC) models in the same context. In all cases, the input signals are assumed to undergo non-ergodic phase shifts due to the channel. The shifts are assumed to be unknown to the transmitters and known to the receivers as a realistic assumption. Both necessary and sufficient conditions in order to reliably send the correlated sources to the destinations over the considered channels are derived. In particular, for all of the channel models, we first derive an outer bound for reliable communication that is defined with respect to the source entropy content (i.e., the triple $(H(U|V),H(V|U),H(U,V))$). Then, using {\em separate} source and channel coding, under specific gain conditions, we establish the same region as the inner bound and therefore obtain tight conditions for reliable communication for the specific channel under study. We thus establish a source-channel separation theorem for each channel and conclude that without the knowledge of the phase shifts at the transmitter sides, separation is optimal. It is further conjectured that separation in general is optimal for all channel coefficients.
Web-Based Multi-View Visualizations for Aggregated Statistics
Venue: arXiv cs.HC 2011
Year: 2011

With the rise of the open data movement a lot of statistical data has been made publicly available by governments, statistical offices and other organizations. First efforts to visualize are made by the data providers themselves. Data aggregators go a step beyond: they collect data from different open data repositories and make them comparable by providing data sets from different providers and showing different statistics in the same chart. Another approach is to visualize two different indicators in a scatter plot or on a map. The integration of several data sets in one graph can have several drawbacks: different scales and units are mixed, the graph gets visually cluttered and one cannot easily distinguish between different indicators. Our approach marks a combination of (1) the integration of live data from different data sources, (2) presenting different indicators in coordinated visualizations and (3) allows adding user visualizations to enrich official statistics with personal data. Each indicator gets its own visualization, which fits best for the individual indicator in case of visualization type, scale, unit etc. The different visualizations are linked, so that related items can easily be identified by using mouse over effects on data items.
Rainbow connections for planar graphs and line graphs
Venue: arXiv cs.CC 2011
Year: 2011

An edge-colored graph $G$ is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a connected graph $G$, denoted by $rc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow connected. It was proved that computing $rc(G)$ is an NP-Hard problem, as well as that even deciding whether a graph has $rc(G)=2$ is NP-Complete. It is known that deciding whether a given edge-colored graph is rainbow connected is NP-Complete. We will prove that it is still NP-Complete even when the edge-colored graph is a planar bipartite graph. We also give upper bounds of the rainbow connection number of outerplanar graphs with small diameters. A vertex-colored graph is rainbow vertex-connected if any two vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex-connection number of a connected graph $G$, denoted by $rvc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow vertex-connected. It is known that deciding whether a given vertex-colored graph is rainbow vertex-connected is NP-Complete. We will prove that it is still NP-Complete even when the vertex-colored graph is a line graph.
On a Class of Quadratic Polynomials with no Zeros and its Application to APN Functions
Venue: arXiv cs.IT 2011
Year: 2011

We show that the there exists an infinite family of APN functions of the form $F(x)=x^{2^{s}+1} + x^{2^{k+s}+2^k} + cx^{2^{k+s}+1} + c^{2^k}x^{2^k + 2^s} + δx^{2^{k}+1}$, over $\gf_{2^{2k}}$, where $k$ is an even integer and $\gcd(2k,s)=1, 3\nmid k$. This is actually a proposed APN family of Lilya Budaghyan and Claude Carlet who show in \cite{carlet-1} that the function is APN when there exists $c$ such that the polynomial $y^{2^s+1}+cy^{2^s}+c^{2^k}y+1=0$ has no solutions in the field $\gf_{2^{2k}}$. In \cite{carlet-1} they demonstrate by computer that such elements $c$ can be found over many fields, particularly when the degree of the field is not divisible by 3. We show that such $c$ exists when $k$ is even and $3\nmid k$ (and demonstrate why the $k$ odd case only re-describes an existing family of APN functions). The form of these coefficients is given so that we may write the infinite family of APN functions.
Secure Hybrid Digital-Analog Coding With Side Information at the Receiver
Venue: arXiv cs.IT 2011
Year: 2011

In this work, the problem of transmitting an i.i.d Gaussian source over an i.i.d Gaussian wiretap channel with an i.i.d Gaussian side information available at the intended receiver is considered. The intended receiver is assumed to have a certain minimum SNR and the eavesdropper is assumed to have a strictly lower SNR, compared to the intended receiver. The objective is to minimize the distortion of source reconstruction at the intended receiver. In this work, it is shown that the source-channel separation coding scheme is optimum in the sense of achieving minimum distortion. Two hybrid digital-analog Wyner-Ziv coding schemes are then proposed which achieve the minimum distortion. These secure joint source-channel coding schemes are based on the Wyner-Ziv coding scheme and wiretap channel coding scheme when the analog source is not explicitly quantized. The proposed secure hybrid digital-analog schemes are analyzed under the main channel SNR mismatch. It is proven that the proposed schemes can give a graceful degradation of distortion with SNR under SNR mismatch, i.e., when the actual SNR is larger than the designed SNR.
Identifying Reference Objects by Hierarchical Clustering in Java Environment
Venue: arXiv cs.SE 2011
Year: 2011

Recently Java programming environment has become so popular. Java programming language is a language that is designed to be portable enough to be executed in wide range of computers ranging from cell phones to supercomputers. Computer programs written in Java are compiled into Java Byte code instructions that are suitable for execution by a Java Virtual Machine implementation. Java virtual Machine is commonly implemented in software by means of an interpreter for the Java Virtual Machine instruction set. As an object oriented language, Java utilizes the concept of objects. Our idea is to identify the candidate objects' references in a Java environment through hierarchical cluster analysis using reference stack and execution stack.
X-ray view on a Class using Conceptual Analysis in Java Environment
Venue: arXiv cs.SE 2011
Year: 2011

Modularity is one of the most important principles in software engineering and a necessity for every practical software. Since the design space of software is generally quite large, it is valuable to provide automatic means to help modularizing it. An automatic technique for software modularization is object- oriented concept analysis (OOCA). X-ray view of the class is one of the aspect of this Object oriented concept analysis. We shall use this concept in a java environment.
Regime Change: Bit-Depth versus Measurement-Rate in Compressive Sensing
Venue: arXiv cs.IT 2011
Year: 2011

The recently introduced compressive sensing (CS) framework enables digital signal acquisition systems to take advantage of signal structures beyond bandlimitedness. Indeed, the number of CS measurements required for stable reconstruction is closer to the order of the signal complexity than the Nyquist rate. To date, the CS theory has focused on real-valued measurements, but in practice, measurements are mapped to bits from a finite alphabet. Moreover, in many potential applications the total number of measurement bits is constrained, which suggests a tradeoff between the number of measurements and the number of bits per measurement. We study this situation in this paper and show that there exist two distinct regimes of operation that correspond to high/low signal-to-noise ratio (SNR). In the measurement compression (MC) regime, a high SNR favors acquiring fewer measurements with more bits per measurement; in the quantization compression (QC) regime, a low SNR favors acquiring more measurements with fewer bits per measurement. A surprise from our analysis and experiments is that in many practical applications it is better to operate in the QC regime, even acquiring as few as 1 bit per measurement.
Information, learning and falsification
Venue: arXiv cs.IT 2011
Year: 2011

There are (at least) three approaches to quantifying information. The first, algorithmic information or Kolmogorov complexity, takes events as strings and, given a universal Turing machine, quantifies the information content of a string as the length of the shortest program producing it. The second, Shannon information, takes events as belonging to ensembles and quantifies the information resulting from observing the given event in terms of the number of alternate events that have been ruled out. The third, statistical learning theory, has introduced measures of capacity that control (in part) the expected risk of classifiers. These capacities quantify the expectations regarding future data that learning algorithms embed into classifiers. This note describes a new method of quantifying information, effective information, that links algorithmic information to Shannon information, and also links both to capacities arising in statistical learning theory. After introducing the measure, we show that it provides a non-universal analog of Kolmogorov complexity. We then apply it to derive basic capacities in statistical learning theory: empirical VC-entropy and empirical Rademacher complexity. A nice byproduct of our approach is an interpretation of the explanatory power of a learning algorithm in terms of the number of hypotheses it falsifies, counted in two different ways for the two capacities. We also discuss how effective information relates to information gain, Shannon and mutual information.
Performance Measurement of the Heterogeneous Network
Venue: arXiv cs.NI 2011
Year: 2011

Till today we dreamt of imperceptible delay in a network. The computer science research grows today faster than ever offering more and more services (computational representational, graphical, intelligent implication etc) to its user. But the problem lies in "greater the volume of services greater the problem of delay". So tracing delay, or performance analysis focusing on time required for computation, in a existing or newly configured network is necessary to conclude the improvement. In this paper, we have done the job of delay analysis in a multi-server system,. For this proposed work we have used continuous -parameter Markov chains (Non -Birth -Death Process),for developing the required models, and for developing the simulator we have used queuing networking, different scheduling algorithms at the servers queue and process scheduling . The work can be further extended to test the performance of wireless domain.
Anti-sparse coding for approximate nearest neighbor search
Venue: arXiv cs.CV 2011
Year: 2011

This paper proposes a binarization scheme for vectors of high dimension based on the recent concept of anti-sparse coding, and shows its excellent performance for approximate nearest neighbor search. Unlike other binarization schemes, this framework allows, up to a scaling factor, the explicit reconstruction from the binary representation of the original vector. The paper also shows that random projections which are used in Locality Sensitive Hashing algorithms, are significantly outperformed by regular frames for both synthetic and real data if the number of bits exceeds the vector dimensionality, i.e., when high precision is required.
On the Power of Adaptivity in Sparse Recovery
Venue: arXiv cs.DS 2011
Year: 2011

The goal of (stable) sparse recovery is to recover a $k$-sparse approximation $x*$ of a vector $x$ from linear measurements of $x$. Specifically, the goal is to recover $x*$ such that ||x-x*||_p <= C min_{k-sparse x'} ||x-x'||_q for some constant $C$ and norm parameters $p$ and $q$. It is known that, for $p=q=1$ or $p=q=2$, this task can be accomplished using $m=O(k \log (n/k))$ non-adaptive measurements [CRT06] and that this bound is tight [DIPW10,FPRU10,PW11]. In this paper we show that if one is allowed to perform measurements that are adaptive, then the number of measurements can be considerably reduced. Specifically, for $C=1+eps$ and $p=q=2$ we show - A scheme with $m=O((1/eps)k log log (n eps/k))$ measurements that uses $O(log* k \log \log (n eps/k))$ rounds. This is a significant improvement over the best possible non-adaptive bound. - A scheme with $m=O((1/eps) k log (k/eps) + k \log (n/k))$ measurements that uses /two/ rounds. This improves over the best possible non-adaptive bound. To the best of our knowledge, these are the first results of this type. As an independent application, we show how to solve the problem of finding a duplicate in a data stream of $n$ items drawn from ${1, 2, ..., n-1}$ using $O(log n)$ bits of space and $O(log log n)$ passes, improving over the best possible space complexity achievable using a single pass.
Constructing and Counting Even-Variable Symmetric Boolean Functions with Algebraic Immunity not Less Than $d$
Venue: arXiv cs.CR 2011
Year: 2011

In this paper, we explicitly construct a large class of symmetric Boolean functions on $2k$ variables with algebraic immunity not less than $d$, where integer $k$ is given arbitrarily and $d$ is a given suffix of $k$ in binary representation. If let $d = k$, our constructed functions achieve the maximum algebraic immunity. Remarkably, $2^{\lfloor \log_2{k} \rfloor + 2}$ symmetric Boolean functions on $2k$ variables with maximum algebraic immunity are constructed, which is much more than the previous constructions. Based on our construction, a lower bound of symmetric Boolean functions with algebraic immunity not less than $d$ is derived, which is $2^{\lfloor \log_2{d} \rfloor + 2(k-d+1)}$. As far as we know, this is the first lower bound of this kind.
GTRACE-RS: Efficient Graph Sequence Mining using Reverse Search
Venue: arXiv cs.DB 2011
Year: 2011

The mining of frequent subgraphs from labeled graph data has been studied extensively. Furthermore, much attention has recently been paid to frequent pattern mining from graph sequences. A method, called GTRACE, has been proposed to mine frequent patterns from graph sequences under the assumption that changes in graphs are gradual. Although GTRACE mines the frequent patterns efficiently, it still needs substantial computation time to mine the patterns from graph sequences containing large graphs and long sequences. In this paper, we propose a new version of GTRACE that enables efficient mining of frequent patterns based on the principle of a reverse search. The underlying concept of the reverse search is a general scheme for designing efficient algorithms for hard enumeration problems. Our performance study shows that the proposed method is efficient and scalable for mining both long and large graph sequence patterns and is several orders of magnitude faster than the original GTRACE.
Handling controversial arguments by matrix
Venue: arXiv cs.AI 2011
Year: 2011

We introduce matrix and its block to the Dung's theory of argumentation framework. It is showed that each argumentation framework has a matrix representation, and the indirect attack relation and indirect defence relation can be characterized by computing the matrix. This provide a powerful mathematics way to determine the "controversial arguments" in an argumentation framework. Also, we introduce several kinds of blocks based on the matrix, and various prudent semantics of argumentation frameworks can all be determined by computing and comparing the matrices and their blocks which we have defined. In contrast with traditional method of directed graph, the matrix method has an excellent advantage: computability(even can be realized on computer easily). So, there is an intensive perspective to import the theory of matrix to the research of argumentation frameworks and its related areas.
Parallel Algorithms for DNA Probe Placement on Small Oligonucleotide Arrays
Venue: arXiv cs.ET 2011
Year: 2011

Oligonucleotide arrays are used in a wide range of genomic analyses, such as gene expression profiling, comparative genomic hybridization, chromatin immunoprecipitation, SNP detection, etc. During fabrication, the sites of an oligonucleotide array are selectively exposed to light in order to activate oligonucleotides for further synthesis. Optical effects can cause unwanted illumination at masked sites that are adjacent to the sites intentionally exposed to light. This results in synthesis of unforeseen sequences in masked sites and compromises interpretation of experimental data. To reduce such uncertainty, one can exploit freedom in how probes are assigned to array sites. The border length minimization problem (BLMP) seeks a placement of probes that minimizes the sum of border lengths in all masks. In this paper, we propose two parallel algorithms for the BLMP. The proposed parallel algorithms have the local-search paradigm at their core, and are especially developed for the BLMP. The results reported show that, for small microarrays with at most 1156 probes, the proposed parallel algorithms perform better than the best previous algorithms.
Joint Scheduling and Resource Allocation in OFDMA Downlink Systems via ACK/NAK Feedback
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we consider the problem of joint scheduling and resource allocation in the OFDMA downlink, with the goal of maximizing an expected long-term goodput-based utility subject to an instantaneous sum-power constraint, and where the feedback to the base station consists only of ACK/NAKs from recently scheduled users. We first establish that the optimal solution is a partially observable Markov decision process (POMDP), which is impractical to implement. In response, we propose a greedy approach to joint scheduling and resource allocation that maintains a posterior channel distribution for every user, and has only polynomial complexity. For frequency-selective channels with Markov time-variation, we then outline a recursive method to update the channel posteriors, based on the ACK/NAK feedback, that is made computationally efficient through the use of particle filtering. To gauge the performance of our greedy approach relative to that of the optimal POMDP, we derive a POMDP performance upper-bound. Numerical experiments show that, for slowly fading channels, the performance of our greedy scheme is relatively close to the upper bound, and much better than fixed-power random user scheduling (FP-RUS), despite its relatively low complexity.
Declarative Event-Based Workflow as Distributed Dynamic Condition Response Graphs
Venue: arXiv cs.LO 2011
Year: 2011

We present Dynamic Condition Response Graphs (DCR Graphs) as a declarative, event-based process model inspired by the workflow language employed by our industrial partner and conservatively generalizing prime event structures. A dynamic condition response graph is a directed graph with nodes representing the events that can happen and arrows representing four relations between events: condition, response, include, and exclude. Distributed DCR Graphs is then obtained by assigning roles to events and principals. We give a graphical notation inspired by related work by van der Aalst et al. We exemplify the use of distributed DCR Graphs on a simple workflow taken from a field study at a Danish hospital, pointing out their flexibility compared to imperative workflow models. Finally we provide a mapping from DCR Graphs to Buchi-automata.
Session Type Inference in Haskell
Venue: arXiv cs.PL 2011
Year: 2011

We present an inference system for a version of the Pi-calculus in Haskell for the session type proposed by Honda et al. The session type is very useful in checking if the communications are well-behaved. The full session type implementation in Haskell was first presented by Pucella and Tov, which is 'semi-automatic' in that the manual operations for the type representation was necessary. We give an automatic type inference for the session type by using a more abstract representation for the session type based on the 'de Bruijn levels'. We show an example of the session type inference for a simple SMTP client.
The Price of Anarchy (POA) of network coding and routing based on average pricing mechanism
Venue: arXiv cs.NI 2011
Year: 2011

The congestion pricing is an efficient allocation approach to mediate demand and supply of network resources. Different from the previous pricing using Affine Marginal Cost (AMC), we focus on studying the game between network coding and routing flows sharing a single link when users are price anticipating based on an Average Cost Sharing (ACS) pricing mechanism. We characterize the worst-case efficiency bounds of the game compared with the optimal, i.e., the price-of anarchy (POA), which can be low bound 50% with routing only. When both network coding and routing are applied, the POA can be as low as 4/9. Therefore, network coding cannot improve the POA significantly under the ACS. Moreover, for more efficient use of limited resources, it indicates the sharing users have a higher tendency to choose network coding.