OpenRaiser/Intern-Atlas huggingface dataset:
Uplink-Downlink Tradeoff in Secure Distributed Matrix Multiplication
Venue: arXiv cs.IT 2020
Year: 2020

In secure distributed matrix multiplication (SDMM) the multiplication $\mathbf{A}\mathbf{B}$ from two private matrices $\mathbf{A}$ and $\mathbf{B}$ is outsourced by a user to $N$ distributed servers. In $\ell$-SDMM, the goal is to a design a joint communication-computation procedure that optimally balances conflicting communication and computation metrics without leaking any information on both $\mathbf{A}$ and $\mathbf{B}$ to any set of $\ell\leq N$ servers. To this end, the user applies coding with $\tilde{\mathbf{A}}_i$ and $\tilde{\mathbf{B}}_i$ representing encoded versions of $\mathbf{A}$ and $\mathbf{B}$ destined to the $i$-th server. Now, SDMM involves multiple tradeoffs. One such tradeoff is the tradeoff between uplink (UL) and downlink (DL) costs. To find a good balance between these two metrics, we propose two schemes which we term USCSA and GSCSA that are based on secure cross subspace alignment (SCSA). We show that there are various scenarios where they outperform existing SDMM schemes from the literature with respect to the UL-DL efficiency. Next, we implement schemes from the literature, including USCSA and GSCSA, and test their performance on Amazon EC2. Our numerical results show that USCSA and GSCSA establish a good balance between the time spend on the communication and computation in SDMMs. This is because they combine advantages of polynomial codes, namely low time for the upload of $\left(\tilde{\mathbf{A}}_i,\tilde{\mathbf{B}}_i\right)_{i=1}^{N}$ and the computation of $\mathbf{O}_i=\tilde{\mathbf{A}}_i\tilde{\mathbf{B}}_i$, with those of SCSA, being a low timing overhead for the download of $\left(\mathbf{O}_i\right)_{i=1}^{N}$ and the decoding of $\mathbf{A}\mathbf{B}$.
W-Net BF: DNN-based Beamformer Using Joint Training Approach
Venue: arXiv cs.SD 2020
Year: 2020

Acoustic beamformers have been widely used to enhance audio signals. The best current methods are DNN-powered variants of the generalized eigenvalue beamformer, and DNN-based filterestimation methods that directly compute beamforming filters. Both approaches, while effective, have blindspots in their generalizability. We propose a novel approach that combines both approaches into a single framework that attempts to exploit the best features of both. The resulting model, called a W-Net beamformer, includes two components: the first computes a noise-masked reference which the second uses to estimate beamforming filters. Results on data that include a wide variety of room and noise conditions, including static and mobile noise sources, show that the proposed beamformer outperforms other methods in all tested evaluation metrics.
Channel Capacity Optimization Using Reconfigurable Intelligent Surfaces in Indoor mmWave Environments
Venue: arXiv cs.IT 2020
Year: 2020

Indoor millimeter-wave (mmWave) environment channels are typically sparsely-scattered and dominated by a strong line-of-sight (LOS) path. Therefore, communication over such channels is in general extremely difficult when the LOS path is not present. However, the recent introduction of reconfigurable intelligent surfaces (RISs), which have the potential to influence the propagation environment in a controlled manner, has the potential to change the previous paradigm. Motivated by this, we study the channel capacity optimization utilizing RISs in indoor mmWave environments where no LOS path is present. More precisely, we propose two optimization schemes that exploit the customizing capabilities of the RIS reflection elements in order to maximize the channel capacity. The first optimization scheme exploits only the adjustability of the RIS reflection elements; for this scheme we derive an approximate expression which explains the connection between the channel capacity gains and the system parameters. The second optimization scheme jointly optimizes the RIS reflection elements and the transmit phase precoder; for this scheme, we propose a low-complexity technique called global co-phasing to determine the phase shift values for use at the RIS. Simulation results show that the optimization of the RIS reflection elements produces a significant channel capacity gain, and that this gain increases with the number of RIS elements.
Pomsets with Boxes: Protection, Separation, and Locality in Concurrent Kleene Algebra
Venue: arXiv cs.LO 2020
Year: 2020

