OpenRaiser/Intern-Atlas huggingface dataset:
Learning Mixtures of Plackett-Luce Models
Venue: arXiv cs.LG 2020
Year: 2020

In this paper we address the identifiability and efficient learning problems of finite mixtures of Plackett-Luce models for rank data. We prove that for any $k\geq 2$, the mixture of $k$ Plackett-Luce models for no more than $2k-1$ alternatives is non-identifiable and this bound is tight for $k=2$. For generic identifiability, we prove that the mixture of $k$ Plackett-Luce models over $m$ alternatives is generically identifiable if $k\leq\lfloor\frac {m-2} 2\rfloor!$. We also propose an efficient generalized method of moments (GMM) algorithm to learn the mixture of two Plackett-Luce models and show that the algorithm is consistent. Our experiments show that our GMM algorithm is significantly faster than the EMM algorithm by Gormley and Murphy (2008), while achieving competitive statistical efficiency.
On the Hessian of Shape Matching Energy
Venue: arXiv cs.GR 2020
Year: 2020

In this technical report we derive the analytic form of the Hessian matrix for shape matching energy. Shape matching is a useful technique for meshless deformation, which can be easily combined with multiple techniques in real-time dynamics. Nevertheless, it has been rarely applied in scenarios where implicit integrators are required, and hence strong viscous damping effect, though popular in simulation systems nowadays, is forbidden for shape matching. The reason lies in the difficulty to derive the Hessian matrix of the shape matching energy. Computing the Hessian matrix correctly, and stably, is the key to more broadly application of shape matching in implicitly-integrated systems.
An integral-transform approach to the bioheat transfer problems in magnetic hyperthermia
Venue: arXiv cs.CE 2020
Year: 2020

Our purpose in this study was to present an integral-transform approach to the analytical solutions of the Pennes's bioheat transfer equation and to apply it to the calculation of temperature distribution in tissues in hyperthermia with magnetic nanoparticles (magnetic hyperthermia). The validity of our method was investigated by comparison with the analytical solutions obtained by the Green's function method for point and shell heat sources and the numerical solutions obtained by the finite-difference method for Gaussin-distributed and step-function sources. There was good agreement between the radial profiles of temperature calculated by our method and those obtained by the Green's function method. There was also good agreement between our method and the finite-difference method except for the central temperature for a step-function source that had approximately a 0.3% difference. We also found that the equations describing the steady-state solutions for point and shell sources obtained by our method agreed with those obtained by the Green's function method. These results appear to indicate the validity of our method. In conclusion, we presented an integral-transform approach to the bioheat transfer problems in magnetic hyperthermia, and this study demonstrated the validity of our method. The analytical solutions presented in this study will be useful for gaining some insight into the heat diffusion process during magnetic hyperthermia, for testing numerical codes and/or more complcated approaches, and for performing sensitivity analysis and optimization of the parameters that affect the thermal diffusion process in magnetic hyperthermia.
Multi-Issue Social Learning
Venue: arXiv cs.GT 2020
Year: 2020

