OpenRaiser/Intern-Atlas huggingface dataset:
A Local Algorithm for the Sparse Spanning Graph Problem
Venue: arXiv cs.DS 2017
Year: 2017

Constructing a sparse spanning subgraph is a fundamental primitive in graph theory. In this paper, we study this problem in the Centralized Local model, where the goal is to decide whether an edge is part of the spanning subgraph by examining only a small part of the input; yet, answers must be globally consistent and independent of prior queries. Unfortunately, maximally sparse spanning subgraphs, i.e., spanning trees, cannot be constructed efficiently in this model. Therefore, we settle for a spanning subgraph containing at most $(1+\varepsilon)n$ edges (where $n$ is the number of vertices and $\varepsilon$ is a given approximation/sparsity parameter). We achieve query complexity of $\tilde{O}(poly(Δ/\varepsilon)n^{2/3})$, ($\tilde{O}$-notation hides polylogarithmic factors in $n$). where $Δ$ is the maximum degree of the input graph. Our algorithm is the first to do so on arbitrary bounded degree graphs. Moreover, we achieve the additional property that our algorithm outputs a spanner, i.e., distances are approximately preserved. With high probability, for each deleted edge there is a path of $O(poly(Δ/\varepsilon)\log^2 n)$ hops in the output that connects its endpoints.
Database Learning: Toward a Database that Becomes Smarter Every Time
Venue: arXiv cs.DB 2017
Year: 2017

In today's databases, previous query answers rarely benefit answering future queries. For the first time, to the best of our knowledge, we change this paradigm in an approximate query processing (AQP) context. We make the following observation: the answer to each query reveals some degree of knowledge about the answer to another query because their answers stem from the same underlying distribution that has produced the entire dataset. Exploiting and refining this knowledge should allow us to answer queries more analytically, rather than by reading enormous amounts of raw data. Also, processing more queries should continuously enhance our knowledge of the underlying distribution, and hence lead to increasingly faster response times for future queries. We call this novel idea---learning from past query answers---Database Learning. We exploit the principle of maximum entropy to produce answers, which are in expectation guaranteed to be more accurate than existing sample-based approximations. Empowered by this idea, we build a query engine on top of Spark SQL, called Verdict. We conduct extensive experiments on real-world query traces from a large customer of a major database vendor. Our results demonstrate that Verdict supports 73.7% of these queries, speeding them up by up to 23.0x for the same accuracy level compared to existing AQP systems.
Using Reinforcement Learning for Demand Response of Domestic Hot Water Buffers: a Real-Life Demonstration
Venue: arXiv cs.SY 2017
Year: 2017

This paper demonstrates a data-driven control approach for demand response in real-life residential buildings. The objective is to optimally schedule the heating cycles of the Domestic Hot Water (DHW) buffer to maximize the self-consumption of the local photovoltaic (PV) production. A model-based reinforcement learning technique is used to tackle the underlying sequential decision-making problem. The proposed algorithm learns the stochastic occupant behavior, predicts the PV production and takes into account the dynamics of the system. A real-life experiment with six residential buildings is performed using this algorithm. The results show that the self-consumption of the PV production is significantly increased, compared to the default thermostat control.
Data Delivery by Mobile Agents with Energy Constraints over a fixed path
Venue: arXiv cs.DS 2017
Year: 2017

We consider $k$ mobile agents of limited energy that are initially located at vertices of an edge-weighted graph $G$ and have to collectively deliver data from a source vertex $s$ to a target vertex $t$. The data are to be collected by an agent reaching $s$, who can carry and then hand them over another agent etc., until some agent with the data reaches $t$. The data can be carried only over a fixed $s-t$ path of $G$; each agent has an initial energy budget and each time it passes an edge, it consumes the edge's weights in energy units and stalls if its energy is not anymore sufficient to move. The main result of this paper is a 3-approximation polynomial time algorithm for the data delivery problem over a fixed $s-t$ path in the graph, for identical initial energy budgets and at most one allowed data hand-over per agent.
Fraternal Twins: Unifying Attacks on Machine Learning and Digital Watermarking
Venue: arXiv cs.CR 2017
Year: 2017

