OpenRaiser/Intern-Atlas huggingface dataset:
Semantic Unification A sheaf theoretic approach to natural language
Venue: arXiv cs.CL 2014
Year: 2014

Language is contextual and sheaf theory provides a high level mathematical framework to model contextuality. We show how sheaf theory can model the contextual nature of natural language and how gluing can be used to provide a global semantics for a discourse by putting together the local logical semantics of each sentence within the discourse. We introduce a presheaf structure corresponding to a basic form of Discourse Representation Structures. Within this setting, we formulate a notion of semantic unification --- gluing meanings of parts of a discourse into a coherent whole --- as a form of sheaf-theoretic gluing. We illustrate this idea with a number of examples where it can used to represent resolutions of anaphoric references. We also discuss multivalued gluing, described using a distributions functor, which can be used to represent situations where multiple gluings are possible, and where we may need to rank them using quantitative measures. Dedicated to Jim Lambek on the occasion of his 90th birthday.
Fingerprinting Smart Devices Through Embedded Acoustic Components
Venue: arXiv cs.CR 2014
Year: 2014

The widespread use of smart devices gives rise to both security and privacy concerns. Fingerprinting smart devices can assist in authenticating physical devices, but it can also jeopardize privacy by allowing remote identification without user awareness. We propose a novel fingerprinting approach that uses the microphones and speakers of smart phones to uniquely identify an individual device. During fabrication, subtle imperfections arise in device microphones and speakers which induce anomalies in produced and received sounds. We exploit this observation to fingerprint smart devices through playback and recording of audio samples. We use audio-metric tools to analyze and explore different acoustic features and analyze their ability to successfully fingerprint smart devices. Our experiments show that it is even possible to fingerprint devices that have the same vendor and model; we were able to accurately distinguish over 93% of all recorded audio clips from 15 different units of the same model. Our study identifies the prominent acoustic features capable of fingerprinting devices with high success rate and examines the effect of background noise and other variables on fingerprinting accuracy.
Automated Reasoning in Social Choice Theory - Some Remarks
Venue: arXiv cs.LO 2014
Year: 2014

Our objective in this note is to comment briefly on the newly emerging literature on computer-aided proofs in Social Choice Theory. We shall specifically comment on two papers, one by Tang and Lin (2009) and another by Geist and Endriss (2011). We also provide statements and brief descriptions of the results discussed in this note.
A New Event-Driven Cooperative Receding Horizon Controller for Multi-agent Systems in Uncertain Environments
Venue: arXiv cs.SY 2014
Year: 2014

In previous work, a Cooperative Receding Horizon (CRH) controller was developed for solving cooperative multi-agent problems in uncertain environments. In this paper, we overcome several limitations of this controller, including potential instabilities in the agent trajectories and poor performance due to inaccurate estimation of a reward-to-go function. We propose an event-driven CRH controller to solve the maximum reward collection problem (MRCP) where multiple agents cooperate to maximize the total reward collected from a set of stationary targets in a given mission space. Rewards are non-increasing functions of time and the environment is uncertain with new targets detected by agents at random time instants. The controller sequentially solves optimization problems over a planning horizon and executes the control for a shorter action horizon, where both are defined by certain events associated with new information becoming available. In contrast to the earlier CRH controller, we reduce the originally infinite-dimensional feasible control set to a finite set at each time step. We prove some properties of this new controller and include simulation results showing its improved performance compared to the original one.
Two-Point $L_1$ Shortest Path Queries in the Plane
Venue: arXiv cs.CG 2014
Year: 2014

