OpenRaiser/Intern-Atlas huggingface dataset:
Putting Fürer Algorithm into Practice with the BPAS Library
Venue: arXiv cs.SC 2018
Year: 2018

Fast algorithms for integer and polynomial multiplication play an important role in scientific computing as well as in other disciplines. In 1971, Sch{ö}nhage and Strassen designed an algorithm that improved the multiplication time for two integers of at most $n$ bits to $\mathcal{O}(\log n \log \log n)$. In 2007, Martin Fürer presented a new algorithm that runs in $O \left(n \log n\ \cdot 2^{O(\log^* n)} \right)$, where $\log^* n$ is the iterated logarithm of $n$. We explain how we can put Fürer's ideas into practice for multiplying polynomials over a prime field $\mathbb{Z} / p \mathbb{Z}$, for which $p$ is a Generalized Fermat prime of the form $p = r^k + 1$ where $k$ is a power of $2$ and $r$ is of machine word size. When $k$ is at least 8, we show that multiplication inside such a prime field can be efficiently implemented via Fast Fourier Transform (FFT). Taking advantage of Cooley-Tukey tensor formula and the fact that $r$ is a $2k$-th primitive root of unity in $\mathbb{Z} / p \mathbb{Z}$, we obtain an efficient implementation of FFT over $\mathbb{Z} / p \mathbb{Z}$. This implementation outperforms comparable implementations either using other encodings of $\mathbb{Z} / p \mathbb{Z}$ or other ways to perform multiplication in $\mathbb{Z} / p \mathbb{Z}$.
Stabilizing the virtual response time in single-server processor sharing queues with slowly time-varying arrival rates
Venue: arXiv cs.PF 2018
Year: 2018

Motivated by the work of Whitt, who studied stabilization of the mean virtual waiting time (excluding service time) in a $GI_t/GI_t/1/FCFS$ queue, this paper investigates the stabilization of the mean virtual response time in a single-server processor sharing (PS) queueing system with a time-varying arrival rate and a service rate control (a $GI_t/GI_t/1/PS$ queue). We propose and compare a modified square-root (SR) control and a difference-matching (DM) control to stabilize the mean virtual response time of a $GI_t/GI_t/1/PS$ queue. Extensive simulation studies with various settings of arrival processes and service times show that the DM control outperforms the SR control for heavy-traffic conditions, and that the SR control performs better for light-traffic conditions.
Identifying influential patents in citation networks using enhanced VoteRank centrality
Venue: arXiv cs.SI 2018
Year: 2018

This study proposes the usage of a method called VoteRank, created by Zhang et al. (2016), to identify influential nodes on patent citation networks. In addition, it proposes enhanced VoteRank algorithms, extending the Zhang et al. work. These novel algorithms comprise a reduction on the voting ability of the nodes affected by a chosen spreader if the nodes are distant from the spreader. One method uses a reduction factor that is linear regarding the distance from the spreader, which we called VoteRank-LRed. The other method uses a reduction factor that is exponential concerning the distance from the spreader, which we called VoteRank-XRed. By applying the methods to a citation network, we were able to demonstrate that VoteRank-LRed improved performance in choosing influence spreaders more efficiently than the original VoteRank on the tested citation network.
Leveraging Random Label Memorization for Unsupervised Pre-Training
Venue: arXiv cs.LG 2018
Year: 2018

We present a novel approach to leverage large unlabeled datasets by pre-training state-of-the-art deep neural networks on randomly-labeled datasets. Specifically, we train the neural networks to memorize arbitrary labels for all the samples in a dataset and use these pre-trained networks as a starting point for regular supervised learning. Our assumption is that the "memorization infrastructure" learned by the network during the random-label training proves to be beneficial for the conventional supervised learning as well. We test the effectiveness of our pre-training on several video action recognition datasets (HMDB51, UCF101, Kinetics) by comparing the results of the same network with and without the random label pre-training. Our approach yields an improvement - ranging from 1.5% on UCF-101 to 5% on Kinetics - in classification accuracy, which calls for further research in this direction.
The dispersion of research performance within and between universities as a potential indicator of the competitive intensity in higher education systems
Venue: arXiv cs.DL 2018
Year: 2018

