OpenRaiser/Intern-Atlas huggingface dataset:
Domain-topic models with chained dimensions: charting an emergent domain of a major oncology conference
Venue: arXiv cs.DL 2021
Year: 2021

This paper presents a contribution to the study of bibliographic corpora in the context of science mapping. Starting from a graph representation of documents and their textual dimension, we observe that stochastic block models (SBMs) can provide a simultaneous clustering of documents and words that we call a domain-topic model. Previous work by (Gerlach et al., 2018) investigated the resulting topics, or word clusters, while ours focuses on the study of the document clusters, which we call domains. To enable the synthetic description and interactive navigation of domains, we introduce measures and interfaces relating both types of clusters, which reflect the structure of the graph and the model. We then present a procedure that, starting from the document clusters, extends the block model to also cluster arbitrary metadata attributes of the documents. We call this procedure a domain-chained model, and our previous measures and interfaces can be directly transposed to read the metadata clusters. We provide an example application to a corpus that is relevant to current STS research, and an interesting case for our approach: the 1995-2017 collection of abstracts presented at ASCO, the main annual oncology research conference. Through a sequence of domain-topic and domain-chained models, we identify and describe a particular group of domains in ASCO that have notably grown through the last decades, and which we relate to the establishment of "oncopolicy" as a major concern in oncology.
Using Nesting to Push the Limits of Transactional Data Structure Libraries
Venue: arXiv cs.DC 2021
Year: 2021

Transactional data structure libraries (TDSL) combine the ease-of-programming of transactions with the high performance and scalability of custom-tailored concurrent data structures. They can be very efficient thanks to their ability to exploit data structure semantics in order to reduce overhead, aborts, and wasted work compared to general-purpose software transactional memory. However, TDSLs were not previously used for complex use-cases involving long transactions and a variety of data structures. In this paper, we boost the performance and usability of a TDSL, towards allowing it to support complex applications. A key idea is nesting. Nested transactions create checkpoints within a longer transaction, so as to limit the scope of abort, without changing the semantics of the original transaction. We build a Java TDSL with built-in support for nested transactions over a number of data structures. We conduct a case study of a complex network intrusion detection system that invests a significant amount of work to process each packet. Our study shows that our library outperforms publicly available STMs twofold without nesting, and by up to 16x when nesting is used.
Reparo: Publicly Verifiable Layer to Repair Blockchains
Venue: arXiv cs.CR 2021
Year: 2021

Although blockchains aim for immutability as their core feature, several instances have exposed the harms with perfect immutability. The permanence of illicit content inserted in Bitcoin poses a challenge to law enforcement agencies like Interpol, and millions of dollars are lost in buggy smart contracts in Ethereum. A line of research then spawned on Redactable blockchains with the aim of solving the problem of redacting illicit contents from both permissioned and permissionless blockchains. However, all the existing proposals follow the build-new-chain approach for redactions, and cannot be integrated with existing systems like Bitcoin and Ethereum. We present Reparo, a generic protocol that acts as a publicly verifiable layer on top of any blockchain to perform repairs, ranging from fixing buggy contracts to removing illicit contents from the chain. Reparo facilitates additional functionalities for blockchains while maintaining the same provable security guarantee; thus, Reparo can be integrated with existing blockchains and start performing repairs on the pre-existent data. Any system user may propose a repair and a deliberation process ensues resulting in a decision that complies with the repair policy of the chain and is publicly verifiable. Our Reparo layer can be easily tailored to different consensus requirements, does not require heavy cryptographic machinery and can, therefore, be efficiently instantiated in any permission-ed or -less setting. We demonstrate it by giving efficient instantiations of Reparo on top of Ethereum (with PoS and PoW), Bitcoin, and Cardano. Moreover, we evaluate Reparo with Ethereum mainnet and show that the cost of fixing several prominent smart contract bugs is almost negligible. For instance, the cost of repairing the prominent Parity Multisig wallet bug with Reparo is as low as 0.000000018% of the Ethers that can be retrieved after the fix.
PrivacyNet: Semi-Adversarial Networks for Multi-attribute Face Privacy
Venue: arXiv cs.CV 2021
Year: 2021

