OpenRaiser/Intern-Atlas huggingface dataset:
Leader Election Problem Versus Pattern Formation Problem
Venue: arXiv cs.DC 2012
Year: 2012

Leader election and arbitrary pattern formation are funda- mental tasks for a set of autonomous mobile robots. The former consists in distinguishing a unique robot, called the leader. The latter aims in arranging the robots in the plane to form any given pattern. The solv- ability of both these tasks turns out to be necessary in order to achieve more complex tasks. In this paper, we study the relationship between these two tasks in a model, called CORDA, wherein the robots are weak in several aspects. In particular, they are fully asynchronous and they have no direct means of communication. They cannot remember any previous observation nor computation performed in any previous step. Such robots are said to be oblivious. The robots are also uniform and anonymous, i.e, they all have the same program using no global parameter (such as an identity) allowing to differentiate any of them. Moreover, we assume that none of them share any kind of common coordinate mechanism or common sense of direction and we discuss the influence of a common handedness (i.e., chirality). In such a system, Flochini et al. proved in [11] that it is possible to elect a leader for n \geq 3 robots if it is possible to form any pattern for n \geq 3. In this paper, we show that the converse is true for n \geq 4 when the robots share a common handedness and for n \geq 5 when they do not. Thus, we deduce that with chirality (resp. without chirality) both problems are equivalent for n \geq 4 (resp. n \geq 5) in CORDA.
A System F accounting for scalars
Venue: arXiv cs.LO 2012
Year: 2012

The Algebraic lambda-calculus and the Linear-Algebraic lambda-calculus extend the lambda-calculus with the possibility of making arbitrary linear combinations of terms. In this paper we provide a fine-grained, System F-like type system for the linear-algebraic lambda-calculus. We show that this "scalar" type system enjoys both the subject-reduction property and the strong-normalisation property, our main technical results. The latter yields a significant simplification of the linear-algebraic lambda-calculus itself, by removing the need for some restrictions in its reduction rules. But the more important, original feature of this scalar type system is that it keeps track of 'the amount of a type' that is present in each term. As an example of its use, we shown that it can serve as a guarantee that the normal form of a term is barycentric, i.e that its scalars are summing to one.
Speedup for Natural Problems and Noncomputability
Venue: arXiv cs.CC 2012
Year: 2012

A resource-bounded version of the statement "no algorithm recognizes all non-halting Turing machines" is equivalent to an infinitely often (i.o.) superpolynomial speedup for the time required to accept any coNP-complete language and also equivalent to a superpolynomial speedup in proof length in propositional proof systems for tautologies, each of which implies P!=NP. This suggests a correspondence between the properties 'has no algorithm at all' and 'has no best algorithm' which seems relevant to open problems in computational and proof complexity.
The Infinite-message Limit of Two-terminal Interactive Source Coding
Venue: arXiv cs.IT 2012
Year: 2012

A two-terminal interactive function computation problem with alternating messages is studied within the framework of distributed block source coding theory. For any finite number of messages, a single-letter characterization of the sum-rate-distortion function was established in previous works using standard information-theoretic techniques. This, however, does not provide a satisfactory characterization of the infinite-message limit, which is a new, unexplored dimension for asymptotic-analysis in distributed block source coding involving potentially an infinite number of infinitesimal-rate messages. In this paper, the infinite-message sum-rate-distortion function, viewed as a functional of the joint source pmf and the distortion levels, is characterized as the least element of a partially ordered family of functionals having certain convex-geometric properties. The new characterization does not involve evaluating the infinite-message limit of a finite-message sum-rate-distortion expression. This characterization leads to a family of lower bounds for the infinite-message sum-rate-distortion expression and a simple criterion to test the optimality of any achievable infinite-message sum-rate-distortion expression. For computing the amplewise Boolean AND function, the infinite-message minimum sum-rates are characterized in closed analytic form. These sum-rates are shown to be achievable using infinitely many infinitesimal-rate messages. The new convex-geometric characterization is used to develop an iterative algorithm for evaluating any finite-message sumrate-distortion function. It is also used to construct the first examples which demonstrate that for lossy source reproduction, two messages can strictly improve the one-message Wyner-Ziv rate-distortion function settling an unresolved question from a 1985 paper.
A theory of intelligence: networked problem solving in animal societies
Venue: arXiv cs.AI 2012
Year: 2012

