OpenRaiser/Intern-Atlas huggingface dataset:
Contact activity and dynamics of the online elite
Venue: arXiv cs.SI 2016
Year: 2016

Humans interact through numerous channels to build and maintain social connections: they meet face-to-face, initiate phone calls or send text messages, and interact via social media. Although it is known that the network of physical contacts, for example, is distinct from the network arising from communication events via phone calls and instant messages, the extent to which these networks differ is not clear. In fact, the network structure of these channels shows large structural variations. Each network of interactions, however, contains both central and peripheral individuals: central members are characterized by higher connectivity and can reach a high fraction of the network within a low number of connections, contrary to the nodes on the periphery. Here we show that the various channels account for diverse relationships between pairs of individuals and the corresponding interaction patterns across channels differ to an extent that hinders the simple reduction of social ties to a single layer. Furthemore, the origin and purpose of each network also determine the role of their respective central members: highly connected individuals in the person-to-person networks interact with their environment in a regular manner, while members central in the social communication networks display irregular behavior with respect to their physical contacts and are more active through rare, social events. These results suggest that due to the inherently different functions of communication channels, each one favors different social behaviors and different strategies for interacting with the environment. Our findings can facilitate the understanding of the varying roles and impact individuals have on the population, which can further shed light on the prediction and prevention of epidemic outbreaks, or information propagation.
An FPTAS for Counting Proper Four-Colorings on Cubic Graphs
Venue: arXiv cs.DS 2016
Year: 2016

Graph coloring is arguably the most exhaustively studied problem in the area of approximate counting. It is conjectured that there is a fully polynomial-time (randomized) approximation scheme (FPTAS/FPRAS) for counting the number of proper colorings as long as $q \geq Δ+ 1$, where $q$ is the number of colors and $Δ$ is the maximum degree of the graph. The bound of $q = Δ+ 1$ is the uniqueness threshold for Gibbs measure on $Δ$-regular infinite trees. However, the conjecture remained open even for any fixed $Δ\geq 3$ (The cases of $Δ=1, 2$ are trivial). In this paper, we design an FPTAS for counting the number of proper $4$-colorings on graphs with maximum degree $3$ and thus confirm the conjecture in the case of $Δ=3$. This is the first time to achieve this optimal bound of $q = Δ+ 1$. Previously, the best FPRAS requires $q > \frac{11}{6} Δ$ and the best deterministic FPTAS requires $q > 2.581Δ+ 1$ for general graphs. In the case of $Δ=3$, the best previous result is an FPRAS for counting proper 5-colorings. We note that there is a barrier to go beyond $q = Δ+ 2$ for single-site Glauber dynamics based FPRAS and we overcome this by correlation decay approach. Moreover, we develop a number of new techniques for the correlation decay approach which can find applications in other approximate counting problems.
Commonsense Knowledge Enhanced Embeddings for Solving Pronoun Disambiguation Problems in Winograd Schema Challenge
Venue: arXiv cs.AI 2016
Year: 2016

In this paper, we propose commonsense knowledge enhanced embeddings (KEE) for solving the Pronoun Disambiguation Problems (PDP). The PDP task we investigate in this paper is a complex coreference resolution task which requires the utilization of commonsense knowledge. This task is a standard first round test set in the 2016 Winograd Schema Challenge. In this task, traditional linguistic features that are useful for coreference resolution, e.g. context and gender information, are no longer effective anymore. Therefore, the KEE models are proposed to provide a general framework to make use of commonsense knowledge for solving the PDP problems. Since the PDP task doesn't have training data, the KEE models would be used during the unsupervised feature extraction process. To evaluate the effectiveness of the KEE models, we propose to incorporate various commonsense knowledge bases, including ConceptNet, WordNet, and CauseCom, into the KEE training process. We achieved the best performance by applying the proposed methods to the 2016 Winograd Schema Challenge. In addition, experiments conducted on the standard PDP task indicate that, the proposed KEE models could solve the PDP problems by achieving 66.7% accuracy, which is a new state-of-the-art performance.
On the $\mathcal{NP}$-hardness of GRacSim Drawing and k-SEFE Problems
Venue: arXiv cs.CG 2016
Year: 2016

