OpenRaiser/Intern-Atlas huggingface dataset:
MIMO B-MAC Interference Network Optimization under Rate Constraints by Polite Water-filling and Duality
Venue: arXiv cs.IT 2010
Year: 2010

We take two new approaches to design efficient algorithms for transmitter optimization under rate constraints, to guarantee the Quality of Service in general MIMO interference networks, which is a combination of multiple interfering broadcast channels (BC) and multiaccess channels (MAC) and is named B-MAC Networks. Two related optimization problems, maximizing the minimum of weighted rates under a sum-power constraint and minimizing the sum-power under rate constraints, are considered. The first approach takes advantage of existing efficient algorithms for SINR problems by building a bridge between rate and SINR through the design of optimal mappings between them. The approach can be applied to other optimization problems as well. The second approach employs polite water-filling, which is the optimal network version of water-filling that we recently found. It replaces most generic optimization algorithms currently used for networks and reduces the complexity while demonstrating superior performance even in non-convex cases. Both centralized and distributed algorithms are designed and the performance is analyzed in addition to numeric examples.
Solving Linux Upgradeability Problems Using Boolean Optimization
Venue: arXiv cs.LO 2010
Year: 2010

Managing the software complexity of package-based systems can be regarded as one of the main challenges in software architectures. Upgrades are required on a short time basis and systems are expected to be reliable and consistent after that. For each package in the system, a set of dependencies and a set of conflicts have to be taken into account. Although this problem is computationally hard to solve, efficient tools are required. In the best scenario, the solutions provided should also be optimal in order to better fulfill users requirements and expectations. This paper describes two different tools, both based on Boolean satisfiability (SAT), for solving Linux upgradeability problems. The problem instances used in the evaluation of these tools were mainly obtained from real environments, and are subject to two different lexicographic optimization criteria. The developed tools can provide optimal solutions for many of the instances, but a few challenges remain. Moreover, it is our understanding that this problem has many similarities with other configuration problems, and therefore the same techniques can be used in other domains.
Inflection system of a language as a complex network
Venue: arXiv cs.CL 2010
Year: 2010

We investigate inflection structure of a synthetic language using Latin as an example. We construct a bipartite graph in which one group of vertices correspond to dictionary headwords and the other group to inflected forms encountered in a given text. Each inflected form is connected to its corresponding headword, which in some cases in non-unique. The resulting sparse graph decomposes into a large number of connected components, to be called word groups. We then show how the concept of the word group can be used to construct coverage curves of selected Latin texts. We also investigate a version of the inflection graph in which all theoretically possible inflected forms are included. Distribution of sizes of connected components of this graphs resembles cluster distribution in a lattice percolation near the critical point.
Weighted Automata and Recurrence Equations for Regular Languages
Venue: arXiv cs.FL 2010
Year: 2010

Let $\mathcal{P}(Σ^*)$ be the semiring of languages, and consider its subset $\mathcal{P}(Σ)$. In this paper we define the language recognized by a weighted automaton over $\mathcal{P}(Σ)$ and a one-letter alphabet. Similarly, we introduce the notion of language recognition by linear recurrence equations with coefficients in $\mathcal{P}(Σ)$. As we will see, these two definitions coincide. We prove that the languages recognized by linear recurrence equations with coefficients in $\mathcal{P}(Σ)$ are precisely the regular languages, thus providing an alternative way to present these languages. A remarkable consequence of this kind of recognition is that it induces a partition of the language into its cross-sections, where the $n$th cross-section contains all the words of length $n$ in the language. Finally, we show how to use linear recurrence equations to calculate the density function of a regular language, which assigns to every $n$ the number of words of length $n$ in the language. We also show how to count the number of successful paths of a weighted automaton.
Simple Gradecast Based Algorithms
Venue: arXiv cs.DC 2010
Year: 2010

