OpenRaiser/Intern-Atlas huggingface dataset:
Throughput Analysis of Cognitive Wireless Networks with Poisson Distributed Nodes Based on Location Information
Venue: arXiv cs.IT 2014
Year: 2014

This paper provides a statistical characterization of the individual achievable rates in bits/s/Hz and the spatial throughput of bipolar Poisson wireless networks in bits/s/Hz/m$^2$. We assume that all transmitters have a cognitive ability to know the distance to their receiver's closest interferers so they can individually tune their coding rates to avoid outage events for each spatial realization. Considering that the closest interferer approximates the aggregate interference of all transmitters treated as noise, we derive closed-form expressions for the probability density function of the achievable rates under two decoding rules: treating interference as noise, and jointly detecting the strongest interfering signals treating the others as noise. Based on these rules and the bipolar model, we approximate the expected maximum spatial throughput, showing the best performance of the latter decoding rule. These results are also compared to the reference scenario where the transmitters do not have cognitive ability, coding their messages at predetermined rates that are chosen to optimize the expected spatial throughput -- regardless of particular realizations -- which yields outages. We prove that, when the same decoding rule and network density are considered, the cognitive spatial throughput always outperforms the other option.
Second-Order Rate Region of Constant-Composition Codes for the Multiple-Access Channel
Venue: arXiv cs.IT 2014
Year: 2014

This paper studies the second-order asymptotics of coding rates for the discrete memoryless multiple-access channel with a fixed target error probability. Using constant-composition random coding, coded time-sharing, and a variant of Hoeffding's combinatorial central limit theorem, an inner bound on the set of locally achievable second-order coding rates is given for each point on the boundary of the capacity region. It is shown that the inner bound for constant-composition random coding includes that recovered by i.i.d. random coding, and that the inclusion may be strict. The inner bound is extended to the Gaussian multiple-access channel via an increasingly fine quantization of the inputs.
Living on the edge: Phase transitions in convex programs with random data
Venue: arXiv cs.IT 2014
Year: 2014

Recent research indicates that many convex optimization problems with random constraints exhibit a phase transition as the number of constraints increases. For example, this phenomenon emerges in the $\ell_1$ minimization method for identifying a sparse vector from random linear measurements. Indeed, the $\ell_1$ approach succeeds with high probability when the number of measurements exceeds a threshold that depends on the sparsity level; otherwise, it fails with high probability. This paper provides the first rigorous analysis that explains why phase transitions are ubiquitous in random convex optimization problems. It also describes tools for making reliable predictions about the quantitative aspects of the transition, including the location and the width of the transition region. These techniques apply to regularized linear inverse problems with random measurements, to demixing problems under a random incoherence model, and also to cone programs with random affine constraints. The applied results depend on foundational research in conic geometry. This paper introduces a summary parameter, called the statistical dimension, that canonically extends the dimension of a linear subspace to the class of convex cones. The main technical result demonstrates that the sequence of intrinsic volumes of a convex cone concentrates sharply around the statistical dimension. This fact leads to accurate bounds on the probability that a randomly rotated cone shares a ray with a fixed cone.
Parameterized algorithms for the 2-clustering problem with minimum sum and minimum sum of squares objective functions
Venue: arXiv cs.DS 2014
Year: 2014

In the {\sc Min-Sum 2-Clustering} problem, we are given a graph and a parameter $k$, and the goal is to determine if there exists a 2-partition of the vertex set such that the total conflict number is at most $k$, where the conflict number of a vertex is the number of its non-neighbors in the same cluster and neighbors in the different cluster. The problem is equivalent to {\sc 2-Cluster Editing} and {\sc 2-Correlation Clustering} with an additional multiplicative factor two in the cost function. In this paper we show an algorithm for {\sc Min-Sum 2-Clustering} with time complexity $O(n\cdot 2.619^{r/(1-4r/n)}+n^3)$, where $n$ is the number of vertices and $r=k/n$. Particularly, the time complexity is $O^*(2.619^{k/n})$ for $k\in o(n^2)$ and polynomial for $k\in O(n\log n)$, which implies that the problem can be solved in subexponential time for $k\in o(n^2)$. We also design a parameterized algorithm for a variant in which the cost is the sum of the squared conflict-numbers. For $k\in o(n^3)$, the algorithm runs in subexponential $O(n^3\cdot 5.171^θ)$ time, where $θ=\sqrt{k/n}$.
Wang's B machines are efficiently universal, as is Hasenjaeger's small universal electromechanical toy
Venue: arXiv cs.CC 2014
Year: 2014

