OpenRaiser/Intern-Atlas huggingface dataset:
Combinatorial Auctions with Conflict-Based Externalities
Venue: arXiv cs.GT 2015
Year: 2015

Combinatorial auctions (CA) are a well-studied area in algorithmic mechanism design. However, contrary to the standard model, empirical studies suggest that a bidder's valuation often does not depend solely on the goods assigned to him. For instance, in adwords auctions an advertiser might not want his ads to be displayed next to his competitors' ads. In this paper, we propose and analyze several natural graph-theoretic models that incorporate such negative externalities, in which bidders form a directed conflict graph with maximum out-degree $Δ$. We design algorithms and truthful mechanisms for social welfare maximization that attain approximation ratios depending on $Δ$. For CA, our results are twofold: (1) A lottery that eliminates conflicts by discarding bidders/items independent of the bids. It allows to apply any truthful $α$-approximation mechanism for conflict-free valuations and yields an $\mathcal{O}(αΔ)$-approximation mechanism. (2) For fractionally sub-additive valuations, we design a rounding algorithm via a novel combination of a semi-definite program and a linear program, resulting in a cone program; the approximation ratio is $\mathcal{O}((Δ\log \log Δ)/\log Δ)$. The ratios are almost optimal given existing hardness results. For the prominent application of adwords auctions, we present several algorithms for the most relevant scenario when the number of items is small. In particular, we design a truthful mechanism with approximation ratio $o(Δ)$ when the number of items is only logarithmic in the number of bidders.
Normalized rotation shape descriptors and lossy compression of molecular shape
Venue: arXiv cs.CE 2015
Year: 2015

There is a common need to search of molecular databases for compounds resembling some shape, what suggests having similar biological activity while searching for new drugs. The large size of the databases requires fast methods for such initial screening, for example based on feature vectors constructed to fulfill the requirement that similar molecules should correspond to close vectors. Ultrafast Shape Recognition (USR) is a popular approach of this type. It uses vectors of 12 real number as 3 first moments of distances from 4 emphasized points. These coordinates might contain unnecessary correlations and does not allow to reconstruct the approximated shape. In contrast, spherical harmonic (SH) decomposition uses orthogonal coordinates, suggesting their independence and so lager informational content of the feature vector. There is usually considered rotationally invariant SH descriptors, what means discarding of some essential information. This article discusses framework for descriptors with normalized rotation, for example by using principal component analysis (PCA-SH). As one of the most interesting are ligands which have to slide into a protein, we will introduce descriptors optimized for such flat elongated shapes. Bent deformed cylinder (BDC) describes the molecule as a cylinder which was first bent, then deformed such that its cross-sections became ellipses of evolving shape. Legendre polynomials are used to describe the central axis of such bent cylinder. Additional polynomials are used to define evolution of such elliptic cross-section along the main axis. There will be also discussed bent cylindrical harmonics (BCH), which uses cross-sections described by cylindrical harmonics instead of ellipses. All these normalized rotation descriptors allow to reconstruct (decode) the approximated representation of the shape, hence can be also used for lossy compression purposes.
Polish to English Statistical Machine Translation
Venue: arXiv cs.CL 2015
Year: 2015

This research explores the effects of various training settings on a Polish to English Statistical Machine Translation system for spoken language. Various elements of the TED, Europarl, and OPUS parallel text corpora were used as the basis for training of language models, for development, tuning and testing of the translation system. The BLEU, NIST, METEOR and TER metrics were used to evaluate the effects of the data preparations on the translation results.
Time Dependent Analysis with Dynamic Counter Measure Trees
Venue: arXiv cs.CR 2015
Year: 2015

The success of a security attack crucially depends on time: the more time available to the attacker, the higher the probability of a successful attack. Formalisms such as Reliability block diagrams, Reliability graphs and Attack Countermeasure trees provide quantitative information about attack scenarios, but they are provably insufficient to model dependent actions which involve costs, skills, and time. In this presentation, we extend the Attack Countermeasure trees with a notion of time; inspired by the fact that there is a strong correlation between the amount of resources in which the attacker invests (in this case time) and probability that an attacker succeeds. This allows for an effective selection of countermeasures and rank them according to their resource consumption in terms of costs/skills of installing them and effectiveness in preventing an attack
Optimal Sensor Scheduling and Remote Estimation over an Additive Noise Channel
Venue: arXiv cs.SY 2015
Year: 2015

We consider a sensor scheduling and remote estimation problem with one sensor and one estimator. At each time step, the sensor makes an observation on the state of a source, and then decides whether to transmit its observation to the estimator or not. The sensor is charged a cost for each transmission. The remote estimator generates a real-time estimate on the state of the source based on the messages received from the sensor. The estimator is charged for estimation error. As compared with previous works from the literature, we further assume that there is an additive communication channel noise. As a consequence, the sensor needs to encode the message before transmitting it to the estimator. For some specific distributions of the underlying random variables, we obtain the optimal solution to the problem of minimizing the expected value of the sum of communication cost and estimation cost over the time horizon.
Supporting Regularized Logistic Regression Privately and Efficiently
Venue: arXiv cs.LG 2015
Year: 2015

