OpenRaiser/Intern-Atlas huggingface dataset:
Enhancement of damaged-image prediction through Cahn-Hilliard Image Inpainting
Venue: arXiv cs.CV 2021
Year: 2021

We assess the benefit of including an image inpainting filter before passing damaged images into a classification neural network. For this we employ a modified Cahn-Hilliard equation as an image inpainting filter, which is solved via a finite volume scheme with reduced computational cost and adequate properties for energy stability and boundedness. The benchmark dataset employed here is MNIST, which consists of binary images of handwritten digits and is a standard dataset to validate image-processing methodologies. We train a neural network based of dense layers with the training set of MNIST, and subsequently we contaminate the test set with damage of different types and intensities. We then compare the prediction accuracy of the neural network with and without applying the Cahn-Hilliard filter to the damaged images test. Our results quantify the significant improvement of damaged-image prediction due to applying the Cahn-Hilliard filter, which for specific damages can increase up to 50% and is in general advantageous for low to moderate damage.
Challenges in Developing Secure Mobile Health Applications, A Systematic Review
Venue: arXiv cs.SE 2021
Year: 2021

Mobile health (mHealth) applications (apps) have gained significant popularity over the last few years due to its tremendous benefits, such as lowering healthcare cost and increasing patient awareness. However, the sensitivity of healthcare data makes the security of mHealth apps a serious concern. In this review, we aim to identify and analyse the reported challenges that the developers of mHealth apps face concerning security. Additionally, our study aimed to develop a conceptual framework with the challenges faced by mHealth apps development organization for developing secure apps. The knowledge of such challenges can help to reduce the risk of developing insecure mHealth apps. We followed the Systematic Literature Review method for this review. We selected studies that have been published between January 2008 and October 2020. We selected 32 primary studies using predefined criteria and used thematic analysis method for analysing the extracted data. We identified nine challenges that can affect the development of secure mHealth apps. Such as 1) lack of security guidelines and regulations for developing secure mHealth apps, 2) developers lack of knowledge and expertise for secure mHealth app development, 3) lack of stakeholders involvement during mHealth app development, etc . Based on our analysis, we have presented a conceptual framework which highlights the correlation between the identified challenges. We conclude that our findings can help them identify their weaknesses and improve their security practices. Similarly, mHealth apps developers can identify the challenges they face to develop mHealth apps that do not pose security risks for users. Our review is a step towards providing insights into the development of secure mHealth apps. Our proposed conceptual framework can act as a practice guideline for practitioners to enhance secure mHealth apps development.
Byzantine-Resilient Secure Federated Learning
Venue: arXiv cs.CR 2021
Year: 2021

Secure federated learning is a privacy-preserving framework to improve machine learning models by training over large volumes of data collected by mobile users. This is achieved through an iterative process where, at each iteration, users update a global model using their local datasets. Each user then masks its local model via random keys, and the masked models are aggregated at a central server to compute the global model for the next iteration. As the local models are protected by random masks, the server cannot observe their true values. This presents a major challenge for the resilience of the model against adversarial (Byzantine) users, who can manipulate the global model by modifying their local models or datasets. Towards addressing this challenge, this paper presents the first single-server Byzantine-resilient secure aggregation framework (BREA) for secure federated learning. BREA is based on an integrated stochastic quantization, verifiable outlier detection, and secure model aggregation approach to guarantee Byzantine-resilience, privacy, and convergence simultaneously. We provide theoretical convergence and privacy guarantees and characterize the fundamental trade-offs in terms of the network size, user dropouts, and privacy protection. Our experiments demonstrate convergence in the presence of Byzantine users, and comparable accuracy to conventional federated learning benchmarks.
Finding large induced sparse subgraphs in $C_{>t}$-free graphs in quasipolynomial time
Venue: arXiv cs.DS 2021
Year: 2021