Machine learning is increasingly used in security-critical applications, such as autonomous driving, face recognition and malware detection. Most learning methods, however, have not been designed with security in mind and thus are vulnerable to different types of attacks. This problem has motivated the research field of adversarial machine learning that is concerned with attacking and defending learning methods. Concurrently, a different line of research has tackled a very similar problem: In digital watermarking information are embedded in a signal in the presence of an adversary. As a consequence, this research field has also extensively studied techniques for attacking and defending watermarking methods. The two research communities have worked in parallel so far, unnoticeably developing similar attack and defense strategies. This paper is a first effort to bring these communities together. To this end, we present a unified notation of black-box attacks against machine learning and watermarking that reveals the similarity of both settings. To demonstrate the efficacy of this unified view, we apply concepts from watermarking to machine learning and vice versa. We show that countermeasures from watermarking can mitigate recent model-extraction attacks and, similarly, that techniques for hardening machine learning can fend off oracle attacks against watermarks. Our work provides a conceptual link between two research fields and thereby opens novel directions for improving the security of both, machine learning and digital watermarking.
Impact of SDN Controllers Deployment on Network Availability
Venue: arXiv cs.NI 2017
Year: 2017

Software-defined networking (SDN) promises to improve the programmability and flexibility of networks, but it may bring also new challenges that need to be explored. The purpose of this technical report is to assess how the deployment of the SDN controllers affects the overall availability of SDN. For this, we have varied the number, homing and location of SDN controllers. A two-level modelling approach that is used to evaluate the availability of the studied scenarios. Our results show how network operators can use the approach to find the optimal cost implied by the connectivity of the SDN control platform by keeping high levels of availability.
Modeling and Analysis of Non-Orthogonal MBMS Transmission in Heterogeneous Networks
Venue: arXiv cs.IT 2017
Year: 2017

Broadcasting/multicasting is an efficient mechanism for multimedia communications due to its high spectrum efficiency, which achieves point-to-multipoint transmission on the same radio resources. To satisfy the increasing demands for multimedia broadcast multicast service (MBMS), we present a power domain non-orthogonal MBMS transmission scheme in a K-tier heterogeneous network (HetNet). Firstly, the system model, usage scenarios, and fundamentals of the presented scheme are discussed. Next, a tractable framework is developed to analyse the performance of non-orthogonal MBMS transmission, by using stochastic geometry. Based on this framework, the analytical expressions for the signal-to-interference-plus-noise ratio (SINR) coverage probability, average number of served users, and sum rate are derived. Furthermore, synchronous non-orthogonal MBMS transmission to further improving the system performance is also studied. The results demonstrate that non-orthogonal MBMS transmission can achieve better performance than the conventional one, in which non-orthogonal multirate one can fully utilize channel conditions to achieve a significant rate gain, while non-orthogonal multi-service one can efficiently use power resources to guarantee the quality of service (QoS) of high priority users, and also provide services for low priority users simultaneously.
Autocomplete Textures for 3D Printing
Venue: arXiv cs.HC 2017
Year: 2017

