OpenRaiser/Intern-Atlas huggingface dataset:
Reducing Compare-and-Swap to Consensus Number One Primitives
Venue: arXiv cs.DS 2018
Year: 2018

The consensus number of an object is the maximum number of processes among which binary consensus can be solved using any number of instances of the object and read-write registers. Herlihy [6] showed in his seminal work that if an object has a consensus number of n, then there is a universal construction for a wait-free and linearizable implementation of any non-trivial concurrent object or data structure that is shared among n processes. Thus, a synchronization object such as compare-and-swap with an infinite consensus number and the corresponding instruction can be viewed as "strong". On the other hand, a synchronization object such as fetch-and-add with consensus number two and the corresponding fetch-and-add instruction can be viewed as "weak". Ellen et al. [2] observed recently that an object supporting two weak instructions can also achieve infinite consensus number like an object that supports one strong instruction. Using Herlihy's universal construction, this implies that ignoring concerns about efficiency, one can design any concurrent data structure or algorithm using only weak instructions. However, is it possible that a combination of weak instructions is really powerful enough to efficiently replace a strong instruction, like compare-and-swap, without incurring a large overhead in time or space? In this paper, we answer this question by giving an O(1) time wait-free and linearizable implementation of a compare-and-swap register shared among n processes using read-write registers and O(1) registers that support two synchronization primitives half-max and max-write, each having consensus number one. Thus, any algorithm that solves some arbitrary synchronization problem using read-write and compare-and-swap registers can be transformed into an algorithm that has the same asymptotic time complexity and only uses consensus number one instructions.
Quantum Algorithm for Optimization and Polynomial System Solving over Finite Field and Application to Cryptanalysis
Venue: arXiv cs.SC 2018
Year: 2018

In this paper, we give quantum algorithms for two fundamental computation problems: solving polynomial systems over finite fields and optimization where the arguments of the objective function and constraints take values from a finite field or a bounded interval of integers. The quantum algorithms can solve these problems with any given success probability and have polynomial runtime complexities in the size of the input, the degree of the inequality constraints, and the condition number of certain matrices derived from the problem. So, we achieved exponential speedup for these problems when their condition numbers are small. As applications, quantum algorithms are given to three basic computational problems in cryptography: the polynomial system with noise problem, the short integer solution problem, the shortest vector problem, as well as the cryptanalysis for the lattice based NTRU cryptosystem. It is shown that these problems and NTRU can against quantum computer attacks only if their condition numbers are large, so the condition number could be used as a new criterion for the lattice based post-quantum cryptosystems.
A New Combinatorial Design of Coded Distributed Computing
Venue: arXiv cs.DC 2018
Year: 2018

Coded distributed computing introduced by Li et al. in 2015 is an efficient approach to trade computing power to reduce the communication load in general distributed computing frameworks such as MapReduce. In particular, Li et al. show that increasing the computation load in the Map phase by a factor of $r$ can create coded multicasting opportunities to reduce the communication load in the Reduce phase by the same factor. However, there are two major limitations in practice. First, it requires an exponentially large number of input files (data batches) when the number of computing nodes gets large. Second, it forces every $s$ computing nodes to compute one Map function, which leads to a large number of Map functions required to achieve the promised gain. In this paper, we make an attempt to overcome these two limitations by proposing a novel coded distributed computing approach based on a combinatorial design. We demonstrate that when the number of computing nodes becomes large, 1) the proposed approach requires an exponentially less number of input files; 2) the required number of Map functions is also reduced exponentially. Meanwhile, the resulting computation-communication trade-off maintains the multiplicative gain compared to conventional uncoded unicast and achieves the information theoretic lower bound asymmetrically for some system parameters.
Resource Allocation for Secure MISO-NOMA Cognitive Radios Relying on SWIPT
Venue: arXiv cs.IT 2018
Year: 2018

Cognitive radio (CR) and non-orthogonal multiple access (NOMA) are two promising technologies in the next generation wireless communication systems. The security of a NOMA CR network (CRN) is important but lacks of study. In this paper, a multiple-input single-output NOMA CRN relying on simultaneous wireless information and power transfer is studied. In order to improve the security of both the primary and secondary network, an artificial noise-aided cooperative jamming scheme is proposed. Different from the most existing works, a power minimization problem is formulated under a practical non-linear energy harvesting model. A suboptimal scheme is proposed to solve this problem based on semidefinite relaxation and successive convex approximation. Simulation results show that the proposed cooperative jamming scheme is efficient to achieve secure communication and NOMA outperforms the conventional orthogonal multiple access in terms of the power consumption.
Algorithms for robust production scheduling with energy consumption limits
Venue: arXiv cs.DS 2018
Year: 2018