We study the complexity of two problems in simultaneous graph drawing. The first problem, GRacSim Drawing, asks for finding a simultaneous geometric embedding of two graphs such that only crossings at right angles are allowed. The second problem, k-SEFE, is a restricted version of the topological simultaneous embedding with fixed edges (SEFE) problem, for two planar graphs, in which every private edge may receive at most $k$ crossings, where $k$ is a prescribed positive integer. We show that GRacSim Drawing is $\mathcal{NP}$-hard and that k-SEFE is $\mathcal{NP}$-complete. The $\mathcal{NP}$-hardness of both problems is proved using two similar reductions from 3-Partition.
Realistic risk-mitigating recommendations via inverse classification
Venue: arXiv cs.LG 2016
Year: 2016

Inverse classification, the process of making meaningful perturbations to a test point such that it is more likely to have a desired classification, has previously been addressed using data from a single static point in time. Such an approach yields inflated probability estimates, stemming from an implicitly made assumption that recommendations are implemented instantaneously. We propose using longitudinal data to alleviate such issues in two ways. First, we use past outcome probabilities as features in the present. Use of such past probabilities ties historical behavior to the present, allowing for more information to be taken into account when making initial probability estimates and subsequently performing inverse classification. Secondly, following inverse classification application, optimized instances' unchangeable features (e.g.,~age) are updated using values from the next longitudinal time period. Optimized test instance probabilities are then reassessed. Updating the unchangeable features in this manner reflects the notion that improvements in outcome likelihood, which result from following the inverse classification recommendations, do not materialize instantaneously. As our experiments demonstrate, more realistic estimates of probability can be obtained by factoring in such considerations.
Ghosts of Deletions Past: New Secure Deletion Challenges and Solutions
Venue: arXiv cs.CR 2016
Year: 2016

Is secure deletion of data still a problem?
A New Recurrent Neural CRF for Learning Non-linear Edge Features
Venue: arXiv cs.CL 2016
Year: 2016

Conditional Random Field (CRF) and recurrent neural models have achieved success in structured prediction. More recently, there is a marriage of CRF and recurrent neural models, so that we can gain from both non-linear dense features and globally normalized CRF objective. These recurrent neural CRF models mainly focus on encode node features in CRF undirected graphs. However, edge features prove important to CRF in structured prediction. In this work, we introduce a new recurrent neural CRF model, which learns non-linear edge features, and thus makes non-linear features encoded completely. We compare our model with different neural models in well-known structured prediction tasks. Experiments show that our model outperforms state-of-the-art methods in NP chunking, shallow parsing, Chinese word segmentation and POS tagging.
Revisiting 802.11 for User Fairness and Efficient Channel Utilization in Presence of LTE-U
Venue: arXiv cs.NI 2016
Year: 2016

A promising solution satisfying the industry's demand to have minimum alterations in LTE for its operation in unlicensed spectrum is duty cycled LTE-U scheme, which adopts discontinuous transmission to ensure fair coexistence with 802.11 (Wi-Fi) WLANs. Even though the scheme guarantees to maintain Wi-Fi network performance, the fairness among Wi-Fi users still remains arcane. In this work, we present a practical scenario where LTE-U, despite being discontinuous (by following an ON-OFF cycle), results in not only unfair throughput distribution among Wi-Fi users but also causes degradation in Wi-Fi APs downlink performance. This is due to the domination of few Wi-Fi users who harness channel in both ON and OFF durations of LTE-U, namely non-victim users over those who get access only in OFF duration, called victim users. In this paper, we studied the performance of victim and non-victim Wi-Fi users, and Wi-Fi AP while varying LTE-U ON duration (i.e., duty cycle). A propitious scheme is proposed for WLANs, with regard to ease of implementation, employing Point Coordination Function (PCF) mode of 802.11, promising fairness among Wi-Fi users with improvement in the channel utilization of Wi-Fi network. An analytical model is developed to demonstrate guaranteed improvement and validate the simulation results.
Chromatic number of ISK4-free graphs
Venue: arXiv cs.DM 2016
Year: 2016

