OpenRaiser/Intern-Atlas huggingface dataset:
Adaptive Lower Bound for Testing Monotonicity on the Line
Venue: arXiv cs.CC 2018
Year: 2018

In the property testing model, the task is to distinguish objects possessing some property from the objects that are far from it. One of such properties is monotonicity, when the objects are functions from one poset to another. This is an active area of research. In this paper we study query complexity of $ε$-testing monotonicity of a function $f\colon [n]\to[r]$. All our lower bounds are for adaptive two-sided testers. * We prove a nearly tight lower bound for this problem in terms of $r$. The bound is $Ω(\frac{\log r}{\log \log r})$ when $ε= 1/2$. No previous satisfactory lower bound in terms of $r$ was known. * We completely characterise query complexity of this problem in terms of $n$ for smaller values of $ε$. The complexity is $Θ(ε^{-1} \log (εn))$. Apart from giving the lower bound, this improves on the best known upper bound. Finally, we give an alternative proof of the $Ω(ε^{-1}d\log n - ε^{-1}\logε^{-1})$ lower bound for testing monotonicity on the hypergrid $[n]^d$ due to Chakrabarty and Seshadhri (RANDOM'13).
Relational Equivalence Proofs Between Imperative and MapReduce Algorithms
Venue: arXiv cs.LO 2018
Year: 2018

MapReduce frameworks are widely used for the implementation of distributed algorithms. However, translating imperative algorithms into these frameworks requires significant structural changes to the algorithm. As the costs of running faulty algorithms at scale can be severe, it is highly desirable to verify the correctness of the translation, i.e., to prove that the MapReduce version is equivalent to the imperative original. We present a novel approach for proving equivalence between imperative and MapReduce algorithms based on partitioning the equivalence proof into a sequence of equivalence proofs between intermediate programs with smaller differences. Our approach is based on the insight that two kinds of sub-proofs are required: (1) uniform transformations changing the controlflow structure that are mostly independent of the particular context in which they are applied; and (2) context-dependent transformations that are not uniform but that preserve the overall structure and can be proved correct using coupling invariants. We demonstrate the feasibility of our approach by evaluating it on two prototypical algorithms commonly used as examples in MapReduce frameworks: k-means and PageRank. To carry out the proofs, we use the interactive theorem prover Coq with partial proof automation. The results show that our approach and its prototypical implementation based on Coq enables equivalence proofs of non-trivial algorithms and could be automated to a large degree.
Characterizing Docker Overhead in Mobile Edge Computing Scenarios
Venue: arXiv cs.NI 2018
Year: 2018

Mobile Edge Computing (MEC) is an emerging network paradigm that provides cloud and IT services at the point of access of the network. Such proximity to the end user translates into ultra-low latency and high bandwidth, while, at the same time, it alleviates traffic congestion in the network core. Due to the need to run servers on edge nodes (e.g., an LTE-A macro eNodeB), a key element of MEC architectures is to ensure server portability and low overhead. A possible tool that can be used for this purpose is Docker, a framework that allows easy, fast deployment of Linux containers. This paper addresses the suitability of Docker in MEC scenar- ios by quantifying the CPU consumed by Docker when running two different containerized services: multiplayer gam- ing and video streaming. Our tests, run with varying numbers of clients and servers, yield different results for the two case studies: for the gaming service, the overhead logged by Docker increases only with the number of servers; con- versely, for the video streaming case, the overhead is not affected by the number of either clients or servers.
On bounded pitch inequalities for the min-knapsack polytope
Venue: arXiv cs.DS 2018
Year: 2018

In the min-knapsack problem one aims at choosing a set of objects with minimum total cost and total profit above a given threshold. In this paper, we study a class of valid inequalities for min-knapsack known as bounded pitch inequalities, which generalize the well-known unweighted cover inequalities. While separating over pitch-1 inequalities is NP-hard, we show that approximate separation over the set of pitch-1 and pitch-2 inequalities can be done in polynomial time. We also investigate integrality gaps of linear relaxations for min-knapsack when these inequalities are added. Among other results, we show that, for any fixed $t$, the $t$-th CG closure of the natural linear relaxation has the unbounded integrality gap.
Object category learning and retrieval with weak supervision
Venue: arXiv cs.CV 2018
Year: 2018

We consider the problem of retrieving objects from image data and learning to classify them into meaningful semantic categories with minimal supervision. To that end, we propose a fully differentiable unsupervised deep clustering approach to learn semantic classes in an end-to-end fashion without individual class labeling using only unlabeled object proposals. The key contributions of our work are 1) a kmeans clustering objective where the clusters are learned as parameters of the network and are represented as memory units, and 2) simultaneously building a feature representation, or embedding, while learning to cluster it. This approach shows promising results on two popular computer vision datasets: on CIFAR10 for clustering objects, and on the more complex and challenging Cityscapes dataset for semantically discovering classes which visually correspond to cars, people, and bicycles. Currently, the only supervision provided is segmentation objectness masks, but this method can be extended to use an unsupervised objectness-based object generation mechanism which will make the approach completely unsupervised.
A Generative Approach to Zero-Shot and Few-Shot Action Recognition
Venue: arXiv cs.CV 2018
Year: 2018

