OpenRaiser/Intern-Atlas huggingface dataset:
Fair Allocation of Indivisible Public Goods
Venue: arXiv cs.GT 2018
Year: 2018

We consider the problem of fairly allocating indivisible public goods. We model the public goods as elements with feasibility constraints on what subsets of elements can be chosen, and assume that agents have additive utilities across elements. Our model generalizes existing frameworks such as fair public decision making and participatory budgeting. We study a groupwise fairness notion called the core, which generalizes well-studied notions of proportionality and Pareto efficiency, and requires that each subset of agents must receive an outcome that is fair relative to its size. In contrast to the case of divisible public goods (where fractional allocations are permitted), the core is not guaranteed to exist when allocating indivisible public goods. Our primary contributions are the notion of an additive approximation to the core (with a tiny multiplicative loss), and polynomial time algorithms that achieve a small additive approximation, where the additive factor is relative to the largest utility of an agent for an element. If the feasibility constraints define a matroid, we show an additive approximation of 2. A similar approach yields a constant additive bound when the feasibility constraints define a matching. More generally, if the feasibility constraints define an arbitrary packing polytope with mild restrictions, we show an additive guarantee that is logarithmic in the width of the polytope. Our algorithms are based on variants of the convex program for maximizing the Nash social welfare, but differ significantly from previous work in how it is used. Our guarantees are meaningful even when there are fewer elements than the number of agents. As far as we are aware, our work is the first to approximate the core in indivisible settings.
Implementing a Method for Stochastization of One-Step Processes in a Computer Algebra System
Venue: arXiv cs.SC 2018
Year: 2018

When modeling such phenomena as population dynamics, controllable ows, etc., a problem arises of adapting the existing models to a phenomenon under study. For this purpose, we propose to derive new models from the rst principles by stochastization of one-step processes. Research can be represented as an iterative process that consists in obtaining a model and its further re nement. The number of such iterations can be extremely large. This work is aimed at software implementation (by means of computer algebra) of a method for stochastization of one-step processes. As a basis of the software implementation, we use the SymPy computer algebra system. Based on a developed algorithm, we derive stochastic di erential equations and their interaction schemes. The operation of the program is demonstrated on the Verhulst and Lotka-Volterra models.
Suburban Residential Building Penetration Loss at 28 GHz for Fixed Wireless Access
Venue: arXiv cs.IT 2018
Year: 2018

Fixed wireless access at mm/cm bands has been proposed for high-speed broadband access to suburban residential customers and building penetration loss is a key parameter. We report a measurement campaign at 28 GHz in a New Jersey suburban residential neighborhood for three representative single-family homes. A base antenna is mounted at 3-meter height, emulating a base station on a lamppost, moves down the street up to 200 meters. A customer premises equipment (CPE) device, acting as relay to provide indoor coverage throughout the desired area, is mounted either on the exterior of a street-facing window or 1.5 meters behind the window. The median indoor-outdoor path gain difference, corresponding to the extra loss by moving the window-mounted CPE indoor, is found to be 9 dB for the house with low-loss materials and plain-glass windows, and 17 dB for the house with low-emissivity windows and foil-backed insulation. These losses are in addition to other losses (e.g., vegetation blockage) in comparison to free space propagation.
Multimodal Hierarchical Reinforcement Learning Policy for Task-Oriented Visual Dialog
Venue: arXiv cs.CL 2018
Year: 2018

Creating an intelligent conversational system that understands vision and language is one of the ultimate goals in Artificial Intelligence (AI)~\cite{winograd1972understanding}. Extensive research has focused on vision-to-language generation, however, limited research has touched on combining these two modalities in a goal-driven dialog context. We propose a multimodal hierarchical reinforcement learning framework that dynamically integrates vision and language for task-oriented visual dialog. The framework jointly learns the multimodal dialog state representation and the hierarchical dialog policy to improve both dialog task success and efficiency. We also propose a new technique, state adaptation, to integrate context awareness in the dialog state representation. We evaluate the proposed framework and the state adaptation technique in an image guessing game and achieve promising results.
Sparse Blind Deconvolution for Distributed Radar Autofocus Imaging
Venue: arXiv cs.CV 2018
Year: 2018

A common problem that arises in radar imaging systems, especially those mounted on mobile platforms, is antenna position ambiguity. Approaches to resolve this ambiguity and correct position errors are generally known as radar autofocus. Common techniques that attempt to resolve the antenna ambiguity generally assume an unknown gain and phase error afflicting the radar measurements. However, ensuring identifiability and tractability of the unknown error imposes strict restrictions on the allowable antenna perturbations. Furthermore, these techniques are often not applicable in near-field imaging, where mapping the position ambiguity to phase errors breaks down. In this paper, we propose an alternate formulation where the position error of each antenna is mapped to a spatial shift operator in the image-domain. Thus, the radar autofocus problem becomes a multichannel blind deconvolution problem, in which the radar measurements correspond to observations of a static radar image that is convolved with the spatial shift kernel associated with each antenna. To solve the reformulated problem, we also develop a block coordinate descent framework that leverages the sparsity and piece-wise smoothness of the radar scene, as well as the one-sparse property of the two dimensional shift kernels. We evaluate the performance of our approach using both simulated and experimental radar measurements, and demonstrate its superior performance compared to state-of-the-art methods.
Read Disturb Errors in MLC NAND Flash Memory
Venue: arXiv cs.AR 2018
Year: 2018

