OpenRaiser/Intern-Atlas huggingface dataset:
Coding for Arbitrarily Varying Remote Sources
Venue: arXiv cs.IT 2017
Year: 2017

We study a lossy source coding problem for a memoryless remote source. The source data is broadcast over an arbitrarily varying channel (AVC) controlled by an adversary. One output of the AVC is received as input at the encoder, and another output is received as side information at the decoder. The adversary is assumed to know the source data non-causally, and can employ randomized jamming strategies arbitrarily correlated to the source data. The decoder reconstructs the source data from the encoded message and the side information. We prove upper and lower bounds on the adversarial rate distortion function for the source under randomized coding. Furthermore, we present some interesting special cases of our general setup where the above bounds coincide, and thus, provide their complete rate distortion function characterization.
Succinct Approximate Rank Queries
Venue: arXiv cs.DS 2017
Year: 2017

We consider the problem of summarizing a multi set of elements in $\{1, 2, \ldots , n\}$ under the constraint that no element appears more than $\ell$ times. The goal is then to answer \emph{rank} queries --- given $i\in\{1, 2, \ldots , n\}$, how many elements in the multi set are smaller than $i$? --- with an additive error of at most $Δ$ and in constant time. For this problem, we prove a lower bound of $\mathcal B_{\ell,n,Δ}\triangleq$ $\left\lfloor{\frac{n}{\left\lceil{Δ/ \ell}\right\rceil}}\right\rfloor $ $\log\big({\max\{\left\lfloor{\ell / Δ}\right\rfloor,1\} + 1}\big)$ bits and provide a \emph{succinct} construction that uses $\mathcal B_{\ell,n,Δ}(1+o(1))$ bits. Next, we generalize our data structure to support processing of a stream of integers in $\{0,1,\ldots,\ell\}$, where upon a query for some $i\le n$ we provide a $Δ$-additive approximation for the sum of the \emph{last} $i$ elements. We show that this too can be done using $\mathcal B_{\ell,n,Δ}(1+o(1))$ bits and in constant time. This yields the first sub linear space algorithm that computes approximate sliding window sums in $O(1)$ time, where the window size is given at the query time; additionally, it requires only $(1+o(1))$ more space than is needed for a fixed window size.
User Profile Based Research Paper Recommendation
Venue: arXiv cs.IR 2017
Year: 2017

We design a recommender system for research papers based on topic-modeling. The users feedback to the results is used to make the results more relevant the next time they fire a query. The user's needs are understood by observing the change in the themes that the user shows a preference for over time.
Sub-string/Pattern Matching in Sub-linear Time Using a Sparse Fourier Transform Approach
Venue: arXiv cs.IT 2017
Year: 2017

We consider the problem of querying a string (or, a database) of length $N$ bits to determine all the locations where a substring (query) of length $M$ appears either exactly or is within a Hamming distance of $K$ from the query. We assume that sketches of the original signal can be computed off line and stored. Using the sparse Fourier transform computation based approach introduced by Pawar and Ramchandran, we show that all such matches can be determined with high probability in sub-linear time. Specifically, if the query length $M = O(N^μ)$ and the number of matches $L=O(N^λ)$, we show that for $λ< 1-μ$ all the matching positions can be determined with a probability that approaches 1 as $N \rightarrow \infty$ for $K \leq \frac{1}{6}M$. More importantly our scheme has a worst-case computational complexity that is only $O\left(\max\{N^{1-μ}\log^2 N, N^{μ+λ}\log N \}\right)$, which means we can recover all the matching positions in {\it sub-linear} time for $λ<1-μ$. This is a substantial improvement over the best known computational complexity of $O\left(N^{1-0.359 μ} \right)$ for recovering one matching position by Andoni {\em et al.} \cite{andoni2013shift}. Further, the number of Fourier transform coefficients that need to be computed, stored and accessed, i.e., the sketching complexity of this algorithm is only $O\left(N^{1-μ}\log N\right)$. Several extensions of the main theme are also discussed.
Generalized subspace subcodes with application in cryptology
Venue: arXiv cs.CR 2017
Year: 2017