Gradecast is a simple three-round algorithm presented by Feldman and Micali. The current work presents a very simple algorithm that utilized Gradecast to achieve Byzantine agreement. Two small variations of the presented algorithm lead to improved algorithms for solving the Approximate agreement problem and the Multi-consensus problem. An optimal approximate agreement algorithm was presented by Fekete, which supports up to 1/4 n Byzantine nodes and has message complexity of O(n^k), where n is the number of nodes and k is the number of rounds. Our solution to the approximate agreement problem is optimal, simple and reduces the message complexity to O(k * n^3), while supporting up to 1/3 n Byzantine nodes. Multi consensus was first presented by Bar-Noy et al. It consists of consecutive executions of l Byzantine consensuses. Bar-Noy et al., show an optimal amortized solution to this problem, assuming that all nodes start each consensus instance at the same time, a property that cannot be guaranteed with early stopping. Our solution is simpler, preserves round complexity optimality, allows early stopping and does not require synchronized starts of the consensus instances.
An Alternative Approach of Steganography using Reference Image
Venue: arXiv cs.MM 2010
Year: 2010

This paper is to create a practical steganographic implementation for 4-bit images.The proposed technique converts 4 bit image into 4 shaded Gray Scale image. This image will be act as reference image to hide the text. Using this grey scale reference image any text can be hidden. Single character of a text can be represented by 8-bit. The 8-bit character can be split into 4X2 bit information. If the reference image and the data file are transmitted through network separately, we can achieve the effect of Steganography. Here the image is not at all distorted because said image is only used for referencing. Any huge mount of text material can be hidden using a very small image. Decipher the text is not possible intercepting the image or data file separately. So, it is more secure.
How to Maximize User Satisfaction Degree in Multi-service IP Networks
Venue: arXiv cs.NI 2010
Year: 2010

Bandwidth allocation is a fundamental problem in communication networks. With current network moving towards the Future Internet model, the problem is further intensified as network traffic demanding far from exceeds network bandwidth capability. Maintaining a certain user satisfaction degree therefore becomes a challenge research topic. In this paper, we deal with the problem by proposing BASMIN, a novel bandwidth allocation scheme that aims to maximize network user's happiness. We also defined a new metric for evaluating network user satisfaction degree: network worth. A three-step evaluation process is then conducted to compare BASMIN efficiency with other three popular bandwidth allocation schemes. Throughout the tests, we experienced BASMIN's advantages over the others; we even found out that one of the most widely used bandwidth allocation schemes, in fact, is not effective at all.
Context Ontology Implementation for Smart Home
Venue: arXiv cs.NI 2010
Year: 2010

Context awareness is one of the important fields in ubiquitous computing. Smart Home, a specific instance of ubiquitous computing, provides every family with opportunities to enjoy the power of hi-tech home living. Discovering that relationship among user, activity and context data in home environment is semantic, therefore, we apply ontology to model these relationships and then reason them as the semantic information. In this paper, we present the realization of smart home's context-aware system based on ontology. We discuss the current challenges in realizing the ontology context base. These challenges can be listed as collecting context information from heterogeneous sources, such as devices, agents, sensors into ontology, ontology management, ontology querying, and the issue related to environment database explosion.
A Flexible Patch-Based Lattice Boltzmann Parallelization Approach for Heterogeneous GPU-CPU Clusters
Venue: arXiv cs.DC 2010
Year: 2010

Sustaining a large fraction of single GPU performance in parallel computations is considered to be the major problem of GPU-based clusters. In this article, this topic is addressed in the context of a lattice Boltzmann flow solver that is integrated in the WaLBerla software framework. We propose a multi-GPU implementation using a block-structured MPI parallelization, suitable for load balancing and heterogeneous computations on CPUs and GPUs. The overhead required for multi-GPU simulations is discussed in detail and it is demonstrated that the kernel performance can be sustained to a large extent. With our GPU implementation, we achieve nearly perfect weak scalability on InfiniBand clusters. However, in strong scaling scenarios multi-GPUs make less efficient use of the hardware than IBM BG/P and x86 clusters. Hence, a cost analysis must determine the best course of action for a particular simulation task. Additionally, weak scaling results of heterogeneous simulations conducted on CPUs and GPUs simultaneously are presented using clusters equipped with varying node configurations.
Parallel Bit Interleaved Coded Modulation
Venue: arXiv cs.IT 2010
Year: 2010