For an integer $t$, a graph $G$ is called {\em{$C_{>t}$-free}} if $G$ does not contain any induced cycle on more than~$t$ vertices. We prove the following statement: for every pair of integers $d$ and $t$ and a CMSO$_2$ statement~$ϕ$, there exists an algorithm that, given an $n$-vertex $C_{>t}$-free graph $G$ with weights on vertices, finds in time $n^{O(\log^4 n)}$ a maximum-weight vertex subset $S$ such that $G[S]$ has degeneracy at most $d$ and satisfies $ϕ$. The running time can be improved to $n^{O(\log^2 n)}$ assuming $G$ is $P_t$-free, that is, $G$ does not contain an induced path on $t$ vertices. This expands the recent results of the authors [to appear at FOCS 2020 and SOSA 2021] on the {\sc{Maximum Weight Independent Set}} problem on $P_t$-free graphs in two directions: by encompassing the more general setting of $C_{>t}$-free graphs, and by being applicable to a much wider variety of problems, such as {\sc{Maximum Weight Induced Forest}} or {\sc{Maximum Weight Induced Planar Graph}}.
Formal Analysis of EDHOC Key Establishment for Constrained IoT Devices
Venue: arXiv cs.CR 2021
Year: 2021

Constrained IoT devices are becoming ubiquitous in society and there is a need for secure communication protocols that respect the constraints under which these devices operate. EDHOC is an authenticated key establishment protocol for constrained IoT devices, currently being standardized by the Internet Engineering Task Force (IETF). A rudimentary version of EDHOC with only two key establishment methods was formally analyzed in 2018. Since then, the protocol has evolved significantly and several new key establishment methods have been added. In this paper, we present a formal analysis of all EDHOC methods in an enhanced symbolic Dolev-Yao model using the Tamarin tool. We show that not all methods satisfy the authentication notion injective of agreement, but that they all do satisfy a notion of implicit authentication, as well as Perfect Forward Secrecy (PFS) of the session key material. We identify other weaknesses to which we propose improvements. For example, a party may intend to establish a session key with a certain peer, but end up establishing it with another, trusted but compromised, peer. We communicated our findings and proposals to the IETF, which has incorporated some of these in newer versions of the standard.
Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time
Venue: arXiv cs.DS 2021
Year: 2021

We consider the problem of building Distance Sensitivity Oracles (DSOs). Given a directed graph $G=(V, E)$ with edge weights in $\{1, 2, \dots, M\}$, we need to preprocess it into a data structure, and answer the following queries: given vertices $u,v\in V$ and a failed vertex or edge $f\in (V\cup E)$, output the length of the shortest path from $u$ to $v$ that does not go through $f$. Our main result is a simple DSO with $\tilde{O}(n^{2.7233}M)$ preprocessing time and $O(1)$ query time. Moreover, if the input graph is undirected, the preprocessing time can be improved to $\tilde{O}(n^{2.6865}M)$. The preprocessing algorithm is randomized with correct probability $\ge 1-1/n^C$, for a constant $C$ that can be made arbitrarily large. Previously, there is a DSO with $\tilde{O}(n^{2.8729}M)$ preprocessing time and $\operatorname{polylog}(n)$ query time [Chechik and Cohen, STOC'20]. At the core of our DSO is the following observation from [Bernstein and Karger, STOC'09]: if there is a DSO with preprocessing time $P$ and query time $Q$, then we can construct a DSO with preprocessing time $P+\tilde{O}(n^2)\cdot Q$ and query time $O(1)$. (Here $\tilde{O}(\cdot)$ hides $\operatorname{polylog}(n)$ factors.)
Semantics-Empowered Communication for Networked Intelligent Systems
Venue: arXiv cs.IT 2021
Year: 2021

Wireless connectivity has traditionally been regarded as an opaque data pipe carrying messages, whose context-dependent meaning and effectiveness have been ignored. Nevertheless, in emerging cyber-physical and autonomous networked systems, acquiring, processing, and sending excessive amounts of distributed real-time data, which ends up being stale or useless to the end user, will cause communication bottlenecks, increased latency, and safety issues. We envision a communication paradigm shift, which makes the Semantics of Information, i.e., the significance and the usefulness of messages with respect to the goal of data exchange, the underpinning of the entire communication process. This entails a goal-oriented unification of information generation, transmission, and usage, by taking into account process dynamics, signal sparsity, data correlation, and semantic information attributes. We apply this structurally new, synergetic approach to a communication scenario where the destination is tasked with real-time source reconstruction for the purpose of remote actuation. Capitalizing on semantics-empowered sampling and communication policies, we show significant reduction in both reconstruction error and cost of actuation error, as well as in the number of uninformative samples generated.
Right for the Right Reason: Making Image Classification Robust
Venue: arXiv cs.CV 2021
Year: 2021