Most of the codes that have an algebraic decoding algorithm are derived from the Reed Solomon codes. They are obtained by taking equivalent codes, for example the generalized Reed Solomon codes, or by using the so-called subfield subcode method, which leads to Alternant codes and Goppa codes over the underlying prime field, or over some intermediate subfield. The main advantages of these constructions is to preserve both the minimum distance and the decoding algorithm of the underlying Reed Solomon code. In this paper, we propose a generalization of the subfield subcode construction by introducing the notion of subspace subcodes and a generalization of the equivalence of codes which leads to the notion of generalized subspace subcodes. When the dimension of the selected subspaces is equal to one, we show that our approach gives exactly the family of the codes obtained by equivalence and subfield subcode technique. However, our approach highlights the links between the subfield subcode of a code defined over an extension field and the operation of puncturing the $q$-ary image of this code. When the dimension of the subspaces is greater than one, we obtain codes whose alphabet is no longer a finite field, but a set of r-uples. We explain why these codes are practically as efficient for applications as the codes defined on an extension of degree r. In addition, they make it possible to obtain decodable codes over a large alphabet having parameters previously inaccessible. As an application, we give some examples that can be used in public key cryptosystems such as McEliece.
Explaining How a Deep Neural Network Trained with End-to-End Learning Steers a Car
Venue: arXiv cs.CV 2017
Year: 2017

As part of a complete software stack for autonomous driving, NVIDIA has created a neural-network-based system, known as PilotNet, which outputs steering angles given images of the road ahead. PilotNet is trained using road images paired with the steering angles generated by a human driving a data-collection car. It derives the necessary domain knowledge by observing human drivers. This eliminates the need for human engineers to anticipate what is important in an image and foresee all the necessary rules for safe driving. Road tests demonstrated that PilotNet can successfully perform lane keeping in a wide variety of driving conditions, regardless of whether lane markings are present or not. The goal of the work described here is to explain what PilotNet learns and how it makes its decisions. To this end we developed a method for determining which elements in the road image most influence PilotNet's steering decision. Results show that PilotNet indeed learns to recognize relevant objects on the road. In addition to learning the obvious features such as lane markings, edges of roads, and other cars, PilotNet learns more subtle features that would be hard to anticipate and program by engineers, for example, bushes lining the edge of the road and atypical vehicle classes.
A Robust Utility Learning Framework via Inverse Optimization
Venue: arXiv cs.GT 2017
Year: 2017

In many smart infrastructure applications flexibility in achieving sustainability goals can be gained by engaging end-users. However, these users often have heterogeneous preferences that are unknown to the decision-maker tasked with improving operational efficiency. Modeling user interaction as a continuous game between non-cooperative players, we propose a robust parametric utility learning framework that employs constrained feasible generalized least squares estimation with heteroskedastic inference. To improve forecasting performance, we extend the robust utility learning scheme by employing bootstrapping with bagging, bumping, and gradient boosting ensemble methods. Moreover, we estimate the noise covariance which provides approximated correlations between players which we leverage to develop a novel correlated utility learning framework. We apply the proposed methods both to a toy example arising from Bertrand-Nash competition between two firms as well as to data from a social game experiment designed to encourage energy efficient behavior amongst smart building occupants. Using occupant voting data for shared resources such as lighting, we simulate the game defined by the estimated utility functions to demonstrate the performance of the proposed methods.
Joint Hybrid Precoder and Combiner Design for mmWave Spatial Multiplexing Transmission
Venue: arXiv cs.IT 2017
Year: 2017