Concurrent Kleene Algebra is an elegant tool for equational reasoning about concurrent programs. An important feature of concurrent programs that is missing from CKA is the ability to restrict legal interleavings. To remedy this we extend the standard model of CKA, namely pomsets, with a new feature, called boxes, which can specify that part of the system is protected from outside interference. We study the algebraic properties of this new model. Another drawback of CKA is that the language used for expressing properties of programs is the same as that which is used to express programs themselves. This is often too restrictive for practical purposes. We provide a logic, 'pomset logic', that is an assertion language for specifying such properties, and which is interpreted on pomsets with boxes. In contrast with other approaches, this logic is not state-based, but rather characterizes the runtime behaviour of a program. We develop the basic metatheory for the relationship between pomset logic and CKA, including frame rules to support local reasoning, and illustrate this relationship with simple examples.
Quantifying (Hyper) Parameter Leakage in Machine Learning
Venue: arXiv cs.CR 2020
Year: 2020

Machine Learning models, extensively used for various multimedia applications, are offered to users as a blackbox service on the Cloud on a pay-per-query basis. Such blackbox models are commercially valuable to adversaries, making them vulnerable to extraction attacks to reverse engineer the proprietary model thereby violating the model privacy and Intellectual Property. Here, the adversary first extracts the model architecture or hyperparameters through side channel leakage, followed by stealing the functionality of the target model by training the reconstructed architecture on a synthetic dataset. While the attacks proposed in literature are empirical, there is a need for a theoretical framework to measure the information leaked under such extraction attacks. To this extent, in this work, we propose a novel probabilistic framework, Airavata, to estimate the information leakage in such model extraction attacks. This framework captures the fact that extracting the exact target model is difficult due to experimental uncertainty while inferring model hyperparameters and stochastic nature of training to steal the target model functionality. Specifically, we use Bayesian Networks to capture uncertainty in estimating the target model under various extraction attacks based on the subjective notion of probability. We validate the proposed framework under different adversary assumptions commonly adopted in literature to reason about the attack efficacy. This provides a practical tool to infer actionable details about extracting blackbox models and help identify the best attack combination which maximises the knowledge extracted (or information leaked) from the target model.
An Abstraction-Based Framework for Neural Network Verification
Venue: arXiv cs.FL 2020
Year: 2020

Deep neural networks are increasingly being used as controllers for safety-critical systems. Because neural networks are opaque, certifying their correctness is a significant challenge. To address this issue, several neural network verification approaches have recently been proposed. However, these approaches afford limited scalability, and applying them to large networks can be challenging. In this paper, we propose a framework that can enhance neural network verification techniques by using over-approximation to reduce the size of the network - thus making it more amenable to verification. We perform the approximation such that if the property holds for the smaller (abstract) network, it holds for the original as well. The over-approximation may be too coarse, in which case the underlying verification tool might return a spurious counterexample. Under such conditions, we perform counterexample-guided refinement to adjust the approximation, and then repeat the process. Our approach is orthogonal to, and can be integrated with, many existing verification techniques. For evaluation purposes, we integrate it with the recently proposed Marabou framework, and observe a significant improvement in Marabou's performance. Our experiments demonstrate the great potential of our approach for verifying larger neural networks.
A poset metric from the directed maximum common edge subgraph
Venue: arXiv cs.DS 2020
Year: 2020

