OpenRaiser/Intern-Atlas huggingface dataset:
Bi-Directional Cooperative NOMA without Full CSIT
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, we propose bi-directional cooperative non-orthogonal multiple access (NOMA). Compared to conventional NOMA, the main contributions of bi-directional cooperative NOMA can be explained in two directions: 1) The proposed NOMA system is still efficient when the channel gains of scheduled users are almost the same. 2) The proposed NOMA system operates well without accurate channel state information (CSI) at the base station (BS). In a two-user scenario, the closed-form ergodic capacity of bi-directional cooperative NOMA is derived and it is proven to be better than those of other techniques. Based on the ergodic capacity, the algorithms to find optimal power allocations maximizing user fairness and sum-rate are presented. Outage probability is also derived, and we show that bi-directional cooperative NOMA achieves a power gain over uni-directional cooperative NOMA and a diversity gain over non-cooperative NOMA and orthogonal multiple access (OMA). We finally extend the bi-directional cooperative NOMA to a multi-user model. The analysis of ergodic capacity and outage probability in two-user scenario is numerically verified. Also, simulation results show that bi-directional cooperative NOMA provdes better data rates than the existing NOMA schemes as well as OMA in multi-user scenario.
On Euclidean Methods for Cubic and Quartic Jacobi Symbols
Venue: arXiv cs.DS 2018
Year: 2018

We study the bit complexity of two methods, related to the Euclidean algorithm, for computing cubic and quartic analogs of the Jacobi symbol. The main bottleneck in such procedures is computation of a quotient for long division. We give examples to show that with standard arithmetic, if quotients are computed naively (by using exact norms as denominators, then rounding), the algorithms have $Θ(n^3)$ bit complexity. It is a "folk theorem" that this can be reduced to $O(n^2)$ by modifying the division procedure. We give a self-contained proof of this, and show that quadratic time is best possible for these algorithms (with standard arithmetic or not). We also address the relative efficiency of using reciprocity, as compared to Euler's criterion, for testing if a given number is a cubic or quartic residue modulo an odd prime. Which is preferable depends on the number of residue tests to be done. Finally, we discuss the cubic and quartic analogs of Eisenstein's even-quotient algorithm for computing Jacobi symbols in ${\bf Z}$. Although the quartic algorithm was given by Smith in 1859, the version for cubic symbols seems to be new. As far as we know, neither was analyzed before. We show that both algorithms have exponential worst-case bit complexity. The proof for the cubic algorithm involves a cyclic repetition of four quotients, which may be of independent interest.
Fast transforms over finite fields of characteristic two
Venue: arXiv cs.SC 2018
Year: 2018

An additive fast Fourier transform over a finite field of characteristic two efficiently evaluates polynomials at every element of an $\mathbb{F}_2$-linear subspace of the field. We view these transforms as performing a change of basis from the monomial basis to the associated Lagrange basis, and consider the problem of performing the various conversions between these two bases, the associated Newton basis, and the '' novel '' basis of Lin, Chung and Han (FOCS 2014). Existing algorithms are divided between two families, those designed for arbitrary subspaces and more efficient algorithms designed for specially constructed subspaces of fields with degree equal to a power of two. We generalise techniques from both families to provide new conversion algorithms that may be applied to arbitrary subspaces, but which benefit equally from the specially constructed subspaces. We then construct subspaces of fields with smooth degree for which our algorithms provide better performance than existing algorithms.
Kripke Semantics of the Perfectly Transparent Equilibrium
Venue: arXiv cs.GT 2018
Year: 2018

The Perfectly Transparent Equilibrium is algorithmically defined, for any game in normal form with perfect information and no ties, as the iterated deletion of non-individually-rational strategy profiles until at most one remains. In this paper, we characterize the Perfectly Transparent Equilibrium with adapted Kripke models having necessary rationality, necessary knowledge of strategies as well as eventual logical omniscience. Eventual logical omniscience is introduced as a weaker version of perfect logical omniscience, with logical omniscience being quantized and fading away counterfactually. It is the price to pay for necessary factual omniscience and necessary rationality: we conjecture that epistemic omniscience, logical omniscience and necessary rationality form an impossibility triangle. We consider multimodal classes of Kripke structures, with respect to agents, but also in the sense that we have both epistemic and logical accessibility relations. Knowledge is defined in terms of the former, while necessity is defined in terms of the latter. Lewisian closest-state functions, which are not restricted to unilateral deviations, model counterfactuals. We use impossible possible worlds à la Rantala to model that some strategy profiles cannot possibly be reached in some situations. Eventual logical omniscience is then bootstrapped with the agents' considering that, at logically possible, but non-normal worlds à la Kripke, any world is logically accessible and thus any deviation of strategy is possible. As in known in literature, under rationality and knowledge of strategies, these worlds characterize individual rationality. Then, in normal worlds, higher levels of logical omniscience characterize higher levels of individual rationality, and a high-enough level of logical omniscience characterizes, when it exists, the Perfectly Transparent Equilibrium.
Wireless Multi-Sensor Networks for Smart Cities: A Prototype System with Statistical Data Analysis
Venue: arXiv cs.CY 2018
Year: 2018