The effectiveness of Convolutional Neural Networks (CNNs)in classifying image data has been thoroughly demonstrated. In order to explain the classification to humans, methods for visualizing classification evidence have been developed in recent years. These explanations reveal that sometimes images are classified correctly, but for the wrong reasons,i.e., based on incidental evidence. Of course, it is desirable that images are classified correctly for the right reasons, i.e., based on the actual evidence. To this end, we propose a new explanation quality metric to measure object aligned explanation in image classification which we refer to as theObAlExmetric. Using object detection approaches, explanation approaches, and ObAlEx, we quantify the focus of CNNs on the actual evidence. Moreover, we show that additional training of the CNNs can improve the focus of CNNs without decreasing their accuracy.
A Solution to Product detection in Densely Packed Scenes
Venue: arXiv cs.CV 2021
Year: 2021

This work is a solution to densely packed scenes dataset SKU-110k. Our work is modified from Cascade R-CNN. To solve the problem, we proposed a random crop strategy to ensure both the sampling rate and input scale is relatively sufficient as a contrast to the regular random crop. And we adopted some of trick and optimized the hyper-parameters. To grasp the essential feature of the densely packed scenes, we analysis the stages of a detector and investigate the bottleneck which limits the performance. As a result, our method obtains 58.7 mAP on test set of SKU-110k.
The Representation Theory of Neural Networks
Venue: arXiv cs.LG 2021
Year: 2021

In this work, we show that neural networks can be represented via the mathematical theory of quiver representations. More specifically, we prove that a neural network is a quiver representation with activation functions, a mathematical object that we represent using a network quiver. Also, we show that network quivers gently adapt to common neural network concepts such as fully-connected layers, convolution operations, residual connections, batch normalization, pooling operations and even randomly wired neural networks. We show that this mathematical representation is by no means an approximation of what neural networks are as it exactly matches reality. This interpretation is algebraic and can be studied with algebraic methods. We also provide a quiver representation model to understand how a neural network creates representations from the data. We show that a neural network saves the data as quiver representations, and maps it to a geometrical space called the moduli space, which is given in terms of the underlying oriented graph of the network, i.e., its quiver. This results as a consequence of our defined objects and of understanding how the neural network computes a prediction in a combinatorial and algebraic way. Overall, representing neural networks through the quiver representation theory leads to 9 consequences and 4 inquiries for future research that we believe are of great interest to better understand what neural networks are and how they work.
A Comprehensive Study on Deep Learning-based Methods for Sign Language Recognition
Venue: arXiv cs.CV 2021
Year: 2021

In this paper, a comparative experimental assessment of computer vision-based methods for sign language recognition is conducted. By implementing the most recent deep neural network methods in this field, a thorough evaluation on multiple publicly available datasets is performed. The aim of the present study is to provide insights on sign language recognition, focusing on mapping non-segmented video streams to glosses. For this task, two new sequence training criteria, known from the fields of speech and scene text recognition, are introduced. Furthermore, a plethora of pretraining schemes is thoroughly discussed. Finally, a new RGB+D dataset for the Greek sign language is created. To the best of our knowledge, this is the first sign language dataset where sentence and gloss level annotations are provided for a video capture.
Predictors of Well-being and Productivity among Software Professionals during the COVID-19 Pandemic -- A Longitudinal Study
Venue: arXiv cs.CY 2021
Year: 2021