Recent research has established the possibility of deducing soft-biometric attributes such as age, gender and race from an individual's face image with high accuracy. However, this raises privacy concerns, especially when face images collected for biometric recognition purposes are used for attribute analysis without the person's consent. To address this problem, we develop a technique for imparting soft biometric privacy to face images via an image perturbation methodology. The image perturbation is undertaken using a GAN-based Semi-Adversarial Network (SAN) - referred to as PrivacyNet - that modifies an input face image such that it can be used by a face matcher for matching purposes but cannot be reliably used by an attribute classifier. Further, PrivacyNet allows a person to choose specific attributes that have to be obfuscated in the input face images (e.g., age and race), while allowing for other types of attributes to be extracted (e.g., gender). Extensive experiments using multiple face matchers, multiple age/gender/race classifiers, and multiple face datasets demonstrate the generalizability of the proposed multi-attribute privacy enhancing method across multiple face and attribute classifiers.
Upper bounds for stabbing simplices by a line
Venue: arXiv cs.CG 2021
Year: 2021

It is known that for every dimension $d\ge 2$ and every $k<d$ there exists a constant $c_{d,k}>0$ such that for every $n$-point set $X\subset \mathbb R^d$ there exists a $k$-flat that intersects at least $c_{d,k} n^{d+1-k} - o(n^{d+1-k})$ of the $(d-k)$-dimensional simplices spanned by $X$. However, the optimal values of the constants $c_{d,k}$ are mostly unknown. The case $k=0$ (stabbing by a point) has received a great deal of attention. In this paper we focus on the case $k=1$ (stabbing by a line). Specifically, we try to determine the upper bounds yielded by two point sets, known as the "stretched grid" and the "stretched diagonal". Even though the calculations are independent of $n$, they are still very complicated, so we resort to analytical and numerical software methods. We provide strong evidence that, surprisingly, for $d=4,5,6$ the stretched grid yields better bounds than the stretched diagonal (unlike for all cases $k=0$ and for the case $(d,k)=(3,1)$, in which both point sets yield the same bound). Our experiments indicate that the stretched grid yields $c_{4,1}\leq 0.00457936$, $c_{5,1}\leq 0.000405335$, and $c_{6,1}\leq 0.0000291323$.
Communication over Quantum Channels with Parameter Estimation
Venue: arXiv cs.IT 2021
Year: 2021

Communication over a random-parameter quantum channel when the decoder is required to reconstruct the parameter sequence is considered. We study scenarios that include either strictly-causal, causal, or non-causal channel side information (CSI) available at the encoder, and also when CSI is not available. This model can be viewed as a form of quantum metrology, and as the quantum counterpart of the classical rate-and-state channel with state estimation at the decoder. Regularized formulas for the capacity-distortion regions are derived. In the special case of measurement channels, single-letter characterizations are derived for the strictly causal and causal settings. Furthermore, in the more general case of entanglement-breaking channels, a single-letter characterization is derived when CSI is not available. As a consequence, we obtain regularized formulas for the capacity of random-parameter quantum channels with CSI, generalizing previous results by Boche et al. (2016) on classical-quantum channels.
Codes over Trees
Venue: arXiv cs.IT 2021
Year: 2021

In graph theory, a tree is one of the more popular families of graphs with a wide range of applications in computer science as well as many other related fields. While there are several distance measures over the set of all trees, we consider here the one which defines the so-called tree distance, defined by the minimum number of edit operations, of removing and adding edges, in order to change one tree into another. From a coding theoretic perspective, codes over the tree distance are used for the correction of edge erasures and errors. However, studying this distance measure is important for many other applications that use trees and properties on their locality and the number of neighbor trees. Under this paradigm, the largest size of code over trees with a prescribed minimum tree distance is investigated. Upper bounds on these codes as well as code constructions are presented. A significant part of our study is dedicated to the problem of calculating the size of the ball of trees of a given radius. These balls are not regular and thus we show that while the star tree has asymptotically the smallest size of the ball, the maximum is achieved for the path tree.
Fair Active Learning
Venue: arXiv cs.LG 2021
Year: 2021