As urbanization proceeds at an astonishing rate, cities have to continuously improve their solutions that affect the safety, health and overall wellbeing of their residents. Smart city projects worldwide build on advanced sensor, information and communication technologies to help dealing with issues like air pollution, waste management, traffic optimization, and energy efficiency. The paper reports about the prototype of a smart city initiative in Budapest which applies various sensors installed on the public lighting system and a cloud-based analytical module. While the installed wireless multi-sensor network gathers information about a number of stressors, the module integrates and statistically processes the data. The module can handle inconsistent, missing and noisy data and can extrapolate the measurements in time and space, namely, it can create short-term forecasts and smoothed maps, both accompanied by reliability estimates. The resulting database uses geometric representations and can serve as an information centre for public services.
Bachelor of informatics competence in programming
Venue: arXiv cs.CY 2018
Year: 2018

Based on the analysis of approaches to the definition of professional competencies of IT students the competence in programming of bachelor of informatics is proposed. Due to the standard of training in 040302 "Informatics" and Computing Curricula 2001 it was defined the content and structure of the competence in programming of bachelor of informatics. The system of content modules providing its formation was designed. The contribution of regulatory competencies of bachelor of informatics in the formation of competence in programming is defined. The directions of formation of competence in programming in the cloudy-oriented learning environment are proposed.
Ensemble of Deep Learned Features for Melanoma Classification
Venue: arXiv cs.CV 2018
Year: 2018

The aim of this work is to propose an ensemble of descriptors for Melanoma Classification, whose performance has been evaluated on validation and test datasets of the melanoma challenge 2018. The system proposed here achieves a strong discriminative power thanks to the combination of multiple descriptors. The proposed system represents a very simple yet effective way of boosting the performance of trained CNNs by composing multiple CNNs into an ensemble and combining scores by sum rule. Several types of ensembles are considered, with different CNN architectures along with different learning parameter sets. Moreover CNN are used as feature extractors: an input image is processed by a trained CNN and the response of a particular layer (usually the classification layer, but also internal layers can be employed) is treated as a descriptor for the image and used for training a set of Support Vector Machines (SVM).
Shared Processor Scheduling of Multiprocessor Jobs
Venue: arXiv cs.DM 2018
Year: 2018

We study shared processor scheduling of $\textit{multiprocessor}$ weighted jobs where each job can be executed on its private processor and simultaneously on possibly $\textit{many}$ processors shared by all jobs in order to reduce their completion times due to processing time overlap. Each of $m$ shared processors may charge different fee but otherwise the processors are identical. The total weighted overlap of all jobs is to be maximized. This problem is key to subcontractor scheduling in extended enterprises and supply chains, and divisible load scheduling in computing. We prove that, quite surprisingly, $\textit{synchronized}$ schedules that complete each job using shared processors at the same time on its private and shared processors include optimal schedules. We show that optimal $α$-$\textit{private}$ schedules that require each job to use its private processor for at least $α=1/2+1/(4(m+1))$ of the time required by the job guarantee more than an $α$ fraction of the total weighted overlap of the optimal schedules. This gives an $α$-approximation algorithm that runs in strongly polynomial time for the problem, and improves the $1/2$-approximation reported recently in the literature to $5/8$-approximation for a single shared processor problem. The computational complexity of the problem, both single and multi-shared processor, remains open. We show however an LP-based optimal algorithm for $\textit{antithetical}$ instances where for any pair of jobs $j$ and $i$, if the processing time of $j$ is smaller than or equal to the processing time of $i$, then the weight of $j$ is greater than or equal to the weight of $i$.
On the Relevance of Blockchain in Identity Management
Venue: arXiv cs.CR 2018
Year: 2018

