OpenRaiser/Intern-Atlas huggingface dataset:
An Account of Opinion Implicatures
Venue: arXiv cs.CL 2014
Year: 2014

While previous sentiment analysis research has concentrated on the interpretation of explicitly stated opinions and attitudes, this work initiates the computational study of a type of opinion implicature (i.e., opinion-oriented inference) in text. This paper described a rule-based framework for representing and analyzing opinion implicatures which we hope will contribute to deeper automatic interpretation of subjective language. In the course of understanding implicatures, the system recognizes implicit sentiments (and beliefs) toward various events and entities in the sentence, often attributed to different sources (holders) and of mixed polarities; thus, it produces a richer interpretation than is typical in opinion analysis.
Cellular Interference Alignment: Omni-Directional Antennas and Asymmetric Configurations
Venue: arXiv cs.IT 2014
Year: 2014

Although interference alignment (IA) can theoretically achieve the optimal degrees of freedom (DoFs) in the $K$-user Gaussian interference channel, its direct application comes at the prohibitive cost of precoding over exponentially-many signaling dimensions. On the other hand, it is known that practical "one-shot" IA precoding (i.e., linear schemes without symbol expansion) provides a vanishing DoFs gain in large fully-connected networks with generic channel coefficients. In our previous work, we introduced the concept of "Cellular IA" for a network topology induced by hexagonal cells with sectors and nearest-neighbor interference. Assuming that neighboring sectors can exchange decoded messages (and not received signal samples) in the uplink, we showed that linear one-shot IA precoding over $M$ transmit/receive antennas can achieve the optimal $M/2$ DoFs per user. In this paper we extend this framework to networks with omni-directional (non-sectorized) cells and consider the practical scenario where users have $2$ antennas, and base-stations have $2$, $3$ or $4$ antennas. In particular, we provide linear one-shot IA schemes for the $2\times 2$, $2\times3$ and $2\times 4$ cases, and show the achievability of $3/4$, $1$ and $7/6$ DoFs per user, respectively. DoFs converses for one-shot schemes require the solution of a discrete optimization problem over a number of variables that grows with the network size. We develop a new approach to transform such challenging optimization problem into a tractable linear program (LP) with significantly fewer variables. This approach is used to show that the achievable $3/4$ DoFs per user are indeed optimal for a large (extended) cellular network with $2\times 2$ links.
Experience in using a typed functional language for the development of a security application
Venue: arXiv cs.SE 2014
Year: 2014

In this paper we present our experience in developing a security application using a typed functional language. We describe how the formal grounding of its semantic and compiler have allowed for a trustworthy development and have facilitated the fulfillment of the security specification.
Space-Time Storage Codes for Wireless Distributed Storage Systems
Venue: arXiv cs.IT 2014
Year: 2014

Distributed storage systems (DSSs) have gained a lot of interest recently, thanks to their robustness and scalability compared to single-device storage. Majority of the related research has exclusively concerned the network layer. At the same time, the number of users of, e.g., peer-to-peer (p2p) and device-to-device (d2d) networks as well as proximity based services is growing rapidly, and the mobility of users is considered more and more important. This motivates, in contrast to the existing literature, the study of the physical layer functionality of wireless distributed storage systems. In this paper, we take the first step towards protecting the storage repair transmissions from physical layer errors when the transmission takes place over a fading channel. To this end, we introduce the notion of a space-time storage code, drawing together the aspects of network layer and physical layer functionality and resulting in cross-layer robustness. It is also pointed out that existing space-time codes are too complex to be utilized in storage networks when the number of helpers involved is larger than the number of receive antennas at the newcomer or data collector, hence creating a call for less complex transmission protocols.
Cooperative Cognitive Relaying Under Primary and Secondary Quality of Service Satisfaction
Venue: arXiv cs.NI 2014
Year: 2014