In this work, we consider a scheduling problem faced by production companies with large electricity consumption. Due to the contract with the electric utility, the production companies are obligated to comply with the total energy consumption limits in the specified time intervals (usually 15-minutes long), otherwise, the companies pay substantial penalty fees. Although it is possible to design production schedules that consider these limits as hard constraints, uncertainties occurring during the execution of the schedules are usually not taken into account. This may lead to situations in which the unexpected delays of the operations cause the violations of the energy consumption limits. Our goal is to design robust production schedules pro-actively guaranteeing that the energy consumption limits are not violated for the given set of uncertainty scenarios. We consider scheduling on one machine with release times of the operations and total tardiness as the objective function. To tackle this problem, we first propose a pseudo-polynomial algorithm for finding the optimal robust schedule for the given permutation of the operations. This algorithm is then utilised in three different algorithms for finding the optimal permutation: two exact (Branch-and-Bound and logic-based Benders decomposition) and one heuristic algorithm (tabu search). All the algorithms were experimentally evaluated on random instances with different sizes of the uncertainty scenarios set. Using the tabu search algorithm, we are able to solve large instances within one minute.
On the Needs for Rotations in Hypercubic Quantization Hashing
Venue: arXiv cs.LG 2018
Year: 2018

The aim of this paper is to endow the well-known family of hypercubic quantization hashing methods with theoretical guarantees. In hypercubic quantization, applying a suitable (random or learned) rotation after dimensionality reduction has been experimentally shown to improve the results accuracy in the nearest neighbors search problem. We prove in this paper that the use of these rotations is optimal under some mild assumptions: getting optimal binary sketches is equivalent to applying a rotation uniformizing the diagonal of the covariance matrix between data points. Moreover, for two closed points, the probability to have dissimilar binary sketches is upper bounded by a factor of the initial distance between the data points. Relaxing these assumptions, we obtain a general concentration result for random matrices. We also provide some experiments illustrating these theoretical points and compare a set of algorithms in both the batch and online settings.
Fast and rigorous arbitrary-precision computation of Gauss-Legendre quadrature nodes and weights
Venue: arXiv cs.NA 2018
Year: 2018

We describe a strategy for rigorous arbitrary-precision evaluation of Legendre polynomials on the unit interval and its application in the generation of Gauss-Legendre quadrature rules. Our focus is on making the evaluation practical for a wide range of realistic parameters, corresponding to the requirements of numerical integration to an accuracy of about 100 to 100 000 bits. Our algorithm combines the summation by rectangular splitting of several types of expansions in terms of hypergeometric series with a fixed-point implementation of Bonnet's three-term recurrence relation. We then compute rigorous enclosures of the Gauss-Legendre nodes and weights using the interval Newton method. We provide rigorous error bounds for all steps of the algorithm. The approach is validated by an implementation in the Arb library, which achieves order-of-magnitude speedups over previous code for computing Gauss-Legendre rules with simultaneous high degree and precision.
From expanders to hitting distributions and simulation theorems
Venue: arXiv cs.CC 2018
Year: 2018

Recently, Chattopadhyay et al. (\cite{chattopadhyay2017simulation}) proved that any gadget having so called \emph{hitting distributions} admits deterministic "query-to-communication" simulation theorem. They applied this result to Inner Product, Gap Hamming Distance and Indexing Function. They also demonstrated that previous works used hitting distributions implicitly (\cite{goos2015deterministic} for Indexing Function and \cite{wu2017raz} for Inner Product). In this paper we show that any expander in which any two distinct vertices have at most one common neighbor can be transformed into a gadget possessing good hitting distributions. We demonstrate that this result is applicable to affine plane expanders and to Lubotzky-Phillips-Sarnak construction of Ramanujan graphs . In particular, from affine plane expanders we extract a gadget achieving the best known trade-off between the arity of outer function and the size of gadget. More specifically, when this gadget has $k$ bits on input, it admits a simulation theorem for all outer function of arity roughly $2^{k/2}$ or less (the same was also known for $k$-bit Inner Product, (\cite{chattopadhyay2017simulation})). In addition we show that, unlike Inner Product, underlying hitting distributions in our new gadget are "polynomial-time listable" in the sense that their supports can be written down in time $2^{O(k)}$, i.e, in time polynomial in size of gadget's matrix.
Automatic Generation of Language-Independent Features for Cross-Lingual Classification
Venue: arXiv cs.CL 2018
Year: 2018