The ubiquitous application of emerging blockchain technology in numerous technological projects leads to a tremendous hype. The significantly high prices of digital currencies and initial coin offerings as the new funding approach has fostered the public perception of blockchain as a cure-all and driven the hype even further. In this evolution, a clear view of the reasonable application of blockchain technology is not given and therefore, the purposeful use of traditional technologies is undermined. To clarify this situation, we derive a novel decision model for evaluating the applicability of blockchain technology that considers two key factors: the remediation of central governance and the management of digital objects. Based on these key factors, we closely analyse the domain of identity management for conscious blockchain application. Finally, we examine uPort, Sovrin, and ShoCard as distinct projects in this scope with regard to the inevitable necessity to implement a blockchain by using our decision model.
Delta-Decision Procedures for Exists-Forall Problems over the Reals
Venue: arXiv cs.LO 2018
Year: 2018

Solving nonlinear SMT problems over real numbers has wide applications in robotics and AI. While significant progress is made in solving quantifier-free SMT formulas in the domain, quantified formulas have been much less investigated. We propose the first delta-complete algorithm for solving satisfiability of nonlinear SMT over real numbers with universal quantification and a wide range of nonlinear functions. Our methods combine ideas from counterexample-guided synthesis, interval constraint propagation, and local optimization. In particular, we show how special care is required in handling the interleaving of numerical and symbolic reasoning to ensure delta-completeness. In experiments, we show that the proposed algorithms can handle many new problems beyond the reach of existing SMT solvers.
On the Analysis of Trajectories of Gradient Descent in the Optimization of Deep Neural Networks
Venue: arXiv cs.LG 2018
Year: 2018

Theoretical analysis of the error landscape of deep neural networks has garnered significant interest in recent years. In this work, we theoretically study the importance of noise in the trajectories of gradient descent towards optimal solutions in multi-layer neural networks. We show that adding noise (in different ways) to a neural network while training increases the rank of the product of weight matrices of a multi-layer linear neural network. We thus study how adding noise can assist reaching a global optimum when the product matrix is full-rank (under certain conditions). We establish theoretical foundations between the noise induced into the neural network - either to the gradient, to the architecture, or to the input/output to a neural network - and the rank of product of weight matrices. We corroborate our theoretical findings with empirical results.
Software Citation in Theory and Practice
Venue: arXiv cs.CY 2018
Year: 2018

In most fields, computational models and data analysis have become a significant part of how research is performed, in addition to the more traditional theory and experiment. Mathematics is no exception to this trend. While the system of publication and credit for theory and experiment (journals and books, often monographs) has developed and has become an expected part of the culture, how research is shared and how candidates for hiring, promotion are evaluated, software (and data) do not have the same history. A group working as part of the FORCE11 community developed a set of principles for software citation that fit software into the journal citation system, allow software to be published and then cited, and there are now over 50,000 DOIs that have been issued for software. However, some challenges remain, including: promoting the idea of software citation to developers and users; collaborating with publishers to ensure that systems collect and retain required metadata; ensuring that the rest of the scholarly infrastructure, particularly indexing sites, include software; working with communities so that software efforts "count" and understanding how best to cite software that has not been published.
A Convolutional Neural Networks Denoising Approach for Salt and Pepper Noise
Venue: arXiv cs.MM 2018
Year: 2018

The salt and pepper noise, especially the one with extremely high percentage of impulses, brings a significant challenge to image denoising. In this paper, we propose a non-local switching filter convolutional neural network denoising algorithm, named NLSF-CNN, for salt and pepper noise. As its name suggested, our NLSF-CNN consists of two steps, i.e., a NLSF processing step and a CNN training step. First, we develop a NLSF pre-processing step for noisy images using non-local information. Then, the pre-processed images are divided into patches and used for CNN training, leading to a CNN denoising model for future noisy images. We conduct a number of experiments to evaluate the effectiveness of NLSF-CNN. Experimental results show that NLSF-CNN outperforms the state-of-the-art denoising algorithms with a few training images.
Inductive Visual Localisation: Factorised Training for Superior Generalisation
Venue: arXiv cs.CV 2018
Year: 2018

End-to-end trained Recurrent Neural Networks (RNNs) have been successfully applied to numerous problems that require processing sequences, such as image captioning, machine translation, and text recognition. However, RNNs often struggle to generalise to sequences longer than the ones encountered during training. In this work, we propose to optimise neural networks explicitly for induction. The idea is to first decompose the problem in a sequence of inductive steps and then to explicitly train the RNN to reproduce such steps. Generalisation is achieved as the RNN is not allowed to learn an arbitrary internal state; instead, it is tasked with mimicking the evolution of a valid state. In particular, the state is restricted to a spatial memory map that tracks parts of the input image which have been accounted for in previous steps. The RNN is trained for single inductive steps, where it produces updates to the memory in addition to the desired output. We evaluate our method on two different visual recognition problems involving visual sequences: (1) text spotting, i.e. joint localisation and reading of text in images containing multiple lines (or a block) of text, and (2) sequential counting of objects in aerial images. We show that inductive training of recurrent models enhances their generalisation ability on challenging image datasets.
Laying the Groundwork for a Worker-Centric Peer Economy
Venue: arXiv cs.HC 2018
Year: 2018

