OpenRaiser/Intern-Atlas huggingface dataset:
Twitter and Facebook posts about COVID-19 are less likely to spread false and low-credibility content compared to other health topics
Venue: arXiv cs.SI 2021
Year: 2021

On February 2, 2020, the World Health Organization declared a COVID-19 social media "infodemic", with special attention to misinformation -- frequently understood as false claims. To understand the infodemic's scope and scale, we analyzed over 500 million posts from Twitter and Facebook about COVID-19 and other health topics, between March 8 and May 1, 2020. Following prior work, we assumed URL source credibility is a proxy for false content, but we also tested this assumption. Contrary to expectations, we found that messages about COVID-19 were more likely to contain links to more credible sources. Additionally, messages linking to government sources, and to news with intermediate credibility, were shared more often, on average, than links to non-credible sources. These results suggest that more ambiguous forms of misinformation about COVID-19 may be more likely to be disseminated through credible sources when compared to other health topics. Furthermore, the assumption that credibility is an adequate proxy for false content may overestimate the prevalence of false content online: less than 25% of posts linking to the least credible sources contained false content. Our results emphasize the importance of distinguishing between explicit falsehoods and more ambiguous forms of misinformation due to the search for meaning in an environment of scientific uncertainty.
Resource Allocation in Virtualized CoMP-NOMA HetNets: Multi-Connectivity for Joint Transmission
Venue: arXiv cs.IT 2021
Year: 2021

In this work, we design a generalized joint transmission coordinated multi-point (JT-CoMP)-non-orthogonal multiple access (NOMA) model for a virtualized multi-infrastructure network. In this model, all users benefit from multiple joint transmissions of CoMP thanks to the multi-connectivity opportunity provided by wireless network virtualization (WNV) in multi-infrastructure networks. The NOMA protocol in CoMP results in an unlimited NOMA clustering (UNC) scheme, where the order of each NOMA cluster is the maximum possible value. We show that UNC results in maximum successful interference cancellation (SIC) complexity at users. In this regard, we propose a limited NOMA clustering (LNC) scheme, where the SIC is performed to only a subset of users. We formulate the problem of joint power allocation and user association for the UNC and LNC schemes. Then, one globally and one locally optimal solution are proposed for each problem based on mixed-integer monotonic optimization and sequential programming, respectively. Numerical assessments reveal that WNV and LNC improves users sum-rate and reduces users SIC complexity by up to $35\%$ and $46\%$ compared to the non-virtualized CoMP-NOMA system and UNC model, respectively. Therefore, the proposed algorithms are suitable candidates for the implementation on open and intelligent radio access networks.
Multi-Server Weakly-Private Information Retrieval
Venue: arXiv cs.IT 2021
Year: 2021

Private information retrieval (PIR) protocols ensure that a user can download a file from a database without revealing any information on the identity of the requested file to the servers storing the database. While existing protocols strictly impose that no information is leaked on the file's identity, this work initiates the study of the tradeoffs that can be achieved by relaxing the perfect privacy requirement. We refer to such protocols as weakly-private information retrieval (WPIR) protocols. In particular, for the case of multiple noncolluding replicated servers, we study how the download rate, the upload cost, and the access complexity can be improved when relaxing the full privacy constraint. To quantify the information leakage on the requested file's identity we consider mutual information (MI), worst-case information leakage, and maximal leakage (MaxL). We present two WPIR schemes, denoted by Scheme A and Scheme B, based on two recent PIR protocols and show that the download rate of the former can be optimized by solving a convex optimization problem. We also show that Scheme A achieves an improved download rate compared to the recently proposed scheme by Samy et al. under the so-called $ε$-privacy metric. Additionally, a family of schemes based on partitioning is presented. Moreover, we provide an information-theoretic converse bound for the maximum possible download rate for the MI and MaxL privacy metrics under a practical restriction on the alphabet size of queries and answers. For two servers and two files, the bound is tight under the MaxL metric, which settles the WPIR capacity in this particular case. Finally, we compare the performance of the proposed schemes and their gap to the converse bound.
Learning High-Level Policies for Model Predictive Control
Venue: arXiv cs.RO 2021
Year: 2021