Machine learning (ML) is increasingly being used in high-stakes applications impacting society. Therefore, it is of critical importance that ML models do not propagate discrimination. Collecting accurate labeled data in societal applications is challenging and costly. Active learning is a promising approach to build an accurate classifier by interactively querying an oracle within a labeling budget. We design algorithms for fair active learning that carefully selects data points to be labeled so as to balance model accuracy and fairness. We demonstrate the effectiveness and efficiency of our proposed algorithms over widely used benchmark datasets using demographic parity and equalized odds notions of fairness.
VulDeeLocator: A Deep Learning-based Fine-grained Vulnerability Detector
Venue: arXiv cs.CR 2021
Year: 2021

Automatically detecting software vulnerabilities is an important problem that has attracted much attention from the academic research community. However, existing vulnerability detectors still cannot achieve the vulnerability detection capability and the locating precision that would warrant their adoption for real-world use. In this paper, we present a vulnerability detector that can simultaneously achieve a high detection capability and a high locating precision, dubbed Vulnerability Deep learning-based Locator (VulDeeLocator). In the course of designing VulDeeLocator, we encounter difficulties including how to accommodate semantic relations between the definitions of types as well as macros and their uses across files, how to accommodate accurate control flows and variable define-use relations, and how to achieve high locating precision. We solve these difficulties by using two innovative ideas: (i) leveraging intermediate code to accommodate extra semantic information, and (ii) using the notion of granularity refinement to pin down locations of vulnerabilities. When applied to 200 files randomly selected from three real-world software products, VulDeeLocator detects 18 confirmed vulnerabilities (i.e., true-positives). Among them, 16 vulnerabilities correspond to known vulnerabilities; the other two are not reported in the National Vulnerability Database (NVD) but have been "silently" patched by the vendor of Libav when releasing newer versions.
Questioning the AI: Informing Design Practices for Explainable AI User Experiences
Venue: arXiv cs.HC 2021
Year: 2021

A surge of interest in explainable AI (XAI) has led to a vast collection of algorithmic work on the topic. While many recognize the necessity to incorporate explainability features in AI systems, how to address real-world user needs for understanding AI remains an open question. By interviewing 20 UX and design practitioners working on various AI products, we seek to identify gaps between the current XAI algorithmic work and practices to create explainable AI products. To do so, we develop an algorithm-informed XAI question bank in which user needs for explainability are represented as prototypical questions users might ask about the AI, and use it as a study probe. Our work contributes insights into the design space of XAI, informs efforts to support design practices in this space, and identifies opportunities for future XAI work. We also provide an extended XAI question bank and discuss how it can be used for creating user-centered XAI.
smartSDH: An Experimental Study of Mechanism Based Building Control
Venue: arXiv cs.HC 2021
Year: 2021