This paper proposes a new cooperative protocol which involves cooperation between primary and secondary users. We consider a cognitive setting with one primary user and multiple secondary users. The time resource is partitioned into discrete time slots. Each time slot, a secondary user is scheduled for transmission according to time division multiple access, and the remainder of the secondary users, which we refer to as secondary relays, attempt to decode the primary packet. Afterwards, the secondary relays employ cooperative beamforming to forward the primary packet and to provide protection to the secondary destination of the secondary source scheduled for transmission from interference. We characterize the diversity-multiplexing tradeoff of the primary source under the proposed protocol. We consider certain quality of service for each user specified by its required throughput. The optimization problem is stated under such condition. It is shown that the optimization problem is linear and can be readily solved. We show that the sum of the secondary required throughputs must be less than or equal to the probability of correct packets reception.
Alternating Optimization Techniques for Power Allocation and Receiver Design in Multihop Wireless Sensor Networks
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we consider a multihop wireless sensor network with multiple relay nodes for each hop where the amplify-and-forward scheme is employed. We present algorithmic strategies to jointly design linear receivers and the power allocation parameters via an alternating optimization approach subject to different power constraints which include global, local and individual ones. Two design criteria are considered: the first one minimizes the mean-square error and the second one maximizes the sum-rate of the wireless sensor network. We derive constrained minimum mean-square error and constrained maximum sum-rate expressions for the linear receivers and the power allocation parameters that contain the optimal complex amplification coefficients for each relay node. An analysis of the computational complexity and the convergence of the algorithms is also presented. Computer simulations show good performance of our proposed methods in terms of bit error rate and sum-rate compared to the method with equal power allocation and an existing power allocation scheme.
Multiplicative Bidding in Online Advertising
Venue: arXiv cs.DS 2014
Year: 2014

In this paper, we initiate the study of the multiplicative bidding language adopted by major Internet search companies. In multiplicative bidding, the effective bid on a particular search auction is the product of a base bid and bid adjustments that are dependent on features of the search (for example, the geographic location of the user, or the platform on which the search is conducted). We consider the task faced by the advertiser when setting these bid adjustments, and establish a foundational optimization problem that captures the core difficulty of bidding under this language. We give matching algorithmic and approximation hardness results for this problem; these results are against an information-theoretic bound, and thus have implications on the power of the multiplicative bidding language itself. Inspired by empirical studies of search engine price data, we then codify the relevant restrictions of the problem, and give further algorithmic and hardness results. Our main technical contribution is an $O(\log n)$-approximation for the case of multiplicative prices and monotone values. We also provide empirical validations of our problem restrictions, and test our algorithms on real data against natural benchmarks. Our experiments show that they perform favorably compared with the baseline.
On the Capacity of the Underwater Acoustic Channel with Dominant Noise Sources
Venue: arXiv cs.IT 2014
Year: 2014

This paper provides an upper-bound for the capacity of the underwater acoustic (UWA) channel with dominant noise sources and generalized fading environments. Previous works have shown that UWA channel noise statistics are not necessary Gaussian, especially in a shallow water environment which is dominated by impulsive noise sources. In this case, noise is best represented by the Generalized Gaussian (GG) noise model with a shaping parameter $β$. On the other hand, fading in the UWA channel is generally represented using an $α$-$μ$ distribution, which is a generalization of a wide range of well known fading distributions. We show that the Additive White Generalized Gaussian Noise (AWGGN) channel capacity is upper bounded by the AWGN capacity in addition to a constant gap of $\frac{1}{2} \log \left(\frac{β^{2} πe^{1-\frac{2}β} Γ(\frac{3}β)}{2(Γ(\frac{1}β))^{3}} \right)$ bits. The same gap also exists when characterizing the ergodic capacity of AWGGN channels with $α$-$μ$ fading compared to the faded AWGN channel capacity. We justify our results by revisiting the sphere-packing problem, which represents a geometric interpertation of the channel capacity. Moreover, UWA channel secrecy rates are characterized and the dependency of UWA channel secrecy on the shaping parameters of the legitimate and eavesdropper channels is highlighted.
10 Inventions on Command Buttons in a Graphical User Interface
Venue: arXiv cs.HC 2014
Year: 2014