We study the directed maximum common edge subgraph problem (DMCES) for the class of directed graphs that are finite, weakly connected, oriented, and simple. We use DMCES to define a metric on partially ordered sets that can be represented as weakly connected directed acyclic graphs. While most existing metrics assume that the underlying sets of the partial order are identical, and only the relationships between elements can differ, the metric defined here allows the partially ordered sets to be different. The proof that there is a metric based on DMCES involves the extension of the concept of line digraphs. Although this extension can be used to compute the metric by a reduction to the maximum clique problem, it is computationally feasible only for sparse graphs. We provide an alternative techniques for computing the metric for directed graphs that have the additional property of being transitively closed.
TAB-VCR: Tags and Attributes based Visual Commonsense Reasoning Baselines
Venue: arXiv cs.CV 2020
Year: 2020

Reasoning is an important ability that we learn from a very early age. Yet, reasoning is extremely hard for algorithms. Despite impressive recent progress that has been reported on tasks that necessitate reasoning, such as visual question answering and visual dialog, models often exploit biases in datasets. To develop models with better reasoning abilities, recently, the new visual commonsense reasoning (VCR) task has been introduced. Not only do models have to answer questions, but also do they have to provide a reason for the given answer. The proposed baseline achieved compelling results, leveraging a meticulously designed model composed of LSTM modules and attention nets. Here we show that a much simpler model obtained by ablating and pruning the existing intricate baseline can perform better with half the number of trainable parameters. By associating visual features with attribute information and better text to image grounding, we obtain further improvements for our simpler & effective baseline, TAB-VCR. We show that this approach results in a 5.3%, 4.4% and 6.5% absolute improvement over the previous state-of-the-art on question answering, answer justification and holistic VCR.
Edge minimization in de Bruijn graphs
Venue: arXiv cs.DS 2020
Year: 2020

This paper introduces the de Bruijn graph edge minimization problem, which is related to the compression of de Bruijn graphs: find the order-k de Bruijn graph with minimum edge count among all orders. We describe an efficient algorithm that solves this problem. Since the edge minimization problem is connected to the BWT compression technique called "tunneling", the paper also describes a way to minimize the length of a tunneled BWT in such a way that useful properties for sequence analysis are preserved. Although being a restriction, this is significant progress towards a solution to the open problem of finding optimal disjoint blocks that minimize space, as stated in Alanko et al. (DCC 2019).
A Game-Theoretic Approach to Covert Communications
Venue: arXiv cs.IT 2020
Year: 2020

This paper considers a game-theoretic formulation of the covert communications problem with finite blocklength, where the transmitter (Alice) can randomly vary her transmit power in different blocks, while the warden (Willie) can randomly vary his detection threshold in different blocks. In this two player game, the payoff for Alice is a combination of the coding rate to the receiver (Bob) and the detection error probability at Willie, while the payoff for Willie is the negative of his detection error probability. Nash equilibrium solutions to the game are obtained, and shown to be efficiently computable using linear programming. For less covert requirements, our game-theoretic approach can achieve significantly higher coding rates than uniformly distributed transmit powers. We then consider the situation with an additional jammer, where Alice and the jammer can both vary their powers. We pose a two player game where Alice and the jammer jointly comprise one player, with Willie the other player. The use of a jammer is shown in numerical simulations to lead to further significant performance improvements.
Towards Robust Deep Neural Networks for Affect and Depression Recognition from Speech
Venue: arXiv cs.HC 2020
Year: 2020

Intelligent monitoring systems and affective computing applications have emerged in recent years to enhance healthcare. Examples of these applications include assessment of affective states such as Major Depressive Disorder (MDD). MDD describes the constant expression of certain emotions: negative emotions (low Valence) and lack of interest (low Arousal). High-performing intelligent systems would enhance MDD diagnosis in its early stages. In this paper, we present a new deep neural network architecture, called EmoAudioNet, for emotion and depression recognition from speech. Deep EmoAudioNet learns from the time-frequency representation of the audio signal and the visual representation of its spectrum of frequencies. Our model shows very promising results in predicting affect and depression. It works similarly or outperforms the state-of-the-art methods according to several evaluation metrics on RECOLA and on DAIC-WOZ datasets in predicting arousal, valence, and depression. Code of EmoAudioNet is publicly available on GitHub: https://github.com/AliceOTHMANI/EmoAudioNet
DialoGPT: Large-Scale Generative Pre-training for Conversational Response Generation
Venue: arXiv cs.CL 2020
Year: 2020