The COVID-19 pandemic has forced governments worldwide to impose movement restrictions on their citizens. Although critical to reducing the virus' reproduction rate, these restrictions come with far-reaching social and economic consequences. In this paper, we investigate the impact of these restrictions on an individual level among software engineers who were working from home. Although software professionals are accustomed to working with digital tools, but not all of them remotely, in their day-to-day work, the abrupt and enforced work-from-home context has resulted in an unprecedented scenario for the software engineering community. In a two-wave longitudinal study (N=192), we covered over 50 psychological, social, situational, and physiological factors that have previously been associated with well-being or productivity. Examples include anxiety, distractions, coping strategies, psychological and physical needs, office set-up, stress, and work motivation. This design allowed us to identify the variables that explained unique variance in well-being and productivity. Results include (1) the quality of social contacts predicted positively, and stress predicted an individual's well-being negatively when controlling for other variables consistently across both waves; (2) boredom and distractions predicted productivity negatively; (3) productivity was less strongly associated with all predictor variables at time two compared to time one, suggesting that software engineers adapted to the lockdown situation over time; and (4) longitudinal analyses did not provide evidence that any predictor variable causal explained variance in well-being and productivity. Overall, we conclude that working from home was per se not a significant challenge for software engineers.
Storywrangler: A massive exploratorium for sociolinguistic, cultural, socioeconomic, and political timelines using Twitter
Venue: arXiv cs.SI 2021
Year: 2021

In real-time, social media data strongly imprints world events, popular culture, and day-to-day conversations by millions of ordinary people at a scale that is scarcely conventionalized and recorded. Vitally, and absent from many standard corpora such as books and news archives, sharing and commenting mechanisms are native to social media platforms, enabling us to quantify social amplification (i.e., popularity) of trending storylines and contemporary cultural phenomena. Here, we describe Storywrangler, a natural language processing instrument designed to carry out an ongoing, day-scale curation of over 100 billion tweets containing roughly 1 trillion 1-grams from 2008 to 2021. For each day, we break tweets into unigrams, bigrams, and trigrams spanning over 100 languages. We track n-gram usage frequencies, and generate Zipf distributions, for words, hashtags, handles, numerals, symbols, and emojis. We make the data set available through an interactive time series viewer, and as downloadable time series and daily distributions. Although Storywrangler leverages Twitter data, our method of extracting and tracking dynamic changes of n-grams can be extended to any similar social media platform. We showcase a few examples of the many possible avenues of study we aim to enable including how social amplification can be visualized through 'contagiograms'. We also present some example case studies that bridge n-gram time series with disparate data sources to explore sociotechnical dynamics of famous individuals, box office success, and social unrest.
Optimal Communication Complexity of Authenticated Byzantine Agreement
Venue: arXiv cs.DC 2021
Year: 2021

Byzantine Agreement (BA) is one of the most fundamental problems in distributed computing, and its communication complexity is an important efficiency metric. It is well known that quadratic communication is necessary for BA in the worst case due to a lower bound by Dolev and Reischuk. This lower bound has been shown to be tight for the unauthenticated setting with $f < n/3$ by Berman et al. but a considerable gap remains for the authenticated setting with $n/3 \le f < n/2$. This paper provides two results towards closing this gap. Both protocols have a quadratic communication complexity and have different trade-offs in resilience and assumptions. The first protocol achieves the optimal resilience of $f < n/2$ but requires a trusted setup for threshold signature. The second protocol achieves near optimal resilience $f \le (1/2 - \varepsilon)n$ in the standard PKI model.
Cyclotomic Identity Testing and Applications
Venue: arXiv cs.CC 2021
Year: 2021