The combination of policy search and deep neural networks holds the promise of automating a variety of decision-making tasks. Model Predictive Control (MPC) provides robust solutions to robot control tasks by making use of a dynamical model of the system and solving an optimization problem online over a short planning horizon. In this work, we leverage probabilistic decision-making approaches and the generalization capability of artificial neural networks to the powerful online optimization by learning a deep high-level policy for the MPC (High-MPC). Conditioning on robot's local observations, the trained neural network policy is capable of adaptively selecting high-level decision variables for the low-level MPC controller, which then generates optimal control commands for the robot. First, we formulate the search of high-level decision variables for MPC as a policy search problem, specifically, a probabilistic inference problem. The problem can be solved in a closed-form solution. Second, we propose a self-supervised learning algorithm for learning a neural network high-level policy, which is useful for online hyperparameter adaptations in highly dynamic environments. We demonstrate the importance of incorporating the online adaption into autonomous robots by using the proposed method to solve a challenging control problem, where the task is to control a simulated quadrotor to fly through a swinging gate. We show that our approach can handle situations that are difficult for standard MPC.
Randomized Automatic Differentiation
Venue: arXiv cs.LG 2021
Year: 2021

The successes of deep learning, variational inference, and many other fields have been aided by specialized implementations of reverse-mode automatic differentiation (AD) to compute gradients of mega-dimensional objectives. The AD techniques underlying these tools were designed to compute exact gradients to numerical precision, but modern machine learning models are almost always trained with stochastic gradient descent. Why spend computation and memory on exact (minibatch) gradients only to use them for stochastic optimization? We develop a general framework and approach for randomized automatic differentiation (RAD), which can allow unbiased gradient estimates to be computed with reduced memory in return for variance. We examine limitations of the general approach, and argue that we must leverage problem specific structure to realize benefits. We develop RAD techniques for a variety of simple neural network architectures, and show that for a fixed memory budget, RAD converges in fewer iterations than using a small batch size for feedforward networks, and in a similar number for recurrent networks. We also show that RAD can be applied to scientific computing, and use it to develop a low-memory stochastic gradient method for optimizing the control parameters of a linear reaction-diffusion PDE representing a fission reactor.
ZLB: A Blockchain to Tolerate Colluding Majorities
Venue: arXiv cs.DC 2021
Year: 2021

In the general setting, consensus cannot be solved if an adversary controls a third of the system. Yet, blockchain participants typically reach consensus "eventually" despite an adversary controlling a minority of the system. Exceeding this $\frac{1}{3}$ cap is made possible by tolerating transient disagreements, where distinct participants select distinct blocks for the same index, before eventually agreeing to select the same block. Until now, no blockchain could tolerate an attacker controlling a majority of the system. In this paper, we present Zero-Loss Blockchain (ZLB), the first blockchain that tolerates an adversary controlling more than half of the system. ZLB is an open blockchain that combines recent theoretical advances in accountable Byzantine agreement to exclude undeniably deceitful replicas. progressively reduces the portion of deceitful replicas below $\frac{1}{3}$, and reaches consensus. Geo-distributed experiments show that ZLB outperforms HotStuff and is almost as fast as the scalable Red Belly Blockchain that cannot tolerate $n/3$ faults.
Breaking the $2^n$ barrier for 5-coloring and 6-coloring
Venue: arXiv cs.DS 2021
Year: 2021