In the 1960's Gisbert Hasenjaeger built Turing Machines from electromechanical relays and uniselectors. Recently, Glaschick reverse engineered the program of one of these machines and found that it is a universal Turing machine. In fact, its program uses only four states and two symbols, making it a very small universal Turing machine. (The machine has three tapes and a number of other features that are important to keep in mind when comparing it to other small universal machines.) Hasenjaeger's machine simulates Hao Wang's B machines, which were proved universal by Wang. Unfortunately, Wang's original simulation algorithm suffers from an exponential slowdown when simulating Turing machines. Hence, via this simulation, Hasenjaeger's machine also has an exponential slowdown when simulating Turing machines. In this work, we give a new efficient simulation algorithm for Wang's B machines by showing that they simulate Turing machines with only a polynomial slowdown. As a second result, we find that Hasenjaeger's machine also efficiently simulates Turing machines in polynomial time. Thus, Hasenjaeger's machine is both small and fast. In another application of our result, we show that Hooper's small universal Turing machine simulates Turing machines in polynomial time, an exponential improvement.
Brightness Control in Dynamic Range Constrained Visible Light OFDM Systems
Venue: arXiv cs.IT 2014
Year: 2014

Visible light communication (VLC) systems can provide illumination and communication simultaneously via light emitting diodes (LEDs). Orthogonal frequency division multiplexing (OFDM) waveforms transmitted in a VLC system will have high peak-to-average power ratios (PAPRs). Since the transmitting LED is dynamic-range limited, OFDM signal has to be scaled and biased to avoid nonlinear distortion. Brightness control is an essential feature for the illumination function. In this paper, we will analyze the performance of dynamic range constrained visible light OFDM systems with biasing adjustment and pulse width modulation (PWM) methods. We will investigate the trade-off between duty cycle and forward ratio of PWM and find the optimum forward ratio to maximize the achievable ergodic rates.
Labeling and Retrieval of Emotionally-Annotated Images using WordNet
Venue: arXiv cs.IR 2014
Year: 2014

Repositories of images with semantic and emotion content descriptions are valuable tools in many areas such as Affective Computing and Human-Computer Interaction, but they are also important in the development of multimodal searchable online databases. Ever growing number of image documents available on the Internet continuously motivates research of better annotation models and more efficient retrieval methods which use mash-up of available data on semantics, scenes, objects, events, context and emotion. Formal knowledge representation of such high-level semantics requires rich, explicit, human but also machine-processable information. To achieve these goals we present an online ontology-based image annotation tool WNtags and demonstrate its usefulness in knowledge representation and image retrieval using the International Affective Picture System database. The WNtags uses WordNet as image tagging glossary but considers Suggested Upper Merged Ontology as the preferred upper labeling formalism. The retrieval is performed using node distance metrics to establish semantic relatedness between a query and the collaboratively weighted tags describing high-level image semantics, after which the result is ranked according to the derived importance. We also elaborate plans to improve the WNtags to create a collaborative Web-based multimedia repository for research in human emotion and attention.
A General Framework for Interacting Bayes-Optimally with Self-Interested Agents using Arbitrary Parametric Model and Model Prior
Venue: arXiv cs.LG 2014
Year: 2014

