OpenRaiser/Intern-Atlas huggingface dataset:
The Unary Fragments of Metric Interval Temporal Logic: Bounded versus Lower bound Constraints (Full Version)
Venue: arXiv cs.LO 2013
Year: 2013

We study two unary fragments of the well-known metric interval temporal logic MITL[U_I,S_I] that was originally proposed by Alur and Henzinger, and we pin down their expressiveness as well as satisfaction complexities. We show that MITL[F_\inf,P_\inf] which has unary modalities with only lower-bound constraints is (surprisingly) expressively complete for Partially Ordered 2-Way Deterministic Timed Automata (po2DTA) and the reduction from logic to automaton gives us its NP-complete satisfiability. We also show that the fragment MITL[F_b,P_b] having unary modalities with only bounded intervals has \nexptime-complete satisfiability. But strangely, MITL[F_b,P_b] is strictly less expressive than MITL[F_\inf,P_\inf]. We provide a comprehensive picture of the decidability and expressiveness of various unary fragments of MITL.
Privacy and Security in IPv6
Venue: arXiv cs.CY 2013
Year: 2013

Many Internet service providers (ISPs) throughout the world are now in the process of integrating IPv6 into their Internet access products for retail customers and corporate clients. One of the most important features of the IPv6 protocol is its huge address space. This will enable users to assign a life-long stable, unique and globally routable IP address to each personal device. All users will be able to set up public services at home and be able to communicate from and to their devices from any point in the network. The resulting end-to-end reachability is considered a major improvement over the current situation.IPv6 evoked a new debate between privacy and security in order to attract more unique IP addresses to locate users, especially with the advent of mobile devices. While the initial IPv6 specification from 1995 does already contain a variety of security considerations (namely, message integrity protection as well as encryption based on IPsec), privacy aspects have not played a major role in the beginning.
The Product Promotion and Consumer Retention Gap in Online Shopping
Venue: arXiv cs.CY 2013
Year: 2013

As the number of online shopping websites increases day by day, so are the online advertisement strategies and promotional techniques. The number of people who uses internet keeps on increasing daily and it has become a vast marketplace to promote products, surely it will be a prime reason to drive any companies growth in the future.This paper primarily focuses on the areas on which online shopping lags product promotion and customer retention. Sellers must concentrate on the areas in which online marketing lags product promotion techniques; also they should introduce new strategies to increase their market share to gain customers attention towards their products.
Physical uncloneable function hardware keys utilizing Kirchhoff-law-Johnson-noise secure key exchange and noise-based logic
Venue: arXiv cs.CR 2013
Year: 2013

Weak physical uncloneable function (WPUF) encryption key means that the manufacturer of the hardware can clone the key but anybody else is unable to so that. Strong physical uncloneable function (SPUF) encryption key means that even the manufacturer of the hardware is unable to clone the key. In this paper, first we introduce a "ultra"-strong PUF with intrinsic dynamical randomness, which is not only not cloneable but it also gets renewed to an independent key (with fresh randomness) during each use via the unconditionally secure key exchange. The solution utilizes the Kirchhoff-law-Johnson-noise (KLJN) method for dynamical key renewal and a one-time-pad secure key for the challenge/response process. The secure key is stored in a flash memory on the chip to provide tamper-resistance and non-volatile storage with zero power requirements in standby mode. Simplified PUF keys are shown: a strong PUF utilizing KLJN protocol during the first run and noise-based logic (NBL) hyperspace vector string verification method for the challenge/response during the rest of its life or until it is re-initialized. Finally, the simplest PUF utilizes NBL without KLJN thus it can be cloned by the manufacturer but not by anybody else.
Field Programmable DSP Arrays - A Novel Reconfigurable Architecture for Efficient Realization of Digital Signal Processing Functions
Venue: arXiv cs.OH 2013
Year: 2013