A society's single emergent, increasing intelligence arises partly from the thermodynamic advantages of networking the innate intelligence of different individuals, and partly from the accumulation of solved problems. Economic growth is proportional to the square of the network entropy of a society's population times the network entropy of the number of the society's solved problems.
Reduced Complexity Sphere Decoding
Venue: arXiv cs.IT 2012
Year: 2012

In Multiple-Input Multiple-Output (MIMO) systems, Sphere Decoding (SD) can achieve performance equivalent to full search Maximum Likelihood (ML) decoding, with reduced complexity. Several researchers reported techniques that reduce the complexity of SD further. In this paper, a new technique is introduced which decreases the computational complexity of SD substantially, without sacrificing performance. The reduction is accomplished by deconstructing the decoding metric to decrease the number of computations and exploiting the structure of a lattice representation. Furthermore, an application of SD, employing a proposed smart implementation with very low computational complexity is introduced. This application calculates the soft bit metrics of a bit-interleaved convolutional-coded MIMO system in an efficient manner. Based on the reduced complexity SD, the proposed smart implementation employs the initial radius acquired by Zero-Forcing Decision Feedback Equalization (ZF-DFE) which ensures no empty spheres. Other than that, a technique of a particular data structure is also incorporated to efficiently reduce the number of executions carried out by SD. Simulation results show that these approaches achieve substantial gains in terms of the computational complexity for both uncoded and coded MIMO systems.
An Invariance Principle for Polytopes
Venue: arXiv cs.CC 2012
Year: 2012

Let X be randomly chosen from {-1,1}^n, and let Y be randomly chosen from the standard spherical Gaussian on R^n. For any (possibly unbounded) polytope P formed by the intersection of k halfspaces, we prove that |Pr [X belongs to P] - Pr [Y belongs to P]| < log^{8/5}k * Delta, where Delta is a parameter that is small for polytopes formed by the intersection of "regular" halfspaces (i.e., halfspaces with low influence). The novelty of our invariance principle is the polylogarithmic dependence on k. Previously, only bounds that were at least linear in k were known. We give two important applications of our main result: (1) A polylogarithmic in k bound on the Boolean noise sensitivity of intersections of k "regular" halfspaces (previous work gave bounds linear in k). (2) A pseudorandom generator (PRG) with seed length O((log n)*poly(log k,1/delta)) that delta-fools all polytopes with k faces with respect to the Gaussian distribution. We also obtain PRGs with similar parameters that fool polytopes formed by intersection of regular halfspaces over the hypercube. Using our PRG constructions, we obtain the first deterministic quasi-polynomial time algorithms for approximately counting the number of solutions to a broad class of integer programs, including dense covering problems and contingency tables.
The Geodesic Diameter of Polygonal Domains
Venue: arXiv cs.CG 2012
Year: 2012

This paper studies the geodesic diameter of polygonal domains having h holes and n corners. For simple polygons (i.e., h = 0), the geodesic diameter is determined by a pair of corners of a given polygon and can be computed in linear time, as known by Hershberger and Suri. For general polygonal domains with h >= 1, however, no algorithm for computing the geodesic diameter was known prior to this paper. In this paper, we present the first algorithms that compute the geodesic diameter of a given polygonal domain in worst-case time O(n^7.73) or O(n^7 (log n + h)). The main difficulty unlike the simple polygon case relies on the following observation revealed in this paper: two interior points can determine the geodesic diameter and in that case there exist at least five distinct shortest paths between the two.
Strong Robustness of Randomized Rumor Spreading Protocols
Venue: arXiv cs.DM 2012
Year: 2012