Recent advances in Bayesian reinforcement learning (BRL) have shown that Bayes-optimality is theoretically achievable by modeling the environment's latent dynamics using Flat-Dirichlet-Multinomial (FDM) prior. In self-interested multi-agent environments, the transition dynamics are mainly controlled by the other agent's stochastic behavior for which FDM's independence and modeling assumptions do not hold. As a result, FDM does not allow the other agent's behavior to be generalized across different states nor specified using prior domain knowledge. To overcome these practical limitations of FDM, we propose a generalization of BRL to integrate the general class of parametric models and model priors, thus allowing practitioners' domain knowledge to be exploited to produce a fine-grained and compact representation of the other agent's behavior. Empirical evaluation shows that our approach outperforms existing multi-agent reinforcement learning algorithms.
Communication over Finite-Chain-Ring Matrix Channels
Venue: arXiv cs.IT 2014
Year: 2014

Though network coding is traditionally performed over finite fields, recent work on nested-lattice-based network coding suggests that, by allowing network coding over certain finite rings, more efficient physical-layer network coding schemes can be constructed. This paper considers the problem of communication over a finite-ring matrix channel $Y = AX + BE$, where $X$ is the channel input, $Y$ is the channel output, $E$ is random error, and $A$ and $B$ are random transfer matrices. Tight capacity results are obtained and simple polynomial-complexity capacity-achieving coding schemes are provided under the assumption that $A$ is uniform over all full-rank matrices and $BE$ is uniform over all rank-$t$ matrices, extending the work of Silva, Kschischang and Kötter (2010), who handled the case of finite fields. This extension is based on several new results, which may be of independent interest, that generalize concepts and methods from matrices over finite fields to matrices over finite chain rings.
Autonomous Algorithms for Centralized and Distributed Interference Coordination: A Virtual Layer Based Approach
Venue: arXiv cs.IT 2014
Year: 2014

Interference mitigation techniques are essential for improving the performance of interference limited wireless networks. In this paper, we introduce novel interference mitigation schemes for wireless cellular networks with space division multiple access (SDMA). The schemes are based on a virtual layer that captures and simplifies the complicated interference situation in the network and that is used for power control. We show how optimization in this virtual layer generates gradually adapting power control settings that lead to autonomous interference minimization. Thereby, the granularity of control ranges from controlling frequency sub-band power via controlling the power on a per-beam basis, to a granularity of only enforcing average power constraints per beam. In conjunction with suitable short-term scheduling, our algorithms gradually steer the network towards a higher utility. We use extensive system-level simulations to compare three distributed algorithms and evaluate their applicability for different user mobility assumptions. In particular, it turns out that larger gains can be achieved by imposing average power constraints and allowing opportunistic scheduling instantaneously, rather than controlling the power in a strict way. Furthermore, we introduce a centralized algorithm, which directly solves the underlying optimization and shows fast convergence, as a performance benchmark for the distributed solutions. Moreover, we investigate the deviation from global optimality by comparing to a branch-and-bound-based solution.
The risks of mixing dependency lengths from sequences of different length
Venue: arXiv cs.CL 2014
Year: 2014

Mixing dependency lengths from sequences of different length is a common practice in language research. However, the empirical distribution of dependency lengths of sentences of the same length differs from that of sentences of varying length and the distribution of dependency lengths depends on sentence length for real sentences and also under the null hypothesis that dependencies connect vertices located in random positions of the sequence. This suggests that certain results, such as the distribution of syntactic dependency lengths mixing dependencies from sentences of varying length, could be a mere consequence of that mixing. Furthermore, differences in the global averages of dependency length (mixing lengths from sentences of varying length) for two different languages do not simply imply a priori that one language optimizes dependency lengths better than the other because those differences could be due to differences in the distribution of sentence lengths and other factors.
Finite-Length Scaling of Polar Codes
Venue: arXiv cs.IT 2014
Year: 2014