As Internet of Things (IoT) technologies are increasingly being deployed, situations frequently arise where multiple stakeholders must reconcile preferences to control a shared resource. We perform a 5-month long experiment dubbed 'smartSDH' (carried out in 27 employees' office space) where users report their preferences for the brightness of overhead lighting. smartSDH implements a modified Vickrey-Clarke-Groves (VCG) mechanism; assuming users are rational, it incentivizes truthful reporting, implements the socially desirable outcome, and compensates participants to ensure higher payoffs under smartSDH when compared with the default outside option(i.e., the option chosen in the absence of such a mechanism). smartSDH assesses the feasibility of the VCG mechanism in the context of smart building control and evaluated smartSDH's effect using metrics such as light level satisfaction, incentive satisfaction, and energy consumption. Although previous studies on the theoretical aspects of the mechanism indicate user satisfaction, our experiments indicate quite the contrary. We found that the participants were significantly less satisfied with light brightness and incentives determined by the VCG mechanism over time. These data suggest the need for more realistic behavioral models to design IoT technologies and highlights difficulties in estimating preferences from observable external factors such as atmospheric conditions.
Deep Network Approximation for Smooth Functions
Venue: arXiv cs.LG 2021
Year: 2021

This paper establishes the (nearly) optimal approximation error characterization of deep rectified linear unit (ReLU) networks for smooth functions in terms of both width and depth simultaneously. To that end, we first prove that multivariate polynomials can be approximated by deep ReLU networks of width $\mathcal{O}(N)$ and depth $\mathcal{O}(L)$ with an approximation error $\mathcal{O}(N^{-L})$. Through local Taylor expansions and their deep ReLU network approximations, we show that deep ReLU networks of width $\mathcal{O}(N\ln N)$ and depth $\mathcal{O}(L\ln L)$ can approximate $f\in C^s([0,1]^d)$ with a nearly optimal approximation error $\mathcal{O}(\|f\|_{C^s([0,1]^d)}N^{-2s/d}L^{-2s/d})$. Our estimate is non-asymptotic in the sense that it is valid for arbitrary width and depth specified by $N\in\mathbb{N}^+$ and $L\in\mathbb{N}^+$, respectively.
Gaussian Approximation of Quantization Error for Estimation from Compressed Data
Venue: arXiv cs.IT 2021
Year: 2021

We consider the distributional connection between the lossy compressed representation of a high-dimensional signal $X$ using a random spherical code and the observation of $X$ under an additive white Gaussian noise (AWGN). We show that the Wasserstein distance between a bitrate-$R$ compressed version of $X$ and its observation under an AWGN-channel of signal-to-noise ratio $2^{2R}-1$ is sub-linear in the problem dimension. We utilize this fact to connect the risk of an estimator based on an AWGN-corrupted version of $X$ to the risk attained by the same estimator when fed with its bitrate-$R$ quantized version. We demonstrate the usefulness of this connection by deriving various novel results for inference problems under compression constraints, including minimax estimation, sparse regression, compressed sensing, and the universality of linear estimation in remote source coding.
New variants of Perfect Non-crossing Matchings
Venue: arXiv cs.CG 2021
Year: 2021

Given a set of points in the plane, we are interested in matching them with straight line segments. We focus on perfect (all points are matched) non-crossing (no two edges intersect) matchings. Apart from the well known MinMax variation, where the length of the longest edge is minimized, we extend work by looking into different optimization variants such as MaxMin, MinMin, and MaxMax. We consider both the monochromatic and bichromatic versions of these problems and by employing diverse techniques we provide efficient algorithms for various input point configurations.
Wiretap channels with causal and non-causal state information: revisited
Venue: arXiv cs.IT 2021
Year: 2021

The coding problem for wiretap channels with causal channel state information (CSI) available at the encoder (Alice) and/or the decoder (Bob) is studied. We are concerned here particularily with the problem of achievable secret-message secret-key rate pairs under the semantic security criterion. Our main result extends all the previous results on achievable rates as given by Chia and El Gamal [10], Fujita [11], and Han and Sasaki [23]. In order to do this, we first derive a unifying theorem (Theorem 2) with causal CSI at Alice, which follows immediately by leveraging the unifying seminal theorem for wiretap channels with non-causal CSI at Alice as recently established by Bunin et al. [22]. The only thing to do here is just to re-interpret the latter non-causal one in a causal manner. A prominent feature of this approach is that we are able to dispense with the block-Markov encoding scheme as used in the previous works. Also, the exact secret-message key capacity region for wiretap channels with non-causal CSI at both Alice and Bob is given.
Commonly Knowing Whether
Venue: arXiv cs.LO 2021
Year: 2021

This paper introduces the notion of `commonly knowing whether', a non-standard version of standard common knowledge which is defined on the basis of `knowing whether', instead of standard `knowing that'. After giving five possible definitions of this notion, we explore the logical relations among them in the single-agent and multi-agent cases. We propose a sound and complete axiomatization. We investigate one of the five definitions in terms of expressivity via a strategy of modal comparison games.
Deep Image Translation with an Affinity-Based Change Prior for Unsupervised Multimodal Change Detection
Venue: arXiv cs.LG 2021
Year: 2021

Image translation with convolutional neural networks has recently been used as an approach to multimodal change detection. Existing approaches train the networks by exploiting supervised information of the change areas, which, however, is not always available. A main challenge in the unsupervised problem setting is to avoid that change pixels affect the learning of the translation function. We propose two new network architectures trained with loss functions weighted by priors that reduce the impact of change pixels on the learning objective. The change prior is derived in an unsupervised fashion from relational pixel information captured by domain-specific affinity matrices. Specifically, we use the vertex degrees associated with an absolute affinity difference matrix and demonstrate their utility in combination with cycle consistency and adversarial training. The proposed neural networks are compared with state-of-the-art algorithms. Experiments conducted on three real datasets show the effectiveness of our methodology.
FASTER: Fast and Safe Trajectory Planner for Navigation in Unknown Environments
Venue: arXiv cs.RO 2021
Year: 2021

Planning high-speed trajectories for UAVs in unknown environments requires algorithmic techniques that enable fast reaction times to guarantee safety as more information about the environment becomes available. The standard approaches that ensure safety by enforcing a "stop" condition in the free-known space can severely limit the speed of the vehicle, especially in situations where much of the world is unknown. Moreover, the ad-hoc time and interval allocation scheme usually imposed on the trajectory also leads to conservative and slower trajectories. This work proposes FASTER (Fast and Safe Trajectory Planner) to ensure safety without sacrificing speed. FASTER obtains high-speed trajectories by enabling the local planner to optimize in both the free-known and unknown spaces. Safety is ensured by always having a safe back-up trajectory in the free-known space. The MIQP formulation proposed also allows the solver to choose the trajectory interval allocation. FASTER is tested extensively in simulation and in real hardware, showing flights in unknown cluttered environments with velocities up to 7.8m/s, and experiments at the maximum speed of a skid-steer ground robot (2m/s).
Negative Statements Considered Useful
Venue: arXiv cs.IR 2021
Year: 2021

Knowledge bases (KBs) about notable entities and their properties are an important asset in applications such as search, question answering and dialogue. All popular KBs capture virtually only positive statements, and abstain from taking any stance on statements not stored in the KB. This paper makes the case for explicitly stating salient statements that do not hold. Negative statements are useful to overcome limitations of question answering systems that are mainly geared for positive questions; they can also contribute to informative summaries of entities. Due to the abundance of such invalid statements, any effort to compile them needs to address ranking by saliency. We present a statisticalinference method for compiling and ranking negative statements, based on expectations from positive statements of related entities in peer groups. Experimental results, with a variety of datasets, show that the method can effectively discover notable negative statements, and extrinsic studies underline their usefulness for entity summarization. Datasets and code are released as resources for further research.
SEERL: Sample Efficient Ensemble Reinforcement Learning
Venue: arXiv cs.LG 2021
Year: 2021

Ensemble learning is a very prevalent method employed in machine learning. The relative success of ensemble methods is attributed to their ability to tackle a wide range of instances and complex problems that require different low-level approaches. However, ensemble methods are relatively less popular in reinforcement learning owing to the high sample complexity and computational expense involved in obtaining a diverse ensemble. We present a novel training and model selection framework for model-free reinforcement algorithms that use ensembles of policies obtained from a single training run. These policies are diverse in nature and are learned through directed perturbation of the model parameters at regular intervals. We show that learning and selecting an adequately diverse set of policies is required for a good ensemble while extreme diversity can prove detrimental to overall performance. Selection of an adequately diverse set of policies is done through our novel policy selection framework. We evaluate our approach on challenging discrete and continuous control tasks and also discuss various ensembling strategies. Our framework is substantially sample efficient, computationally inexpensive and is seen to outperform state-of-the-art (SOTA) scores in Atari 2600 and Mujoco.