We present a generative framework for zero-shot action recognition where some of the possible action classes do not occur in the training data. Our approach is based on modeling each action class using a probability distribution whose parameters are functions of the attribute vector representing that action class. In particular, we assume that the distribution parameters for any action class in the visual space can be expressed as a linear combination of a set of basis vectors where the combination weights are given by the attributes of the action class. These basis vectors can be learned solely using labeled data from the known (i.e., previously seen) action classes, and can then be used to predict the parameters of the probability distributions of unseen action classes. We consider two settings: (1) Inductive setting, where we use only the labeled examples of the seen action classes to predict the unseen action class parameters; and (2) Transductive setting which further leverages unlabeled data from the unseen action classes. Our framework also naturally extends to few-shot action recognition where a few labeled examples from unseen classes are available. Our experiments on benchmark datasets (UCF101, HMDB51 and Olympic) show significant performance improvements as compared to various baselines, in both standard zero-shot (disjoint seen and unseen classes) and generalized zero-shot learning settings.
Spectral and Energy Efficient Wireless Powered IoT Networks: NOMA or TDMA?
Venue: arXiv cs.IT 2018
Year: 2018

Wireless powered communication networks (WPCNs), where multiple energy-limited devices first harvest energy in the downlink and then transmit information in the uplink, have been envisioned as a promising solution for the future Internet-of-Things (IoT). Meanwhile, non-orthogonal multiple access (NOMA) has been proposed to improve the system spectral efficiency (SE) of the fifth-generation (5G) networks by allowing concurrent transmissions of multiple users in the same spectrum. As such, NOMA has been recently considered for the uplink of WPCNs based IoT networks with a massive number of devices. However, simultaneous transmissions in NOMA may also incur more transmit energy consumption as well as circuit energy consumption in practice which is critical for energy constrained IoT devices. As a result, compared to orthogonal multiple access schemes such as time-division multiple access (TDMA), whether the SE can be improved and/or the total energy consumption can be reduced with NOMA in such a scenario still remains unknown. To answer this question, we first derive the optimal time allocations for maximizing the SE of a TDMA-based WPCN (T-WPCN) and a NOMA-based WPCN (N-WPCN), respectively. Subsequently, we analyze the total energy consumption as well as the maximum SE achieved by these two networks. Surprisingly, it is found that N-WPCN not only consumes more energy, but also is less spectral efficient than T-WPCN. Simulation results verify our theoretical findings and unveil the fundamental performance bottleneck, i.e., "worst user bottleneck problem", in multiuser NOMA systems.
Robust Multi-subspace Analysis Using Novel Column L0-norm Constrained Matrix Factorization
Venue: arXiv cs.CV 2018
Year: 2018

We study the underlying structure of data (approximately) generated from a union of independent subspaces. Traditional methods learn only one subspace, failing to discover the multi-subspace structure, while state-of-the-art methods analyze the multi-subspace structure using data themselves as the dictionary, which cannot offer the explicit basis to span each subspace and are sensitive to errors via an indirect representation. Additionally, they also suffer from a high computational complexity, being quadratic or cubic to the sample size. To tackle all these problems, we propose a method, called Matrix Factorization with Column L0-norm constraint (MFC0), that can simultaneously learn the basis for each subspace, generate a direct sparse representation for each data sample, as well as removing errors in the data in an efficient way. Furthermore, we develop a first-order alternating direction algorithm, whose computational complexity is linear to the sample size, to stably and effectively solve the nonconvex objective function and non- smooth l0-norm constraint of MFC0. Experimental results on both synthetic and real-world datasets demonstrate that besides the superiority over traditional and state-of-the-art methods for subspace clustering, data reconstruction, error correction, MFC0 also shows its uniqueness for multi-subspace basis learning and direct sparse representation.
A Comparison of SC-FDE and UW DFT-s-OFDM for Millimeter Wave Communications
Venue: arXiv cs.IT 2018
Year: 2018