As one of the most popular statistical and machine learning models, logistic regression with regularization has found wide adoption in biomedicine, social sciences, information technology, and so on. These domains often involve data of human subjects that are contingent upon strict privacy regulations. Increasing concerns over data privacy make it more and more difficult to coordinate and conduct large-scale collaborative studies, which typically rely on cross-institution data sharing and joint analysis. Our work here focuses on safeguarding regularized logistic regression, a widely-used machine learning model in various disciplines while at the same time has not been investigated from a data security and privacy perspective. We consider a common use scenario of multi-institution collaborative studies, such as in the form of research consortia or networks as widely seen in genetics, epidemiology, social sciences, etc. To make our privacy-enhancing solution practical, we demonstrate a non-conventional and computationally efficient method leveraging distributing computing and strong cryptography to provide comprehensive protection over individual-level and summary data. Extensive empirical evaluation on several studies validated the privacy guarantees, efficiency and scalability of our proposal. We also discuss the practical implications of our solution for large-scale studies and applications from various disciplines, including genetic and biomedical studies, smart grid, network analysis, etc.
A Wait-Free Stack
Venue: arXiv cs.DC 2015
Year: 2015

In this paper, we describe a novel algorithm to create a con- current wait-free stack. To the best of our knowledge, this is the first wait-free algorithm for a general purpose stack. In the past, researchers have proposed restricted wait-free implementations of stacks, lock-free implementations, and efficient universal constructions that can support wait-free stacks. The crux of our wait-free implementation is a fast pop operation that does not modify the stack top; instead, it walks down the stack till it finds a node that is unmarked. It marks it but does not delete it. Subsequently, it is lazily deleted by a cleanup operation. This operation keeps the size of the stack in check by not allowing the size of the stack to increase beyond a factor of W as compared to the actual size. All our operations are wait-free and linearizable.
Making problems tractable on big data via preprocessing with polylog-size output
Venue: arXiv cs.CC 2015
Year: 2015

To provide a dichotomy between those queries that can be made feasible on big data after appropriate preprocessing and those for which preprocessing does not help, Fan et al. developed the $\sqcap$-tractability theory. This theory provides a formal foundation for understanding the tractability of query classes in the context of big data. Along this line, we introduce a novel notion of $\sqcap'$-tractability in this paper. Inspired by some technologies used to deal big data, we place a restriction on preprocessing function, which limits the function to produce a relatively small database as output, at most polylog-size of the input database. At the same time, we bound the redundancy information when re-factorizing data and queries for preprocessing. These changes aim to make our theory more closely linked to practice. We set two complexity classes to denote the classes of Boolean queries that are $\sqcap'$-tractable themselves and that can be made $\sqcap'$-tractable, respectively. Based on a new factorization in our complexity classes, we investigate two reductions, which differ from whether allowing re-factorizing data and query parts. We verify the transitive and compatible properties of the reductions and analysis the complete problems and sizes of the complexity classes. We conclude that all PTIME classes of Boolean queries can be made $\sqcap'$-tractable, similar to that of the $\sqcap$-tractability theory. With a little surprise, we prove that the set of all $\sqcap'$-tractable queries is strictly smaller than that of all $\sqcap$-tractable queries, and thus the set of $\sqcap'$-tractable queries is properly contained in that of PTIME queries. In this way, we attain a new complexity class inside the complexity class of PTIME queries.
Determination of the Internet Anonymity Influence on the Level of Aggression and Usage of Obscene Lexis
Venue: arXiv cs.CL 2015
Year: 2015

This article deals with the analysis of the semantic content of the anonymous Russian-speaking forum 2ch.hk, different verbal means of expressing of the emotional state of aggression are revealed for this site, and aggression is classified by its directions. The lexis of different Russian-and English- speaking anonymous forums (2ch.hk and iichan.hk, 4chan.org) and public community "MDK" of the Russian-speaking social network VK is analyzed and compared with the Open Corpus of the Russian language (Opencorpora.org and Brown corpus). The analysis shows that anonymity has no influence on the amount of invective items usage. The effectiveness of moderation was shown for anonymous forums. It was established that Russian obscene lexis was used to express the emotional state of aggression only in 60.4% of cases for 2ch.hk. These preliminary results show that the Russian obscene lexis on the Internet does not have direct dependence on the emotional state of aggression.
RDF Knowledge Graph Visualization From a Knowledge Extraction System
Venue: arXiv cs.HC 2015
Year: 2015