A command button may contain a textual label or a graphic image or both. It may be static or animated. There can be many different features to make a command button attractive and effective. As command button is a typical GUI element, most improvement on GUI in general will also be applicable to command buttons. Besides, there are also inventions to improve various aspects of command buttons in specific. This article illustrates 10 selected inventions from US patent database. Each invention is followed by a TRIZ based analysis in brief.
Why a Global Time is Needed in a Dependable SoS
Venue: arXiv cs.DC 2014
Year: 2014

A system-of-systems (SoS) is a large information processing system formed by the integration of autonomous computer systems (called constituent systems, CS), physical machines and humans for the purpose of providing new synergistic services and/or more efficient economic processes. In a number of applications, e.g robotics, the autonomous CSs must coordinate their actions in the temporal domain to realize the desired objectives. In this paper we argue that the introduction of a proper global physical time establishes a shared view about the progress of physical time and helps to realize the temporal coordination of the autonomous CSs. The available global time can also be used to simplify the solution of many challenging problems within the SoS, such as distributed resource allocation, and helps to improve the dependability and fault-tolerance of the SoS.
Inventions on GUI Aesthetics
Venue: arXiv cs.HC 2014
Year: 2014

Aesthetics or "look and feel" is one of the most important features of any graphical user interface. Better aesthetics makes the interface user-friendlier and more popular. Better aesthetics helps the user to understand the meaning of various components and memorize the navigation paths. A better look and feel ultimately makes a GUI more efficient and effective. Various methods are adopted to improve the aesthetics of a GUI, such as, by using colors, using 3D graphics, using pictorial icons, using sound etc. It is important to provide links to all the important features on a desktop or on a quick access panel. But too many icons or buttons sometimes creates confusion. Hence it is important to restrict the temptation of putting everything on the first screen or load the rarely used buttons on the toolbar. One should ensure that the aesthetics of a GUI is not compromising with its accessibility and other important features. This article illustrates some inventions made on GUI aesthetics.
Towards Assessing Necessary Competence
Venue: arXiv cs.SE 2014
Year: 2014

We sketch a series of studies and experiments designed to provide empirical evidence about the truth or falsity of claims that non-prescriptive approaches to standards demand greater competence from regulators than prescriptive approaches require.
Information Measures: the Curious Case of the Binary Alphabet
Venue: arXiv cs.IT 2014
Year: 2014

Four problems related to information divergence measures defined on finite alphabets are considered. In three of the cases we consider, we illustrate a contrast which arises between the binary-alphabet and larger-alphabet settings. This is surprising in some instances, since characterizations for the larger-alphabet settings do not generalize their binary-alphabet counterparts. Specifically, we show that $f$-divergences are not the unique decomposable divergences on binary alphabets that satisfy the data processing inequality, thereby clarifying claims that have previously appeared in the literature. We also show that KL divergence is the unique Bregman divergence which is also an $f$-divergence for any alphabet size. We show that KL divergence is the unique Bregman divergence which is invariant to statistically sufficient transformations of the data, even when non-decomposable divergences are considered. Like some of the problems we consider, this result holds only when the alphabet size is at least three.
Bypassing Erdős' Girth Conjecture: Hybrid Stretch and Sourcewise Spanners
Venue: arXiv cs.DS 2014
Year: 2014