Texture is an essential property of physical objects that affects aesthetics, usability, and functionality. However, designing and applying textures to 3D objects with existing tools remains difficult and time-consuming; it requires proficient 3D modeling skills. To address this, we investigated an auto-completion approach for efficient texture creation that automates the tedious, repetitive process of applying texture while allowing flexible customization. We developed techniques for users to select a target surface, sketch and manipulate a texture with 2D drawings, and then generate 3D printable textures onto an arbitrary curved surface. In a controlled experiment our tool sped texture creation by 80% over conventional tools, a performance gain that is higher with more complex target surfaces. This result confirms that auto-completion is powerful for creating 3D textures.
Learning Robust Hash Codes for Multiple Instance Image Retrieval
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, for the first time, we introduce a multiple instance (MI) deep hashing technique for learning discriminative hash codes with weak bag-level supervision suited for large-scale retrieval. We learn such hash codes by aggregating deeply learnt hierarchical representations across bag members through a dedicated MI pool layer. For better trainability and retrieval quality, we propose a two-pronged approach that includes robust optimization and training with an auxiliary single instance hashing arm which is down-regulated gradually. We pose retrieval for tumor assessment as an MI problem because tumors often coexist with benign masses and could exhibit complementary signatures when scanned from different anatomical views. Experimental validations on benchmark mammography and histology datasets demonstrate improved retrieval performance over the state-of-the-art methods.
Object-Centric Behavioral Constraints
Venue: arXiv cs.DB 2017
Year: 2017

Today's process modeling languages often force the analyst or modeler to straightjacket real-life processes into simplistic or incomplete models that fail to capture the essential features of the domain under study. Conventional business process models only describe the lifecycles of individual instances (cases) in isolation. Although process models may include data elements (cf. BPMN), explicit connections to real data models (e.g., an entity relationship model or a UML class model) are rarely made. Therefore, we propose a novel approach that extends data models with a behavioral perspective. Data models can easily deal with many-to-many and one-to-many relationships. This is exploited to create process models that can also model complex interactions between different types of instances. Classical multiple-instance problems are circumvented by using the data model for event correlation. The declarative nature of the proposed language makes it possible to model behavioral constraints over activities like cardinality constraints in data models. The resulting object-centric behavioral constraint (OCBC) model is able to describe processes involving interacting instances and complex data dependencies. In this paper, we introduce the OCBC model and notation, providing a number of examples that give a flavour of the approach. We then define a set-theoretic semantics exploiting cardinality constraints within and across time points. We finally formalize conformance checking in our setting, arguing that evaluating conformance against OCBC models requires diagnostics that go beyond what is provided by contemporary conformance checking approaches.
A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$
Venue: arXiv cs.CC 2017
Year: 2017

The approximate degree of a Boolean function $f \colon \{-1, 1\}^n \rightarrow \{-1, 1\}$ is the least degree of a real polynomial that approximates $f$ pointwise to error at most $1/3$. We introduce a generic method for increasing the approximate degree of a given function, while preserving its computability by constant-depth circuits. Specifically, we show how to transform any Boolean function $f$ with approximate degree $d$ into a function $F$ on $O(n \cdot \operatorname{polylog}(n))$ variables with approximate degree at least $D = Ω(n^{1/3} \cdot d^{2/3})$. In particular, if $d= n^{1-Ω(1)}$, then $D$ is polynomially larger than $d$. Moreover, if $f$ is computed by a polynomial-size Boolean circuit of constant depth, then so is $F$. By recursively applying our transformation, for any constant $δ> 0$ we exhibit an AC$^0$ function of approximate degree $Ω(n^{1-δ})$. This improves over the best previous lower bound of $Ω(n^{2/3})$ due to Aaronson and Shi (J. ACM 2004), and nearly matches the trivial upper bound of $n$ that holds for any function. Our lower bounds also apply to (quasipolynomial-size) DNFs of polylogarithmic width. We describe several applications of these results. We give: * For any constant $δ> 0$, an $Ω(n^{1-δ})$ lower bound on the quantum communication complexity of a function in AC$^0$. * A Boolean function $f$ with approximate degree at least $C(f)^{2-o(1)}$, where $C(f)$ is the certificate complexity of $f$. This separation is optimal up to the $o(1)$ term in the exponent. * Improved secret sharing schemes with reconstruction procedures in AC$^0$.
Automatically identifying, counting, and describing wild animals in camera-trap images with deep learning
Venue: arXiv cs.CV 2017
Year: 2017