Digital Signal Processing functions are widely used in real time high speed applications. Those functions are generally implemented either on ASICs with inflexibility, or on FPGAs with bottlenecks of relatively smaller utilization factor or lower speed compared to ASIC. The proposed reconfigurable DSP processor is redolent to FPGA, but with basic fixed Common Modules (CMs) (like adders, subtractors, multipliers, scaling units, shifters) instead of CLBs. This paper introduces the development of a reconfigurable DSP processor that integrates different filter and transform functions. The switching between DSP functions is occurred by reconfiguring the interconnection between CMs. Validation of the proposed reconfigurable architecture has been achieved on Virtex5 FPGA. The architecture provides sufficient amount of flexibility, parallelism and scalability.
Social Network for Smart Devices using Embedded Ethernet
Venue: arXiv cs.NI 2013
Year: 2013

Embedded Ethernet is nothing but a microcontroller which is able to communicate with the network. A design of AVR controller-based embedded Ethernet interface is presented. In the design, an existing SPI serial device can be converted into a network interface peripheral to obtain compatibility with the network. By typing the IP-address of LAN on the web browser, the user gets a web page on screen; this page contains all the information about the status of the devices. The user can also control the devices interfaced to the web server by pressing buttons provided in the web page. This creates a network for easy communication among the devices.
Approximate Distance Oracle with Constant Query Time
Venue: arXiv cs.DS 2013
Year: 2013

An approximate distance oracle is a succinct data structure that provides fast answers to distance queries between any two nodes. In this paper we consider approximate distance oracles for general undirected graphs with non-negative edge weights with constant query time. We present a distance oracle of size O(k n^{1+1/k}), with 2k-1 stretch and O(1) query time. This improves the O(log{k}) query time of Wulff-Nilsen's distance oracle [SODA '13], which in turn improved the O(k) query time of Thorup and Zwick's distance oracle [J. ACM '05].
Linear Reduced-Rank Interference Suppression for DS-UWB Systems Using Switched Approximations of Adaptive Basis Functions
Venue: arXiv cs.IT 2013
Year: 2013

In this work, we propose a novel low-complexity reduced-rank scheme and consider its application to linear interference suppression in direct-sequence ultra-wideband (DS-UWB) systems. Firstly, we investigate a generic reduced-rank scheme that jointly optimizes a projection vector and a reduced-rank filter by using the minimum mean-squared error (MMSE) criterion. Then a low-complexity scheme, denoted switched approximation of adaptive basis functions (SAABF), is proposed. The SAABF scheme is an extension of the generic scheme, in which the complexity reduction is achieved by using a multi-branch framework to simplify the structure of the projection vector. Adaptive implementations for the SAABF scheme are developed by using least-mean squares (LMS) and recursive least-squares (RLS) algorithms. We also develop algorithms for selecting the branch number and the model order of the SAABF scheme. Simulations show that in the scenarios with severe inter-symbol interference (ISI) and multiple access interference (MAI), the proposed SAABF scheme has fast convergence and remarkable interference suppression performance with low complexity.
On the Role of Common Codewords in Quadratic Gaussian Multiple Descriptions Coding
Venue: arXiv cs.IT 2013
Year: 2013

