OpenRaiser/Intern-Atlas huggingface dataset:
Faster Information Dissemination in Dynamic Networks via Network Coding
Venue: arXiv cs.DS 2011
Year: 2011

We use network coding to improve the speed of distributed computation in the dynamic network model of Kuhn, Lynch and Oshman [STOC '10]. In this model an adversary adaptively chooses a new network topology in every round, making even basic distributed computations challenging. Kuhn et al. show that n nodes, each starting with a d-bit token, can broadcast them to all nodes in time O(n^2) using b-bit messages, where b > d + log n. Their algorithms take the natural approach of {token forwarding}: in every round each node broadcasts some particular token it knows. They prove matching Omega(n^2) lower bounds for a natural class of token forwarding algorithms and an Omega(n log n) lower bound that applies to all token-forwarding algorithms. We use network coding, transmitting random linear combinations of tokens, to break both lower bounds. Our algorithm's performance is quadratic in the message size b, broadcasting the n tokens in roughly d/b^2 * n^2 rounds. For b = d = O(log n) our algorithms use O(n^2/log n) rounds, breaking the first lower bound, while for larger message sizes we obtain linear-time algorithms. We also consider networks that change only every T rounds, and achieve an additional factor T^2 speedup. This contrasts with related lower and upper bounds of Kuhn et al. implying that for natural token-forwarding algorithms a speedup of T, but not more, can be obtained. Lastly, we give a general way to derandomize random linear network coding, that also leads to new deterministic information dissemination algorithms.
Idealized Dynamic Population Sizing for Uniformly Scaled Problems
Venue: arXiv cs.NE 2011
Year: 2011

This paper explores an idealized dynamic population sizing strategy for solving additive decomposable problems of uniform scale. The method is designed on top of the foundations of existing population sizing theory for this class of problems, and is carefully compared with an optimal fixed population sized genetic algorithm. The resulting strategy should be close to a lower bound in terms of what can be achieved, performance-wise, by self-adjusting population sizing algorithms for this class of problems.
A counterexample to Beck's conjecture on the discrepancy of three permutations
Venue: arXiv cs.DM 2011
Year: 2011

Given three permutations on the integers 1 through n, consider the set system consisting of each interval in each of the three permutations. Jozsef Beck conjectured (c. 1987) that the discrepancy of this set system is O(1). We give a counterexample to this conjecture: for any positive integer n = 3^k, we exhibit three permutations whose corresponding set system has discrepancy Omega(log(n)). Our counterexample is based on a simple recursive construction, and our proof of the discrepancy lower bound is by induction. This example also disproves a generalization of Beck's conjecture due to Spencer, Srinivasan and Tetali, who conjectured that a set system corresponding to l permutations has discrepancy O(sqrt(l)).
Global Computation in a Poorly Connected World: Fast Rumor Spreading with No Dependence on Conductance
Venue: arXiv cs.DM 2011
Year: 2011

In this paper, we study the question of how efficiently a collection of interconnected nodes can perform a global computation in the widely studied GOSSIP model of communication. In this model, nodes do not know the global topology of the network, and they may only initiate contact with a single neighbor in each round. This model contrasts with the much less restrictive LOCAL model, where a node may simultaneously communicate with all of its neighbors in a single round. A basic question in this setting is how many rounds of communication are required for the information dissemination problem, in which each node has some piece of information and is required to collect all others. In this paper, we give an algorithm that solves the information dissemination problem in at most $O(D+\text{polylog}{(n)})$ rounds in a network of diameter $D$, withno dependence on the conductance. This is at most an additive polylogarithmic factor from the trivial lower bound of $D$, which applies even in the LOCAL model. In fact, we prove that something stronger is true: any algorithm that requires $T$ rounds in the LOCAL model can be simulated in $O(T +\mathrm{polylog}(n))$ rounds in the GOSSIP model. We thus prove that these two models of distributed computation are essentially equivalent.
Parallel Recursive State Compression for Free
Venue: arXiv cs.DS 2011
Year: 2011

This paper focuses on reducing memory usage in enumerative model checking, while maintaining the multi-core scalability obtained in earlier work. We present a tree-based multi-core compression method, which works by leveraging sharing among sub-vectors of state vectors. An algorithmic analysis of both worst-case and optimal compression ratios shows the potential to compress even large states to a small constant on average (8 bytes). Our experiments demonstrate that this holds up in practice: the median compression ratio of 279 measured experiments is within 17% of the optimum for tree compression, and five times better than the median compression ratio of SPIN's COLLAPSE compression. Our algorithms are implemented in the LTSmin tool, and our experiments show that for model checking, multi-core tree compression pays its own way: it comes virtually without overhead compared to the fastest hash table-based methods.
Automatic Optimization for MapReduce Programs
Venue: arXiv cs.DB 2011
Year: 2011

The MapReduce distributed programming framework has become popular, despite evidence that current implementations are inefficient, requiring far more hardware than a traditional relational databases to complete similar tasks. MapReduce jobs are amenable to many traditional database query optimizations (B+Trees for selections, column-store- style techniques for projections, etc), but existing systems do not apply them, substantially because free-form user code obscures the true data operation being performed. For example, a selection in SQL is easily detected, but a selection in a MapReduce program is embedded in Java code along with lots of other program logic. We could ask the programmer to provide explicit hints about the program's data semantics, but one of MapReduce's attractions is precisely that it does not ask the user for such information. This paper covers Manimal, which automatically analyzes MapReduce programs and applies appropriate data- aware optimizations, thereby requiring no additional help at all from the programmer. We show that Manimal successfully detects optimization opportunities across a range of data operations, and that it yields speedups of up to 1,121% on previously-written MapReduce programs.
Affine trajectory correction for nonholonomic mobile robots
Venue: arXiv cs.RO 2011
Year: 2011

Planning trajectories for nonholonomic systems is difficult and computationally expensive. When facing unexpected events, it may therefore be preferable to deform in some way the initially planned trajectory rather than to re-plan entirely a new one. We suggest here a method based on affine transformations to make such deformations. This method is exact and fast: the deformations and the resulting trajectories can be computed algebraically, in one step, and without any trajectory re-integration. To demonstrate the possibilities offered by this new method, we use it to derive position and orientation correction algorithms for the general class of planar wheeled robots and for a tridimensional underwater vehicle. These algorithms allow in turn achieving more complex applications, including obstacle avoidance, feedback control or gap filling for sampling-based kinodynamic planners.
Quantum Interaction Approach in Cognition, Artificial Intelligence and Robotics
Venue: arXiv cs.AI 2011
Year: 2011

The mathematical formalism of quantum mechanics has been successfully employed in the last years to model situations in which the use of classical structures gives rise to problematical situations, and where typically quantum effects, such as 'contextuality' and 'entanglement', have been recognized. This 'Quantum Interaction Approach' is briefly reviewed in this paper focusing, in particular, on the quantum models that have been elaborated to describe how concepts combine in cognitive science, and on the ensuing identification of a quantum structure in human thought. We point out that these results provide interesting insights toward the development of a unified theory for meaning and knowledge formalization and representation. Then, we analyze the technological aspects and implications of our approach, and a particular attention is devoted to the connections with symbolic artificial intelligence, quantum computation and robotics.
Probabilistic Analysis of Loss in Interface Adapter Chaining
Venue: arXiv cs.SE 2011
Year: 2011

Interface adapters allow applications written for one interface to be reused with another interface without having to rewrite application code, and chaining interface adapters can significantly reduce the development effort required to create the adapters. However, interface adapters will often be unable to convert interfaces perfectly, so there must be a way to analyze the loss from interface adapter chains in order to improve the quality of interface adaptation. This paper describes a probabilistic approach to analyzing loss in interface adapter chains, which not only models whether a method can be adapted but also how well methods can be adapted. We also show that probabilistic optimal adapter chaining is an NP-complete problem, so we describe a greedy algorithm which can construct an optimal interface adapter chain with exponential time in the worst case.
Clean relaying aided cognitive radio under the coexistence constraint
Venue: arXiv cs.IT 2011
Year: 2011

We consider the interference-mitigation based cognitive radio where the primary and secondary users can coexist at the same time and frequency bands, under the constraint that the rate of the primary user (PU) must remain the same with a single-user decoder. To meet such a coexistence constraint, the relaying from the secondary user (SU) can help the PU's transmission under the interference from the SU. However, the relayed signal in the known dirty paper coding (DPC) based scheme is interfered by the SU's signal, and is not "clean". In this paper, under the half-duplex constraints, we propose two new transmission schemes aided by the clean relaying from the SU's transmitter and receiver without interference from the SU. We name them as the clean transmitter relaying (CT) and clean transmitter-receiver relaying (CTR) aided cognitive radio, respectively. The rate and multiplexing gain performances of CT and CTR in fading channels with various availabilities of the channel state information at the transmitters (CSIT) are studied. Our CT generalizes the celebrated DPC based scheme proposed previously. With full CSIT, the multiplexing gain of the CTR is proved to be better (or no less) than that of the previous DPC based schemes. This is because the silent period for decoding the PU's messages for the DPC may not be necessary in the CTR. With only the statistics of CSIT, we further prove that the CTR outperforms the rate performance of the previous scheme in fast Rayleigh fading channels. The numerical examples also show that in a large class of channels, the proposed CT and CTR provide significant rate gains over the previous scheme with small complexity penalties.
How to Achieve Privacy in Bidirectional Relay Networks
Venue: arXiv cs.IT 2011
Year: 2011

Recent research developments show that the concept of bidirectional relaying significantly improves the performance in wireless networks. This applies to three-node networks, where a half-duplex relay node establishes a bidirectional communication between two other nodes using a decode-and-forward protocol. In this work we consider the scenario when in the broadcast phase the relay transmits additional confidential information to one node, which should be kept as secret as possible from the other, non-intended node. This is the bidirectional broadcast channel with confidential messages for which we derive the capacityequivocation region and the secrecy capacity region. The latter characterizes the communication scenario with perfect secrecy, where the confidential message is completely hidden from the non-legitimated node.
IUPC: Identification and Unification of Process Constraints
Venue: arXiv cs.FL 2011
Year: 2011

Business Process Compliance (BPC) has gained significant momentum in research and practice during the last years. Although many approaches address BPC, they mostly assume the existence of some kind of unified base of process constraints and focus on their verification over the business processes. However, it remains unclear how such an inte- grated process constraint base can be built up, even though this con- stitutes the essential prerequisite for all further compliance checks. In addition, the heterogeneity of process constraints has been neglected so far. Without identification and separation of process constraints from domain rules as well as unification of process constraints, the success- ful IT support of BPC will not be possible. In this technical report we introduce a unified representation framework that enables the identifica- tion of process constraints from domain rules and their later unification within a process constraint base. Separating process constraints from domain rules can lead to significant reduction of compliance checking effort. Unification enables consistency checks and optimizations as well as maintenance and evolution of the constraint base on the other side.
A Large Family of Multi-path Dual Congestion Control Algorithms
Venue: arXiv cs.NI 2011
Year: 2011

The goal of traffic management is efficiently utilizing network resources via adapting of source sending rates and routes selection. Traditionally, this problem is formulated into a utilization maximization problem. The single-path routing scheme fails to react to instantaneous network congestion. Multi-path routing schemes thus have been proposed aiming at improving network efficiency. Unfortunately, the natural optimization problem to consider is concave but not strictly concave. It thus brings a huge challenge to design stable multi-path congestion control algorithms. In this paper, we propose a generalized multi-path utility maximization model to consider the problem of routes selection and flow control, and derive a family of multi-path dual congestion control algorithms. We show that the proposed algorithms are stable in the absence of delays. We also derive decentralized and scalable sufficient conditions for a particular scheme when propagation delays exist in networks. Simulations are implemented using both Matlab and NS2, on which evaluation of the proposed multi-path dual algorithms is exerted. The comparison results, between the proposed algorithms and the other two existing algorithms, show that the proposed multi-path dual algorithms with appropriate parameter settings can achieve a stable aggregated throughput while maintaining fairness among the involved users.
An Unmanned Aerial Vehicle as Human-Assistant Robotics System
Venue: arXiv cs.RO 2011
Year: 2011

According to the American Heritage Dictionary [1],Robotics is the science or study of the technology associated with the design, fabrication, theory, and application of Robots. The term Hoverbot is also often used to refer to sophisticated mechanical devices that are remotely controlled by human beings even though these devices are not autonomous. This paper describes a remotely controlled hoverbot by installing a transmitter and receiver on both sides that is the control computer (PC) and the hoverbot respectively. Data is transmitted as signal or instruction via a infrastructure network which is converted into a command for the hoverbot that operates at a remote site.
Inapproximability of NP-Complete Variants of Nash Equilibrium
Venue: arXiv cs.CC 2011
Year: 2011

In recent work of Hazan and Krauthgamer (SICOMP 2011), it was shown that finding an $\eps$-approximate Nash equilibrium with near-optimal value in a two-player game is as hard as finding a hidden clique of size $O(\log n)$ in the random graph $G(n,1/2)$. This raises the question of whether a similar intractability holds for approximate Nash equilibrium without such constraints. We give evidence that the constraint of near-optimal value makes the problem distinctly harder: a simple algorithm finds an optimal 1/2-approximate equilibrium, while finding strictly better than 1/2-approximate equilibria is as hard as the Hidden Clique problem. This is in contrast to the unconstrained problem where more sophisticated algorithms, achieving better approximations, are known. Unlike general Nash equilibrium, which is in PPAD, optimal (maximum value) Nash equilibrium is NP-hard. We proceed to show that optimal Nash equilibrium is just one of several known NP-hard problems related to Nash equilibrium, all of which have approximate variants which are as hard as finding a planted clique. In particular, we show this for approximate variants of the following problems: finding a Nash equilibrium with value greater than $η$ (for any $η>0$, even when the best Nash equilibrium has value $1-η$), finding a second Nash equilibrium, and finding a Nash equilibrium with small support. Finally, we consider the complexity of approximate pure Bayes Nash equilibria in two-player games. Here we show that for general Bayesian games the problem is NP-hard. For the special case where the distribution over types is uniform, we give a quasi-polynomial time algorithm matched by a hardness result based on the Hidden Clique problem.
Fast matrix computations for pair-wise and column-wise commute times and Katz scores
Venue: arXiv cs.SI 2011
Year: 2011

We first explore methods for approximating the commute time and Katz score between a pair of nodes. These methods are based on the approach of matrices, moments, and quadrature developed in the numerical linear algebra community. They rely on the Lanczos process and provide upper and lower bounds on an estimate of the pair-wise scores. We also explore methods to approximate the commute times and Katz scores from a node to all other nodes in the graph. Here, our approach for the commute times is based on a variation of the conjugate gradient algorithm, and it provides an estimate of all the diagonals of the inverse of a matrix. Our technique for the Katz scores is based on exploiting an empirical localization property of the Katz matrix. We adopt algorithms used for personalized PageRank computing to these Katz scores and theoretically show that this approach is convergent. We evaluate these methods on 17 real world graphs ranging in size from 1000 to 1,000,000 nodes. Our results show that our pair-wise commute time method and column-wise Katz algorithm both have attractive theoretical properties and empirical performance.
Information Exchange Limits in Cooperative MIMO Networks
Venue: arXiv cs.IT 2011
Year: 2011

Concurrent presence of inter-cell and intra-cell interferences constitutes a major impediment to reliable downlink transmission in multi-cell multiuser networks. Harnessing such interferences largely hinges on two levels of information exchange in the network: one from the users to the base-stations (feedback) and the other one among the base-stations (cooperation). We demonstrate that exchanging a finite number of bits across the network, in the form of feedback and cooperation, is adequate for achieving the optimal capacity scaling. We also show that the average level of information exchange is independent of the number of users in the network. This level of information exchange is considerably less than that required by the existing coordination strategies which necessitate exchanging infinite bits across the network for achieving the optimal sum-rate capacity scaling. The results provided rely on a constructive proof.
General Iteration graphs and Boolean automata circuits
Venue: arXiv cs.DM 2011
Year: 2011

This article is set in the field of regulation networks modeled by discrete dynamical systems. It focuses on Boolean automata networks. In such networks, there are many ways to update the states of every element. When this is done deterministically, at each time step of a discretised time flow and according to a predefined order, we say that the network is updated according to block-sequential update schedule (blocks of elements are updated sequentially while, within each block, the elements are updated synchronously). Many studies, for the sake of simplicity and with some biologically motivated reasons, have concentrated on networks updated with one particular block-sequential update schedule (more often the synchronous/parallel update schedule or the sequential update schedules). The aim of this paper is to give an argument formally proven and inspired by biological considerations in favour of the fact that the choice of a particular update schedule does not matter so much in terms of the possible and likely dynamical behaviours that networks may display.
Laminar Families and Metric Embeddings: Non-bipartite Maximum Matching Problem in the Semi-Streaming Model
Venue: arXiv cs.DS 2011
Year: 2011

In this paper, we study the non-bipartite maximum matching problem in the semi-streaming model. The maximum matching problem in the semi-streaming model has received a significant amount of attention lately. While the problem has been somewhat well solved for bipartite graphs, the known algorithms for non-bipartite graphs use $2^{\frac1ε}$ passes or $n^{\frac1ε}$ time to compute a $(1-ε)$ approximation. In this paper we provide the first FPTAS (polynomial in $n,\frac1ε$) for the problem which is efficient in both the running time and the number of passes. We also show that we can estimate the size of the matching in $O(\frac1ε)$ passes using slightly superlinear space. To achieve both results, we use the structural properties of the matching polytope such as the laminarity of the tight sets and total dual integrality. The algorithms are iterative, and are based on the fractional packing and covering framework. However the formulations herein require exponentially many variables or constraints. We use laminarity, metric embeddings and graph sparsification to reduce the space required by the algorithms in between and across the iterations. This is the first use of these ideas in the semi-streaming model to solve a combinatorial optimization problem.
On Variants of the Matroid Secretary Problem
Venue: arXiv cs.DS 2011
Year: 2011

We present a number of positive and negative results for variants of the matroid secretary problem. Most notably, we design a constant-factor competitive algorithm for the "random assignment" model where the weights are assigned randomly to the elements of a matroid, and then the elements arrive on-line in an adversarial order (extending a result of Soto \cite{Soto11}). This is under the assumption that the matroid is known in advance. If the matroid is unknown in advance, we present an $O(\log r \log n)$-approximation, and prove that a better than $O(\log n / \log \log n)$ approximation is impossible. This resolves an open question posed by Babaioff et al. \cite{BIK07}. As a natural special case, we also consider the classical secretary problem where the number of candidates $n$ is unknown in advance. If $n$ is chosen by an adversary from $\{1,...,N\}$, we provide a nearly tight answer, by providing an algorithm that chooses the best candidate with probability at least $1/(H_{N-1}+1)$ and prove that a probability better than $1/H_N$ cannot be achieved (where $H_N$ is the $N$-th harmonic number).