We consider social learning where agents can only observe part of the population (modeled as neighbors on an undirected graph), face many decision problems, and arrival order of the agents is unknown. The central question we pose is whether there is a natural observability graph that prevents the information cascade phenomenon. We introduce the `celebrities graph' and prove that indeed it allows for proper information aggregation in large populations even when the order at which agents decide is random and even when different issues are decided in different orders.
Towards Extending Noiseless Privacy -- Dependent Data and More Practical Approach
Venue: arXiv cs.CR 2020
Year: 2020

In 2011 Bhaskar et al. pointed out that in many cases one can ensure sufficient level of privacy without adding noise by utilizing adversarial uncertainty. Informally speaking, this observation comes from the fact that if at least a part of the data is randomized from the adversary's point of view, it can be effectively used for hiding other values. So far the approach to that idea in the literature was mostly purely asymptotic, which greatly limited its adaptation in real-life scenarios. In this paper we aim to make the concept of utilizing adversarial uncertainty not only an interesting theoretical idea, but rather a practically useful technique, complementary to differential privacy, which is the state-of-the-art definition of privacy. This requires non-asymptotic privacy guarantees, more realistic approach to the randomness inherently present in the data and to the adversary's knowledge. In our paper we extend the concept proposed by Bhaskar et al. and present some results for wider class of data. In particular we cover the data sets that are dependent. We also introduce rigorous adversarial model. Moreover, in contrast to most of previous papers in this field, we give detailed (non-asymptotic) results which is motivated by practical reasons. Note that it required a modified approach and more subtle mathematical tools, including Stein method which, to the best of our knowledge, was not used in privacy research before. Apart from that, we show how to combine adversarial uncertainty with differential privacy approach and explore synergy between them to enhance the privacy parameters already present in the data itself by adding small amount of noise.
Microwave Tomographic Imaging of Cerebrovascular Accidents by Using High-Performance Computing
Venue: arXiv cs.CE 2020
Year: 2020

The motivation of this work is the detection of cerebrovascular accidents by microwave tomographic imaging. This requires the solution of an inverse problem relying on a minimization algorithm (for example, gradient-based), where successive iterations consist in repeated solutions of a direct problem. The reconstruction algorithm is extremely computationally intensive and makes use of efficient parallel algorithms and high-performance computing. The feasibility of this type of imaging is conditioned on one hand by an accurate reconstruction of the material properties of the propagation medium and on the other hand by a considerable reduction in simulation time. Fulfilling these two requirements will enable a very rapid and accurate diagnosis. From the mathematical and numerical point of view, this means solving Maxwell's equations in time-harmonic regime by appropriate domain decomposition methods, which are naturally adapted to parallel architectures.
Estimating Current-Flow Closeness Centrality with a Multigrid Laplacian Solver
Venue: arXiv cs.DS 2020
Year: 2020

Matrices associated with graphs, such as the Laplacian, lead to numerous interesting graph problems expressed as linear systems. One field where Laplacian linear systems play a role is network analysis, e. g. for certain centrality measures that indicate if a node (or an edge) is important in the network. One such centrality measure is current-flow closeness. To allow network analysis workflows to profit from a fast Laplacian solver, we provide an implementation of the LAMG multigrid solver in the NetworKit package, facilitating the computation of current-flow closeness values or related quantities. Our main contribution consists of two algorithms that accelerate the current-flow computation for one node or a reasonably small node subset significantly. One sampling-based algorithm provides an unbiased estimation of the related electrical farness, the other one is based on the Johnson-Lindenstrauss transform. Our inexact algorithms lead to very accurate results in practice. Thanks to them one is now able to compute an estimation of current-flow closeness of one node on networks with tens of millions of nodes and edges within seconds or a few minutes. From a network analytical point of view, our experiments indicate that current-flow closeness can discriminate among different nodes significantly better than traditional shortest-path closeness and is also considerably more resistant to noise -- we thus show that two known drawbacks of shortest-path closeness are alleviated by the current-flow variant.
Liquid Information Flow Control
Venue: arXiv cs.PL 2020
Year: 2020

We present Lifty, a domain-specific language for data-centric applications that manipulate sensitive data. A Lifty programmer annotates the sources of sensitive data with declarative security policies, and the language statically and automatically verifies that the application handles the data according to the policies. Moreover, if verification fails, Lifty suggests a provably correct repair, thereby easing the programmer burden of implementing policy enforcing code throughout the application. The main insight behind Lifty is to encode information flow control using liquid types, an expressive yet decidable type system. Liquid types enable fully automatic checking of complex, data dependent policies, and power our repair mechanism via type-driven error localization and patch synthesis. Our experience using Lifty to implement three case studies from the literature shows that (1) the Lifty policy language is sufficiently expressive to specify many real-world policies, (2) the Lifty type checker is able to verify secure programs and find leaks in insecure programs quickly, and (3) even if the programmer leaves out all policy enforcing code, the Lifty repair engine is able to patch all leaks automatically within a reasonable time.
Millimeter Wave Receiver Efficiency: A Comprehensive Comparison of Beamforming Schemes with Low Resolution ADCs
Venue: arXiv cs.IT 2020
Year: 2020

In this work, we study the achievable rate and the energy efficiency of Analog, Hybrid and Digital Combining (AC, HC and DC) for millimeter wave (mmW) receivers. We take into account the power consumption of all receiver components, not just Analog-to-Digital Converters (ADC), determine some practical limitations of beamforming in each architecture, and develop performance analysis charts that enable comparison of different receivers simultaneously in terms of two metrics, namely, Spectral Efficiency (SE) and Energy Efficiency (EE). We present a multi-objective utility optimization interpretation to find the best SE-EE weighted trade-off among AC, DC and HC schemes. We consider an Additive Quantization Noise Model (AQNM) to evaluate the achievable rates with low resolution ADCs. Our analysis shows that AC is only advantageous if the channel rank is strictly one, the link has very low SNR, or there is a very stringent low power constraint at the receiver. Otherwise, we show that the usual claim that DC requires the highest power is not universally valid. Rather, either DC or HC alternatively result in the better SE vs EE trade-off depending strongly on the considered power consumption characteristic values for each component of the mmW receiver.
On the Existence of a Projective Reconstruction
Venue: arXiv cs.CV 2020
Year: 2020

In this note we study the connection between the existence of a projective reconstruction and the existence of a fundamental matrix satisfying the epipolar constraints.
Programming the Universe: The First Commandment of Software Engineering for all Varieties of Information Systems
Venue: arXiv cs.SE 2020
Year: 2020

Since the early days of computers and programs, the process and outcomes of software development has been a minefield plagued with problems and failures, as much as the complexity and complication of software and its development has increased by a thousandfold in half a century. Over the years, a number of theories, laws, best practices, manifestos and methodologies have emerged, with varied degrees of (un)success. Our experience as software engineers of complex and large-scale systems shows that those guidelines are bound to previously defined and often narrow scopes. Enough is enough. Nowadays, nearly every company is in the software and services business and everything is - or is managed by - software. It is about time, then, that the laws that govern our universe ought to be redefined. In this context, we discuss and present a set of universal laws that leads us to propose the first commandment of software engineering for all varieties of information systems.
The Hamiltonian Cycle in $K_{1,r}$-free Split Graphs -- A Dichotomy
Venue: arXiv cs.DM 2020
Year: 2020

In this paper, we investigate the well-studied Hamiltonian cycle problem (HCYCLE), and present an interesting dichotomy result on split graphs. T. Akiyama et al. (1980) have shown that HCYCLE is NP-complete in planar bipartite graphs with maximum degree $3$. Using this reduction, we show that HCYCLE is NP-complete in split graphs. In particular, we show that the problem is NP-complete in $K_{1,5}$-free split graphs. Further, we present polynomial-time algorithms for Hamiltonian cycle in $K_{1,3}$-free and $K_{1,4}$-free split graphs. We believe that the structural results presented in this paper can be used to show similar dichotomy result for Hamiltonian path problem (HPATH) and other variants of HCYCLE.
A Practical Approach to Interval Refinement for math.h/cmath Functions
Venue: arXiv cs.PL 2020
Year: 2020

Verification of C++ programs has seen considerable progress in several areas, but not for programs that use these languages' mathematical libraries. The reason is that all libraries in widespread use come with no guarantees about the computed results. This would seem to prevent any attempt at formal verification of programs that use them: without a specification for the functions, no conclusion can be drawn statically about the behavior of the program. We propose an alternative to surrender. We introduce a pragmatic approach that leverages the fact that most math.h/cmath functions are almost piecewise monotonic: as we discovered through exhaustive testing, they may have glitches, often of very small size and in small numbers. We develop interval refinement techniques for such functions based on a modified dichotomic search, that enable verification via symbolic execution based model checking, abstract interpretation, and test data generation. Our refinement algorithms are the first in the literature to be able to handle non-correctly rounded function implementations, enabling verification in the presence of the most common implementations. We experimentally evaluate our approach on real-world code, showing its ability to detect or rule out anomalous behaviors.
Oh-RAM! One and a Half Round Atomic Memory
Venue: arXiv cs.DC 2020
Year: 2020

Emulating atomic read/write shared objects in a message-passing system is a fundamental problem in distributed computing. Considering that network communication is the most expensive resource, efficiency is measured first of all in terms of the communication needed to implement read and write operations. It is well known that 2 communication round-trip phases involving in total 4 message exchanges are sufficient to implemented atomic operations. It is also known that under certain constraints on the number of readers with respect to the numbers of replica servers and failures it is possible to implement single-writer atomic objects such that each operation involves one round-trip phase. We present algorithms that allow operations to complete in 3 communication exchanges without imposing any constraints on the number of readers and writers. Specifically, we present an atomic memory implementation for the SWMR setting, where reads complete in 3 communication exchanges and writes complete in 2 exchanges. We pose the question of whether it is possible to implement MWMR memory where operations complete in at most 3 communication exchanges. We answer this question in the negative by showing that an atomic memory implementation is impossible if both read and write operations take 3 communication exchanges, even when assuming two writers, two readers, and a single replica server failure. Motivated by this impossibility result, we provide a MWMR atomic memory implementation where reads involve 3 and writes 4 communication exchanges. In light of our impossibility result these algorithms are optimal in terms of the number of communication exchanges. We rigorously reason about the correctness of the algorithms.
Algebraic Laws for True Concurrency
Venue: arXiv cs.LO 2020
Year: 2020

We find the algebraic laws for true concurrency. Eventually, we establish a whole axiomatization for true concurrency called APTC (Algebra for Parallelism in True Concurrency). The theory APTC has four modules: BATC (Basic Algebra for True Concurrency), APTC (Algebra for Parallelism in True Concurrency), recursion and abstraction. And also, we show the applications and extensions of APTC.
Testing Bayesian Networks
Venue: arXiv cs.DS 2020
Year: 2020

This work initiates a systematic investigation of testing high-dimensional structured distributions by focusing on testing Bayesian networks -- the prototypical family of directed graphical models. A Bayesian network is defined by a directed acyclic graph, where we associate a random variable with each node. The value at any particular node is conditionally independent of all the other non-descendant nodes once its parents are fixed. Specifically, we study the properties of identity testing and closeness testing of Bayesian networks. Our main contribution is the first non-trivial efficient testing algorithms for these problems and corresponding information-theoretic lower bounds. For a wide range of parameter settings, our testing algorithms have sample complexity sublinear in the dimension and are sample-optimal, up to constant factors.
Reliable recovery of hierarchically sparse signals for Gaussian and Kronecker product measurements
Venue: arXiv cs.IT 2020
Year: 2020

We propose and analyze a solution to the problem of recovering a block sparse signal with sparse blocks from linear measurements. Such problems naturally emerge inter alia in the context of mobile communication, in order to meet the scalability and low complexity requirements of massive antenna systems and massive machine-type communication. We introduce a new variant of the Hard Thresholding Pursuit (HTP) algorithm referred to as HiHTP. We provide both a proof of convergence and a recovery guarantee for noisy Gaussian measurements that exhibit an improved asymptotic scaling in terms of the sampling complexity in comparison with the usual HTP algorithm. Furthermore, hierarchically sparse signals and Kronecker product structured measurements naturally arise together in a variety of applications. We establish the efficient reconstruction of hierarchically sparse signals from Kronecker product measurements using the HiHTP algorithm. Additionally, we provide analytical results that connect our recovery conditions to generalized coherence measures. Again, our recovery results exhibit substantial improvement in the asymptotic sampling complexity scaling over the standard setting. Finally, we validate in numerical experiments that for hierarchically sparse signals, HiHTP performs significantly better compared to HTP.
Secure Cloud Storage Protocols with Data Dynamics Using Secure Network Coding Techniques
Venue: arXiv cs.CR 2020
Year: 2020

In the age of cloud computing, cloud users with limited storage can outsource their data to remote servers. These servers, in lieu of monetary benefits, offer retrievability of their clients' data at any point of time. Secure cloud storage protocols enable a client to check integrity of outsourced data. In this work, we explore the possibility of constructing a secure cloud storage for dynamic data by leveraging the algorithms involved in secure network coding. We show that some of the secure network coding schemes can be used to construct efficient secure cloud storage protocols for dynamic data, and we construct such a protocol (DSCS I) based on a secure network coding protocol. To the best of our knowledge, DSCS I is the first secure cloud storage protocol for dynamic data constructed using secure network coding techniques which is secure in the standard model. Although generic dynamic data support arbitrary insertions, deletions and modifications, append-only data find numerous applications in the real world. We construct another secure cloud storage protocol (DSCS II) specific to append-only data -- that overcomes some limitations of DSCS I. Finally, we provide prototype implementations for DSCS I and DSCS II in order to evaluate their performance.
Is Lipschitz Continuity Preserved under Sampled-Data Discretization?
Venue: arXiv cs.SY 2020
Year: 2020

Usually, given a continuous-time nonlinear model, a closed form solution for an exact discretization cannot be found explicitly, originating the need of approximating discrete-time models. This note studies the preservation of the Lipschitz continuity under approximate discretizations.
Client-Based Control Channel Analysis for Connectivity Estimation in LTE Networks
Venue: arXiv cs.NI 2020
Year: 2020

Advanced Cyber-Physical Systems aim for the balancing of restricted local resources of deeply embedded systems with cloud-based resources depending on the availability of network connectivity: in case of excellent connectivity, the offloading of large amounts of data can be more efficient than the local processing on a resource-constraint platform, while this latter solution is preferred in case of limited connectivity. This paper proposes a Client-Based Control Channel Analysis for Connectivity Estimation (C3ACE), a new passive probing mechanism to enable the client-side to estimate the connection quality of 4G networks in range. The results show that by observing and analyzing the control traffic in real-time, the number of active user equipment in a cell can be determined with surprising accuracy (with errors well below 10e-6). The specific challenge addressed in this paper lies in a dedicated filtering and validation of the DCI (Downlink Control Information). In a subsequent step the data rates to be expected can be estimated in order to enable decision about the choice of network and the timing of the data offloading to the cloud. The proposed methods have been implemented and validated leveraging the SDR OpenAirInterface, a real-life LTE network and a distributed load generator producing a scalable network traffic by a number of LTE User Equipment.