A new variant of bit interleaved coded modulation (BICM) is proposed. In the new scheme, called Parallel BICM, L identical binary codes are used in parallel using a mapper, a newly proposed finite-length interleaver and a binary dither signal. As opposed to previous approaches, the scheme does not rely on any assumptions of an ideal, infinite-length interleaver. Over a memoryless channel, the new scheme is proven to be equivalent to a binary memoryless channel. Therefore the scheme enables one to easily design coded modulation schemes using a simple binary code that was designed for that binary channel. The overall performance of the coded modulation scheme is analytically evaluated based on the performance of the binary code over the binary channel. The new scheme is analyzed from an information theoretic viewpoint, where the capacity, error exponent and channel dispersion are considered. The capacity of the scheme is identical to the BICM capacity. The error exponent of the scheme is numerically compared to a recently proposed mismatched-decoding exponent analysis of BICM.
An ICT based solution to make mines safer
Venue: arXiv cs.NI 2010
Year: 2010

Concern for the human security inside mines is as old as the mining itself. However, ICT (Information and communication technologies), which has impacted human life in so many ways has not been much used for making mines safer. We propose a method that has been practically implemented which can enhance mine safety enormously. It is based on integration of wireless sensor network with an external network through a gateway.
A Fault-Resistant Asynchronous Clock Function
Venue: arXiv cs.DC 2010
Year: 2010

Consider an asynchronous network in a shared-memory environment consisting of n nodes. Assume that up to f of the nodes might be Byzantine (n > 12f), where the adversary is full-information and dynamic (sometimes called adaptive). In addition, the non-Byzantine nodes may undergo transient failures. Nodes advance in atomic steps, which consist of reading all registers, performing some calculation and writing to all registers. This paper contains three main contributions. First, the clock-function problem is defined, which is a generalization of the clock synchronization problem. This generalization encapsulates previous clock synchronization problem definitions while extending them to the current paper's model. Second, a randomized asynchronous self-stabilizing Byzantine tolerant clock synchronization algorithm is presented. In the construction of the clock synchronization algorithm, a building block that ensures different nodes advance at similar rates is developed. This feature is the third contribution of the paper. It is self-stabilizing and Byzantine tolerant and can be used as a building block for different algorithms that operate in an asynchronous self-stabilizing Byzantine model. The convergence time of the presented algorithm is exponential. Observe that in the asynchronous setting the best known full-information dynamic Byzantine agreement also has expected exponential convergence time, even though currently there is no known reduction between the two.
Rewritable Codes for Flash Memories Based Upon Lattices, and an Example Using the E8 Lattice
Venue: arXiv cs.IT 2010
Year: 2010

A rewriting code construction for flash memories based upon lattices is described. The values stored in flash cells correspond to lattice points. This construction encodes information to lattice points in such a way that data can be written to the memory multiple times without decreasing the cell values. The construction partitions the flash memory's cubic signal space into blocks. The minimum number of writes is shown to be linear in one of the code parameters. An example using the E8 lattice is given, with numerical results.
Communication Complexity
Venue: arXiv cs.CC 2010
Year: 2010

The first section starts with the basic definitions following mainly the notations of the book written by E. Kushilevitz and N. Nisan. At the end of the first section I examine tree-balancing. In the second section I summarize the well-known lower bound methods and prove the exact complexity of certain functions. In the first part of the third section I introduce the random complexity and prove the basic lemmas about it. In the second part I prove a better lower bound for the complexity of all random functions. In the third part I introduce and compare several upper bounds for the complexity of the identity function. In the fourth section I examine the well-known Direct-sum conjecture. I introduce a different model of computation then prove that it is the same as the original one up to a constant factor. This new model is used to bound the Amortized Time Complexity of a function by the number of the leaves of its protocol-tree. After this I examine the Direct-sum problem in case of Partial Information and in the Random case. In the last section I introduce the well-known hierarchy classes, the reducibility and the completeness of series of functions. Then I define the class PSPACE and Oracles in the communication complexity model and prove some basic claims about them.
LHC Databases on the Grid: Achievements and Open Issues
Venue: arXiv cs.DB 2010
Year: 2010