The coloring problem (i.e., computing the chromatic number of a graph) can be solved in $O^*(2^n)$ time, as shown by Björklund, Husfeldt and Koivisto in 2009. For $k=3,4$, better algorithms are known for the $k$-coloring problem. $3$-coloring can be solved in $O(1.33^n)$ time (Beigel and Eppstein, 2005) and $4$-coloring can be solved in $O(1.73^n)$ time (Fomin, Gaspers and Saurabh, 2007). Surprisingly, for $k>4$ no improvements over the general $O^*(2^n)$ are known. We show that both $5$-coloring and $6$-coloring can also be solved in $O\left(\left(2-\varepsilon\right)^n\right)$ time for some $\varepsilon>0$. As a crucial step, we obtain an exponential improvement for computing the chromatic number of a very large family of graphs. In particular, for any constants $Δ,α>0$, the chromatic number of graphs with at least $α\cdot n$ vertices of degree at most $Δ$ can be computed in $O\left(\left(2-\varepsilon\right)^n\right)$ time, for some $\varepsilon = \varepsilon_{Δ,α} > 0$. This statement generalizes previous results for bounded-degree graphs (Björklund, Husfeldt, Kaski, and Koivisto, 2010) and graphs with bounded average degree (Golovnev, Kulikov and Mihajilin, 2016). We generalize the aforementioned statement to List Coloring, for which no previous improvements are known even for the case bounded-degree graphs.
Reference study of IFC software support: the GeoBIM benchmark 2019 -- Part I
Venue: arXiv cs.DB 2021
Year: 2021

IFC, buildingSMART open standard for Building Information Models, is underused with respect to its promising potential, since, according to the experience of practitioners and researchers working with BIM, issues in the standard's implementation and use prevent its effective use. Nevertheless, a systematic investigation of these issues has never been performed, and there is thus insufficient evidence for tackling the problems. The GeoBIM benchmark project is aimed at finding such evidence by involving external volunteers, reporting on tools behaviour about relevant aspects (geometry, semantics, georeferencing, functionalities), analysed and described in this paper. Interestingly, few patterns are detectable about the behaviour of different software with standardised data, and significant issues are found in their support of the standards, probably due to the very high complexity of the standard data model. This paper is in tandem with Part II, describing the results of the benchmark related to CityGML, counterpart of IFC within geoinformation.
PISTIS: An Event-Triggered Real-Time Byzantine-Resilient Protocol Suite
Venue: arXiv cs.DC 2021
Year: 2021

The accelerated digitalisation of society along with technological evolution have extended the geographical span of cyber-physical systems. Two main threats have made the reliable and real-time control of these systems challenging: (i) uncertainty in the communication infrastructure induced by scale, and heterogeneity of the environment and devices; and (ii) targeted attacks maliciously worsening the impact of the above-mentioned communication uncertainties, disrupting the correctness of real-time applications. This paper addresses those challenges by showing how to build distributed protocols that provide both real-time with practical performance, and scalability in the presence of network faults and attacks, in probabilistic synchronous environments. We provide a suite of real-time Byzantine protocols, which we prove correct, starting from a reliable broadcast protocol, called PISTIS, up to atomic broadcast and consensus. This suite simplifies the construction of powerful distributed and decentralized monitoring and control applications, including state-machine replication. Extensive empirical simulations showcase PISTIS's robustness, latency, and scalability. For example, PISTIS can withstand message loss (and delay) rates up to 50% in systems with 49 nodes and provides bounded delivery latencies in the order of a few milliseconds.
BorderDet: Border Feature for Dense Object Detection
Venue: arXiv cs.CV 2021
Year: 2021

