OpenRaiser/Intern-Atlas huggingface dataset:
On the Complexity of the F5 Gröbner basis Algorithm
Venue: arXiv cs.SC 2014
Year: 2014

We study the complexity of Gröbner bases computation, in particular in the generic situation where the variables are in simultaneous Noether position with respect to the system. We give a bound on the number of polynomials of degree $d$ in a Gröbner basis computed by Faugère's $F_5$ algorithm~(Fau02) in this generic case for the grevlex ordering (which is also a bound on the number of polynomials for a reduced Gröbner basis, independently of the algorithm used). Next, we analyse more precisely the structure of the polynomials in the Gröbner bases with signatures that $F_5$ computes and use it to bound the complexity of the algorithm. Our estimates show that the version of~$F_5$ we analyse, which uses only standard Gaussian elimination techniques, outperforms row reduction of the Macaulay matrix with the best known algorithms for moderate degrees, and even for degrees up to the thousands if Strassen's multiplication is used. The degree being fixed, the factor of improvement grows exponentially with the number of variables.
Optimal Error Rates for Interactive Coding II: Efficiency and List Decoding
Venue: arXiv cs.DS 2014
Year: 2014

We study coding schemes for error correction in interactive communications. Such interactive coding schemes simulate any $n$-round interactive protocol using $N$ rounds over an adversarial channel that corrupts up to $ρN$ transmissions. Important performance measures for a coding scheme are its maximum tolerable error rate $ρ$, communication complexity $N$, and computational complexity. We give the first coding scheme for the standard setting which performs optimally in all three measures: Our randomized non-adaptive coding scheme has a near-linear computational complexity and tolerates any error rate $δ< 1/4$ with a linear $N = Θ(n)$ communication complexity. This improves over prior results which each performed well in two of these measures. We also give results for other settings of interest, namely, the first computationally and communication efficient schemes that tolerate $ρ< \frac{2}{7}$ adaptively, $ρ< \frac{1}{3}$ if only one party is required to decode, and $ρ< \frac{1}{2}$ if list decoding is allowed. These are the optimal tolerable error rates for the respective settings. These coding schemes also have near linear computational and communication complexity. These results are obtained via two techniques: We give a general black-box reduction which reduces unique decoding, in various settings, to list decoding. We also show how to boost the computational and communication efficiency of any list decoder to become near linear.
How Santa Fe Ants Evolve
Venue: arXiv cs.NE 2014
Year: 2014

The Santa Fe Ant model problem has been extensively used to investigate, test and evaluate Evolutionary Computing systems and methods over the past two decades. There is however no literature on its program structures that are systematically used for fitness improvement, the geometries of those structures and their dynamics during optimization. This paper analyzes the Santa Fe Ant Problem using a new phenotypic schema and landscape analysis based on executed instruction sequences. For the first time we detail systematic structural features that give high fitness and the evolutionary dynamics of such structures. The new schema avoids variances due to introns. We develop a phenotypic variation method that tests the new understanding of the landscape. We also develop a modified function set that tests newly identified synchronization constraints. We obtain favorable computational efforts compared to those in the literature, on testing the new variation and function set on both the Santa Fe Trail, and the more computationally demanding Los Altos Trail. Our findings suggest that for the Santa Fe Ant problem, a perspective of program assembly from repetition of highly fit responses to trail conditions leads to better analysis and performance.
Bounds on Double-Sided Myopic Algorithms for Unconstrained Non-monotone Submodular Maximization
Venue: arXiv cs.DS 2014
Year: 2014

Unconstrained submodular maximization captures many NP-hard combinatorial optimization problems, including Max-Cut, Max-Di-Cut, and variants of facility location problems. Recently, Buchbinder et al. presented a surprisingly simple linear time randomized greedy-like online algorithm that achieves a constant approximation ratio of 1/2, matching optimally the hardness result of Feige et al.. Motivated by the algorithm of Buchbinder et al., we introduce a precise algorithmic model called double-sided myopic algorithms. We show that while the algorithm of Buchbinder et al. can be realized as a randomized online double-sided myopic algorithm, no such deterministic algorithm, even with adaptive ordering, can achieve the same approximation ratio. With respect to the Max-Di-Cut problem, we relate the Buchbinder et al. algorithm and our myopic framework to the online algorithm and inapproximation of Bar-Noy and Lampis.
Time-Switching Uplink Network-Coded Cooperative Communication with Downlink Energy Transfer
Venue: arXiv cs.IT 2014
Year: 2014