This paper focuses on the problem of $L-$channel quadratic Gaussian multiple description (MD) coding. We recently introduced a new encoding scheme in [1] for general $L-$channel MD problem, based on a technique called `Combinatorial Message Sharing' (CMS), where every subset of the descriptions shares a distinct common message. The new achievable region subsumes the most well known region for the general problem, due to Venkataramani, Kramer and Goyal (VKG) [2]. Moreover, we showed in [3] that the new scheme provides a strict improvement of the achievable region for any source and distortion measures for which some 2-description subset is such that the Zhang and Berger (ZB) scheme achieves points outside the El-Gamal and Cover (EC) region. In this paper, we show a more surprising result: CMS outperforms VKG for a general class of sources and distortion measures, which includes scenarios where for all 2-description subsets, the ZB and EC regions coincide. In particular, we show that CMS strictly extends VKG region, for the $L$-channel quadratic Gaussian MD problem for all $L\geq3$, despite the fact that the EC region is complete for the corresponding 2-descriptions problem. Using the encoding principles derived, we show that the CMS scheme achieves the complete rate-distortion region for several asymmetric cross-sections of the $L-$channel quadratic Gaussian MD problem, which have not been considered earlier.
Noisy Subspace Clustering via Thresholding
Venue: arXiv cs.IT 2013
Year: 2013

We consider the problem of clustering noisy high-dimensional data points into a union of low-dimensional subspaces and a set of outliers. The number of subspaces, their dimensions, and their orientations are unknown. A probabilistic performance analysis of the thresholding-based subspace clustering (TSC) algorithm introduced recently in [1] shows that TSC succeeds in the noisy case, even when the subspaces intersect. Our results reveal an explicit tradeoff between the allowed noise level and the affinity of the subspaces. We furthermore find that the simple outlier detection scheme introduced in [1] provably succeeds in the noisy case.
New Greedy Heuristics For Set Cover and Set Packing
Venue: arXiv cs.DS 2013
Year: 2013

The Set Cover problem (SCP) and Set Packing problem (SPP) are standard NP-hard combinatorial optimization problems. Their decision problem versions are shown to be NP-Complete in Karp's 1972 paper. We specify a rough guide to constructing approximation heuristics that may have widespread applications and apply it to devise greedy approximation algorithms for SCP and SPP, where the selection heuristic is a variation of that in the standard greedy approximation algorithm. Our technique involves assigning to each input set a valuation and then selecting, in each round, the set whose valuation is highest. We prove that the technique we use for determining a valuation of the input sets yields a unique value for all Set Cover instances. For both SCP and SPP we give experimental evidence that the valuations we specify are unique and can be computed to high precision quickly by an iterative algorithm. Others have experimented with testing the observed approximation ratio of various algorithms over a variety of randomly generated instances, and we have extensive experimental evidence to show the quality of the new algorithm relative to greedy heuristics in common use. Our algorithms are somewhat more computationally intensive than the standard heuristics, though they are still practical for large instances. We discuss some ways to speed up our algorithms that do not significantly distort their effectiveness in practice on random instances.
Robust Streaming Erasure Codes based on Deterministic Channel Approximations
Venue: arXiv cs.IT 2013
Year: 2013

We study near optimal error correction codes for real-time communication. In our setup the encoder must operate on an incoming source stream in a sequential manner, and the decoder must reconstruct each source packet within a fixed playback deadline of $T$ packets. The underlying channel is a packet erasure channel that can introduce both burst and isolated losses. We first consider a class of channels that in any window of length ${T+1}$ introduce either a single erasure burst of a given maximum length $B,$ or a certain maximum number $N$ of isolated erasures. We demonstrate that for a fixed rate and delay, there exists a tradeoff between the achievable values of $B$ and $N,$ and propose a family of codes that is near optimal with respect to this tradeoff. We also consider another class of channels that introduce both a burst {\em and} an isolated loss in each window of interest and develop the associated streaming codes. All our constructions are based on a layered design and provide significant improvements over baseline codes in simulations over the Gilbert-Elliott channel.
Empirical Coordination in a Triangular Multiterminal Network
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we investigate the problem of the empirical coordination in a triangular multiterminal network. A triangular multiterminal network consists of three terminals where two terminals observe two external i.i.d correlated sequences. The third terminal wishes to generate a sequence with desired empirical joint distribution. For this problem, we derive inner and outer bounds on the empirical coordination capacity region. It is shown that the capacity region of the degraded source network and the inner and outer bounds on the capacity region of the cascade multiterminal network can be directly obtained from our inner and outer bounds. For a cipher system, we establish key distribution over a network with a reliable terminal, using the results of the empirical coordination. As another example, the problem of rate distortion in the triangular multiterminal network is investigated in which a distributed doubly symmetric binary source is available.
Binary Tree based Chinese Word Segmentation
Venue: arXiv cs.CL 2013
Year: 2013

Chinese word segmentation is a fundamental task for Chinese language processing. The granularity mismatch problem is the main cause of the errors. This paper showed that the binary tree representation can store outputs with different granularity. A binary tree based framework is also designed to overcome the granularity mismatch problem. There are two steps in this framework, namely tree building and tree pruning. The tree pruning step is specially designed to focus on the granularity problem. Previous work for Chinese word segmentation such as the sequence tagging can be easily employed in this framework. This framework can also provide quantitative error analysis methods. The experiments showed that after using a more sophisticated tree pruning function for a state-of-the-art conditional random field based baseline, the error reduction can be up to 20%.
A Peep on the Interplays between Online Video Websites and Online Social Networks
Venue: arXiv cs.SI 2013
Year: 2013

Many online video websites provide the shortcut links to facilitate the video sharing to other websites especially to the online social networks (OSNs). Such video sharing behavior greatly changes the interplays between the two types of websites. For example, users in OSNs may watch and re-share videos shared by their friends from online video websites, and this can also boost the popularity of videos in online video websites and attract more people to watch and share them. Characterizing these interplays can provide great insights for understanding the relationships among online video websites, OSNs, ISPs and so on. In this paper we conduct empirical experiments to study the interplays between video sharing websites and OSNs using three totally different data sources: online video websites, OSNs, and campus network traffic. We find that, a) there are many factors that can affect the external sharing probability of videos in online video websites. b) The popularity of a video itself in online video websites can greatly impact on its popularity in OSNs. Videos in Renren, Qzone (the top two most popular Chinese OSNs) usually attract more viewers than in Sina and Tencent Weibo (the top two most popular Chinese microblogs), which indicates the different natures of the two kinds of OSNs. c) The analysis based on real traffic data illustrates that 10\% of video flows are related to OSNs, and they account for 25\% of traffic generated by all videos.
Semantic Guidance and Feedback for the Construction of Specifications and Implementations
Venue: arXiv cs.SE 2013
Year: 2013

The problem of writing a specification which accurately reflects the intent of the developer has long been recognized as fundamental. We propose a method and a supporting tool to write and check a specification and an implementation using a set of use cases, \ie input-output pairs that the developer supplies. These are instances of both good (correct) and bad (incorrect) behavior. We assume that the use cases are accurate, as it is easier to generate use cases than to write an accurate specification. We incrementally construct a specification (precondition and postcondition) based on semantic feedback generated from these use cases. We check the accuracy of the constructed specification using two proposed algorithms. The first algorithm checks the accuracy of the specification against an automatically generated specification from a supplied finite domain of use cases. The second checks the accuracy of the specification via reducing its domain to a finite yet equally satisfiable domain if possible. When the specification is mature, we start to also construct a program that satisfies the specification. However, our method makes provision for the continued modification of the specification, if needed. We illustrate our method with two examples; linear search and text justify.
Social Network Generation and Role Determination Based on Smartphone Data
Venue: arXiv cs.SI 2013
Year: 2013

We deal with the problem of automatically generating social networks by analyzing and assessing smartphone usage and interaction data. We start by assigning weights to the different types of interactions such as messaging, email, phone calls, chat and physical proximity. Next, we propose a ranking algorithm which recognizes the pattern of interaction taking into account the changes in the collected data over time. Both algorithms are based on recent findings from social network research.
Quickest Change Point Detection and Identification Across a Generic Sensor Array
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we consider the problem of quickest change point detection and identification over a linear array of $N$ sensors, where the change pattern could first reach any of these sensors, and then propagate to the other sensors. Our goal is not only to detect the presence of such a change as quickly as possible, but also to identify which sensor that the change pattern first reaches. We jointly design two decision rules: a stopping rule, which determines when we should stop sampling and claim a change occurred, and a terminal decision rule, which decides which sensor that the change pattern reaches first, with the objective to strike a balance among the detection delay, the false alarm probability, and the false identification probability. We show that this problem can be converted to a Markov optimal stopping time problem, from which some technical tools could be borrowed. Furthermore, to avoid the high implementation complexity issue of the optimal rules, we develop a scheme with a much simpler structure and certain performance guarantee.
Implementation of linear maps with circulant matrices via modulo 2 rectifier circuits of bounded depth
Venue: arXiv cs.DS 2013
Year: 2013

In the present note we show that for any positive integer k an arbitrary Boolean circulant matrix can be implemented via modulo 2 rectifier circuit of depth 2k-1 and complexity O(n^{1+1/k}), and also via circuit of depth 2k and complexity O(n^{1+1/k} log^{-1/k} n).
Multi-receiver Authentication Scheme for Multiple Messages Based on Linear Codes
Venue: arXiv cs.CR 2013
Year: 2013

In this paper, we construct an authentication scheme for multi-receivers and multiple messages based on a linear code $C$. This construction can be regarded as a generalization of the authentication scheme given by Safavi-Naini and Wang. Actually, we notice that the scheme of Safavi-Naini and Wang is constructed with Reed-Solomon codes. The generalization to linear codes has the similar advantages as generalizing Shamir's secret sharing scheme to linear secret sharing sceme based on linear codes. For a fixed message base field $\f$, our scheme allows arbitrarily many receivers to check the integrity of their own messages, while the scheme of Safavi-Naini and Wang has a constraint on the number of verifying receivers $V\leqslant q$. And we introduce access structure in our scheme. Massey characterized the access structure of linear secret sharing scheme by minimal codewords in the dual code whose first component is 1. We slightly modify the definition of minimal codewords in \cite{Massey93}. Let $C$ be a $[V,k]$ linear code. For any coordinate $i\in \{1,2,\cdots,V\}$, a codeword $\vec{c}$ in $C$ is called minimal respect to $i$ if the codeword $\vec{c}$ has component 1 at the $i$-th coordinate and there is no other codeword whose $i$-th component is 1 with support strictly contained in that of $\vec{c}$. Then the security of receiver $R_i$ in our authentication scheme is characterized by the minimal codewords respect to $i$ in the dual code $C^\bot$.
Quadratic Residue Codes over F_p+vF_p and their Gray Images
Venue: arXiv cs.IT 2013
Year: 2013

In this paper quadratic residue codes over the ring Fp + vFp are introduced in terms of their idempotent generators. The structure of these codes is studied and it is observed that these codes share similar properties with quadratic residue codes over finite fields. For the case p = 2, Euclidean and Hermitian self-dual families of codes as extended quadratic residue codes are considered and two optimal Hermitian self-dual codes are obtained as examples. Moreover, a substantial number of good p-ary codes are obtained as images of quadratic residue codes over Fp +vFp in the cases where p is an odd prime. These results are presented in tables.
The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into $\ell_1$
Venue: arXiv cs.CC 2013
Year: 2013

In this paper, we disprove a conjecture of Goemans and Linial; namely, that every negative type metric embeds into $\ell_1$ with constant distortion. We show that for an arbitrarily small constant $δ> 0$, for all large enough $n$, there is an $n$-point negative type metric which requires distortion at least $(\log\log n)^{1/6-δ}$ to embed into $\ell_1.$ Surprisingly, our construction is inspired by the Unique Games Conjecture (UGC) of Khot, establishing a previously unsuspected connection between probabilistically checkable proof systems (PCPs) and the theory of metric embeddings. We first prove that the UGC implies a super-constant hardness result for the (non-uniform) Sparsest Cut problem. Though this hardness result relies on the UGC, we demonstrate, nevertheless, that the corresponding PCP reduction can be used to construct an "integrality gap instance" for Sparsest Cut. Towards this, we first construct an integrality gap instance for a natural SDP relaxation of Unique Games. Then we "simulate" the PCP reduction and "translate" the integrality gap instance of Unique Games to an integrality gap instance of Sparsest Cut. This enables us to prove a $(\log \log n)^{1/6-δ}$ integrality gap for Sparsest Cut, which is known to be equivalent to the metric embedding lower bound.