To extract physics results from the recorded data, the LHC experiments are using Grid computing infrastructure. The event data processing on the Grid requires scalable access to non-event data (detector conditions, calibrations, etc.) stored in relational databases. The database-resident data are critical for the event data reconstruction processing steps and often required for physics analysis. This paper reviews LHC experience with database technologies for the Grid computing. List of topics includes: database integration with Grid computing models of the LHC experiments; choice of database technologies; examples of database interfaces; distributed database applications (data complexity, update frequency, data volumes and access patterns); scalability of database access in the Grid computing environment of the LHC experiments. The review describes areas in which substantial progress was made and remaining open issues.
Faster Replacement Paths
Venue: arXiv cs.DS 2010
Year: 2010

The replacement paths problem for directed graphs is to find for given nodes s and t and every edge e on the shortest path between them, the shortest path between s and t which avoids e. For unweighted directed graphs on n vertices, the best known algorithm runtime was \tilde{O}(n^{2.5}) by Roditty and Zwick. For graphs with integer weights in {-M,...,M}, Weimann and Yuster recently showed that one can use fast matrix multiplication and solve the problem in O(Mn^{2.584}) time, a runtime which would be O(Mn^{2.33}) if the exponent ωof matrix multiplication is 2. We improve both of these algorithms. Our new algorithm also relies on fast matrix multiplication and runs in O(M n^ω polylog(n)) time if ω>2 and O(n^{2+\eps}) for any \eps>0 if ω=2. Our result shows that, at least for small integer weights, the replacement paths problem in directed graphs may be easier than the related all pairs shortest paths problem in directed graphs, as the current best runtime for the latter is Ω(n^{2.5}) time even if ω=2.
Trichotomy and Dichotomy Results on the Complexity of Reasoning with Disjunctive Logic Programs
Venue: arXiv cs.LO 2010
Year: 2010

We present trichotomy results characterizing the complexity of reasoning with disjunctive logic programs. To this end, we introduce a certain definition schema for classes of programs based on a set of allowed arities of rules. We show that each such class of programs has a finite representation, and for each of the classes definable in the schema we characterize the complexity of the existence of an answer set problem. Next, we derive similar characterizations of the complexity of skeptical and credulous reasoning with disjunctive logic programs. Such results are of potential interest. On the one hand, they reveal some reasons responsible for the hardness of computing answer sets. On the other hand, they identify classes of problem instances, for which the problem is "easy" (in P) or "easier than in general" (in NP). We obtain similar results for the complexity of reasoning with disjunctive programs under the supported-model semantics. To appear in Theory and Practice of Logic Programming (TPLP)
A Selection Region Based Routing Protocol for Random Mobile ad hoc Networks
Venue: arXiv cs.IT 2010
Year: 2010

We propose a selection region based multi-hop routing protocol for random mobile ad hoc networks, where the selection region is defined by two parameters: a reference distance and a selection angle. At each hop, a relay is chosen as the nearest node to the transmitter that is located within the selection region. By assuming that the relay nodes are randomly placed, we derive an upper bound for the optimum reference distance to maximize the expected density of progress and investigate the relationship between the optimum selection angle and the optimum reference distance. We also note that the optimized expected density of progress scales as $Θ(\sqrtλ)$, which matches the prior results in the literature. Compared with the spatial-reuse multi-hop protocol in \cite{Baccelli:Aloha} recently proposed by Baccelli \emph{et al.}, in our new protocol the amount of nodes involved and the calculation complexity for each relay selection are reduced significantly, which is attractive for energy-limited wireless ad hoc networks (e.g., wireless sensor networks).
Logic-Based Decision Support for Strategic Environmental Assessment
Venue: arXiv cs.AI 2010
Year: 2010