Having accurate, detailed, and up-to-date information about the location and behavior of animals in the wild would revolutionize our ability to study and conserve ecosystems. We investigate the ability to automatically, accurately, and inexpensively collect such data, which could transform many fields of biology, ecology, and zoology into "big data" sciences. Motion sensor "camera traps" enable collecting wildlife pictures inexpensively, unobtrusively, and frequently. However, extracting information from these pictures remains an expensive, time-consuming, manual task. We demonstrate that such information can be automatically extracted by deep learning, a cutting-edge type of artificial intelligence. We train deep convolutional neural networks to identify, count, and describe the behaviors of 48 species in the 3.2-million-image Snapshot Serengeti dataset. Our deep neural networks automatically identify animals with over 93.8% accuracy, and we expect that number to improve rapidly in years to come. More importantly, if our system classifies only images it is confident about, our system can automate animal identification for 99.3% of the data while still performing at the same 96.6% accuracy as that of crowdsourced teams of human volunteers, saving more than 8.4 years (at 40 hours per week) of human labeling effort (i.e. over 17,000 hours) on this 3.2-million-image dataset. Those efficiency gains immediately highlight the importance of using deep neural networks to automate data extraction from camera-trap images. Our results suggest that this technology could enable the inexpensive, unobtrusive, high-volume, and even real-time collection of a wealth of information about vast numbers of animals in the wild.
Towards Closing the Energy Gap Between HOG and CNN Features for Embedded Vision
Venue: arXiv cs.CV 2017
Year: 2017

Computer vision enables a wide range of applications in robotics/drones, self-driving cars, smart Internet of Things, and portable/wearable electronics. For many of these applications, local embedded processing is preferred due to privacy and/or latency concerns. Accordingly, energy-efficient embedded vision hardware delivering real-time and robust performance is crucial. While deep learning is gaining popularity in several computer vision algorithms, a significant energy consumption difference exists compared to traditional hand-crafted approaches. In this paper, we provide an in-depth analysis of the computation, energy and accuracy trade-offs between learned features such as deep Convolutional Neural Networks (CNN) and hand-crafted features such as Histogram of Oriented Gradients (HOG). This analysis is supported by measurements from two chips that implement these algorithms. Our goal is to understand the source of the energy discrepancy between the two approaches and to provide insight about the potential areas where CNNs can be improved and eventually approach the energy-efficiency of HOG while maintaining its outstanding performance accuracy.
Search Engine Drives the Evolution of Social Networks
Venue: arXiv cs.SI 2017
Year: 2017

The search engine is tightly coupled with social networks and is primarily designed for users to acquire interested information. Specifically, the search engine assists the information dissemination for social networks, i.e., enabling users to access interested contents with keywords-searching and promoting the process of contents-transferring from the source users directly to potential interested users. Accompanying such processes, the social network evolves as new links emerge between users with common interests. However, there is no clear understanding of such a "chicken-and-egg" problem, namely, new links encourage more social interactions, and vice versa. In this paper, we aim to quantitatively characterize the social network evolution phenomenon driven by a search engine. First, we propose a search network model for social network evolution. Second, we adopt two performance metrics, namely, degree distribution and network diameter. Theoretically, we prove that the degree distribution follows an intensified power-law, and the network diameter shrinks. Third, we quantitatively show that the search engine accelerates the rumor propagation in social networks. Finally, based on four real-world data sets (i.e., CDBLP, Facebook, Weibo Tweets, P2P), we verify our theoretical findings. Furthermore, we find that the search engine dramatically increases the speed of rumor propagation.
Color Orchestra: Ordering Color Palettes for Interpolation and Prediction
Venue: arXiv cs.CV 2017
Year: 2017