Millimeter-wave (mmWave) communications have been considered as a key technology for future 5G wireless networks because of the orders-of-magnitude wider bandwidth than current cellular bands. In this paper, we consider the problem of codebook-based joint analog-digital hybrid precoder and combiner design for spatial multiplexing transmission in a mmWave multiple-input multiple-output (MIMO) system. We propose to jointly select analog precoder and combiner pair for each data stream successively aiming at maximizing the channel gain while suppressing the interference between different data streams. After all analog precoder/combiner pairs have been determined, we can obtain the effective baseband channel. Then, the digital precoder and combiner are computed based on the obtained effective baseband channel to further mitigate the interference and maximize the sum-rate. Simulation results demonstrate that our proposed algorithm exhibits prominent advantages in combating interference between different data streams and offer satisfactory performance improvement compared to the existing codebook-based hybrid beamforming schemes.
Towards Estimating the Upper Bound of Visual-Speech Recognition: The Visual Lip-Reading Feasibility Database
Venue: arXiv cs.CV 2017
Year: 2017

Speech is the most used communication method between humans and it involves the perception of auditory and visual channels. Automatic speech recognition focuses on interpreting the audio signals, although the video can provide information that is complementary to the audio. Exploiting the visual information, however, has proven challenging. On one hand, researchers have reported that the mapping between phonemes and visemes (visual units) is one-to-many because there are phonemes which are visually similar and indistinguishable between them. On the other hand, it is known that some people are very good lip-readers (e.g: deaf people). We study the limit of visual only speech recognition in controlled conditions. With this goal, we designed a new database in which the speakers are aware of being read and aim to facilitate lip-reading. In the literature, there are discrepancies on whether hearing-impaired people are better lip-readers than normal-hearing people. Then, we analyze if there are differences between the lip-reading abilities of 9 hearing-impaired and 15 normal-hearing people. Finally, human abilities are compared with the performance of a visual automatic speech recognition system. In our tests, hearing-impaired participants outperformed the normal-hearing participants but without reaching statistical significance. Human observers were able to decode 44% of the spoken message. In contrast, the visual only automatic system achieved 20% of word recognition rate. However, if we repeat the comparison in terms of phonemes both obtained very similar recognition rates, just above 50%. This suggests that the gap between human lip-reading and automatic speech-reading might be more related to the use of context than to the ability to interpret mouth appearance.
Hybrid Procoder and Combiner Design for Secure Transmission in mmWave MIMO Systems
Venue: arXiv cs.IT 2017
Year: 2017

Millimeter wave (mmWave) communications have been considered as a key technology for future 5G wireless networks. In order to overcome the severe propagation loss of mmWave channel, mmWave multiple-input multiple-output (MIMO) systems with analog/digital hybrid precoding and combining transceiver architecture have been widely considered. However, physical layer security (PLS) in mmWave MIMO systems and the secure hybrid beamformer design have not been well investigated. In this paper, we consider the problem of hybrid precoder and combiner design for secure transmission in mmWave MIMO systems in order to protect the legitimate transmission from eavesdropping. When eavesdropper's channel state information (CSI) is known, we first propose a joint analog precoder and combiner design algorithm which can prevent the information leakage to the eavesdropper. Then, the digital precoder and combiner are computed based on the obtained effective baseband channel to further maximize the secrecy rate. Next, if prior knowledge of the eavesdropper's CSI is unavailable, we develop an artificial noise (AN)-based hybrid beamforming approach, which can jam eavesdropper's reception while maintaining the quality-of-service (QoS) of intended receiver at the pre-specified level. Simulation results demonstrate that our proposed algorithms offer significant secrecy performance improvement compared with other hybrid beamforming algorithms.
Where, When, and How mmWave is Used in 5G and Beyon
Venue: arXiv cs.NI 2017
Year: 2017