We present a large, tunable neural conversational response generation model, DialoGPT (dialogue generative pre-trained transformer). Trained on 147M conversation-like exchanges extracted from Reddit comment chains over a period spanning from 2005 through 2017, DialoGPT extends the Hugging Face PyTorch transformer to attain a performance close to human both in terms of automatic and human evaluation in single-turn dialogue settings. We show that conversational systems that leverage DialoGPT generate more relevant, contentful and context-consistent responses than strong baseline systems. The pre-trained model and training pipeline are publicly released to facilitate research into neural response generation and the development of more intelligent open-domain dialogue systems.
Twin-Finder: Integrated Reasoning Engine for Pointer-related Code Clone Detection
Venue: arXiv cs.SE 2020
Year: 2020

Detecting code clones is crucial in various software engineering tasks. In particular, code clone detection can have significant uses in the context of analyzing and fixing bugs in large scale applications. However, prior works, such as machine learning-based clone detection, may cause a considerable amount of false positives. In this paper, we propose Twin-Finder, a novel, closed-loop approach for pointer-related code clone detection that integrates machine learning and symbolic execution techniques to achieve precision. Twin-Finder introduces a clone verification mechanism to formally verify if two clone samples are indeed clones and a feedback loop to automatically generated formal rules to tune machine learning algorithm and further reduce the false positives. Our experimental results show that Twin-Finder can swiftly identify up 9X more code clones comparing to a tree-based clone detector, Deckard and remove an average 91.69% false positives.
Assessing the Privacy Benefits of Domain Name Encryption
Venue: arXiv cs.CR 2020
Year: 2020

As Internet users have become more savvy about the potential for their Internet communication to be observed, the use of network traffic encryption technologies (e.g., HTTPS/TLS) is on the rise. However, even when encryption is enabled, users leak information about the domains they visit via DNS queries and via the Server Name Indication (SNI) extension of TLS. Two recent proposals to ameliorate this issue are DNS over HTTPS/TLS (DoH/DoT) and Encrypted SNI (ESNI). In this paper we aim to assess the privacy benefits of these proposals by considering the relationship between hostnames and IP addresses, the latter of which are still exposed. We perform DNS queries from nine vantage points around the globe to characterize this relationship. We quantify the privacy gain offered by ESNI for different hosting and CDN providers using two different metrics, the k-anonymity degree due to co-hosting and the dynamics of IP address changes. We find that 20% of the domains studied will not gain any privacy benefit since they have a one-to-one mapping between their hostname and IP address. On the other hand, 30% will gain a significant privacy benefit with a k value greater than 100, since these domains are co-hosted with more than 100 other domains. Domains whose visitors' privacy will meaningfully improve are far less popular, while for popular domains the benefit is not significant. Analyzing the dynamics of IP addresses of long-lived domains, we find that only 7.7% of them change their hosting IP addresses on a daily basis. We conclude by discussing potential approaches for website owners and hosting/CDN providers for maximizing the privacy benefits of ESNI.
A Solution of the P versus NP Problem based on specific property of clique function
Venue: arXiv cs.CC 2020
Year: 2020

Circuit lower bounds are important since it is believed that a super-polynomial circuit lower bound for a problem in NP implies that P!=NP. Razborov has proved superpolynomial lower bounds for monotone circuits by using method of approximation. By extending this approach, researchers have proved exponential lower bounds for the monotone network complexity of several different functions. But until now, no one could prove a non-linear lower bound for the non-monotone complexity of any Boolean function in NP. While we show that in this paper by replacement of each Not gates into constant 1 equivalently in standard circuit for clique problem, it can be proved that non-monotone network has the same or higher lower bound compared to the monotone one for computing the clique function. This indicates that the non-monotone network complexity of the clique function is super-polynomial which implies that P!=NP.
An Algorithm for Routing Capsules in All Domains
Venue: arXiv cs.LG 2020
Year: 2020