In this work, we consider a multiuser cooperative wireless network where the energy-constrained sources have independent information to transmit to a common destination, which is assumed to be externally powered and responsible for transferring energy wirelessly to the sources. The source nodes may cooperate, under either decode-and-forward or network coding-based protocols. Taking into account the fact that the energy harvested by the source nodes is a function of the fading realization of inter-user channels and user-destination channels, we obtain a closed-form approximation for the system outage probability, as well as an approximation for the optimal energy transfer period that minimizes such outage probability. It is also shown that, even though the achievable diversity order is reduced due to wireless energy transfer process, it is very close to the one achieved for a network without energy constraints. Numerical results are also presented to validate the theoretical results.
Synchrophasor monitoring of single line outages via area angle and susceptance
Venue: arXiv cs.SY 2014
Year: 2014

The area angle is a scalar measure of power system area stress that responds to line outages within the area and is a combination of synchrophasor measurements of voltage angles around the border of the area. Both idealized and practical examples are given to show that the variation of the area angle for single line outages can be approximately related to changes in the overall susceptance of the area and the line outage severity.
No-Sense: Sense with Dormant Sensors
Venue: arXiv cs.NI 2014
Year: 2014

Wireless sensor networks (WSNs) have enabled continuous monitoring of an area of interest (body, room, region, etc.) while eliminating expensive wired infrastructure. Typically in such applications, wireless sensor nodes report the sensed values to a sink node, where the information is required for the end-user. WSNs also provide the flexibility to the end-user for choosing several parameters for the monitoring application. For example, placement of sensors, frequency of sensing and transmission of those sensed data. Over the years, the advancement in embedded technology has led to increased processing power and memory capacity of these battery powered devices. However, batteries can only supply limited energy, thus limiting the lifetime of the network. In order to prolong the lifetime of the deployment, various efforts have been made to improve the battery technologies and also reduce the energy consumption of the sensor node at various layers in the networking stack. Of all the operations in the network stack, wireless data transmission and reception have found to consume most of the energy. Hence many proposals found in the literature target reducing them through intelligent schemes like power control, reducing retransmissions, etc. In this article we propose a new framework called Virtual Sensing Framework (VSF), which aims to sufficiently satisfy application requirements while conserving energy at the sensor nodes.
Sparse Matrix-based Random Projection for Classification
Venue: arXiv cs.LG 2014
Year: 2014

As a typical dimensionality reduction technique, random projection can be simply implemented with linear projection, while maintaining the pairwise distances of high-dimensional data with high probability. Considering this technique is mainly exploited for the task of classification, this paper is developed to study the construction of random matrix from the viewpoint of feature selection, rather than of traditional distance preservation. This yields a somewhat surprising theoretical result, that is, the sparse random matrix with exactly one nonzero element per column, can present better feature selection performance than other more dense matrices, if the projection dimension is sufficiently large (namely, not much smaller than the number of feature elements); otherwise, it will perform comparably to others. For random projection, this theoretical result implies considerable improvement on both complexity and performance, which is widely confirmed with the classification experiments on both synthetic data and real data.
Vulnerability of LTE to Hostile Interference
Venue: arXiv cs.OH 2014
Year: 2014

LTE is well on its way to becoming the primary cellular standard, due to its performance and low cost. Over the next decade we will become dependent on LTE, which is why we must ensure it is secure and available when we need it. Unfortunately, like any wireless technology, disruption through radio jamming is possible. This paper investigates the extent to which LTE is vulnerable to intentional jamming, by analyzing the components of the LTE downlink and uplink signals. The LTE physical layer consists of several physical channels and signals, most of which are vital to the operation of the link. By taking into account the density of these physical channels and signals with respect to the entire frame, as well as the modulation and coding schemes involved, we come up with a series of vulnerability metrics in the form of jammer to signal ratios. The ``weakest links'' of the LTE signals are then identified, and used to establish the overall vulnerability of LTE to hostile interference.
Codes for Tasks and Rényi Entropy Rate
Venue: arXiv cs.IT 2014
Year: 2014

A task is randomly drawn from a finite set of tasks and is described using a fixed number of bits. All the tasks that share its description must be performed. Upper and lower bounds on the minimum $ρ$-th moment of the number of performed tasks are derived. The key is an analog of the Kraft Inequality for partitions of finite sets. When a sequence of tasks is produced by a source of a given Rényi entropy rate of order $1/(1+ρ)$ and $n$ tasks are jointly described using $nR$ bits, it is shown that for $R$ larger than the Rényi entropy rate, the $ρ$-th moment of the ratio of performed tasks to $n$ can be driven to one as $n$ tends to infinity, and that for $R$ less than the Rényi entropy rate it tends to infinity. This generalizes a recent result for IID sources by the same authors. A mismatched version of the direct part is also considered, where the code is designed according to the wrong law. The penalty incurred by the mismatch can be expressed in terms of a divergence measure that was shown by Sundaresan to play a similar role in the Massey-Arikan guessing problem.
Network error correction with limited feedback capacity
Venue: arXiv cs.IT 2014
Year: 2014