Let $\mathcal{P}$ be a set of $h$ pairwise-disjoint polygonal obstacles with a total of $n$ vertices in the plane. We consider the problem of building a data structure that can quickly compute an $L_1$ shortest obstacle-avoiding path between any two query points $s$ and $t$. Previously, a data structure of size $O(n^2\log n)$ was constructed in $O(n^2\log^2 n)$ time that answers each two-point query in $O(\log^2 n+k)$ time, i.e., the shortest path length is reported in $O(\log^2 n)$ time and an actual path is reported in additional $O(k)$ time, where $k$ is the number of edges of the output path. In this paper, we build a new data structure of size $O(n+h^2\cdot \log h \cdot 4^{\sqrt{\log h}})$ in $O(n+h^2\cdot \log^{2} h \cdot 4^{\sqrt{\log h}})$ time that answers each query in $O(\log n+k)$ time. Note that $n+h^2\cdot \log^{2} h \cdot 4^{\sqrt{\log h}}=O(n+h^{2+ε})$ for any constant $ε>0$. Further, we extend our techniques to the weighted rectilinear version in which the "obstacles" of $\mathcal{P}$ are rectilinear regions with "weights" and allow $L_1$ paths to travel through them with weighted costs. Our algorithm answers each query in $O(\log n+k)$ time with a data structure of size $O(n^2\cdot \log n\cdot 4^{\sqrt{\log n}})$ that is built in $O(n^2\cdot \log^{2} n\cdot 4^{\sqrt{\log n}})$ time (note that $n^2\cdot \log^{2} n\cdot 4^{\sqrt{\log n}}= O(n^{2+ε})$ for any constant $ε>0$).
Deciding the Borel complexity of regular tree languages
Venue: arXiv cs.LO 2014
Year: 2014

We show that it is decidable whether a given a regular tree language belongs to the class ${\bf Δ^0_2}$ of the Borel hierarchy, or equivalently whether the Wadge degree of a regular tree language is countable.
Threshold Analysis of Non-Binary Spatially-Coupled LDPC Codes with Windowed Decoding
Venue: arXiv cs.IT 2014
Year: 2014

In this paper we study the iterative decoding threshold performance of non-binary spatially-coupled low-density parity-check (NB-SC-LDPC) code ensembles for both the binary erasure channel (BEC) and the binary-input additive white Gaussian noise channel (BIAWGNC), with particular emphasis on windowed decoding (WD). We consider both (2,4)-regular and (3,6)-regular NB-SC-LDPC code ensembles constructed using protographs and compute their thresholds using protograph versions of NB density evolution and NB extrinsic information transfer analysis. For these code ensembles, we show that WD of NB-SC-LDPC codes, which provides a significant decrease in latency and complexity compared to decoding across the entire parity-check matrix, results in a negligible decrease in the near-capacity performance for a sufficiently large window size W on both the BEC and the BIAWGNC. Also, we show that NB-SC-LDPC code ensembles exhibit gains in the WD threshold compared to the corresponding block code ensembles decoded across the entire parity-check matrix, and that the gains increase as the finite field size q increases. Moreover, from the viewpoint of decoding complexity, we see that (3,6)-regular NB-SC-LDPC codes are particularly attractive due to the fact that they achieve near-capacity thresholds even for small q and W.
Modular Verification of Hybrid System Code with VCC
Venue: arXiv cs.SE 2014
Year: 2014

We present a methodology for object-modular reasoning about hybrid system code using VCC, a deductive verifier for concurrent C code. We define in VCC an explicit time model, in which the passage of time must respect the invariants of certain timed objects. Fields that change automatically with changes to time are then defined as volatile fields with suitable invariants. We also define two types of timed objects that prevent time from advancing past a given expiration: Timers (which represent assumptions about the upper limit on the time it takes to do something) and Deadlines (which represent assertions about these limits). The difference between the two is that once the expiration time of a Deadline is reached, the Deadline and time itself are permanently deadlocked. Our methodology includes showing that all Deadlines are eventually destroyed, proving that they do not interfere with the flow of time.
The Effect of Saturation on Belief Propagation Decoding of LDPC Codes
Venue: arXiv cs.IT 2014
Year: 2014

We consider the effect of LLR saturation on belief propagation decoding of low-density parity-check codes. Saturation occurs universally in practice and is known to have a significant effect on error floor performance. Our focus is on threshold analysis and stability of density evolution. We analyze the decoder for certain low-density parity-check code ensembles and show that belief propagation decoding generally degrades gracefully with saturation. Stability of density evolution is, on the other hand, rather strongly affected by saturation and the asymptotic qualitative effect of saturation is similar to reduction of variable node degree by one.
Saving Energy in Mobile Devices for On-Demand Multimedia Streaming -- A Cross-Layer Approach
Venue: arXiv cs.MM 2014
Year: 2014