Building on recent work on capsule networks, we propose a new, general-purpose form of "routing by agreement" that activates output capsules in a layer as a function of their net benefit to use and net cost to ignore input capsules from earlier layers. To illustrate the usefulness of our routing algorithm, we present two capsule networks that apply it in different domains: vision and language. The first network achieves new state-of-the-art accuracy of 99.1% on the smallNORB visual recognition task with fewer parameters and an order of magnitude less training than previous capsule models, and we find evidence that it learns to perform a form of "reverse graphics." The second network achieves new state-of-the-art accuracies on the root sentences of the Stanford Sentiment Treebank: 58.5% on fine-grained and 95.6% on binary labels with a single-task model that routes frozen embeddings from a pretrained transformer as capsules. In both domains, we train with the same regime. Code is available at https://github.com/glassroom/heinsen_routing along with replication instructions.
MadNet: Using a MAD Optimization for Defending Against Adversarial Attacks
Venue: arXiv cs.LG 2020
Year: 2020

This paper is concerned with the defense of deep models against adversarial attacks. Inspired by the certificate defense approach, we propose a maximal adversarial distortion (MAD) optimization method for robustifying deep networks. MAD captures the idea of increasing separability of class clusters in the embedding space while decreasing the network sensitivity to small distortions. Given a deep neural network (DNN) for a classification problem, an application of MAD optimization results in MadNet, a version of the original network, now equipped with an adversarial defense mechanism. MAD optimization is intuitive, effective and scalable, and the resulting MadNet can improve the original accuracy. We present an extensive empirical study demonstrating that MadNet improves adversarial robustness performance compared to state-of-the-art methods.
Interpreting Verbal Irony: Linguistic Strategies and the Connection to the Type of Semantic Incongruity
Venue: arXiv cs.CL 2020
Year: 2020

Human communication often involves the use of verbal irony or sarcasm, where the speakers usually mean the opposite of what they say. To better understand how verbal irony is expressed by the speaker and interpreted by the hearer we conduct a crowdsourcing task: given an utterance expressing verbal irony, users are asked to verbalize their interpretation of the speaker's ironic message. We propose a typology of linguistic strategies for verbal irony interpretation and link it to various theoretical linguistic frameworks. We design computational models to capture these strategies and present empirical studies aimed to answer three questions: (1) what is the distribution of linguistic strategies used by hearers to interpret ironic messages?; (2) do hearers adopt similar strategies for interpreting the speaker's ironic intent?; and (3) does the type of semantic incongruity in the ironic message (explicit vs. implicit) influence the choice of interpretation strategies by the hearers?
Fresher Content or Smoother Playback? A Brownian-Approximation Framework for Scheduling Real-Time Wireless Video Streams
Venue: arXiv cs.NI 2020
Year: 2020

This paper presents a Brownian-approximation framework to optimize the quality of experience (QoE) for real-time video streaming in wireless networks. In real-time video streaming, one major challenge is to tackle the natural tension between the two most critical QoE metrics: playback latency and video interruption. To study this trade-off, we first propose an analytical model that precisely captures all aspects of the playback process of a real-time video stream, including playback latency, video interruptions, and packet dropping. Built on this model, we show that the playback process of a real-time video can be approximated by a two-sided reflected Brownian motion. Through such Brownian approximation, we are able to study the fundamental limits of the two QoE metrics and characterize a necessary and sufficient condition for a set of QoE performance requirements to be feasible. We propose a scheduling policy that satisfies any feasible set of QoE performance requirements and then obtain simple rules on the trade-off between playback latency and the video interrupt rates, in both heavy-traffic and under-loaded regimes. Finally, simulation results verify the accuracy of the proposed approximation and show that the proposed policy outperforms other popular baseline policies.