Randomized rumor spreading is a classical protocol to disseminate information across a network. At SODA 2008, a quasirandom version of this protocol was proposed and competitive bounds for its run-time were proven. This prompts the question: to what extent does the quasirandom protocol inherit the second principal advantage of randomized rumor spreading, namely robustness against transmission failures? In this paper, we present a result precise up to $(1 \pm o(1))$ factors. We limit ourselves to the network in which every two vertices are connected by a direct link. Run-times accurate to their leading constants are unknown for all other non-trivial networks. We show that if each transmission reaches its destination with a probability of $p \in (0,1]$, after $(1+\e)(\frac{1}{\log_2(1+p)}\log_2n+\frac{1}{p}\ln n)$ rounds the quasirandom protocol has informed all $n$ nodes in the network with probability at least $1-n^{-p\e/40}$. Note that this is faster than the intuitively natural $1/p$ factor increase over the run-time of approximately $\log_2 n + \ln n $ for the non-corrupted case. We also provide a corresponding lower bound for the classical model. This demonstrates that the quasirandom model is at least as robust as the fully random model despite the greatly reduced degree of independent randomness.
On the Construction of Prefix-Free and Fix-Free Codes with Specified Codeword Compositions
Venue: arXiv cs.IT 2012
Year: 2012

We investigate the construction of prefix-free and fix-free codes with specified codeword compositions. We present a polynomial time algorithm which constructs a fix-free code with the same codeword compositions as a given code for a special class of codes called distinct codes. We consider the construction of optimal fix-free codes which minimizes the average codeword cost for general letter costs with uniform distribution of the codewords and present an approximation algorithm to find a near optimal fix-free code with a given constant cost.
Cryptanalysis of an Efficient Signcryption Scheme with Forward Secrecy Based on Elliptic Curve
Venue: arXiv cs.CR 2012
Year: 2012

The signcryption is a relatively new cryptographic technique that is supposed to fulfill the functionalities of encryption and digital signature in a single logical step. Several signcryption schemes are proposed throughout the years, each of them having its own problems and limitations. In this paper, the security of a recent signcryption scheme, i.e. Hwang et al.'s scheme is analyzed, and it is proved that it involves several security flaws and shortcomings. Several devastating attacks are also introduced to the mentioned scheme whereby it fails all the desired and essential security attributes of a signcryption scheme.
Simple heuristics for the assembly line worker assignment and balancing problem
Venue: arXiv cs.DS 2012
Year: 2012

We propose simple heuristics for the assembly line worker assignment and balancing problem. This problem typically occurs in assembly lines in sheltered work centers for the disabled. Different from the classical simple assembly line balancing problem, the task execution times vary according to the assigned worker. We develop a constructive heuristic framework based on task and worker priority rules defining the order in which the tasks and workers should be assigned to the workstations. We present a number of such rules and compare their performance across three possible uses: as a stand-alone method, as an initial solution generator for meta-heuristics, and as a decoder for a hybrid genetic algorithm. Our results show that the heuristics are fast, they obtain good results as a stand-alone method and are efficient when used as a initial solution generator or as a solution decoder within more elaborate approaches.
Coding Theorems for a (2,2)-Threshold Scheme with Detectability of Impersonation Attacks
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we discuss coding theorems on a $(2, 2)$--threshold scheme in the presence of an opponent who impersonates one of the two shareholders in an asymptotic setup. We consider a situation where $n$ secrets $S^n$ from a memoryless source is blockwisely encoded to two shares and the two shares are decoded to $S^n$ with permitting negligible decoding error. We introduce correlation level of the two shares and characterize the minimum attainable rates of the shares and a uniform random number for realizing a $(2, 2)$--threshold scheme that is secure against the impersonation attack by an opponent. It is shown that, if the correlation level between the two shares equals to an $\ell \ge 0$, the minimum attainable rates coincide with $H(S)+\ell$, where $H(S)$ denotes the entropy of the source, and the maximum attainable exponent of the success probability of the impersonation attack equals to $\ell$. We also give a simple construction of an encoder and a decoder using an ordinary $(2,2)$--threshold scheme where the two shares are correlated and attains all the bounds.
Approximately achieving Gaussian relay network capacity with lattice codes
Venue: arXiv cs.IT 2012
Year: 2012