An $(α,β)$-spanner of an $n$-vertex graph $G=(V,E)$ is a subgraph $H$ of $G$ satisfying that $dist(u, v, H) \leq α\cdot dist(u, v, G)+β$ for every pair $(u, v)\in V \times V$, where $dist(u,v,G')$ denotes the distance between $u$ and $v$ in $G' \subseteq G$. It is known that for every integer $k \geq 1$, every graph $G$ has a polynomially constructible $(2k-1,0)$-spanner of size $O(n^{1+1/k})$. This size-stretch bound is essentially optimal by the girth conjecture. It is therefore intriguing to ask if one can "bypass" the conjecture by settling for a multiplicative stretch of $2k-1$ only for \emph{neighboring} vertex pairs, while maintaining a strictly \emph{better} multiplicative stretch for the rest of the pairs. We answer this question in the affirmative and introduce the notion of \emph{$k$-hybrid spanners}, in which non neighboring vertex pairs enjoy a \emph{multiplicative} $k$-stretch and the neighboring vertex pairs enjoy a \emph{multiplicative} $(2k-1)$ stretch (hence, tight by the conjecture). We show that for every unweighted $n$-vertex graph $G$ with $m$ edges, there is a (polynomially constructible) $k$-hybrid spanner with $O(k^2 \cdot n^{1+1/k})$ edges. \indent An alternative natural approach to bypass the girth conjecture is to allow ourself to take care only of a subset of pairs $S \times V$ for a given subset of vertices $S \subseteq V$ referred to here as \emph{sources}. Spanners in which the distances in $S \times V$ are bounded are referred to as \emph{sourcewise spanners}. Several constructions for this variant are provided (e.g., multiplicative sourcewise spanners, additive sourcewise spanners and more).
Precedence-constrained Scheduling of Malleable Jobs with Preemption
Venue: arXiv cs.DS 2014
Year: 2014

Scheduling jobs with precedence constraints on a set of identical machines to minimize the total processing time (makespan) is a fundamental problem in combinatorial optimization. In practical settings such as cloud computing, jobs are often malleable, i.e., can be processed on multiple machines simultaneously. The instantaneous processing rate of a job is a non-decreasing function of the number of machines assigned to it (we call it the processing function). Previous research has focused on practically relevant concave processing functions, which obey the law of diminishing utility and generalize the classical (non-malleable) problem. Our main result is a $(2+ε)$-approximation algorithm for concave processing functions (for any $ε> 0$), which is the best possible under complexity theoretic assumptions. The approximation ratio improves to $(1 + ε)$ for the interesting and practically relevant special case of power functions, i.e., $p_j(z) = c_j \cdot z^γ$.
Performance Estimates of the Pseudo-Random Method for Radar Detection
Venue: arXiv cs.IT 2014
Year: 2014

A performance of the pseudo-random method for the radar detection is analyzed. The radar sends a pseudo-random sequence of length $N$, and receives echo from $r$ targets. We assume the natural assumptions of uniformity on the channel and of the square root cancellation on the noise. Then for $r \leq N^{1-δ}$, where $δ> 0$, the following holds: (i) the probability of detection goes to one, and (ii) the expected number of false targets goes to zero, as $N$ goes to infinity.
To Achieve Maximal Throughputs in CSMA Wireless Networks Through Offered_load Control
Venue: arXiv cs.NI 2014
Year: 2014

This paper studies how to achieve the maximal link throughputs in a CSMA wireless network through offered-load control. First, we propose an analytical model, contention-graph-combination (CGC), to describe the relationship between the offered-load and the output link throughputs of an unsaturated CSMA network. Based on CGC, we then formulate a linear optimization model to improve the aggregate link throughput through properly setting the occurrence probabilities of each sub-network, based on which we can obtain the optimal offered-load of each link. Simulation results bore out the accuracy of our CGC analysis and the maximal link throughputs can be closely achieved. Different from prior work in which CSMA protocol parameters are adaptively adjusted to achieve better performance, in this paper we propose to achieve maximal link throughputs by adjusting the rates of the traffic pumped into the source nodes of links, which runs in a software manner and is more practical to implement in real networks.
Probabilistic graphs using coupled random variables
Venue: arXiv cs.LG 2014
Year: 2014

Neural network design has utilized flexible nonlinear processes which can mimic biological systems, but has suffered from a lack of traceability in the resulting network. Graphical probabilistic models ground network design in probabilistic reasoning, but the restrictions reduce the expressive capability of each node making network designs complex. The ability to model coupled random variables using the calculus of nonextensive statistical mechanics provides a neural node design incorporating nonlinear coupling between input states while maintaining the rigor of probabilistic reasoning. A generalization of Bayes rule using the coupled product enables a single node to model correlation between hundreds of random variables. A coupled Markov random field is designed for the inferencing and classification of UCI's MLR 'Multiple Features Data Set' such that thousands of linear correlation parameters can be replaced with a single coupling parameter with just a (3%, 4%) percent reduction in (classification, inference) performance.
Preliminary Report on WASP 2.0
Venue: arXiv cs.AI 2014
Year: 2014

Answer Set Programming (ASP) is a declarative programming paradigm. The intrinsic complexity of the evaluation of ASP programs makes the development of more effective and faster systems a challenging research topic. This paper reports on the recent improvements of the ASP solver WASP. WASP is undergoing a refactoring process which will end up in the release of a new and more performant version of the software. In particular the paper focus on the improvements to the core evaluation algorithms working on normal programs. A preliminary experiment on benchmarks from the 3rd ASP competition belonging to the NP class is reported. The previous version of WASP was often not competitive with alternative solutions on this class. The new version of WASP shows a substantial increase in performance.
Stereo on a budget
Venue: arXiv cs.CV 2014
Year: 2014

We propose an algorithm for recovering depth using less than two images. Instead of having both cameras send their entire image to the host computer, the left camera sends its image to the host while the right camera sends only a fraction $ε$ of its image. The key aspect is that the cameras send the information without communicating at all. Hence, the required communication bandwidth is significantly reduced. While standard image compression techniques can reduce the communication bandwidth, this requires additional computational resources on the part of the encoder (camera). We aim at designing a light weight encoder that only touches a fraction of the pixels. The burden of decoding is placed on the decoder (host). We show that it is enough for the encoder to transmit a sparse set of pixels. Using only $1+ε$ images, with $ε$ as little as 2% of the image, the decoder can compute a depth map. The depth map's accuracy is comparable to traditional stereo matching algorithms that require both images as input. Using the depth map and the left image, the right image can be synthesized. No computations are required at the encoder, and the decoder's runtime is linear in the images' size.
Testing Forest-Isomorphism in the Adjacency List Model
Venue: arXiv cs.DS 2014
Year: 2014

We consider the problem of testing if two input forests are isomorphic or are far from being so. An algorithm is called an $\varepsilon$-tester for forest-isomorphism if given an oracle access to two forests $G$ and $H$ in the adjacency list model, with high probability, accepts if $G$ and $H$ are isomorphic and rejects if we must modify at least $\varepsilon n$ edges to make $G$ isomorphic to $H$. We show an $\varepsilon$-tester for forest-isomorphism with a query complexity $\mathrm{polylog}(n)$ and a lower bound of $Ω(\sqrt{\log{n}})$. Further, with the aid of the tester, we show that every graph property is testable in the adjacency list model with $\mathrm{polylog}(n)$ queries if the input graph is a forest.
Inventions on Drag and Drop in GUI
Venue: arXiv cs.HC 2014
Year: 2014

Drag and drop operation is one of the key capabilities of any Graphical User Interface. The user can do quite complex operations simply by visually dragging and dropping objects from one location to another. It saves user from remembering and typing a lot of commands. The result of a drag and drop operation may vary depending the type of source object and type of destination object. For example dragging a file and dropping on a folder may copy or move the file to the destination folder, dropping that file to a remote FTP location may upload that file using internet, dropping that file on a printer icon may print that file, dropping that file on the trash can may delete that file, and dropping that file on an executable may play or open or compute or manipulate that file. Although a drag and drop operation prima facie seems to be a simple operation, it can become extremely complicated depending on the type of source objects dragged and the type of destination objects selected for dropping. There are many limitations of a conventional drag and drop operation. This article points out the difficulties of a drag and drop operation and illustrates the solutions disclosed by various inventions to overcome those difficulties.