The "gig economy" has transformed the ways in which people work, but in many ways these markets stifle the growth of workers and the autonomy and protections that workers have grown to expect. We explored the viability of a "worker centric peer economy"--a system wherein workers benefit as well as consumers-- and conducted ethnographic field work across fields ranging from domestic labor to home health care. We discovered seven facets that system designers ought to consider when designing a labor market for "gig workers," consisting principally of the following: constructive feedback, assigning work fairly, managing customer expectations, protecting vulnerable workers, reconciling worker identities, assessing worker qualifications, & communicating worker quality. We discuss these considerations and provide guidance toward the design of a mutually beneficial market for gig workers.
Analysis of Logarithmic Amortised Complexity
Venue: arXiv cs.PL 2018
Year: 2018

We introduce a novel amortised resource analysis based on a potential-based type system. This type system gives rise to logarithmic and polynomial bounds on the runtime complexity and is the first such system to exhibit logarithmic amortised complexity. We relate the thus obtained automatable amortised resource analysis to manual amortised analyses of self-adjusting data structures, like splay trees, that can be found in the literature.
Taint Tracking for WebAssembly
Venue: arXiv cs.CR 2018
Year: 2018

WebAssembly seeks to provide an alternative to running large and untrusted binaries within web browsers by implementing a portable, performant, and secure bytecode format for native web computation. However, WebAssembly is largely unstudied from a security perspective. In this work, we build the first WebAssembly virtual machine that runs in native JavaScript, and implement a novel taint tracking system that allows a user to run untrusted WebAssembly code while monitoring the flow of sensitive data through the application. We also introduce indirect taint, a label that denotes the implicit flow of sensitive information between local variables. Through rigorous testing and validation, we show that our system is correct, secure, and relatively efficient, benefiting from the native performance of WebAssembly while retaining precise security guarantees of more mature software paradigms.
Adaptive Target Tracking with a Mixed Team of Static and Mobile Guards: Deployment and Activation Strategies
Venue: arXiv cs.CG 2018
Year: 2018

This work explores a variation of the art gallery problem in which a team of static and mobile guards track a mobile intruder with unknown maximum speed. First, we present an algorithm to identify {\it candidate vertices} in a polygon at which either static guards can be placed or they can serve as endpoints of the trajectory of mobile guards. Based on the triangulation of the polygon and the deployment of the guards we propose an allocation technique for the guards, such that each one of them is assigned to guard a subregion of the environment when the intruder is inside it. The allocation strategy leads to a classification of the guards based on their task and coordination requirements. Next, we present an activation strategy for the static guards that is adaptive to the instantaneous speed of the intruder. The deployment and the activation technique guarantee that a variable speed intruder is successfully tracked. Simulation results are presented to validate the efficacy of the proposed techniques.
Technical Report: Reactive Navigation in Partially Known Non-Convex Environments
Venue: arXiv cs.RO 2018
Year: 2018

This paper presents a provably correct method for robot navigation in 2D environments cluttered with familiar but unexpected non-convex, star-shaped obstacles as well as completely unknown, convex obstacles. We presuppose a limited range onboard sensor, capable of recognizing, localizing and (leveraging ideas from constructive solid geometry) generating online from its catalogue of the familiar, non-convex shapes an implicit representation of each one. These representations underlie an online change of coordinates to a completely convex model planning space wherein a previously developed online construction yields a provably correct reactive controller that is pulled back to the physically sensed representation to generate the actual robot commands. We extend the construction to differential drive robots, and suggest the empirical utility of the proposed control architecture using both formal proofs and numerical simulations.
On the Anonymization of Differentially Private Location Obfuscation
Venue: arXiv cs.CR 2018
Year: 2018

Obfuscation techniques in location-based services (LBSs) have been shown useful to hide the concrete locations of service users, whereas they do not necessarily provide the anonymity. We quantify the anonymity of the location data obfuscated by the planar Laplacian mechanism and that by the optimal geo-indistinguishable mechanism of Bordenabe et al. We empirically show that the latter provides stronger anonymity than the former in the sense that more users in the database satisfy k-anonymity. To formalize and analyze such approximate anonymity we introduce the notion of asymptotic anonymity. Then we show that the location data obfuscated by the optimal geo-indistinguishable mechanism can be anonymized by removing a smaller number of users from the database. Furthermore, we demonstrate that the optimal geo-indistinguishable mechanism has better utility both for users and for data analysts.