We consider the problem of characterizing network capacity in the presence of adversarial errors on network links,focusing in particular on the effect of low-capacity feedback links cross network cuts.
Parametrized Invariance for Infinite State Processes
Venue: arXiv cs.LO 2014
Year: 2014

We study the uniform verification problem for infinite state processes, which consists of proving that the parallel composition of an arbitrary number of processes satisfies a temporal property. Our practical motivation is to build a general framework for the temporal verification of concurrent datatypes. The contribution of this paper is a general method for the verification of safety properties of parametrized programs that manipulate complex local and global data, including mutable state in the heap. This method is based on the separation between two concerns: (1) the interaction between executing threads---handled by novel parametrized invariance rules---,and the data being manipulated---handled by specialized decision procedures. The proof rules discharge automatically a finite collection of verification conditions (VCs), the number depending only on the size of the program description and the specification, but not on the number of processes in any given instance or on the kind of data manipulated. Moreover, all VCs are quantifier free, which eases the development of decision procedures for complex data-types on top of off-the-shelf SMT solvers. We discuss the practical verification (of shape and also functional correctness properties) of a concurrent list implementation based on the method presented in this paper. Our tool also all VCs using a decision procedure for a theory of list layouts in the heap built on top of state-of-the-art SMT solvers.
Scheduling MapReduce Jobs and Data Shuffle on Unrelated Processors
Venue: arXiv cs.DC 2014
Year: 2014

We propose constant approximation algorithms for generalizations of the Flexible Flow Shop (FFS) problem which form a realistic model for non-preemptive scheduling in MapReduce systems. Our results concern the minimization of the total weighted completion time of a set of MapReduce jobs on unrelated processors and improve substantially on the model proposed by Moseley et al. (SPAA 2011) in two directions. First, we consider each job consisting of multiple Map and Reduce tasks, as this is the key idea behind MapReduce computations, and we propose a constant approximation algorithm. Then, we introduce into our model the crucial cost of data shuffle phase, i.e., the cost for the transmission of intermediate data from Map to Reduce tasks. In fact, we model this phase by an additional set of Shuffle tasks for each job and we manage to keep the same approximation ratio when they are scheduled on the same processors with the corresponding Reduce tasks and to provide also a constant ratio when they are scheduled on different processors. This is the most general setting of the FFS problem (with a special third stage) for which a constant approximation ratio is known.
Is Non-Unique Decoding Necessary?
Venue: arXiv cs.IT 2014
Year: 2014

In multi-terminal communication systems, signals carrying messages meant for different destinations are often observed together at any given destination receiver. Han and Kobayashi (1981) proposed a receiving strategy which performs a joint unique decoding of messages of interest along with a subset of messages which are not of interest. It is now well-known that this provides an achievable region which is, in general, larger than if the receiver treats all messages not of interest as noise. Nair and El Gamal (2009) and Chong, Motani, Garg, and El Gamal (2008) independently proposed a generalization called indirect or non-unique decoding where the receiver uses the codebook structure of the messages to uniquely decode only its messages of interest. Non-unique decoding has since been used in various scenarios. The main result in this paper is to provide an interpretation and a systematic proof technique for why non-unique decoding, in all known cases where it has been employed, can be replaced by a particularly designed joint unique decoding strategy, without any penalty from a rate region viewpoint.
Social Media Monitoring of the Campaigns for the 2013 German Bundestag Elections on Facebook and Twitter
Venue: arXiv cs.SI 2014
Year: 2014

As more and more people use social media to communicate their view and perception of elections, researchers have increasingly been collecting and analyzing data from social media platforms. Our research focuses on social media communication related to the 2013 election of the German parlia-ment [translation: Bundestagswahl 2013]. We constructed several social media datasets using data from Facebook and Twitter. First, we identified the most relevant candidates (n=2,346) and checked whether they maintained social media accounts. The Facebook data was collected in November 2013 for the period of January 2009 to October 2013. On Facebook we identified 1,408 Facebook walls containing approximately 469,000 posts. Twitter data was collected between June and December 2013 finishing with the constitution of the government. On Twitter we identified 1,009 candidates and 76 other agents, for example, journalists. We estimated the number of relevant tweets to exceed eight million for the period from July 27 to September 27 alone. In this document we summarize past research in the literature, discuss possibilities for research with our data set, explain the data collection procedures, and provide a description of the data and a discussion of issues for archiving and dissemination of social media data.
A Survey of Data Mining Techniques for Social Media Analysis
Venue: arXiv cs.SI 2014
Year: 2014