This paper proposes a novel energy-efficient multimedia delivery system called EStreamer. First, we study the relationship between buffer size at the client, burst-shaped TCP-based multimedia traffic, and energy consumption of wireless network interfaces in smartphones. Based on the study, we design and implement EStreamer for constant bit rate and rate-adaptive streaming. EStreamer can improve battery lifetime by 3x, 1.5x and 2x while streaming over Wi-Fi, 3G and 4G respectively.
Interference Coordination Schemes for Wireless Mobile Advanced Systems: A Survey
Venue: arXiv cs.NI 2014
Year: 2014

Mobile communication networks have witnessed a perpetual evolution since their launching as voice only networks. In the few past years, the focus was addressed to high data rate networks that offer high quality of service. The lately released LTE-Advanced network was the first to completely fulfill 4G requirements. However, performance gains remain limited due to severe interference levels. This paper is a survey upon the evolution of interference mitigation solutions from Release 8 to Release 11. This problem was addressed since earlier releases by coordinating transmission/reception among different cells. Many enhancements were then carried out by each subsequent specification. The originality of this work resides on the comparison between the different schemes and the perspective of developing a new interference coordination method available for 4G and beyond systems with small cells deployment. Several similarities are noted and differences on performance impact are highlighted.
Geometric VLAD for Large Scale Image Search
Venue: arXiv cs.CV 2014
Year: 2014

We present a novel compact image descriptor for large scale image search. Our proposed descriptor - Geometric VLAD (gVLAD) is an extension of VLAD (Vector of Locally Aggregated Descriptors) that incorporates weak geometry information into the VLAD framework. The proposed geometry cues are derived as a membership function over keypoint angles which contain evident and informative information but yet often discarded. A principled technique for learning the membership function by clustering angles is also presented. Further, to address the overhead of iterative codebook training over real-time datasets, a novel codebook adaptation strategy is outlined. Finally, we demonstrate the efficacy of proposed gVLAD based retrieval framework where we achieve more than 15% improvement in mAP over existing benchmarks.
Efficient Computation of Visibility Polygons
Venue: arXiv cs.CG 2014
Year: 2014

Determining visibility in planar polygons and arrangements is an important subroutine for many algorithms in computational geometry. In this paper, we report on new implementations, and corresponding experimental evaluations, for two established and one novel algorithm for computing visibility polygons. These algorithms will be released to the public shortly, as a new package for the Computational Geometry Algorithms Library (CGAL).
Measuring Global Similarity between Texts
Venue: arXiv cs.CL 2014
Year: 2014

We propose a new similarity measure between texts which, contrary to the current state-of-the-art approaches, takes a global view of the texts to be compared. We have implemented a tool to compute our textual distance and conducted experiments on several corpuses of texts. The experiments show that our methods can reliably identify different global types of texts.
Efficient Maximum-Likelihood Decoding of Linear Block Codes on Binary Memoryless Channels
Venue: arXiv cs.IT 2014
Year: 2014

In this work, we consider efficient maximum-likelihood decoding of linear block codes for small-to-moderate block lengths. The presented approach is a branch-and-bound algorithm using the cutting-plane approach of Zhang and Siegel (IEEE Trans. Inf. Theory, 2012) for obtaining lower bounds. We have compared our proposed algorithm to the state-of-the-art commercial integer program solver CPLEX, and for all considered codes our approach is faster for both low and high signal-to-noise ratios. For instance, for the benchmark (155,64) Tanner code our algorithm is more than 11 times as fast as CPLEX for an SNR of 1.0 dB on the additive white Gaussian noise channel. By a small modification, our algorithm can be used to calculate the minimum distance, which we have again verified to be much faster than using the CPLEX solver.
A Methodology for Implementation of MMS Client on Embedded Platforms
Venue: arXiv cs.MM 2014
Year: 2014