A graph $G$ is said to be ISK4-free if it does not contain any subdivision of $K_4$ as an induced subgraph. In this paper, we propose new upper bounds for chromatic number of ISK4-free graphs and $\{$ISK4, triangle$\}$-free graphs.
Counting generalized Reed-Solomon codes
Venue: arXiv cs.IT 2016
Year: 2016

In this article we count the number of generalized Reed-Solomon (GRS) codes of dimension k and length n, including the codes coming from a non-degenerate conic plus nucleus. We compare our results with known formulae for the number of 3-dimensional MDS codes of length n=6,7,8,9.
Feature Engineering and Ensemble Modeling for Paper Acceptance Rank Prediction
Venue: arXiv cs.AI 2016
Year: 2016

Measuring research impact and ranking academic achievement are important and challenging problems. Having an objective picture of research institution is particularly valuable for students, parents and funding agencies, and also attracts attention from government and industry. KDD Cup 2016 proposes the paper acceptance rank prediction task, in which the participants are asked to rank the importance of institutions based on predicting how many of their papers will be accepted at the 8 top conferences in computer science. In our work, we adopt a three-step feature engineering method, including basic features definition, finding similar conferences to enhance the feature set, and dimension reduction using PCA. We propose three ranking models and the ensemble methods for combining such models. Our experiment verifies the effectiveness of our approach. In KDD Cup 2016, we achieved the overall rank of the 2nd place.
Advancing Memristive Analog Neuromorphic Networks: Increasing Complexity, and Coping with Imperfect Hardware Components
Venue: arXiv cs.ET 2016
Year: 2016

We experimentally demonstrate classification of 4x4 binary images into 4 classes, using a 3-layer mixed-signal neuromorphic network ("MLP perceptron"), based on two passive 20x20 memristive crossbar arrays, board-integrated with discrete CMOS components. The network features 10 hidden-layer and 4 output-layer analog CMOS neurons and 428 metal-oxide memristors, i.e. is almost an order of magnitude more complex than any previously reported functional memristor circuit. Moreover, the inference operation of this classifier is performed entirely in the integrated hardware. To deal with larger crossbar arrays, we have developed a semi-automatic approach to their forming and testing, and compared several memristor training schemes for coping with imperfect behavior of these devices, as well as with variability of analog CMOS neurons. The effectiveness of the proposed schemes for defect and variation tolerance was verified experimentally using the implemented network and, additionally, by modeling the operation of a larger network, with 300 hidden-layer neurons, on the MNIST benchmark. Finally, we propose a simple modification of the implemented memristor-based vector-by-matrix multiplier to allow its operation in a wider temperature range.
Some conjectures on codes
Venue: arXiv cs.FL 2016
Year: 2016

Variable-length codes are the bases of the free submonoids of a free monoid. There are some important longstanding open questions about the structure of finite maximal codes. In this paper we discuss this conjectures and their relations with factorizations of cyclic groups.
Robust Matrix Regression
Venue: arXiv cs.LG 2016
Year: 2016

Modern technologies are producing datasets with complex intrinsic structures, and they can be naturally represented as matrices instead of vectors. To preserve the latent data structures during processing, modern regression approaches incorporate the low-rank property to the model and achieve satisfactory performance for certain applications. These approaches all assume that both predictors and labels for each pair of data within the training set are accurate. However, in real-world applications, it is common to see the training data contaminated by noises, which can affect the robustness of these matrix regression methods. In this paper, we address this issue by introducing a novel robust matrix regression method. We also derive efficient proximal algorithms for model training. To evaluate the performance of our methods, we apply it to real world applications with comparative studies. Our method achieves the state-of-the-art performance, which shows the effectiveness and the practical value of our method.
Prediction of Seasonal Temperature Using Soft Computing Techniques: Application in Benevento (Southern Italy) Area
Venue: arXiv cs.NE 2016
Year: 2016