Dense object detectors rely on the sliding-window paradigm that predicts the object over a regular grid of image. Meanwhile, the feature maps on the point of the grid are adopted to generate the bounding box predictions. The point feature is convenient to use but may lack the explicit border information for accurate localization. In this paper, We propose a simple and efficient operator called Border-Align to extract "border features" from the extreme point of the border to enhance the point feature. Based on the BorderAlign, we design a novel detection architecture called BorderDet, which explicitly exploits the border information for stronger classification and more accurate localization. With ResNet-50 backbone, our method improves single-stage detector FCOS by 2.8 AP gains (38.6 v.s. 41.4). With the ResNeXt-101-DCN backbone, our BorderDet obtains 50.3 AP, outperforming the existing state-of-the-art approaches. The code is available at (https://github.com/Megvii-BaseDetection/BorderDet).
A Deep Learning-Based FPGA Function Block Detection Method with Bitstream to Image Transformation
Venue: arXiv cs.OH 2021
Year: 2021

In the context of various application scenarios and/or for the sake of strengthening field-programmable gate array (FPGA) security, the system functions of an FPGA design need to be analyzed, which can be achieved by systematically partitioning the FPGA's bitstream into manageable functional blocks and detecting their functionalities thereafter. In this paper, we propose a novel deep learning-based FPGA function block detection method with three major steps. In specific, we first analyze the format of the bitstream to obtain the mapping relationship between the configuration bits and configurable logic blocks because of the discontinuity of the configuration bits in the bitstream for one element. In order to reap the maturity of object detection techniques based on deep learning, our next step is to convert an FPGA bitstream to an image, following the proposed transformation method that takes account of both the adjacency nature of the programmable logic and the high degree of redundancy of configuration information. Once the image is obtained, a deep learning-based object detection algorithm is applied to this transformed image, and the objects detected can be reflected back to determine the function blocks of the original FPGA design. The deep neural network used for function block detection is trained and validated with a specially crafted bitstream/image dataset. Experiments have confirmed high detection accuracy of the proposed function detection method, showing a 98.11% of mean Average Precision (IoU=0.5) for 10 function blocks within a YOLOv3 detector implemented on Xilinx Zynq-7000 SoCs and Zynq UltraScale+ MPSoCs.
Geometric compression of invariant manifolds in neural nets
Venue: arXiv cs.LG 2021
Year: 2021

We study how neural networks compress uninformative input space in models where data lie in $d$ dimensions, but whose label only vary within a linear manifold of dimension $d_\parallel < d$. We show that for a one-hidden layer network initialized with infinitesimal weights (i.e. in the feature learning regime) trained with gradient descent, the first layer of weights evolve to become nearly insensitive to the $d_\perp=d-d_\parallel$ uninformative directions. These are effectively compressed by a factor $λ\sim \sqrt{p}$, where $p$ is the size of the training set. We quantify the benefit of such a compression on the test error $ε$. For large initialization of the weights (the lazy training regime), no compression occurs and for regular boundaries separating labels we find that $ε\sim p^{-β}$, with $β_\text{Lazy} = d / (3d-2)$. Compression improves the learning curves so that $β_\text{Feature} = (2d-1)/(3d-2)$ if $d_\parallel = 1$ and $β_\text{Feature} = (d + d_\perp/2)/(3d-2)$ if $d_\parallel > 1$. We test these predictions for a stripe model where boundaries are parallel interfaces ($d_\parallel=1$) as well as for a cylindrical boundary ($d_\parallel=2$). Next we show that compression shapes the Neural Tangent Kernel (NTK) evolution in time, so that its top eigenvectors become more informative and display a larger projection on the labels. Consequently, kernel learning with the frozen NTK at the end of training outperforms the initial NTK. We confirm these predictions both for a one-hidden layer FC network trained on the stripe model and for a 16-layers CNN trained on MNIST, for which we also find $β_\text{Feature}>β_\text{Lazy}$.
Set It and Forget It! Turnkey ECC for Instant Integration
Venue: arXiv cs.CR 2021
Year: 2021

Historically, Elliptic Curve Cryptography (ECC) is an active field of applied cryptography where recent focus is on high speed, constant time, and formally verified implementations. While there are a handful of outliers where all these concepts join and land in real-world deployments, these are generally on a case-by-case basis: e.g. a library may feature such X25519 or P-256 code, but not for all curves. In this work, we propose and implement a methodology that fully automates the implementation, testing, and integration of ECC stacks with the above properties. We demonstrate the flexibility and applicability of our methodology by seamlessly integrating into three real-world projects: OpenSSL, Mozilla's NSS, and the GOST OpenSSL Engine, achieving roughly 9.5x, 4.5x, 13.3x, and 3.7x speedup on any given curve for key generation, key agreement, signing, and verifying, respectively. Furthermore, we showcase the efficacy of our testing methodology by uncovering flaws and vulnerabilities in OpenSSL, and a specification-level vulnerability in a Russian standard. Our work bridges the gap between significant applied cryptography research results and deployed software, fully automating the process.
Neural Sparse Voxel Fields
Venue: arXiv cs.CV 2021
Year: 2021

Photo-realistic free-viewpoint rendering of real-world scenes using classical computer graphics techniques is challenging, because it requires the difficult step of capturing detailed appearance and geometry models. Recent studies have demonstrated promising results by learning scene representations that implicitly encode both geometry and appearance without 3D supervision. However, existing approaches in practice often show blurry renderings caused by the limited network capacity or the difficulty in finding accurate intersections of camera rays with the scene geometry. Synthesizing high-resolution imagery from these representations often requires time-consuming optical ray marching. In this work, we introduce Neural Sparse Voxel Fields (NSVF), a new neural scene representation for fast and high-quality free-viewpoint rendering. NSVF defines a set of voxel-bounded implicit fields organized in a sparse voxel octree to model local properties in each cell. We progressively learn the underlying voxel structures with a differentiable ray-marching operation from only a set of posed RGB images. With the sparse voxel octree structure, rendering novel views can be accelerated by skipping the voxels containing no relevant scene content. Our method is typically over 10 times faster than the state-of-the-art (namely, NeRF(Mildenhall et al., 2020)) at inference time while achieving higher quality results. Furthermore, by utilizing an explicit sparse voxel representation, our method can easily be applied to scene editing and scene composition. We also demonstrate several challenging tasks, including multi-scene learning, free-viewpoint rendering of a moving human, and large-scale scene rendering. Code and data are available at our website: https://github.com/facebookresearch/NSVF.
Assessing top-$k$ preferences
Venue: arXiv cs.IR 2021
Year: 2021

Assessors make preference judgments faster and more consistently than graded judgments. Preference judgments can also recognize distinctions between items that appear equivalent under graded judgments. Unfortunately, preference judgments can require more than linear effort to fully order a pool of items, and evaluation measures for preference judgments are not as well established as those for graded judgments, such as NDCG. In this paper, we explore the assessment process for partial preference judgments, with the aim of identifying and ordering the top items in the pool, rather than fully ordering the entire pool. To measure the performance of a ranker, we compare its output to this preferred ordering by applying a rank similarity measure.We demonstrate the practical feasibility of this approach by crowdsourcing partial preferences for the TREC 2019 Conversational Assistance Track, replacing NDCG with a new measure named "compatibility". This new measure has its most striking impact when comparing modern neural rankers, where it is able to recognize significant improvements in quality that would otherwise be missed by NDCG.
Robust Machine Learning via Privacy/Rate-Distortion Theory
Venue: arXiv cs.LG 2021
Year: 2021

Robust machine learning formulations have emerged to address the prevalent vulnerability of deep neural networks to adversarial examples. Our work draws the connection between optimal robust learning and the privacy-utility tradeoff problem, which is a generalization of the rate-distortion problem. The saddle point of the game between a robust classifier and an adversarial perturbation can be found via the solution of a maximum conditional entropy problem. This information-theoretic perspective sheds light on the fundamental tradeoff between robustness and clean data performance, which ultimately arises from the geometric structure of the underlying data distribution and perturbation constraints.
Adversarial Attacks against Face Recognition: A Comprehensive Study
Venue: arXiv cs.CV 2021
Year: 2021

Face recognition (FR) systems have demonstrated outstanding verification performance, suggesting suitability for real-world applications ranging from photo tagging in social media to automated border control (ABC). In an advanced FR system with deep learning-based architecture, however, promoting the recognition efficiency alone is not sufficient, and the system should also withstand potential kinds of attacks designed to target its proficiency. Recent studies show that (deep) FR systems exhibit an intriguing vulnerability to imperceptible or perceptible but natural-looking adversarial input images that drive the model to incorrect output predictions. In this article, we present a comprehensive survey on adversarial attacks against FR systems and elaborate on the competence of new countermeasures against them. Further, we propose a taxonomy of existing attack and defense methods based on different criteria. We compare attack methods on the orientation and attributes and defense approaches on the category. Finally, we explore the challenges and potential research direction.