Higher education systems in competitive environments generally present top universities, that are able to attract top scientists, top students and public and private financing, with notable socio-economic benefits in their region. The same does not hold true for non-competitive systems. In this study we will measure the dispersion of research performance within and between universities in the Italian university system, typically non-competitive. We will also investigate the level of correlation that occurs between performance in research and its dispersion in universities. The findings may represent a first benchmark for similar studies in other nations. Furthermore, they lead to policy indications, questioning the effectiveness of selective funding of universities based on national research assessment exercises. The field of observation is composed of all Italian universities active in the hard sciences. Research performance will be evaluated using a bibliometric approach, through publications indexed in the Web of Science between 2004 and 2008.
Role of Awareness and Universal Context in a Spiking Conscious Neural Network (SCNN): A New Perspective and Future Directions
Venue: arXiv cs.AI 2018
Year: 2018

Awareness plays a major role in human cognition and adaptive behaviour, though mechanisms involved remain unknown. Awareness is not an objectively established fact, therefore, despite extensive research, scientists have not been able to fully interpret its contribution in multisensory integration and precise neural firing, hence, questions remain: (1) How the biological neuron integrates the incoming multisensory signals with respect to different situations? (2) How are the roles of incoming multisensory signals defined (selective amplification/attenuation) that help neuron(s) to originate a precise neural firing complying with the anticipated behavioural-constraint of the environment? (3) How are the external environment and anticipated behaviour integrated? Recently, scientists have exploited deep learning to integrate multimodal cues and capture context-dependent meanings. Yet, these methods suffer from imprecise behavioural representation. In this research, we introduce a new theory on the role of awareness and universal context that can help answering the aforementioned crucial neuroscience questions. Specifically, we propose a class of spiking conscious neuron in which the output depends on three functionally distinctive integrated input variables: receptive field (RF), local contextual field (LCF), and universal contextual field (UCF). The RF defines the incoming ambiguous sensory signal, LCF defines the modulatory signal coming from other parts of the brain, and UCF defines the awareness. It is believed that the conscious neuron inherently contains enough knowledge about the situation in which the problem is to be solved based on past learning and reasoning and it defines the precise role of incoming multisensory signals to originate a precise neural firing (exhibiting switch-like behaviour). It is shown that the conscious neuron helps modelling a more precise human behaviour.
Research productivity: are higher academic ranks more productive than lower ones?
Venue: arXiv cs.DL 2018
Year: 2018

This work analyses the links between individual research performance and academic rank. A typical bibliometric methodology is used to study the performance of all Italian university researchers active in the hard sciences, for the period 2004-2008. The objective is to characterize the performance of the ranks of full, associate and assistant professors, along various dimensions, in order to verify the existence of performance differences among the ranks in general and for single disciplines.
FUNN: Flexible Unsupervised Neural Network
Venue: arXiv cs.LG 2018
Year: 2018

Deep neural networks have demonstrated high accuracy in image classification tasks. However, they were shown to be weak against adversarial examples: a small perturbation in the image which changes the classification output dramatically. In recent years, several defenses have been proposed to solve this issue in supervised classification tasks. We propose a method to obtain robust features in unsupervised learning tasks against adversarial attacks. Our method differs from existing solutions by directly learning the robust features without the need to project the adversarial examples in the original examples distribution space. A first auto-encoder A1 is in charge of perturbing the input image to fool another auto-encoder A2 which is in charge of regenerating the original image. A1 tries to find the less perturbed image under the constraint that the error in the output of A2 should be at least equal to a threshold. Thanks to this training, the encoder of A2 will be robust against adversarial attacks and could be used in different tasks like classification. Using state-of-art network architectures, we demonstrate the robustness of the features obtained thanks to this method in classification tasks.
University-industry research collaboration: a model to assess university capability
Venue: arXiv cs.DL 2018
Year: 2018