In this work two soft computing methods, Artificial Neural Networks and Genetic Programming, are proposed in order to forecast the mean temperature that will occur in future seasons. The area in which the soft computing techniques were applied is that of the surroundings of the town of Benevento, in the south of Italy, having geographic coordinates (lat. 41°07'50"N; long.14°47'13"E). This area is not affected by maritime influences as well as by winds coming from the west. The methods are fed by data recorded in the meteorological stations of Benevento and Castelvenere, located in the hilly area, which characterizes the territory surrounding this city, at 144 m a.s.l. Both the applied methods show low error rates, while the Genetic Programming offers an explicit rule representation (a formula) explaining the prevision. Keywords Seasonal Temperature Forecasting; Soft Computing; Artificial Neural Networks; Genetic Programming; Southern Italy.
AdversariaLib: An Open-source Library for the Security Evaluation of Machine Learning Algorithms Under Attack
Venue: arXiv cs.CR 2016
Year: 2016

We present AdversariaLib, an open-source python library for the security evaluation of machine learning (ML) against carefully-targeted attacks. It supports the implementation of several attacks proposed thus far in the literature of adversarial learning, allows for the evaluation of a wide range of ML algorithms, runs on multiple platforms, and has multi-processing enabled. The library has a modular architecture that makes it easy to use and to extend by implementing novel attacks and countermeasures. It relies on other widely-used open-source ML libraries, including scikit-learn and FANN. Classification algorithms are implemented and optimized in C/C++, allowing for a fast evaluation of the simulated attacks. The package is distributed under the GNU General Public License v3, and it is available for download at http://sourceforge.net/projects/adversarialib.
Stall Pattern Avoidance in Polynomial Product Codes
Venue: arXiv cs.IT 2016
Year: 2016

Product codes are a concatenated error-correction scheme that has been often considered for applications requiring very low bit-error rates, which demand that the error floor be decreased as much as possible. In this work, we consider product codes constructed from polynomial algebraic codes, and propose a novel low-complexity post-processing technique that is able to improve the error-correction performance by orders of magnitude. We provide lower bounds for the error rate achievable under post processing, and present simulation results indicating that these bounds are tight.
An Evaluation of Information Sharing Parking Guidance Policies Using a Bayesian Approach
Venue: arXiv cs.AI 2016
Year: 2016

Real-time parking occupancy information is critical for a parking management system to facilitate drivers to park more efficiently. Recent advances in connected and automated vehicle technologies enable sensor-equipped cars (probe cars) to detect and broadcast available parking spaces when driving through parking lots. In this paper, we evaluate the impact of market penetration of probe cars on the system performance, and investigate different parking guidance policies to improve the data acquisition process. We adopt a simulation-based approach to impose four policies on an off- street parking lot influencing the behavior of probe cars to park in assigned parking spaces. This in turn effects the scanning route and the parking space occupancy estimations. The last policy we propose is a near-optimal guidance strategy that maximizes the information gain of posteriors. The results suggest that an efficient information gathering policy can compensate for low penetration of connected and automated vehicles. We also highlight the policy trade-off that occur while attempting to maximize information gain through explorations and improve assignment accuracy through exploitations. Our results can assist urban policy makers in designing and managing smart parking systems.
On the Coded Caching Delivery Design over Wireless Networks
Venue: arXiv cs.IT 2016
Year: 2016

Coded caching scheme is a promising technique to migrate the network burden in peak hours, which attains more prominent gains than the uncoded caching. The coded caching scheme can be classified into two types, namely, the centralized and the decentralized scheme, according to whether the placement procedures are carefully designed or operated at random. However, most of the previous analysis assumes that the connected links between server and users are error-free. In this paper, we explore the coded caching based delivery design in wireless networks, where all the connected wireless links are different. For both centralized and decentralized cases, we proposed two delivery schemes, namely, the orthogonal delivery scheme and the concurrent delivery scheme. We focus on the transmission time slots spent on satisfying the system requests, and prove that for both the centralized and the decentralized cases, the concurrent delivery always outperforms orthogonal delivery scheme. Furthermore, for the orthogonal delivery scheme, we derive the gap in terms of transmission time between the decentralized and centralized case, which is essentially no more than 1.5.
Naming the Pain in Requirements Engineering: Design of a Global Family of Surveys and First Results from Germany
Venue: arXiv cs.SE 2016
Year: 2016

Context: For many years, we have observed industry struggling in defining a high quality requirements engineering (RE) and researchers trying to understand industrial expectations and problems. Although we are investigating the discipline with a plethora of empirical studies, those studies either concentrate on validating specific methods or on single companies or countries. Therefore, they allow only for limited empirical generalisations. Objective: To lay an empirical and generalisable foundation about the state of the practice in RE, we aim at a series of open and reproducible surveys that allow us to steer future research in a problem-driven manner. Method: We designed a globally distributed family of surveys in joint collaborations with different researchers from different countries. The instrument is based on an initial theory inferred from available studies. As a long-term goal, the survey will be regularly replicated to manifest a clear understanding on the status quo and practical needs in RE. In this paper, we present the design of the family of surveys and first results of its start in Germany. Results: Our first results contain responses from 30 German companies. The results are not yet generalisable, but already indicate several trends and problems. For instance, a commonly stated problem respondents see in their company standards are artefacts being underrepresented, and important problems they experience in their projects are incomplete and inconsistent requirements. Conclusion: The results suggest that the survey design and instrument are well-suited to be replicated and, thereby, to create a generalisable empirical basis of RE in practice.
Recurrent Neural Network based Part-of-Speech Tagger for Code-Mixed Social Media Text
Venue: arXiv cs.CL 2016
Year: 2016

This paper describes Centre for Development of Advanced Computing's (CDACM) submission to the shared task-'Tool Contest on POS tagging for Code-Mixed Indian Social Media (Facebook, Twitter, and Whatsapp) Text', collocated with ICON-2016. The shared task was to predict Part of Speech (POS) tag at word level for a given text. The code-mixed text is generated mostly on social media by multilingual users. The presence of the multilingual words, transliterations, and spelling variations make such content linguistically complex. In this paper, we propose an approach to POS tag code-mixed social media text using Recurrent Neural Network Language Model (RNN-LM) architecture. We submitted the results for Hindi-English (hi-en), Bengali-English (bn-en), and Telugu-English (te-en) code-mixed data.
Linear Precoder Design for a MIMO Gaussian Wiretap Channel with Full-Duplex Source and Destination Nodes
Venue: arXiv cs.IT 2016
Year: 2016

We consider linear precoder design for a multiple-input multiple-output (MIMO) Gaussian wiretap channel, which comprises two legitimate nodes, i.e., Alice and Bob, operating in Full-Duplex (FD) mode and exchanging confidential messages in the presence of a passive eavesdropper. Using the sum secrecy degrees of freedoms (sum S.D.o.F.) as reliability measure, we formulate an optimization problem with respect to the precoding matrices. In order to solve this problem, we first propose a cooperative secrecy transmission scheme, and prove that its feasible set is sufficient to achieve the maximum sum S.D.o.F.. Based on that feasible set, we then determine the maximum achievable sum S.D.o.F. in closed form, and provide a method for constructing the precoding matrix pair which achieves the maximum sum S.D.o.F.. Results show that, the FD based network provides an attractive secrecy transmission rate performance.
Training Spiking Deep Networks for Neuromorphic Hardware
Venue: arXiv cs.NE 2016
Year: 2016

We describe a method to train spiking deep networks that can be run using leaky integrate-and-fire (LIF) neurons, achieving state-of-the-art results for spiking LIF networks on five datasets, including the large ImageNet ILSVRC-2012 benchmark. Our method for transforming deep artificial neural networks into spiking networks is scalable and works with a wide range of neural nonlinearities. We achieve these results by softening the neural response function, such that its derivative remains bounded, and by training the network with noise to provide robustness against the variability introduced by spikes. Our analysis shows that implementations of these networks on neuromorphic hardware will be many times more power-efficient than the equivalent non-spiking networks on traditional hardware.