In this study, we compare the single-carrier (SC) waveform adopted in IEEE 802.11ad and unique word discrete Fourier transform spread orthogonal frequency division multiplexing (UW DFT-s-OFDM) waveform. We provide equivalent representations of up-sampling and down-sampling operations of the SC waveform by using discrete Fourier transform (DFT) and inverse DFT to enable explicit comparison of these two similar waveforms. By using this representation, we discuss why the IEEE 802.11ad SC waveform can cause suboptimal performance in multipath channel and discuss how to improve it with UW DFT-s-OFDM. With comprehensive link-level simulations, we show that replacing the 802.11ad SC waveform with UW DFT-spread OFDM can result in 1 dB gain in peak throughput without affecting the IEEE 802.11ad packet structure. We also evaluate the cross links where the transmitter is UW-DFT-s-OFDM and the receiver is traditional SC-FDE or vice versa. We demonstrate that UW DFT-s-OFDM receiver can decode an IEEE 802.11ad SC waveform with a slight SNR loss while IEEE 802.11ad SC receiver can decode a UW DFT-spread OFDM waveform with an interference floor.
Generalized Points-to Graphs: A New Abstraction of Memory in the Presence of Pointers
Venue: arXiv cs.PL 2018
Year: 2018

Flow- and context-sensitive points-to analysis is difficult to scale; for top-down approaches, the problem centers on repeated analysis of the same procedure; for bottom-up approaches, the abstractions used to represent procedure summaries have not scaled while preserving precision. We propose a novel abstraction called the Generalized Points-to Graph (GPG) which views points-to relations as memory updates and generalizes them using the counts of indirection levels leaving the unknown pointees implicit. This allows us to construct GPGs as compact representations of bottom-up procedure summaries in terms of memory updates and control flow between them. Their compactness is ensured by the following optimizations: strength reduction reduces the indirection levels, redundancy elimination removes redundant memory updates and minimizes control flow (without over-approximating data dependence between memory updates), and call inlining enhances the opportunities of these optimizations. We devise novel operations and data flow analyses for these optimizations. Our quest for scalability of points-to analysis leads to the following insight: The real killer of scalability in program analysis is not the amount of data but the amount of control flow that it may be subjected to in search of precision. The effectiveness of GPGs lies in the fact that they discard as much control flow as possible without losing precision (i.e., by preserving data dependence without over-approximation). This is the reason why the GPGs are very small even for main procedures that contain the effect of the entire program. This allows our implementation to scale to 158kLoC for C programs.
A Probabilistic Ant-based Heuristic for the Longest Simple Cycle Problem in Complex Networks
Venue: arXiv cs.SI 2018
Year: 2018

We propose a new probabilistic ant-based heuristic (ANTH-LS) for the longest simple cycle problem. This NP-hard problem has numerous real-world applications in complex networks, including efficient construction of graph layouts, analysis of social networks or bioinformatics. Our algorithm is based on reinforcing the probability of traversing the edges, which have not been present in the long cycles found so far. Experimental results are presented for a set of social networks, protein-protein interation networks, network science graphs and DIMACS graphs. For 6 out of our 22 real-world network test instances, ANTH-LS has obtained an improvement on the longest cycle ever found.
Time Constrained Continuous Subgraph Search over Streaming Graphs
Venue: arXiv cs.DB 2018
Year: 2018

The growing popularity of dynamic applications such as social networks provides a promising way to detect valuable information in real time. Efficient analysis over high-speed data from dynamic applications is of great significance. Data from these dynamic applications can be easily modeled as streaming graph. In this paper, we study the subgraph (isomorphism) search over streaming graph data that obeys timing order constraints over the occurrence of edges in the stream. We propose a data structure and algorithm to efficiently answer subgraph search and introduce optimizations to greatly reduce the space cost, and propose concurrency management to improve system throughput. Extensive experiments on real network traffic data and synthetic social streaming data confirms the efficiency and effectiveness of our solution.
Study on Energy Consumption and Coverage of Hierarchical Cooperation of Small Cell Base Stations in Heterogeneous Networks
Venue: arXiv cs.IT 2018
Year: 2018

The demand for communication services in the era of intelligent terminals is unprecedented and huge. To meet such development, modern wireless communications must provide higher quality services with higher energy efficiency in terms of system capacity and quality of service (QoS), which could be achieved by the high-speed data rate, the wider coverage and the higher band utilization. In this paper, we propose a way to offload users from a macro base station(MBS) with a hierarchical distribution of small cell base stations(SBS). The connection probability is the key indicator of the implementation of the unload operation. Furthermore, we measure the service performance of the system by finding the conditional probability-coverage probability with the certain SNR threshold as the condition, that is, the probability of obtaining the minimum communication quality when the different base stations are connected to the user. Then, user-centered total energy consumption of the system is respectively obtained when the macro base station(MBS) and the small cell base stations(SBS) serve each of the users. The simulation results show that the hierarchical SBS cooperation in heterogeneous networks can provide a higher system total coverage probability for the system with a lower overall system energy consumption than MBS.
Algebraic dependencies and PSPACE algorithms in approximative complexity
Venue: arXiv cs.CC 2018
Year: 2018