Recently, it has been shown that a quantize-map-and-forward scheme approximately achieves (within a constant number of bits) the Gaussian relay network capacity for arbitrary topologies. This was established using Gaussian codebooks for transmission and random mappings at the relays. In this paper, we show that the same approximation result can be established by using lattices for transmission and quantization along with structured mappings at the relays.
Normalized Range Voting Broadly Resists Control
Venue: arXiv cs.GT 2012
Year: 2012

We study the behavior of Range Voting and Normalized Range Voting with respect to electoral control. Electoral control encompasses attempts from an election chair to alter the structure of an election in order to change the outcome. We show that a voting system resists a case of control by proving that performing that case of control is computationally infeasible. Range Voting is a natural extension of approval voting, and Normalized Range Voting is a simple variant which alters each vote to maximize the potential impact of each voter. We show that Normalized Range Voting has among the largest number of control resistances among natural voting systems.
The Stability of Low-Rank Matrix Reconstruction: a Constrained Singular Value View
Venue: arXiv cs.IT 2012
Year: 2012

The stability of low-rank matrix reconstruction with respect to noise is investigated in this paper. The $\ell_*$-constrained minimal singular value ($\ell_*$-CMSV) of the measurement operator is shown to determine the recovery performance of nuclear norm minimization based algorithms. Compared with the stability results using the matrix restricted isometry constant, the performance bounds established using $\ell_*$-CMSV are more concise, and their derivations are less complex. Isotropic and subgaussian measurement operators are shown to have $\ell_*$-CMSVs bounded away from zero with high probability, as long as the number of measurements is relatively large. The $\ell_*$-CMSV for correlated Gaussian operators are also analyzed and used to illustrate the advantage of $\ell_*$-CMSV compared with the matrix restricted isometry constant. We also provide a fixed point characterization of $\ell_*$-CMSV that is potentially useful for its computation.
Gaussian Z-Interference Channel with a Relay Link: Achievability Region and Asymptotic Sum Capacity
Venue: arXiv cs.IT 2012
Year: 2012

This paper studies a Gaussian Z-interference channel with a rate-limited digital relay link from one receiver to another. Achievable rate regions are derived based on a combination of Han-Kobayashi common-private information splitting technique and several different relay strategies including compress-and-forward and a partial decode-and-forward strategy, in which the interference is partially decoded then binned and forwarded through the digital link for subtraction at the other end. For the Gaussian Z-interference channel with a digital link from the interference-free receiver to the interfered receiver, the capacity region is established in the strong interference regime; an achievable rate region is established in the weak interference regime. In the weak interference regime, the partial decode-and-forward strategy is shown to be asymptotically sum-capacity achieving in the high signal-to-noise ratio and high interference-to-noise ratio limit. In this case, each relay bit asymptotically improves the sum capacity by one bit. For the Gaussian Z-interference channel with a digital link from the interfered receiver to the interference-free receiver, the capacity region is established in the strong interference regime; achievable rate regions are established in the moderately strong and weak interference regimes. In addition, the asymptotically sum capacity is established in the limit of large relay link rate. In this case, the sum capacity improvement due to the digital link is bounded by half a bit when the interference link is weaker than certain threshold, but the sum capacity improvement becomes unbounded as the interference link becomes stronger.
Tree-formed Verification Data for Trusted Platforms
Venue: arXiv cs.CR 2012
Year: 2012