In this paper, we present a system to visualize RDF knowledge graphs. These graphs are obtained from a knowledge extraction system designed by GEOLSemantics. This extraction is performed using natural language processing and trigger detection. The user can visualize subgraphs by selecting some ontology features like concepts or individuals. The system is also multilingual, with the use of the annotated ontology in English, French, Arabic and Chinese.
The ICSTM+TUM+UP Approach to the 3rd CHIME Challenge: Single-Channel LSTM Speech Enhancement with Multi-Channel Correlation Shaping Dereverberation and LSTM Language Models
Venue: arXiv cs.SD 2015
Year: 2015

This paper presents our contribution to the 3rd CHiME Speech Separation and Recognition Challenge. Our system uses Bidirectional Long Short-Term Memory (BLSTM) Recurrent Neural Networks (RNNs) for Single-channel Speech Enhancement (SSE). Networks are trained to predict clean speech as well as noise features from noisy speech features. In addition, the system applies two methods of dereverberation on the 6-channel recordings of the challenge. The first is the Phase-Error based Filtering (PEF) that uses time-varying phase-error filters based on estimated time-difference of arrival of the speech source and the phases of the microphone signals. The second is the Correlation Shaping (CS) that applies a reduction of the long-term correlation energy in reverberant speech. The Linear Prediction (LP) residual is processed to suppress the long-term correlation. Furthermore, the system employs a LSTM Language Model (LM) to perform N-best rescoring of recognition hypotheses. Using the proposed methods, an improved Word Error Rate (WER) of 24.38% is achieved over the real eval test set. This is around 25% relative improvement over the challenge baseline.
On independent set on B1-EPG graphs
Venue: arXiv cs.DS 2015
Year: 2015

In this paper we consider the Maximum Independent Set problem (MIS) on $B_1$-EPG graphs. EPG (for Edge intersection graphs of Paths on a Grid) was introduced in ~\cite{edgeintersinglebend} as the class of graphs whose vertices can be represented as simple paths on a rectangular grid so that two vertices are adjacent if and only if the corresponding paths share at least one edge of the underlying grid. The restricted class $B_k$-EPG denotes EPG-graphs where every path has at most $k$ bends. The study of MIS on $B_1$-EPG graphs has been initiated in~\cite{wadsMIS} where authors prove that MIS is NP-complete on $B_1$-EPG graphs, and provide a polynomial $4$-approximation. In this article we study the approximability and the fixed parameter tractability of MIS on $B_1$-EPG. We show that there is no PTAS for MIS on $B_1$-EPG unless P$=$NP, even if there is only one shape of path, and even if each path has its vertical part or its horizontal part of length at most $3$. This is optimal, as we show that if all paths have their horizontal part bounded by a constant, then MIS admits a PTAS. Finally, we show that MIS is FPT in the standard parameterization on $B_1$-EPG restricted to only three shapes of path, and $W_1$-hard on $B_2$-EPG. The status for general $B_1$-EPG (with the four shapes) is left open.
Multi-armed Bandits with Application to 5G Small Cells
Venue: arXiv cs.LG 2015
Year: 2015

Due to the pervasive demand for mobile services, next generation wireless networks are expected to be able to deliver high date rates while wireless resources become more and more scarce. This requires the next generation wireless networks to move towards new networking paradigms that are able to efficiently support resource-demanding applications such as personalized mobile services. Examples of such paradigms foreseen for the emerging fifth generation (5G) cellular networks include very densely deployed small cells and device-to-device communications. For 5G networks, it will be imperative to search for spectrum and energy-efficient solutions to the resource allocation problems that i) are amenable to distributed implementation, ii) are capable of dealing with uncertainty and lack of information, and iii) can cope with users' selfishness. The core objective of this article is to investigate and to establish the potential of multi-armed bandit (MAB) framework to address this challenge. In particular, we provide a brief tutorial on bandit problems, including different variations and solution approaches. Furthermore, we discuss recent applications as well as future research directions. In addition, we provide a detailed example of using an MAB model for energy-efficient small cell planning in 5G networks.
A Note on Graphs with 2 Bends
Venue: arXiv cs.CC 2015
Year: 2015

We show NP-completeness for the recognition problem of 2-line-bend graphs.
Machine Learning for Machine Data from a CATI Network
Venue: arXiv cs.LG 2015
Year: 2015

This is a machine learning application paper involving big data. We present high-accuracy prediction methods of rare events in semi-structured machine log files, which are produced at high velocity and high volume by NORC's computer-assisted telephone interviewing (CATI) network for conducting surveys. We judiciously apply natural language processing (NLP) techniques and data-mining strategies to train effective learning and prediction models for classifying uncommon error messages in the log---without access to source code, updated documentation or dictionaries. In particular, our simple but effective approach of features preallocation for learning from imbalanced data coupled with naive Bayes classifiers can be conceivably generalized to supervised or semi-supervised learning and prediction methods for other critical events such as cyberattack detection.
Trilateral Large-Scale OSN Account Linkability Study
Venue: arXiv cs.CY 2015
Year: 2015