MMS (Multimedia Messaging Service) is the next generation of messaging services in multimedia mobile communications. MMS enables messaging with full multimedia content including images, audios, videos, texts and data, from client to client or e-mail. MMS is based on WAP technology, so it is technology independent. This means that enabling messages from a GSM/GPRS network to be sent to a TDMA or WCDMA network. In this paper a methodology for implementing MMS client on embedded platforms especially on Wince OS is described.
Approximate dynamic programming with $(\min,+)$ linear function approximation for Markov decision processes
Venue: arXiv cs.SY 2014
Year: 2014

Markov Decision Processes (MDP) is an useful framework to cast optimal sequential decision making problems. Given any MDP the aim is to find the optimal action selection mechanism i.e., the optimal policy. Typically, the optimal policy ($u^*$) is obtained by substituting the optimal value-function ($J^*$) in the Bellman equation. Alternately $u^*$ is also obtained by learning the optimal state-action value function $Q^*$ known as the $Q$ value-function. However, it is difficult to compute the exact values of $J^*$ or $Q^*$ for MDPs with large number of states. Approximate Dynamic Programming (ADP) methods address this difficulty by computing lower dimensional approximations of $J^*$/$Q^*$. Most ADP methods employ linear function approximation (LFA), i.e., the approximate solution lies in a subspace spanned by a family of pre-selected basis functions. The approximation is obtain via a linear least squares projection of higher dimensional quantities and the $L_2$ norm plays an important role in convergence and error analysis. In this paper, we discuss ADP methods for MDPs based on LFAs in $(\min,+)$ algebra. Here the approximate solution is a $(\min,+)$ linear combination of a set of basis functions whose span constitutes a subsemimodule. Approximation is obtained via a projection operator onto the subsemimodule which is different from linear least squares projection used in ADP methods based on conventional LFAs. MDPs are not $(\min,+)$ linear systems, nevertheless, we show that the monotonicity property of the projection operator helps us to establish the convergence of our ADP schemes. We also discuss future directions in ADP methods for MDPs based on the $(\min,+)$ LFAs.
Spatial Topology Adjustment for Minimizing Multicell Network Power Consumption
Venue: arXiv cs.IT 2014
Year: 2014

While the deployment of base stations (BSs) becomes increasingly dense in order to accommodate the growth in traffic demand, these BSs may be under-utilized during most hours except peak hours. Accordingly, the deactivation of these under-utilized BSs is regarded as the key to reducing network power consumption; however, the remaining active BSs should increase their transmit power in order to fill network coverage holes that result from BS switching off. This paper investigates the optimal balance between such beneficial and harmful effects of BS switching off in terms of minimizing the network power consumption, through comprehensively considering the spatial BS distribution, BS transmit power, BS power consumption behaviors, radio propagation environments, and frequency reuse. When BSs are deployed according to a homogeneous Poisson point process, the suboptimal and approximated design problems are formulated as geometric programming and the solutions lead to insightful design principles for the key design parameters including the spatial density, transmit power, and frequency reuse of remaining active BSs. The numerical results demonstrate that these solutions are very close to the optimal balances.
Low-Complexity Transmission Mode Selection in MU-MIMO Systems
Venue: arXiv cs.IT 2014
Year: 2014

We propose a low-complexity transmission strategy in multi-user multiple-input multiple-output downlink systems. The adaptive strategy adjusts the precoding methods, denoted as the transmission mode, to improve the system sum rates while maintaining the number of simultaneously served users. Three linear precoding transmission modes are discussed, i.e., the block diagonalization zero-forcing, the cooperative zero-forcing (CZF), and the cooperative matched-filter (CMF). Considering both the number of data streams and the multiple-antenna configuration of users, we modify the common CZF and CMF modes by allocating data streams. Then, the transmission mode is selected between the modified ones according to the asymptotic sum rate analyses. As instantaneous channel state information is not needed for the mode selection, the computational complexity is significantly reduced. Numerical simulations confirm our analyses and demonstrate that the proposed scheme achieves substantial performance gains with very low computational complexity.
Synchronous Relaying Of Sensor Data
Venue: arXiv cs.NI 2014
Year: 2014