Wireless engineers and business planners commonly raise the question on where, when, and how millimeter-wave (mmWave) will be used in 5G and beyond. Since the next generation network is not just a new radio access standard, but instead an integration of networks for vertical markets with diverse applications, answers to the question depend on scenarios and use cases to be deployed. This paper gives four 5G mmWave deployment examples and describes in chronological order the scenarios and use cases of their probable deployment, including expected system architectures and hardware prototypes. The paper starts with 28 GHz outdoor backhauling for fixed wireless access and moving hotspots, which will be demonstrated at the PyeongChang winter Olympic games in 2018. The second deployment example is a 60 GHz unlicensed indoor access system at the Tokyo-Narita airport, which is combined with Mobile Edge Computing (MEC) to enable ultra-high speed content download with low latency. The third example is mmWave mesh network to be used as a micro Radio Access Network (μ-RAN), for cost-effective backhauling of small-cell Base Stations (BSs) in dense urban scenarios. The last example is mmWave based Vehicular-to-Vehicular (V2V) and Vehicular-to-Everything (V2X) communications system, which enables automated driving by exchanging High Definition (HD) dynamic map information between cars and Roadside Units (RSUs). For 5G and beyond, mmWave and MEC will play important roles for a diverse set of applications that require both ultra-high data rate and low latency communications.
Coverage and Rate Analysis of Super Wi-Fi Networks Using Stochastic Geometry
Venue: arXiv cs.IT 2017
Year: 2017

Recent regulatory changes proposed by the Federal Communications Commission (FCC) permitting unlicensed use of television white space (TVWS) channels present new opportunities for designing wireless networks that make efficient use of this spectrum. The favorable propagation characteristics of these channels and their widespread availability, especially in rural areas, make them well-suited for providing broadband services in sparsely populated regions where economic factors hinder deployment of such services on licensed spectrum. In this context, this paper explores the deployment of an outdoor Wi-Fi-like network operating in TVWS channels, referred to commonly as a Super Wi-Fi network. Since regulations governing unlicensed use of these channels allow (a) mounting fixed devices up to a height of 30 m and operation at transmit powers of up to 4 W EIRP, and (b) operation at transmit powers of up to 100 mW EIRP for portable devices, such networks can provide extended coverage and higher rates than traditional Wi-Fi networks. However, these gains are subject to the viability of the uplink from the portable devices (clients) to the fixed devices (access points (AP)) because of tighter restrictions on transmit power of clients compared to APs. This paper leverages concepts from stochastic geometry to study the performance of such networks with specific focus on the effect of (a) transmit power asymmetry between APs and clients and its impact on uplink viability and coverage, and (b) the interplay between height and transmit power of APs in determining the network throughput. Such an analysis reveals that (a) maximum coverage of no more than 700 m is obtained even when APs are deployed at 30 m height, and (b) operating APs at transmit power of more than 1 W is beneficial only at sparse deployment densities when rate is prioritized over coverage.
Decremental Data Structures for Connectivity and Dominators in Directed Graphs
Venue: arXiv cs.DS 2017
Year: 2017

We introduce a new dynamic data structure for maintaining the strongly connected components (SCCs) of a directed graph (digraph) under edge deletions, so as to answer a rich repertoire of connectivity queries. Our main technical contribution is a decremental data structure that supports sensitivity queries of the form "are $ u $ and $ v $ strongly connected in the graph $ G \setminus w $?", for any triple of vertices $ u, v, w $, while $ G $ undergoes deletions of edges. Our data structure processes a sequence of edge deletions in a digraph with $n$ vertices in $O(m n \log{n})$ total time and $O(n^2 \log{n})$ space, where $m$ is the number of edges before any deletion, and answers the above queries in constant time. We can leverage our data structure to obtain decremental data structures for many more types of queries within the same time and space complexity. For instance for edge-related queries, such as testing whether two query vertices $u$ and $v$ are strongly connected in $G \setminus e$, for some query edge $e$. As another important application of our decremental data structure, we provide the first nontrivial algorithm for maintaining the dominator tree of a flow graph under edge deletions. We present an algorithm that processes a sequence of edge deletions in a flow graph in $O(m n \log{n})$ total time and $O(n^2 \log{n})$ space. For reducible flow graphs we provide an $O(mn)$-time and $O(m + n)$-space algorithm. We give a conditional lower bound that provides evidence that these running times may be tight up to subpolynomial factors.
The Complexity of Computing a Robust Flow
Venue: arXiv cs.DM 2017
Year: 2017