We consider the cyclotomic identity testing (CIT) problem: given a polynomial $f(x_1,\ldots,x_k)$, decide whether $f(ζ_n^{e_1},\ldots,ζ_n^{e_k})$ is zero, where $ζ_n = e^{2πi/n}$ is a primitive complex $n$-th root of unity and $e_1,\ldots,e_k$ are integers, represented in binary. When $f$ is given by an algebraic circuit, we give a randomized polynomial-time algorithm for CIT assuming the generalised Riemann hypothesis (GRH), and show that the problem is in coNP unconditionally. When $f$ is given by a circuit of polynomially bounded degree, we give a randomized NC algorithm. In case $f$ is a linear form we show that the problem lies in NC. Towards understanding when CIT can be solved in deterministic polynomial-time, we consider so-called diagonal depth-3 circuits, i.e., polynomials $f=\sum_{i=1}^m g_i^{d_i}$, where $g_i$ is a linear form and $d_i$ a positive integer given in unary. We observe that a polynomial-time algorithm for CIT on this class would yield a sub-exponential-time algorithm for polynomial identity testing. However, assuming GRH, we show that if the linear forms~$g_i$ are all identical then CIT can be solved in polynomial time. Finally, we use our results to give a new proof that equality of compressed strings, i.e., strings presented using context-free grammars, can be decided in randomized NC.
Learning "What-if" Explanations for Sequential Decision-Making
Venue: arXiv cs.LG 2021
Year: 2021

Building interpretable parameterizations of real-world decision-making on the basis of demonstrated behavior -- i.e. trajectories of observations and actions made by an expert maximizing some unknown reward function -- is essential for introspecting and auditing policies in different institutions. In this paper, we propose learning explanations of expert decisions by modeling their reward function in terms of preferences with respect to "what if" outcomes: Given the current history of observations, what would happen if we took a particular action? To learn these cost-benefit tradeoffs associated with the expert's actions, we integrate counterfactual reasoning into batch inverse reinforcement learning. This offers a principled way of defining reward functions and explaining expert behavior, and also satisfies the constraints of real-world decision-making -- where active experimentation is often impossible (e.g. in healthcare). Additionally, by estimating the effects of different actions, counterfactuals readily tackle the off-policy nature of policy evaluation in the batch setting, and can naturally accommodate settings where the expert policies depend on histories of observations rather than just current states. Through illustrative experiments in both real and simulated medical environments, we highlight the effectiveness of our batch, counterfactual inverse reinforcement learning approach in recovering accurate and interpretable descriptions of behavior.
The Complexity of the Distributed Constraint Satisfaction Problem
Venue: arXiv cs.DS 2021
Year: 2021

We study the complexity of the Distributed Constraint Satisfaction Problem (DCSP) on a synchronous, anonymous network from a theoretical standpoint. In this setting, variables and constraints are controlled by agents which communicate with each other by sending messages through fixed communication channels. Our results endorse the well-known fact from classical CSPs that the complexity of fixed-template computational problems depends on the template's invariance under certain operations. Specifically, we show that DCSP($Γ$) is polynomial-time tractable if and only if $Γ$ is invariant under symmetric polymorphisms of all arities. Otherwise, there are no algorithms that solve DCSP($Γ$) in finite time. We also show that the same condition holds for the search variant of DCSP. Collaterally, our results unveil a feature of the processes' neighbourhood in a distributed network, its iterated degree, which plays a major role in the analysis. We explore this notion establishing a tight connection with the basic linear programming relaxation of a CSP.
Calibration of Google Trends Time Series
Venue: arXiv cs.SI 2021
Year: 2021

Google Trends is a tool that allows researchers to analyze the popularity of Google search queries across time and space. In a single request, users can obtain time series for up to 5 queries on a common scale, normalized to the range from 0 to 100 and rounded to integer precision. Despite the overall value of Google Trends, rounding causes major problems, to the extent that entirely uninformative, all-zero time series may be returned for unpopular queries when requested together with more popular queries. We address this issue by proposing Google Trends Anchor Bank (G-TAB), an efficient solution for the calibration of Google Trends data. Our method expresses the popularity of an arbitrary number of queries on a common scale without being compromised by rounding errors. The method proceeds in two phases. In the offline preprocessing phase, an "anchor bank" is constructed, a set of queries spanning the full spectrum of popularity, all calibrated against a common reference query by carefully chaining together multiple Google Trends requests. In the online deployment phase, any given search query is calibrated by performing an efficient binary search in the anchor bank. Each search step requires one Google Trends request, but few steps suffice, as we demonstrate in an empirical evaluation. We make our code publicly available as an easy-to-use library at https://github.com/epfl-dlab/GoogleTrendsAnchorBank.