Scholars and policy makers recognize that collaboration between industry and the public research institutions is a necessity for innovation and national economic development. This work presents an econometric model which expresses the university capability for collaboration with industry as a function of size, location and research quality. The field of observation is made of the census of 2001-2003 scientific articles in the hard sciences, co-authored by universities and private enterprises located in Italy. The analysis shows that research quality of universities has an impact higher than geographic distance on the capability for collaborating with industry. The model proposed and the measures that descend from it are suited for use at various levels of administration, to assist in realizing the "third role" of universities: the contribution to socio-economic development through public to private technology transfer.
Reliable Broadcast in Dynamic Networks with Locally Bounded Byzantine Failures
Venue: arXiv cs.DC 2018
Year: 2018

Ensuring reliable communication despite possibly malicious participants is a primary objective in any distributed system or network. In this paper, we investigate the possibility of reliable broadcast in a dynamic network whose topology may evolve while the broadcast is in progress. In particular, we adapt the Certified Propagation Algorithm (CPA) to make it work on dynamic networks and we present conditions (on the underlying dynamic graph) to enable safety and liveness properties of the reliable broadcast. We furthermore explore the complexity of assessing these conditions for various classes of dynamic networks.
The role of information asymmetry in the market for university-industry research collaboration
Venue: arXiv cs.DL 2018
Year: 2018

This study concerns the market for research collaboration between industry and universities. It presents an analysis of the population of all Italian university-industry collaborations that resulted in at least one international scientific publication between 2001 and 2003. Using spatial and bibliometric analysis relating to scientific output of university researchers, the study shows the importance of geographic proximity in companies' choices of university partner. The analysis also reveals inefficiency in the market: in a large proportion of cases private companies could have chosen more qualified research partners in universities located closer to the place of business.
Citations versus journal impact factor as proxy of quality: Could the latter ever be preferable?
Venue: arXiv cs.DL 2018
Year: 2018

In recent years bibliometricians have paid increasing attention to research evaluation methodological problems, among these being the choice of the most appropriate indicators for evaluating quality of scientific publications, and thus for evaluating the work of single scientists, research groups and entire organizations. Much literature has been devoted to analyzing the robustness of various indicators, and many works warn against the risks of using easily available and relatively simple proxies, such as journal impact factor. The present work continues this line of research, examining whether it is valid that the use of the impact factor should always be avoided in favour of citations, or whether the use of impact factor could be acceptable, even preferable, in certain circumstances. The evaluation was conducted by observing all scientific publications in the hard sciences by Italian universities, for the period 2004-2007. Performance sensitivity analyses were conducted with changing indicators of quality and years of observation.
A robust benchmark for the h- and g-indexes
Venue: arXiv cs.DL 2018
Year: 2018

The use Hirsch's h-index as a joint proxy of the impact and productivity of a scientist's research work continues to gain ground, accompanied by the efforts of bibliometrists to resolve some of its critical issues, through the application of a number of more or less sophisticated variants. However, the literature does not reveal any appreciable attempt to overcome the objective problems of measuring h-indexes on a large scale, for purposes of comparative evaluation. Scientists may succeed in calculating their own h-indexes but, being unable to compare them to those of their peers, they are unable to obtain truly useful indications of their individual research performance. This study proposes to overcome this gap, measuring the h- and Egghe's g-indexes of all Italian university researchers in the hard sciences, over a 5-year window. Descriptive statistics are provided concerning all of the 165 subject fields examined, offering robust benchmarks for those who wish to compare their individual performance to those of their colleagues in the same subject field.
Multi-layer Relation Networks
Venue: arXiv cs.LG 2018
Year: 2018