Robust network flows are a concept for dealing with uncertainty and unforeseen failures in the network infrastructure. They and their dual counterpart, network flow interdiction, have received steady attention within the operations research community over the past years. One of the most basic models is the Maximum Robust Flow Problem: Given a network and an integer k, the task is to find a path flow of maximum robust value, i.e., the guaranteed value of surviving flow after removal of any k arcs in the network. The complexity of this problem appeared to have been settled almost a decade ago: Aneja et al. (2001) showed that the problem can be solved efficiently when k = 1, while an article by Du and Chandrasekaran (2007) established that the problem is NP-hard for any constant value of k larger than 1. We point to a flaw in the proof of the latter result, leaving the complexity for constant k open once again. For the case that k is not bounded by a constant, we present a new hardness proof, establishing that the problem is strongly NP-hard, even when only two different capacity values occur and the number of paths is polynomial in the size of the input. We further show that computing optimal integral solutions is already NP-hard for k = 2 (whereas for k=1, an efficient algorithm is known) and give a positive result for the case that capacities are in {1, 2}.
Exploring the Performance Benefit of Hybrid Memory System on HPC Environments
Venue: arXiv cs.DC 2017
Year: 2017

Hardware accelerators have become a de-facto standard to achieve high performance on current supercomputers and there are indications that this trend will increase in the future. Modern accelerators feature high-bandwidth memory next to the computing cores. For example, the Intel Knights Landing (KNL) processor is equipped with 16 GB of high-bandwidth memory (HBM) that works together with conventional DRAM memory. Theoretically, HBM can provide 5x higher bandwidth than conventional DRAM. However, many factors impact the effective performance achieved by applications, including the application memory access pattern, the problem size, the threading level and the actual memory configuration. In this paper, we analyze the Intel KNL system and quantify the impact of the most important factors on the application performance by using a set of applications that are representative of scientific and data-analytics workloads. Our results show that applications with regular memory access benefit from MCDRAM, achieving up to 3x performance when compared to the performance obtained using only DRAM. On the contrary, applications with random memory access pattern are latency-bound and may suffer from performance degradation when using only MCDRAM. For those applications, the use of additional hardware threads may help hide latency and achieve higher aggregated bandwidth when using HBM.
An Improved Bound for Minimizing the Total Weighted Completion Time of Coflows in Datacenters
Venue: arXiv cs.DS 2017
Year: 2017

In data-parallel computing frameworks, intermediate parallel data is often produced at various stages which needs to be transferred among servers in the datacenter network (e.g. the shuffle phase in MapReduce). A stage often cannot start or be completed unless all the required data pieces from the preceding stage are received. \emph{Coflow} is a recently proposed networking abstraction to capture such communication patterns. We consider the problem of efficiently scheduling coflows with release dates in a shared datacenter network so as to minimize the total weighted completion time of coflows. Several heuristics have been proposed recently to address this problem, as well as a few polynomial-time approximation algorithms with provable performance guarantees. Our main result in this paper is a polynomial-time deterministic algorithm that improves the prior known results. Specifically, we propose a deterministic algorithm with approximation ratio of $5$, which improves the prior best known ratio of $12$. For the special case when all coflows are released at time zero, our deterministic algorithm obtains approximation ratio of $4$ which improves the prior best known ratio of $8$. The key ingredient of our approach is an improved linear program formulation for sorting the coflows followed by a simple list scheduling policy. Extensive simulation results, using both synthetic and real traffic traces, are presented that verify the performance of our algorithm and show improvement over the prior approaches.
A New Type of Neurons for Machine Learning
Venue: arXiv cs.NE 2017
Year: 2017

In machine learning, the use of an artificial neural network is the mainstream approach. Such a network consists of layers of neurons. These neurons are of the same type characterized by the two features: (1) an inner product of an input vector and a matching weighting vector of trainable parameters and (2) a nonlinear excitation function. Here we investigate the possibility of replacing the inner product with a quadratic function of the input vector, thereby upgrading the 1st order neuron to the 2nd order neuron, empowering individual neurons, and facilitating the optimization of neural networks. Also, numerical examples are provided to illustrate the feasibility and merits of the 2nd order neurons. Finally, further topics are discussed.