Color theme or color palette can deeply influence the quality and the feeling of a photograph or a graphical design. Although color palettes may come from different sources such as online crowd-sourcing, photographs and graphical designs, in this paper, we consider color palettes extracted from fine art collections, which we believe to be an abundant source of stylistic and unique color themes. We aim to capture color styles embedded in these collections by means of statistical models and to build practical applications upon these models. As artists often use their personal color themes in their paintings, making these palettes appear frequently in the dataset, we employed density estimation to capture the characteristics of palette data. Via density estimation, we carried out various predictions and interpolations on palettes, which led to promising applications such as photo-style exploration, real-time color suggestion, and enriched photo recolorization. It was, however, challenging to apply density estimation to palette data as palettes often come as unordered sets of colors, which make it difficult to use conventional metrics on them. To this end, we developed a divide-and-conquer sorting algorithm to rearrange the colors in the palettes in a coherent order, which allows meaningful interpolation between color palettes. To confirm the performance of our model, we also conducted quantitative experiments on datasets of digitized paintings collected from the Internet and received favorable results.
Outcome-Based Quality Assessment Framework for Higher Education
Venue: arXiv cs.CY 2017
Year: 2017

This research paper proposes a quality framework for higher education that evaluates the performance of institutions on the basis of performance of outgoing students. Literature was surveyed to evaluate existing quality frameworks and develop a framework that provides insights on an unexplored dimension of quality. In order to implement and test the framework, cloud-based big data technology, BigQuery, was used with R to perform analytics. It was found that how the students fair after passing out of a course is the outcome of educational process. This aspect can also be used as a quality metric for performance evaluation and management of educational organizations. However, it has not been taken into account in existing research. The lack of an integrated data collection system and rich datasets for educational intelligence applications, are some of the limitations that plague this area of research. Educational organizations are responsible for the performance of their students even after they complete their course. The inclusion of this dimension to quality assessment shall allow evaluation of educational institutions on these grounds. Assurance of this quality dimension shall boost enrolments in postgraduate and research degrees. Moreover, educational institutions will be motivated to groom students for placements or higher studies.
Robust Assignments with Vulnerable Nodes
Venue: arXiv cs.DS 2017
Year: 2017

Various real-life planning problems require making upfront decisions before all parameters of the problem have been disclosed. An important special case of such problem especially arises in scheduling and staff rostering problems, where a set of tasks needs to be assigned to an available set of resources (personnel or machines), in a way that each task is assigned to one resource, while no task is allowed to share a resource with another task. In its nominal form, the resulting computational problem reduces to the well-known assignment problem that can be modeled as matching problems on bipartite graphs. In recent work \cite{adjiashvili_bindewald_michaels_icalp2016}, a new robust model for the assignment problem was introduced that can deal with situations in which certain resources, i.e.\ nodes or edges of the underlying bipartite graph, are vulnerable and may become unavailable after a solution has been chosen. In the original version from \cite{adjiashvili_bindewald_michaels_icalp2016} the resources subject to uncertainty are the edges of the underlying bipartite graph. In this follow-up work, we complement our previous study by considering nodes as being vulnerable, instead of edges. The goal is now to choose a minimum-cost collection of nodes such that, if any vulnerable node becomes unavailable, the remaining part of the solution still contains sufficient nodes to perform all tasks. From a practical point of view, such type of unavailability is interesting as it is typically caused e.g.\ by an employee's sickness, or machine failure. We present algorithms and hardness of approximation results for several variants of the problem.
Impossibility of Three Pass Protocol using Public Abelian Groups
Venue: arXiv cs.CR 2017
Year: 2017

Key transport protocols are designed to transfer a secret key from an initiating principal to other entities in a network. The three-pass protocol is a key transport protocol developed by Adi Shamir in 1980 where Alice wants to transport a secret message to Bob over an insecure channel, and they do not have any pre-shared secret information. In this paper, we prove the impossibility of secret key transportation from a principal to another entity in a network by using the three pass protocol over public Abelian groups. If it were possible to employ public Abelian groups to implement the three-pass protocol, we could use it in post-quantum cryptography for transporting keys providing information theoretic security without relying on any computationally difficult problem.