In this paper we have put forth a novel methodology to relay data obtained by inbuilt sensors of smart phones in real time to remote database followed by fetching of this data . Smart phones are becoming very common and they are laced with a number of sensors that can not only be used in native applications but can also be sent to external nodes to be used by third parties for application and service development.
Performance Analysis of Arbitrarily-Shaped Underlay Cognitive Networks: Effects of Secondary User Activity Protocols
Venue: arXiv cs.IT 2014
Year: 2014

This paper analyzes the performance of the primary and secondary users (SUs) in an arbitrarily-shaped underlay cognitive network. In order to meet the interference threshold requirement for a primary receiver (PU-Rx) at an arbitrary location, we consider different SU activity protocols which limit the number of active SUs. We propose a framework, based on the moment generating function (MGF) of the interference due to a random SU, to analytically compute the outage probability in the primary network, as well as the average number of active SUs in the secondary network. We also propose a cooperation-based SU activity protocol in the underlay cognitive network which includes the existing threshold-based protocol as a special case. We study the average number of active SUs for the different SU activity protocols, subject to a given outage probability constraint at the PU and we employ it as an analytical approach to compare the effect of different SU activity protocols on the performance of the primary and secondary networks.
Quantized Output Feedback Stabilization of Switched Linear Systems
Venue: arXiv cs.SY 2014
Year: 2014

This paper studies the problem of stabilizing a continuous-time switched linear system by quantized output feedback. We assume that the quantized outputs and the switching signal are available to the controller at all time. We develop an encoding strategy by using multiple Lyapunov functions and an average dwell time property. The encoding strategy is based on the results in the case of a single mode, and it requires an additional adjustment of the "zoom" parameter at every switching time.
Performance Analysis of Location Profile Routing
Venue: arXiv cs.NI 2014
Year: 2014

We propose using the predictability of human motion to eliminate the overhead of distributed location services in human-carried MANETs, dubbing the technique location profile routing. This method outperforms the Geographic Hashing Location Service when nodes change locations 2x more frequently than they initiate connections (e.g., start new TCP streams), as in applications like text- and instant-messaging. Prior characterizations of human mobility are used to show that location profile routing achieves a 93% delivery ratio with a 1.75x first-packet latency increase relative to an oracle location service.
On the Automorphisms of Order 15 for a Binary Self-Dual [96, 48, 20] Code
Venue: arXiv cs.IT 2014
Year: 2014

The structure of binary self-dual codes invariant under the action of a cyclic group of order $pq$ for odd primes $p\neq q$ is considered. As an application we prove the nonexistence of an extremal self-dual $[96, 48, 20]$ code with an automorphism of order $15$ which closes a gap in `"On extremal self-dual codes of length 96", IEEE Trans. Inf. Theory, vol. 57, pp. 6820-6823, 2011'.
Dynamics of social balance under temporal interaction
Venue: arXiv cs.SI 2014
Year: 2014

Real social contacts are often intermittent such that a link between a pair of nodes in a social network is only temporarily used. Effects of such temporal networks on social dynamics have been investigated for several phenomenological models such as epidemic spreading, linear diffusion processes, and nonlinear oscillations. Here, we numerically investigate nonlinear social balance dynamics in such a situation. Social balance is a classical psychological theory, which dictates that a triad is balanced if the three agents are mutual friends or if the two of them are the friends of each other and hostile to the other agent. We show that the social balance dynamics is slowed down on the temporal complete graph as compared to the corresponding static complete graph.
A Non-Cooperative Game Model for Reliability-Based Task Scheduling in Cloud Computing
Venue: arXiv cs.DC 2014
Year: 2014

Cloud computing is a newly emerging distributed system which is evolved from Grid computing. Task scheduling is the core research of cloud computing which studies how to allocate the tasks among the physical nodes, so that the tasks can get a balanced allocation or each task's execution cost decreases to the minimum, or the overall system performance is optimal. Unlike task scheduling based on time or cost before, aiming at the special reliability requirements in cloud computing, we propose a non-cooperative game model for reliability-based task scheduling approach. This model takes the steady-state availability that computing nodes provide as the target, takes the task slicing strategy of the schedulers as the game strategy, then finds the Nash equilibrium solution. And also, we design a task scheduling algorithm based on this model. The experiments can be seen that our task scheduling algorithm is better than the so-called balanced scheduling algorithm.