Relational Networks (RN) as introduced by Santoro et al. (2017) have demonstrated strong relational reasoning capabilities with a rather shallow architecture. Its single-layer design, however, only considers pairs of information objects, making it unsuitable for problems requiring reasoning across a higher number of facts. To overcome this limitation, we propose a multi-layer relation network architecture which enables successive refinements of relational information through multiple layers. We show that the increased depth allows for more complex relational reasoning by applying it to the bAbI 20 QA dataset, solving all 20 tasks with joint training and surpassing the state-of-the-art results.
Learning Two Layer Rectified Neural Networks in Polynomial Time
Venue: arXiv cs.DS 2018
Year: 2018

Consider the following fundamental learning problem: given input examples $x \in \mathbb{R}^d$ and their vector-valued labels, as defined by an underlying generative neural network, recover the weight matrices of this network. We consider two-layer networks, mapping $\mathbb{R}^d$ to $\mathbb{R}^m$, with $k$ non-linear activation units $f(\cdot)$, where $f(x) = \max \{x , 0\}$ is the ReLU. Such a network is specified by two weight matrices, $\mathbf{U}^* \in \mathbb{R}^{m \times k}, \mathbf{V}^* \in \mathbb{R}^{k \times d}$, such that the label of an example $x \in \mathbb{R}^{d}$ is given by $\mathbf{U}^* f(\mathbf{V}^* x)$, where $f(\cdot)$ is applied coordinate-wise. Given $n$ samples as a matrix $\mathbf{X} \in \mathbb{R}^{d \times n}$ and the (possibly noisy) labels $\mathbf{U}^* f(\mathbf{V}^* \mathbf{X}) + \mathbf{E}$ of the network on these samples, where $\mathbf{E}$ is a noise matrix, our goal is to recover the weight matrices $\mathbf{U}^*$ and $\mathbf{V}^*$. In this work, we develop algorithms and hardness results under varying assumptions on the input and noise. Although the problem is NP-hard even for $k=2$, by assuming Gaussian marginals over the input $\mathbf{X}$ we are able to develop polynomial time algorithms for the approximate recovery of $\mathbf{U}^*$ and $\mathbf{V}^*$. Perhaps surprisingly, in the noiseless case our algorithms recover $\mathbf{U}^*,\mathbf{V}^*$ exactly, i.e., with no error. To the best of the our knowledge, this is the first algorithm to accomplish exact recovery. For the noisy case, we give the first polynomial time algorithm that approximately recovers the weights in the presence of mean-zero noise $\mathbf{E}$. Our algorithms generalize to a larger class of rectified activation functions, $f(x) = 0$ when $x\leq 0$, and $f(x) > 0$ otherwise.
Evolutionary Data Measures: Understanding the Difficulty of Text Classification Tasks
Venue: arXiv cs.CL 2018
Year: 2018