Social network has gained remarkable attention in the last decade. Accessing social network sites such as Twitter, Facebook LinkedIn and Google+ through the internet and the web 2.0 technologies has become more affordable. People are becoming more interested in and relying on social network for information, news and opinion of other users on diverse subject matters. The heavy reliance on social network sites causes them to generate massive data characterised by three computational issues namely; size, noise and dynamism. These issues often make social network data very complex to analyse manually, resulting in the pertinent use of computational means of analysing them. Data mining provides a wide range of techniques for detecting useful knowledge from massive datasets like trends, patterns and rules [44]. Data mining techniques are used for information retrieval, statistical modelling and machine learning. These techniques employ data pre-processing, data analysis, and data interpretation processes in the course of data analysis. This survey discusses different data mining techniques used in mining diverse aspects of the social network over decades going from the historical techniques to the up-to-date models, including our novel technique named TRCM. All the techniques covered in this survey are listed in the Table.1 including the tools employed as well as names of their authors.
Heterogeneous Programming with Single Operation Multiple Data
Venue: arXiv cs.DC 2014
Year: 2014

Heterogeneity is omnipresent in today's commodity computational systems, which comprise at least one multi-core Central Processing Unit (CPU) and one Graphics Processing Unit (GPU). Nonetheless, all this computing power is not being exploited in mainstream computing, as the programming of these systems entails many details of the underlying architecture and of its distinct execution models. Current research on parallel programming is addressing these issues but, still, the systems' heterogeneity is exposed at language level. This paper proposes a uniform framework, grounded on the Single Operation Multiple Data model, for the programming of such heterogeneous systems. The model is declarative, empowering the compiler to generate code for multiple architectures from the same source. To this extent, we designed a simple extension of the Java programming language that embodies the model, and developed a compiler that generates code for both multi-core CPUs and GPUs. A performance evaluation attests the validity of the approach that, despite being based on a simple programming model, is able to deliver performance gains on par with hand-tuned data parallel multi-threaded Java applications.
Object Selection under Team Context
Venue: arXiv cs.DB 2014
Year: 2014

Context-aware database has drawn increasing attention from both industry and academia recently by taking users' current situation and environment into consideration. However, most of the literature focus on individual context, overlooking the team users. In this paper, we investigate how to integrate team context into database query process to help the users' get top-ranked database tuples and make the team more competitive. We introduce naive and optimized query algorithm to select the suitable records and show that they output the same results while the latter is more computational efficient. Extensive empirical studies are conducted to evaluate the query approaches and demonstrate their effectiveness and efficiency.
Security of the Improved Fuzzy Vault Scheme in the Presence of Record Multiplicity (Full Version)
Venue: arXiv cs.CR 2014
Year: 2014

Dodis et al. proposed an improved version of the fuzzy vault scheme, one of the most popular primitives used in biometric cryptosystems, requiring less storage and leaking less information. Recently, Blanton and Aliasgari have shown that the relation of two improved fuzzy vault records of the same individual may be determined by solving a system of non-linear equations. However, they conjectured that this is feasible for small parameters only. In this paper, we present a new attack against the improved fuzzy vault scheme based on the extended Euclidean algorithm that determines if two records are related and recovers the elements by which the protected features, e.g., the biometric templates, differ. Our theoretical and empirical analysis demonstrates that the attack is very effective and efficient for practical parameters. Furthermore, we show how this attack can be extended to fully recover both feature sets from related vault records much more efficiently than possible by attacking each record individually. We complement this work by deriving lower bounds for record multiplicity attacks and use these to show that our attack is asymptotically optimal in an information theoretic sense. Finally, we propose remedies to harden the scheme against record multiplicity attacks.
A Pricing-Based Cooperative Spectrum Sharing Stackelberg Game
Venue: arXiv cs.NI 2014
Year: 2014

We consider the problem of cooperative spectrum sharing among a primary user (PU) and multiple secondary users (SUs) under quality of service (QoS) constraints. The SUs network is controlled by the PU through a relay which gets a revenue for amplifying and forwarding the SUs signals to their respective destinations. The relay charges each SU a different price depending on its received signal-to-interference and-noise ratio (SINR). The relay can control the SUs network and maximize any desired PU utility function. The PU utility function represents its rate, which is affected by the SUs access, and its gained revenue to allow the access of the SUs. The SU network can be formulated as a game in which each SU wants to maximize its utility function; the problem is formulated as a Stackelberg game. Finally, the problem of maximizing the primary utility function is solved through three different approaches, namely, the optimal, the heuristic and the suboptimal algorithms.