This paper summarizes our work on experimentally characterizing, mitigating, and recovering read disturb errors in multi-level cell (MLC) NAND flash memory, which was published in DSN 2015, and examines the work's significance and future potential. NAND flash memory reliability continues to degrade as the memory is scaled down and more bits are programmed per cell. A key contributor to this reduced reliability is read disturb, where a read to one row of cells impacts the threshold voltages of unread flash cells in different rows of the same block. For the first time in open literature, this work experimentally characterizes read disturb errors on state-of-the-art 2Y-nm (i.e., 20-24 nm) MLC NAND flash memory chips. Our findings (1) correlate the magnitude of threshold voltage shifts with read operation counts, (2) demonstrate how program/erase cycle count and retention age affect the read-disturb-induced error rate, and (3) identify that lowering pass-through voltage levels reduces the impact of read disturb and extend flash lifetime. Particularly, we find that the probability of read disturb errors increases with both higher wear-out and higher pass-through voltage levels. We leverage these findings to develop two new techniques. The first technique mitigates read disturb errors by dynamically tuning the pass-through voltage on a per-block basis. Using real workload traces, our evaluations show that this technique increases flash memory endurance by an average of 21%. The second technique recovers from previously-uncorrectable flash errors by identifying and probabilistically correcting cells susceptible to read disturb errors. Our evaluations show that this recovery technique reduces the raw bit error rate by 36%.
Deep Neural Networks for Optimal Team Composition
Venue: arXiv cs.SI 2018
Year: 2018

Cooperation is a fundamental social mechanism, whose effects on human performance have been investigated in several environments. Online games are modern-days natural settings in which cooperation strongly affects human behavior. Every day, millions of players connect and play together in team-based games: the patterns of cooperation can either foster or hinder individual skill learning and performance. This work has three goals: (i) identifying teammates' influence on players' performance in the short and long term, (ii) designing a computational framework to recommend teammates to improve players' performance, and (iii) setting to demonstrate that such improvements can be predicted via deep learning. We leverage a large dataset from Dota 2, a popular Multiplayer Online Battle Arena game. We generate a directed co-play network, whose links' weights depict the effect of teammates on players' performance. Specifically, we propose a measure of network influence that captures skill transfer from player to player over time. We then use such framing to design a recommendation system to suggest new teammates based on a modified deep neural autoencoder and we demonstrate its state-of-the-art recommendation performance. We finally provide insights into skill transfer effects: our experimental results demonstrate that such dynamics can be predicted using deep neural networks.
Characterizing, Exploiting, and Mitigating Vulnerabilities in MLC NAND Flash Memory Programming
Venue: arXiv cs.AR 2018
Year: 2018

This paper summarizes our work on experimentally analyzing, exploiting, and addressing vulnerabilities in multi-level cell NAND flash memory programming, which was published in the industrial session of HPCA 2017, and examines the work's significance and future potential. Modern NAND flash memory chips use multi-level cells (MLC), which store two bits of data in each cell, to improve chip density. As MLC NAND flash memory scaled down to smaller manufacturing process technologies, manufacturers adopted a two-step programming method to improve reliability. In two-step programming, the two bits of a multi-level cell are programmed using two separate steps, in order to minimize the amount of cell-to-cell program interference induced on neighboring flash cells. In this work, we demonstrate that two-step programming exposes new reliability and security vulnerabilities in state-of-the-art MLC NAND flash memory. We experimentally characterize contemporary 1X-nm (i.e., 15--19nm) flash memory chips, and find that a partially-programmed flash cell (i.e., a cell where the second programming step has not yet been performed) is much more vulnerable to cell-to-cell interference and read disturb than a fully-programmed cell. We show that it is possible to exploit these vulnerabilities on solid-state drives (SSDs) to alter the partially-programmed data, causing (potentially malicious) data corruption. Based on our observations, we propose several new mechanisms that eliminate or mitigate these vulnerabilities in partially-programmed cells, and at the same time increase flash memory lifetime by 16%.
Investor Reaction to Financial Disclosures Across Topics: An Application of Latent Dirichlet Allocation
Venue: arXiv cs.CL 2018
Year: 2018