Consider a binary-input memoryless output-symmetric channel $W$. Such a channel has a capacity, call it $I(W)$, and for any $R<I(W)$ and strictly positive constant $P_{\rm e}$ we know that we can construct a coding scheme that allows transmission at rate $R$ with an error probability not exceeding $P_{\rm e}$. Assume now that we let the rate $R$ tend to $I(W)$ and we ask how we have to "scale" the blocklength $N$ in order to keep the error probability fixed to $P_{\rm e}$. We refer to this as the "finite-length scaling" behavior. This question was addressed by Strassen as well as Polyanskiy, Poor and Verdu, and the result is that $N$ must grow at least as the square of the reciprocal of $I(W)-R$. Polar codes are optimal in the sense that they achieve capacity. In this paper, we are asking to what degree they are also optimal in terms of their finite-length behavior. Our approach is based on analyzing the dynamics of the un-polarized channels. The main results of this paper can be summarized as follows. Consider the sum of Bhattacharyya parameters of sub-channels chosen (by the polar coding scheme) to transmit information. If we require this sum to be smaller than a given value $P_{\rm e}>0$, then the required block-length $N$ scales in terms of the rate $R < I(W)$ as $N \geq \fracα{(I(W)-R)^{\underlineμ}}$, where $α$ is a positive constant that depends on $P_{\rm e}$ and $I(W)$, and $\underlineμ = 3.579$. Also, we show that with the same requirement on the sum of Bhattacharyya parameters, the block-length scales in terms of the rate like $N \leq \fracβ{(I(W)-R)^{\overlineμ}}$, where $β$ is a constant that depends on $P_{\rm e}$ and $I(W)$, and $\overlineμ=6$.
Local Backbones
Venue: arXiv cs.CC 2014
Year: 2014

A backbone of a propositional CNF formula is a variable whose truth value is the same in every truth assignment that satisfies the formula. The notion of backbones for CNF formulas has been studied in various contexts. In this paper, we introduce local variants of backbones, and study the computational complexity of detecting them. In particular, we consider k-backbones, which are backbones for sub-formulas consisting of at most k clauses, and iterative k-backbones, which are backbones that result after repeated instantiations of k-backbones. We determine the parameterized complexity of deciding whether a variable is a k-backbone or an iterative k-backbone for various restricted formula classes, including Horn, definite Horn, and Krom. We also present some first empirical results regarding backbones for CNF-Satisfiability (SAT). The empirical results we obtain show that a large fraction of the backbones of structured SAT instances are local, in contrast to random instances, which appear to have few local backbones.
Improved bounds for reduction to depth 4 and depth 3
Venue: arXiv cs.CC 2014
Year: 2014

Koiran showed that if a $n$-variate polynomial of degree $d$ (with $d=n^{O(1)}$) is computed by a circuit of size $s$, then it is also computed by a homogeneous circuit of depth four and of size $2^{O(\sqrt{d}\log(d)\log(s))}$. Using this result, Gupta, Kamath, Kayal and Saptharishi gave a $\exp(O(\sqrt{d\log(d)\log(n)\log(s)}))$ upper bound for the size of the smallest depth three circuit computing a $n$-variate polynomial of degree $d=n^{O(1)}$ given by a circuit of size $s$. We improve here Koiran's bound. Indeed, we show that if we reduce an arithmetic circuit to depth four, then the size becomes $\exp(O(\sqrt{d\log(ds)\log(n)}))$. Mimicking Gupta, Kamath, Kayal and Saptharishi's proof, it also implies the same upper bound for depth three circuits. This new bound is not far from optimal in the sense that Gupta, Kamath, Kayal and Saptharishi also showed a $2^{Ω(\sqrt{d})}$ lower bound for the size of homogeneous depth four circuits such that gates at the bottom have fan-in at most $\sqrt{d}$. Finally, we show that this last lower bound also holds if the fan-in is at least $\sqrt{d}$.
How Hard Is It to Control an Election by Breaking Ties?
Venue: arXiv cs.AI 2014
Year: 2014

We study the computational complexity of controlling the result of an election by breaking ties strategically. This problem is equivalent to the problem of deciding the winner of an election under parallel universes tie-breaking. When the chair of the election is only asked to break ties to choose between one of the co-winners, the problem is trivially easy. However, in multi-round elections, we prove that it can be NP-hard for the chair to compute how to break ties to ensure a given result. Additionally, we show that the form of the tie-breaking function can increase the opportunities for control. Indeed, we prove that it can be NP-hard to control an election by breaking ties even with a two-stage voting rule.
A semantic account of strong normalization in Linear Logic
Venue: arXiv cs.LO 2014
Year: 2014