Strategic Environmental Assessment is a procedure aimed at introducing systematic assessment of the environmental effects of plans and programs. This procedure is based on the so-called coaxial matrices that define dependencies between plan activities (infrastructures, plants, resource extractions, buildings, etc.) and positive and negative environmental impacts, and dependencies between these impacts and environmental receptors. Up to now, this procedure is manually implemented by environmental experts for checking the environmental effects of a given plan or program, but it is never applied during the plan/program construction. A decision support system, based on a clear logic semantics, would be an invaluable tool not only in assessing a single, already defined plan, but also during the planning process in order to produce an optimized, environmentally assessed plan and to study possible alternative scenarios. We propose two logic-based approaches to the problem, one based on Constraint Logic Programming and one on Probabilistic Logic Programming that could be, in the future, conveniently merged to exploit the advantages of both. We test the proposed approaches on a real energy plan and we discuss their limitations and advantages.
A Non-Null Annotation Inferencer for Java Bytecode
Venue: arXiv cs.PL 2010
Year: 2010

We present a non-null annotations inferencer for the Java bytecode language. We previously proposed an analysis to infer non-null annotations and proved it soundness and completeness with respect to a state of the art type system. This paper proposes extensions to our former analysis in order to deal with the Java bytecode language. We have implemented both analyses and compared their behaviour on several benchmarks. The results show a substantial improvement in the precision and, despite being a whole-program analysis, production applications can be analyzed within minutes.
Testing and Debugging Techniques for Answer Set Solver Development
Venue: arXiv cs.AI 2010
Year: 2010

This paper develops automated testing and debugging techniques for answer set solver development. We describe a flexible grammar-based black-box ASP fuzz testing tool which is able to reveal various defects such as unsound and incomplete behavior, i.e. invalid answer sets and inability to find existing solutions, in state-of-the-art answer set solver implementations. Moreover, we develop delta debugging techniques for shrinking failure-inducing inputs on which solvers exhibit defective behavior. In particular, we develop a delta debugging algorithm in the context of answer set solving, and evaluate two different elimination strategies for the algorithm.
Lower Bounds on Query Complexity for Testing Bounded-Degree CSPs
Venue: arXiv cs.DS 2010
Year: 2010

In this paper, we consider lower bounds on the query complexity for testing CSPs in the bounded-degree model. First, for any ``symmetric'' predicate $P:{0,1}^{k} \to {0,1}$ except \equ where $k\geq 3$, we show that every (randomized) algorithm that distinguishes satisfiable instances of CSP(P) from instances $(|P^{-1}(0)|/2^k-ε)$-far from satisfiability requires $Ω(n^{1/2+δ})$ queries where $n$ is the number of variables and $δ>0$ is a constant that depends on $P$ and $ε$. This breaks a natural lower bound $Ω(n^{1/2})$, which is obtained by the birthday paradox. We also show that every one-sided error tester requires $Ω(n)$ queries for such $P$. These results are hereditary in the sense that the same results hold for any predicate $Q$ such that $P^{-1}(1) \subseteq Q^{-1}(1)$. For EQU, we give a one-sided error tester whose query complexity is $\tilde{O}(n^{1/2})$. Also, for 2-XOR (or, equivalently E2LIN2), we show an $Ω(n^{1/2+δ})$ lower bound for distinguishing instances between $ε$-close to and $(1/2-ε)$-far from satisfiability. Next, for the general k-CSP over the binary domain, we show that every algorithm that distinguishes satisfiable instances from instances $(1-2k/2^k-ε)$-far from satisfiability requires $Ω(n)$ queries. The matching NP-hardness is not known, even assuming the Unique Games Conjecture or the $d$-to-$1$ Conjecture. As a corollary, for Maximum Independent Set on graphs with $n$ vertices and a degree bound $d$, we show that every approximation algorithm within a factor $d/\poly\log d$ and an additive error of $εn$ requires $Ω(n)$ queries. Previously, only super-constant lower bounds were known.