Testing whether a set $\mathbf{f}$ of polynomials has an algebraic dependence is a basic problem with several applications. The polynomials are given as algebraic circuits. Algebraic independence testing question is wide open over finite fields (Dvir, Gabizon, Wigderson, FOCS'07). The best complexity known is NP$^{\#\rm P}$ (Mittmann, Saxena, Scheiblechner, Trans.AMS'14). In this work we put the problem in AM $\cap$ coAM. In particular, dependence testing is unlikely to be NP-hard and joins the league of problems of "intermediate" complexity, eg. graph isomorphism & integer factoring. Our proof method is algebro-geometric-- estimating the size of the image/preimage of the polynomial map $\mathbf{f}$ over the finite field. A gap in this size is utilized in the AM protocols. Next, we study the open question of testing whether every annihilator of $\mathbf{f}$ has zero constant term (Kayal, CCC'09). We give a geometric characterization using Zariski closure of the image of $\mathbf{f}$; introducing a new problem called approximate polynomials satisfiability (APS). We show that APS is NP-hard and, using projective algebraic-geometry ideas, we put APS in PSPACE (prior best was EXPSPACE via Grobner basis computation). As an unexpected application of this to approximative complexity theory we get-- Over any field, hitting-set for $\overline{\rm VP}$ can be designed in PSPACE. This solves an open problem posed in (Mulmuley, FOCS'12, J.AMS 2017); greatly mitigating the GCT Chasm (exponentially in terms of space complexity).
A Survey on Behavioral Biometric Authentication on Smartphones
Venue: arXiv cs.CR 2018
Year: 2018

Recent research has shown the possibility of using smartphones' sensors and accessories to extract some behavioral attributes such as touch dynamics, keystroke dynamics and gait recognition. These attributes are known as behavioral biometrics and could be used to verify or identify users implicitly and continuously on smartphones. The authentication systems that have been built based on these behavioral biometric traits are known as active or continuous authentication systems. This paper provides a review of the active authentication systems. We present the components and the operating process of the active authentication systems in general, followed by an overview of the state-of-the-art behavioral biometric traits that used to develop an active authentication systems and their evaluation on smartphones. We discuss the issues, strengths and limitations that associated with each behavioral biometric trait. Also, we introduce a comparative summary between them. Finally, challenges and open research problems are presented in this research field.
Safeguarding Millimeter Wave Communications Against Randomly Located Eavesdroppers
Venue: arXiv cs.IT 2018
Year: 2018

Millimeter wave offers a sensible solution to the capacity crunch faced by 5G wireless communications. This paper comprehensively studies physical layer security in a multi-input single-output (MISO) millimeter wave system where multiple single-antenna eavesdroppers are randomly located. Concerning the specific propagation characteristics of millimeter wave, we investigate two secure transmission schemes, namely maximum ratio transmitting (MRT) beamforming and artificial noise (AN) beamforming. Specifically, we first derive closed-form expressions of the connection probability for both schemes. We then analyze the secrecy outage probability (SOP) in both non-colluding eavesdroppers and colluding eavesdroppers scenarios. Also, we maximize the secrecy throughput under a SOP constraint, and obtain optimal transmission parameters, especially the power allocation between AN and the information signal for AN beamforming. Numerical results are provided to verify our theoretical analysis. We observe that the density of eavesdroppers, the spatially resolvable paths of the destination and eavesdroppers all contribute to the secrecy performance and the parameter design of millimeter wave systems.
Multichannel Sound Event Detection Using 3D Convolutional Neural Networks for Learning Inter-channel Features
Venue: arXiv cs.SD 2018
Year: 2018

In this paper, we propose a stacked convolutional and recurrent neural network (CRNN) with a 3D convolutional neural network (CNN) in the first layer for the multichannel sound event detection (SED) task. The 3D CNN enables the network to simultaneously learn the inter- and intra-channel features from the input multichannel audio. In order to evaluate the proposed method, multichannel audio datasets with different number of overlapping sound sources are synthesized. Each of this dataset has a four-channel first-order Ambisonic, binaural, and single-channel versions, on which the performance of SED using the proposed method are compared to study the potential of SED using multichannel audio. A similar study is also done with the binaural and single-channel versions of the real-life recording TUT-SED 2017 development dataset. The proposed method learns to recognize overlapping sound events from multichannel features faster and performs better SED with a fewer number of training epochs. The results show that on using multichannel Ambisonic audio in place of single-channel audio we improve the overall F-score by 7.5%, overall error rate by 10% and recognize 15.6% more sound events in time frames with four overlapping sound sources.
Optical Network Programmability - Requirements and Applications
Venue: arXiv cs.NI 2018
Year: 2018

Datacenter operators and internet content providers require optical network programmability to efficiently interconnect distributed datacenters. This paper describes the requirements, applications and use cases for optical network programmability. Based on application scenarios, open northbound APIs with different levels of control and abstraction to address different network operator requirements which are defined. For their illustration, use cases for optical network programmability show current research directions.