We prove that given two cut free nets of linear logic, by means of their relational interpretations one can: 1) first determine whether or not the net obtained by cutting the two nets is strongly normalizable 2) then (in case it is strongly normalizable) compute the maximal length of the reduction sequences starting from that net.
Geometry-Based Vehicle-to-Vehicle Channel Modeling for Large-Scale Simulation
Venue: arXiv cs.NI 2014
Year: 2014

Due to the dynamic nature of vehicular traffic and the road surroundings, vehicle-to-vehicle (V2V) propagation characteristics vary greatly on both small- and large-scale. Recent measurements have shown that both large static objects (e.g., buildings and foliage) as well as mobile objects (surrounding vehicles) have a profound impact on V2V communication. At the same time, system-level Vehicular Ad Hoc Network (VANET) simulators by and large employ simple statistical propagation models, which do not account for surrounding objects explicitly. We designed GEMV$^2$ (Geometry-based Efficient propagation Model for V2V communication), which uses outlines of vehicles, buildings, and foliage to distinguish the following three types of links: line of sight (LOS), non-LOS due to vehicles, and non- LOS due to static objects. For each link, GEMV$^2$ calculates the large-scale signal variations deterministically, whereas the small- scale signal variations are calculated stochastically based on the number and size of surrounding objects. We implement GEMV$^2$ in MATLAB and show that it scales well by using it to simulate radio propagation for city-wide networks with tens of thousands of vehicles on commodity hardware. We make the source code of GEMV$^2$ freely available. Finally, we validate GEMV$^2$ against extensive measurements performed in urban, suburban, highway, and open space environment.
Approximately Optimal Mechanisms for Strategyproof Facility Location: Minimizing $L_p$ Norm of Costs
Venue: arXiv cs.GT 2014
Year: 2014

We consider the problem of locating a single facility on the real line. This facility serves a set of agents, each of whom is located on the line, and incurs a cost equal to his distance from the facility. An agent's location is private information that is known only to him. Agents report their location to a central planner who decides where to locate the facility. The planner's objective is to minimize a "social" cost function that depends on the agent-costs. However, agents might not report truthfully; to address this issue, the planner must restrict himself to {\em strategyproof} mechanisms, in which truthful reporting is a dominant strategy for each agent. A mechanism that simply chooses the optimal solution is generally not strategyproof, and so the planner aspires to use a mechanism that effectively {\em approximates} his objective function. In our paper, we study the problem described above with the social cost function being the $L_p$ norm of the vector of agent-costs. We show that the median mechanism (which is known to be strategyproof) provides a $2^{1-\frac{1}{p}}$ approximation ratio, and that is the optimal approximation ratio among all deterministic strategyproof mechanisms. For randomized mechanisms, we present two results. First, we present a negative result: we show that for integer $\infty>p>2$, no mechanism---from a rather large class of randomized mechanisms--- has an approximation ratio better than that of the median mechanism. This is in contrast to the case of $p=2$ and $p=\infty$ where a randomized mechanism provably helps improve the worst case approximation ratio. Second, for the case of 2 agents, we show that a mechanism called LRM, first designed by Procaccia and Tennenholtz for the special case of $L_{\infty}$, provides the optimal approximation ratio among all randomized mechanisms.
Further Refinements of Miller Algorithm on Edwards curves
Venue: arXiv cs.CR 2014
Year: 2014

Recently, Edwards curves have received a lot of attention in the cryptographic community due to their fast scalar multiplication algorithms. Then, many works on the application of these curves to pairing-based cryptography have been introduced. Xu and Lin (CT-RSA, 2010) presented refinements to improve the Miller algorithm that is central role compute pairings on Edwards curves. In this paper, we study further refinements to Miller algorithm. Our approach is generic, hence it allow to compute both Weil and Tate pairings on pairing-friendly Edwards curves of any embedding degree. We analyze and show that our algorithm is faster than the original Miller algorithm and the Xu-Lin's refinements.