Many applications require categorization of text documents using predefined categories. The main approach to performing text categorization is learning from labeled examples. For many tasks, it may be difficult to find examples in one language but easy in others. The problem of learning from examples in one or more languages and classifying (categorizing) in another is called cross-lingual learning. In this work, we present a novel approach that solves the general cross-lingual text categorization problem. Our method generates, for each training document, a set of language-independent features. Using these features for training yields a language-independent classifier. At the classification stage, we generate language-independent features for the unlabeled document, and apply the classifier on the new representation. To build the feature generator, we utilize a hierarchical language-independent ontology, where each concept has a set of support documents for each language involved. In the preprocessing stage, we use the support documents to build a set of language-independent feature generators, one for each language. The collection of these generators is used to map any document into the language-independent feature space. Our methodology works on the most general cross-lingual text categorization problems, being able to learn from any mix of languages and classify documents in any other language. We also present a method for exploiting the hierarchical structure of the ontology to create virtual supporting documents for languages that do not have them. We tested our method, using Wikipedia as our ontology, on the most commonly used test collections in cross-lingual text categorization, and found that it outperforms existing methods.
Inferring the time-varying functional connectivity of large-scale computer networks from emitted events
Venue: arXiv cs.LG 2018
Year: 2018

We consider the problem of inferring the functional connectivity of a large-scale computer network from sparse time series of events emitted by its nodes. We do so under the following three domain-specific constraints: (a) non-stationarity of the functional connectivity due to unknown temporal changes in the network, (b) sparsity of the time-series of events that limits the effectiveness of classical correlation-based analysis, and (c) lack of an explicit model describing how events propagate through the network. Under the assumption that the probability of two nodes being functionally connected correlates with the mean delay between their respective events, we develop an inference method whose output is an undirected weighted network where the weight of an edge between two nodes denotes the probability of these nodes being functionally connected. Using a combination of windowing and convolution to calculate at each time window a score quantifying the likelihood of a pair of nodes emitting events in quick succession, we develop a model of time-varying connectivity whose parameters are determined by maximising the model's predictive power from one time window to the next. To assess the effectiveness of our inference method, we construct synthetic data for which ground truth is available and use these data to benchmark our approach against three state-of-the-art inference methods. We conclude by discussing its application to data from a real-world large-scale computer network.
Alternating Nonzero Automata
Venue: arXiv cs.LO 2018
Year: 2018

We introduce a new class of automata on infinite trees called \emph{alternating nonzero automata}, which extends the class of non-deterministic nonzero automata. We reduce the emptiness problem for alternating nonzero automata to the same problem for non-deterministic ones, which implies decidability. We obtain as a corollary algorithms for the satisfiability of a probabilistic temporal logic extending both CTL* and the qualitative fragment of pCTL*.
Towards an Open Science Platform for the Evaluation of Data Fusion
Venue: arXiv cs.IR 2018
Year: 2018

Combining the results of different search engines in order to improve upon their performance has been the subject of many research papers. This has become known as the "Data Fusion" task, and has great promise in dealing with the vast quantity of unstructured textual data that is a feature of many Big Data scenarios. However, no universally-accepted evaluation methodology has emerged in the community. This makes it difficult to make meaningful comparisons between the various proposed techniques from reading the literature alone. Variations in the datasets, metrics, and baseline results have all contributed to this difficulty. This paper argues that a more unified approach is required, and that a centralised software platform should be developed to aid researchers in making comparisons between their algorithms and others. The desirable qualities of such a system have been identified and proposed, and an early prototype has been developed. Re-implementing algorithms published by other researchers is a great burden on those proposing new techniques. The prototype system has the potential to greatly reduce this burden and thus encourage more comparable results being generated and published more easily.
Don't Leave Me Alone: Retrospective Think Aloud supported by Real-time Monitoring of Participant's Physiology
Venue: arXiv cs.HC 2018
Year: 2018

Think aloud protocols are widely applied in user experience studies. In this paper, the effect of two different applications of the Retrospective Think Aloud (RTA) protocol on the number of user-reported usability issues is examined. To this end, 30 users were asked to use the National Cadastre and Mapping Agency web application and complete a set of tasks, such as measuring the land area of a square in their hometown. The order of tasks was randomized per participant. Next, participants were involved in RTA sessions. Each participant was involved in two different RTA modes: (a) the strict guidance, in which the facilitator stayed in the background and prompted participants to keep thinking aloud based on his judgement and experience, and (b) the physiology-supported interventions, in which the facilitator intervened based on real-time monitoring of user's physiological signals. During each session, three participant's physiological signals were recorded: skin conductance, skin temperature and blood volume pulse. Participants were also asked to provide valence-arousal ratings for each self-reported usability issue. Analysis of the collected data showed that participants in the physiology-supported RTA mode reported significantly more usability issues. No significant effect of the RTA mode was found on the va-lence-arousal ratings for the reported usability issues. Participants' physiological signals during the RTA sessions did not also differ significantly between the two modes.
Agile development for vulnerable populations: lessons learned and recommendations
Venue: arXiv cs.CY 2018
Year: 2018