In the last decade, Online Social Networks (OSNs) have taken the world by storm. They range from superficial to professional, from focused to general-purpose, and, from free-form to highly structured. Numerous people have multiple accounts within the same OSN and even more people have an account on more than one OSN. Since all OSNs involve some amount of user input, often in written form, it is natural to consider whether multiple incarnations of the same person in various OSNs can be effectively correlated or linked. One intuitive means of linking accounts is by using stylometric analysis. This paper reports on (what we believe to be) the first trilateral large-scale stylometric OSN linkability study. Its outcome has important implications for OSN privacy. The study is trilateral since it involves three OSNs with very different missions: (1) Yelp, known primarily for its user-contributed reviews of various venues, e.g, dining and entertainment, (2) Twitter, popular for its pithy general-purpose micro-blogging style, and (3) Flickr, used exclusively for posting and labeling (describing) photographs. As our somewhat surprising results indicate, stylometric linkability of accounts across these heterogeneous OSNs is both viable and quite effective. The main take-away of this work is that, despite OSN heterogeneity, it is very challenging for one person to maintain privacy across multiple active accounts on different OSNs.
Delay-optimal Data Transmission in Renewable Energy Aided Cognitive Radio Networks
Venue: arXiv cs.IT 2015
Year: 2015

Renewable energy powered cognitive radio (CR) network has gained much attention due to its combination of the CR's spectrum efficiency and the renewable energy's "green" nature. In the paper, we investigate the delay-optimal data transmission in the renewable energy aided CR networks. Specifically, a primary user (PU) and a secondary user (SU) share the same frequency in an area. The SU's interference to the PU is controlled by interference-signal-ratio (ISR) constraint, which means that the ISR at the PU receiver (Rx) should be less than a threshold. Under this constraint, the renewable energy powered SU aims to minimize the average data buffer delay by scheduling the renewable allocations in each slot. A constrained stochastic optimization problem is formulated when the randomness of the renewable arrival, the uncertainty of the SU's data generation, and the variability of the fading channel are taken into account. By analyzing the formulated problem, we propose two practical algorithms that is optimal for two special scenarios. And the two algorithms respectively give an upper and a lower bound for the general scenario. In addition, the availability of the PU's private information at the SU is discussed. Finally, numerical simulations verify the effectiveness of the proposed algorithm.
Background Image Generation Using Boolean Operations
Venue: arXiv cs.CV 2015
Year: 2015

Tracking moving objects from a video sequence requires segmentation of these objects from the background image. However, getting the actual background image automatically without object detection and using only the video is difficult. In this paper, we describe a novel algorithm that generates background from real world images without foreground detection. The algorithm assumes that the background image is shown in the majority of the video. Given this simple assumption, the method described in this paper is able to accurately generate, with high probability, the background image from a video using only a small number of binary operations.
Retractable state-finite automata without outputs
Venue: arXiv cs.FL 2015
Year: 2015

A homomorphism of an automaton ${\bf A}$ without outputs onto a subautomaton ${\bf B}$ of ${\bf A}$ is called a retract homomorphism if it leaves the elements of $B$ fixed. An automaton ${\bf A}$ is called a retractable automaton if, for every subautomaton ${\bf B}$ of ${\bf A}$, there is a retract homomorphism of ${\bf A}$ onto ${\bf B}$. In [1] and [3], special retractable automata are examined. The purpose of this paper is to give a complete description of state-finite retractable automata without outputs.
The Essence of JavaScript
Venue: arXiv cs.PL 2015
Year: 2015

We reduce JavaScript to a core calculus structured as a small-step operational semantics. We present several peculiarities of the language and show that our calculus models them. We explicate the desugaring process that turns JavaScript programs into ones in the core. We demonstrate faithfulness to JavaScript using real-world test suites. Finally, we illustrate utility by defining a security property, implementing it as a type system on the core, and extending it to the full language.
Rank distribution of Delsarte codes
Venue: arXiv cs.IT 2015
Year: 2015

In analogy with the Singleton defect for classical codes, we propose a definition of rank defect for Delsarte rank-metric codes. We characterize codes whose rank defect and dual rank defect are both zero, and prove that the rank distribution of such codes is determined by their parameters. This extends a result by Delsarte on the rank distribution of MRD codes. In the general case of codes of positive defect, we show that the rank distribution is determined by the parameters of the code, together the number of codewords of small rank. Moreover, we prove that if the rank defect of a code and its dual are both one, and the dimension satisfies a divisibility condition, then the number of minimum-rank codewords and dual minimum-rank codewords is the same. Finally, we discuss how our results specialize to Gabidulin codes.