The establishment of trust relationships to a computing platform relies on validation processes. Validation allows an external entity to build trust in the expected behaviour of the platform based on provided evidence of the platform's configuration. In a process like remote attestation, the 'trusted' platform submits verification data created during a start up process. These data consist of hardware-protected values of platform configuration registers, containing nested measurement values, e.g., hash values, of loaded or started components. Commonly, the register values are created in linear order by a hardware-secured operation. Fine-grained diagnosis of components, based on the linear order of verification data and associated measurement logs, is not optimal. We propose a method to use tree-formed verification data to validate a platform. Component measurement values represent leaves, and protected registers represent roots of a hash tree. We describe the basic mechanism of validating a platform using tree-formed measurement logs and root registers and show an logarithmic speed-up for the search of faults. Secure creation of a tree is possible using a limited number of hardware-protected registers and a single protected operation. In this way, the security of tree-formed verification data is maintained.
A Dichotomy Theorem for the Approximate Counting of Complex-Weighted Bounded-Degree Boolean CSPs
Venue: arXiv cs.CC 2012
Year: 2012

We determine the computational complexity of approximately counting the total weight of variable assignments for every complex-weighted Boolean constraint satisfaction problem (or CSP) with any number of additional unary (i.e., arity 1) constraints, particularly, when degrees of input instances are bounded from above by a fixed constant. All degree-1 counting CSPs are obviously solvable in polynomial time. When the instance's degree is more than two, we present a dichotomy theorem that classifies all counting CSPs admitting free unary constraints into exactly two categories. This classification theorem extends, to complex-weighted problems, an earlier result on the approximation complexity of unweighted counting Boolean CSPs of bounded degree. The framework of the proof of our theorem is based on a theory of signature developed from Valiant's holographic algorithms that can efficiently solve seemingly intractable counting CSPs. Despite the use of arbitrary complex weight, our proof of the classification theorem is rather elementary and intuitive due to an extensive use of a novel notion of limited T-constructibility. For the remaining degree-2 problems, in contrast, they are as hard to approximate as Holant problems, which are a generalization of counting CSPs.
Optimal Distributed P2P Streaming under Node Degree Bounds
Venue: arXiv cs.NI 2012
Year: 2012

We study the problem of maximizing the broadcast rate in peer-to-peer (P2P) systems under \emph{node degree bounds}, i.e., the number of neighbors a node can simultaneously connect to is upper-bounded. The problem is critical for supporting high-quality video streaming in P2P systems, and is challenging due to its combinatorial nature. In this paper, we address this problem by providing the first distributed solution that achieves near-optimal broadcast rate under arbitrary node degree bounds, and over arbitrary overlay graph. It runs on individual nodes and utilizes only the measurement from their one-hop neighbors, making the solution easy to implement and adaptable to peer churn and network dynamics. Our solution consists of two distributed algorithms proposed in this paper that can be of independent interests: a network-coding based broadcasting algorithm that optimizes the broadcast rate given a topology, and a Markov-chain guided topology hopping algorithm that optimizes the topology. Our distributed broadcasting algorithm achieves the optimal broadcast rate over arbitrary P2P topology, while previously proposed distributed algorithms obtain optimality only for P2P complete graphs. We prove the optimality of our solution and its convergence to a neighborhood around the optimal equilibrium under noisy measurements or without time-scale separation assumptions. We demonstrate the effectiveness of our solution in simulations using uplink bandwidth statistics of Internet hosts.
Basic Performance Limits and Tradeoffs in Energy Harvesting Sensor Nodes with Finite Data and Energy Storage
Venue: arXiv cs.NI 2012
Year: 2012

As many sensor network applications require deployment in remote and hard-to-reach areas, it is critical to ensure that such networks are capable of operating unattended for long durations. Consequently, the concept of using nodes with energy replenishment capabilities has been gaining popularity. However, new techniques and protocols must be developed to maximize the performance of sensor networks with energy replenishment. Here, we analyze limits of the performance of sensor nodes with limited energy, being replenished at a variable rate. We provide a simple localized energy management scheme that achieves a performance close to that with an unlimited energy source, and at the same time keeps the probability of complete battery discharge low. Based on the insights developed, we address the problem of energy management for energy-replenishing nodes with finite battery and finite data buffer capacities. To this end, we give an energy management scheme that achieves the optimal utility asymptotically while keeping both the battery discharge and data loss probabilities low.