Classification tasks are usually analysed and improved through new model architectures or hyperparameter optimisation but the underlying properties of datasets are discovered on an ad-hoc basis as errors occur. However, understanding the properties of the data is crucial in perfecting models. In this paper we analyse exactly which characteristics of a dataset best determine how difficult that dataset is for the task of text classification. We then propose an intuitive measure of difficulty for text classification datasets which is simple and fast to calculate. We show that this measure generalises to unseen data by comparing it to state-of-the-art datasets and results. This measure can be used to analyse the precise source of errors in a dataset and allows fast estimation of how difficult a dataset is to learn. We searched for this measure by training 12 classical and neural network based models on 78 real-world datasets, then use a genetic algorithm to discover the best measure of difficulty. Our difficulty-calculating code ( https://github.com/Wluper/edm ) and datasets ( http://data.wluper.com ) are publicly available.
Optimal Data Detection in Large MIMO
Venue: arXiv cs.IT 2018
Year: 2018

Large multiple-input multiple-output (MIMO) appears in massive multi-user MIMO and randomly-spread code-division multiple access (CDMA)-based wireless systems. In order to cope with the excessively high complexity of optimal data detection in such systems, a variety of efficient yet sub-optimal algorithms have been proposed in the past. In this paper, we propose a data detection algorithm that is computationally efficient and optimal in a sense that it is able to achieve the same error-rate performance as the individually optimal (IO) data detector under certain assumptions on the MIMO system matrix and constellation alphabet. Our algorithm, which we refer to as LAMA (short for large MIMO AMP), builds on complex-valued Bayesian approximate message passing (AMP), which enables an exact analytical characterization of the performance and complexity in the large-system limit via the state-evolution framework. We derive optimality conditions for LAMA and investigate performance/complexity trade-offs. As a byproduct of our analysis, we recover classical results of IO data detection for randomly-spread CDMA. We furthermore provide practical ways for LAMA to approach the theoretical performance limits in realistic, finite-dimensional systems at low computational complexity.
Towards a Unified Theory of Sparsification for Matching Problems
Venue: arXiv cs.DS 2018
Year: 2018

In this paper, we present a construction of a `matching sparsifier', that is, a sparse subgraph of the given graph that preserves large matchings approximately and is robust to modifications of the graph. We use this matching sparsifier to obtain several new algorithmic results for the maximum matching problem: * An almost $(3/2)$-approximation one-way communication protocol for the maximum matching problem, significantly simplifying the $(3/2)$-approximation protocol of Goel, Kapralov, and Khanna (SODA 2012) and extending it from bipartite graphs to general graphs. * An almost $(3/2)$-approximation algorithm for the stochastic matching problem, improving upon and significantly simplifying the previous $1.999$-approximation algorithm of Assadi, Khanna, and Li (EC 2017). * An almost $(3/2)$-approximation algorithm for the fault-tolerant matching problem, which, to our knowledge, is the first non-trivial algorithm for this problem. Our matching sparsifier is obtained by proving new properties of the edge-degree constrained subgraph (EDCS) of Bernstein and Stein (ICALP 2015; SODA 2016)---designed in the context of maintaining matchings in dynamic graphs---that identifies EDCS as an excellent choice for a matching sparsifier. This leads to surprisingly simple and non-technical proofs of the above results in a unified way. Along the way, we also provide a much simpler proof of the fact that an EDCS is guaranteed to contain a large matching, which may be of independent interest.
Out-Of-Place debugging: a debugging architecture to reduce debugging interference
Venue: arXiv cs.SE 2018
Year: 2018

Context. Recent studies show that developers spend most of their programming time testing, verifying and debugging software. As applications become more and more complex, developers demand more advanced debugging support to ease the software development process. Inquiry. Since the 70's many debugging solutions were introduced. Amongst them, online debuggers provide a good insight on the conditions that led to a bug, allowing inspection and interaction with the variables of the program. However, most of the online debugging solutions introduce \textit{debugging interference} to the execution of the program, i.e. pauses, latency, and evaluation of code containing side-effects. Approach. This paper investigates a novel debugging technique called \outofplace debugging. The goal is to minimize the debugging interference characteristic of online debugging while allowing online remote capabilities. An \outofplace debugger transfers the program execution and application state from the debugged application to the debugger application, both running in different processes. Knowledge. On the one hand, \outofplace debugging allows developers to debug applications remotely, overcoming the need of physical access to the machine where the debugged application is running. On the other hand, debugging happens locally on the remote machine avoiding latency. That makes it suitable to be deployed on a distributed system and handle the debugging of several processes running in parallel. Grounding. We implemented a concrete out-of-place debugger for the Pharo Smalltalk programming language. We show that our approach is practical by performing several benchmarks, comparing our approach with a classic remote online debugger. We show that our prototype debugger outperforms by a 1000 times a traditional remote debugger in several scenarios. Moreover, we show that the presence of our debugger does not impact the overall performance of an application. Importance. This work combines remote debugging with the debugging experience of a local online debugger. Out-of-place debugging is the first online debugging technique that can minimize debugging interference while debugging a remote application. Yet, it still keeps the benefits of online debugging ( e.g. step-by-step execution). This makes the technique suitable for modern applications which are increasingly parallel, distributed and reactive to streams of data from various sources like sensors, UI, network, etc.