In this paper we draw attention to the challenges of managing software projects for vulnerable populations, i.e., people potentially exposed to harm or not capable of protecting their own interests. The focus on human aspects, and particularly, the inclusion of human-centered approaches, has been a popular topic in the software engineering community. We argue, however, that current literature provides little understanding and guidance on how to approach these type of scenarios. Here, we shed some light on the topic by reporting on our experiences in developing innovative solutions for the residential care scenario, outlining potential issues and recommendations.
Infrastructure Enabled Autonomy: A Distributed Intelligence Architecture for Autonomous Vehicles
Venue: arXiv cs.CY 2018
Year: 2018

Multiple studies have illustrated the potential for dramatic societal, environmental and economic benefits from significant penetration of autonomous driving. However, all the current approaches to autonomous driving require the automotive manufacturers to shoulder the primary responsibility and liability associated with replacing human perception and decision making with automation, potentially slowing the penetration of autonomous vehicles, and consequently slowing the realization of the societal benefits of autonomous vehicles. We propose here a new approach to autonomous driving that will re-balance the responsibility and liabilities associated with autonomous driving between traditional automotive manufacturers, infrastructure players, and third-party players. Our proposed distributed intelligence architecture leverages the significant advancements in connectivity and edge computing in the recent decades to partition the driving functions between the vehicle, edge computers on the road side, and specialized third-party computers that reside in the vehicle. Infrastructure becomes a critical enabler for autonomy. With this Infrastructure Enabled Autonomy (IEA) concept, the traditional automotive manufacturers will only need to shoulder responsibility and liability comparable to what they already do today, and the infrastructure and third-party players will share the added responsibility and liabilities associated with autonomous functionalities. We propose a Bayesian Network Model based framework for assessing the risk benefits of such a distributed intelligence architecture. An additional benefit of the proposed architecture is that it enables "autonomy as a service" while still allowing for private ownership of automobiles.
Cryptographically Secure Multi-Tenant Provisioning of FPGAs
Venue: arXiv cs.CR 2018
Year: 2018

FPGAs (Field Programmable Gate arrays) have gained massive popularity today as accelerators for a variety of workloads, including big data analytics, and parallel and distributed computing. This has fueled the study of mechanisms to provision FPGAs among multiple tenants as general purpose computing resources on the cloud. Such mechanisms offer new challenges, such as ensuring IP protection and bitstream confidentiality for mutually distrusting clients sharing the same FPGA. A direct adoption of existing IP protection techniques from the single tenancy setting do not completely address these challenges, and are also not scalable enough for practical deployment. In this paper, we propose a dedicated and scalable framework for secure multi-tenant FPGA provisioning that can be easily integrated into existing cloud-based infrastructures such as OpenStack. Our technique has constant resource/memory overhead irrespective of the number of tenants sharing a given FPGA, and is provably secure under well-studied cryptographic assumptions. A prototype implementation of our proposition on Xilinx Virtex-7 UltraScale FPGAs is presented to validate its overheads and scalability when supporting multiple tenants and workloads. To the best of our knowledge, this is the first FPGA provisioning framework to be prototyped that achieves a desirable balance between security and scalability in the multi-tenancy setting.
One-Bit Precoding and Constellation Range Design for Massive MIMO with QAM Signaling
Venue: arXiv cs.IT 2018
Year: 2018

The use of low-resolution digital-to-analog converters (DACs) for transmit precoding provides crucial energy efficiency advantage for massive multiple-input multiple-output (MIMO) implementation. This paper formulates a quadrature amplitude modulation (QAM) constellation range and one-bit symbol-level precoding design problem for minimizing the average symbol error rate (SER) in downlink massive MIMO transmission. A tight upper-bound for SER with low-resolution DAC precoding is first derived. The derived expression suggests that the performance degradation of one-bit precoding can be interpreted as a decrease in the effective minimum distance of the QAM constellation. Using the obtained SER expression, we propose a QAM constellation range design for the single-user case. It is shown that in the massive MIMO limit, a reasonable choice for constellation range with one-bit precoding is that of the infinite-resolution precoding with per-symbol power constraint, but reduced by a factor of $\sqrt{2/π}$ or about $0.8$. The corresponding minimum distance reduction translates to about 2dB gap between the performance of one-bit precoding and infinite-resolution precoding. This paper further proposes a low-complexity heuristic algorithm for one-bit precoder design. Finally, the proposed QAM constellation range and precoder design are generalized to the multi-user downlink. We propose to scale the constellation range for infinite-resolution zero-forcing (ZF) precoding with per-symbol power constraint by the same factor of $\sqrt{2/π}$ for one-bit precoding. The proposed one-bit precoding scheme is shown to be within 2dB of infinite-resolution ZF. In term of number of antennas, one-bit precoding requires about 50% more antennas to achieve the same performance as infinite-resolution precoding.