This paper provides a holistic study of how stock prices vary in their response to financial disclosures across different topics. Thereby, we specifically shed light into the extensive amount of filings for which no a priori categorization of their content exists. For this purpose, we utilize an approach from data mining - namely, latent Dirichlet allocation - as a means of topic modeling. This technique facilitates our task of automatically categorizing, ex ante, the content of more than 70,000 regulatory 8-K filings from U.S. companies. We then evaluate the subsequent stock market reaction. Our empirical evidence suggests a considerable discrepancy among various types of news stories in terms of their relevance and impact on financial markets. For instance, we find a statistically significant abnormal return in response to earnings results and credit rating, but also for disclosures regarding business strategy, the health sector, as well as mergers and acquisitions. Our results yield findings that benefit managers, investors and policy-makers by indicating how regulatory filings should be structured and the topics most likely to precede changes in stock valuations.
Quadratically Constrained Channels with Causal Adversaries
Venue: arXiv cs.IT 2018
Year: 2018

We consider the problem of communication over a channel with a causal jamming adversary subject to quadratic constraints. A sender Alice wishes to communicate a message to a receiver Bob by transmitting a real-valued length-$n$ codeword $\mathbf{x}=x_1,...,x_n$ through a communication channel. Alice and Bob do not share common randomness. Knowing Alice's encoding strategy, an adversarial jammer James chooses a real-valued length-n noise sequence $\mathbf{s}=s_1,..,s_n$ in a causal manner, i.e., each $s_t (1<=t<=n)$ can only depend on $x_1,...,x_t$. Bob receives $\mathbf{y}$, the sum of Alice's transmission $\mathbf{x}$ and James' jamming vector $\mathbf{s}$, and is required to reliably estimate Alice's message from this sum. In addition, Alice and James's transmission powers are restricted by quadratic constraints $P>0$ and $N>0$. In this work, we characterize the channel capacity for such a channel as the limit superior of the optimal values of a series of optimizations. Upper and lower bounds on the optimal values are provided both analytically and numerically. Interestingly, unlike many communication problems, in this causal setting Alice's optimal codebook may not have a uniform power allocation - for certain SNR, a codebook with a two-level uniform power allocation results in a strictly higher rate than a codebook with a uniform power allocation would.
A Sample Path Measure of Causal Influence
Venue: arXiv cs.IT 2018
Year: 2018

We present a sample path dependent measure of causal influence between two time series. The proposed measure is a random variable whose expected sum is the directed information. A realization of the proposed measure may be used to identify the specific patterns in the data that yield a greater flow of information from one process to another, even in stationary processes. We demonstrate how sequential prediction theory may be leveraged to obtain accurate estimates of the causal measure at each point in time and introduce a notion of regret for assessing the performance of estimators of the measure. We prove a finite sample bound on this regret that is determined by the regret of the sequential predictors used in obtaining the estimate. We estimate the causal measure for a simulated collection of binary Markov processes using a Bayesian updating approach. Finally, given that the measure is a function of time, we demonstrate how estimators of the causal measure may be extended to effectively capture causality in time-varying scenarios.
SPG-Net: Segmentation Prediction and Guidance Network for Image Inpainting
Venue: arXiv cs.CV 2018
Year: 2018

In this paper, we focus on image inpainting task, aiming at recovering the missing area of an incomplete image given the context information. Recent development in deep generative models enables an efficient end-to-end framework for image synthesis and inpainting tasks, but existing methods based on generative models don't exploit the segmentation information to constrain the object shapes, which usually lead to blurry results on the boundary. To tackle this problem, we propose to introduce the semantic segmentation information, which disentangles the inter-class difference and intra-class variation for image inpainting. This leads to much clearer recovered boundary between semantically different regions and better texture within semantically consistent segments. Our model factorizes the image inpainting process into segmentation prediction (SP-Net) and segmentation guidance (SG-Net) as two steps, which predict the segmentation labels in the missing area first, and then generate segmentation guided inpainting results. Experiments on multiple public datasets show that our approach outperforms existing methods in optimizing the image inpainting quality, and the interactive segmentation guidance provides possibilities for multi-modal predictions of image inpainting.
Opinion Fraud Detection via Neural Autoencoder Decision Forest
Venue: arXiv cs.CL 2018
Year: 2018

Online reviews play an important role in influencing buyers' daily purchase decisions. However, fake and meaningless reviews, which cannot reflect users' genuine purchase experience and opinions, widely exist on the Web and pose great challenges for users to make right choices. Therefore,it is desirable to build a fair model that evaluates the quality of products by distinguishing spamming reviews. We present an end-to-end trainable unified model to leverage the appealing properties from Autoencoder and random forest. A stochastic decision tree model is implemented to guide the global parameter learning process. Extensive experiments were conducted on a large Amazon review dataset. The proposed model consistently outperforms a series of compared methods.
N-BaIoT: Network-based Detection of IoT Botnet Attacks Using Deep Autoencoders
Venue: arXiv cs.CR 2018
Year: 2018

The proliferation of IoT devices which can be more easily compromised than desktop computers has led to an increase in the occurrence of IoT based botnet attacks. In order to mitigate this new threat there is a need to develop new methods for detecting attacks launched from compromised IoT devices and differentiate between hour and millisecond long IoTbased attacks. In this paper we propose and empirically evaluate a novel network based anomaly detection method which extracts behavior snapshots of the network and uses deep autoencoders to detect anomalous network traffic emanating from compromised IoT devices. To evaluate our method, we infected nine commercial IoT devices in our lab with two of the most widely known IoT based botnets, Mirai and BASHLITE. Our evaluation results demonstrated our proposed method's ability to accurately and instantly detect the attacks as they were being launched from the compromised IoT devices which were part of a botnet.
Evaluating Manual Intervention to Address the Challenges of Bug Finding with KLEE
Venue: arXiv cs.SE 2018
Year: 2018

Symbolic execution has shown its ability to find security-relevant flaws in software, but faces significant scalability challenges. There is a commonly held belief that manual intervention by an expert can help alleviate these limiting factors. However, there has been little formal investigation of this idea. In this paper, we present our experiences applying the KLEE symbolic execution engine to a new bug corpus, and of using manual intervention to alleviate the issues encountered. Our contributions are (1) Hemiptera, a novel corpus of over 130 bugs in real world software, (2) a comprehensive evaluation of the KLEE symbolic execution engine on Hemiptera with a categorisation of frequently occurring software patterns that are problematic for symbolic execution, and (3) an evaluation of manual mitigations aimed at addressing the underlying issues of symbolic execution. Our experience shows that manual intervention can increase both code coverage and bug detection in many situations. It is not a silver bullet however, and we discuss its limitations and the challenges encountered.
Tight bounds for undirected graph exploration with pebbles and multiple agents
Venue: arXiv cs.DS 2018
Year: 2018

We study the problem of deterministically exploring an undirected and initially unknown graph with $n$ vertices either by a single agent equipped with a set of pebbles, or by a set of collaborating agents. The vertices of the graph are unlabeled and cannot be distinguished by the agents, but the edges incident to a vertex have locally distinct labels. The graph is explored when all vertices have been visited by at least one agent. In this setting, it is known that for a single agent without pebbles $Θ(\log n)$ bits of memory are necessary and sufficient to explore any graph with at most $n$ vertices. We are interested in how the memory requirement decreases as the agent may mark vertices by dropping and retrieving distinguishable pebbles, or when multiple agents jointly explore the graph. We give tight results for both questions showing that for a single agent with constant memory $Θ(\log \log n)$ pebbles are necessary and sufficient for exploration. We further prove that the same bound holds for the number of collaborating agents needed for exploration. For the upper bound, we devise an algorithm for a single agent with constant memory that explores any $n$-vertex graph using $\mathcal{O}(\log \log n)$ pebbles, even when $n$ is unknown. The algorithm terminates after polynomial time and returns to the starting vertex. Since an additional agent is at least as powerful as a pebble, this implies that $\mathcal{O}(\log \log n)$ agents with constant memory can explore any $n$-vertex graph. For the lower bound, we show that the number of agents needed for exploring any graph of size $n$ is already $Ω(\log \log n)$ when we allow each agent to have at most $\mathcal{O}( \log n ^{1-\varepsilon})$ bits of memory for any $\varepsilon>0$. This also implies that a single agent with sublogarithmic memory needs $Θ(\log \log n)$ pebbles to explore any $n$-vertex graph.
Full 3D Reconstruction of Transparent Objects
Venue: arXiv cs.GR 2018
Year: 2018

Numerous techniques have been proposed for reconstructing 3D models for opaque objects in past decades. However, none of them can be directly applied to transparent objects. This paper presents a fully automatic approach for reconstructing complete 3D shapes of transparent objects. Through positioning an object on a turntable, its silhouettes and light refraction paths under different viewing directions are captured. Then, starting from an initial rough model generated from space carving, our algorithm progressively optimizes the model under three constraints: surface and refraction normal consistency, surface projection and silhouette consistency, and surface smoothness. Experimental results on both synthetic and real objects demonstrate that our method can successfully recover the complex shapes of transparent objects and faithfully reproduce their light refraction properties.
Revisiting Decision Diagrams for SAT
Venue: arXiv cs.LO 2018
Year: 2018

Symbolic variants of clause distribution using decision diagrams to eliminate variables in SAT were shown to perform well on hard combinatorial instances. In this paper we revisit both existing ZDD and BDD variants of this approach. We further investigate different heuristics for selecting the next variable to eliminate. Our implementation makes further use of parallel features of the open source BDD library Sylvan.