OpenRaiser/Intern-Atlas huggingface dataset:
On the Bit Complexity of Sum-of-Squares Proofs
Venue: arXiv cs.CC 2017
Year: 2017

It has often been claimed in recent papers that one can find a degree d Sum-of-Squares proof if one exists via the Ellipsoid algorithm. In [O17], Ryan O'Donnell notes this widely quoted claim is not necessarily true. He presents an example of a polynomial system with bounded coeffcients that admits low-degree proofs of non-negativity, but these proofs necessarily involve numbers with an exponential number of bits, causing the Ellipsoid algorithm to take exponential time. In this paper we obtain both positive and negative results on the bit complexity of SoS proofs. First, we propose a suffcient condition on a polynomial system that implies a bound on the coefficients in an SoS proof. We demonstrate that this sufficient condition is applicable for common use-cases of the SoS algorithm, such as Max-CSP, Balanced Separator, Max- Clique, Max-Bisection, and Unit-Vector constraints. On the negative side, O'Donnell asked whether every polynomial system containing Boolean constraints admits proofs of polynomial bit complexity. We answer this question in the negative, giving a counterexample system and non-negative polynomial which has degree two SoS proofs, but no SoS proof with small coefficients until degree Omega(sqrt(n))
Direct Estimation of Information Divergence Using Nearest Neighbor Ratios
Venue: arXiv cs.IT 2017
Year: 2017

We propose a direct estimation method for Rényi and f-divergence measures based on a new graph theoretical interpretation. Suppose that we are given two sample sets $X$ and $Y$, respectively with $N$ and $M$ samples, where $η:=M/N$ is a constant value. Considering the $k$-nearest neighbor ($k$-NN) graph of $Y$ in the joint data set $(X,Y)$, we show that the average powered ratio of the number of $X$ points to the number of $Y$ points among all $k$-NN points is proportional to Rényi divergence of $X$ and $Y$ densities. A similar method can also be used to estimate f-divergence measures. We derive bias and variance rates, and show that for the class of $γ$-Hölder smooth functions, the estimator achieves the MSE rate of $O(N^{-2γ/(γ+d)})$. Furthermore, by using a weighted ensemble estimation technique, for density functions with continuous and bounded derivatives of up to the order $d$, and some extra conditions at the support set boundary, we derive an ensemble estimator that achieves the parametric MSE rate of $O(1/N)$. Our estimators are more computationally tractable than other competing estimators, which makes them appealing in many practical applications.
Intelligent User Interfaces - A Tutorial
Venue: arXiv cs.HC 2017
Year: 2017

IUIs aim to incorporate intelligent automated capabilities in human computer interaction, where the net impact is a human-computer interaction that improves performance or usability in critical ways. It also involves designing and implementing an artificial intelligence (AI) component that effectively leverages human skills and capabilities, so that human performance with an application excels. IUIs embody capabilities that have traditionally been associated more strongly with humans than with computers: how to perceive, interpret, learn, use language, reason, plan, and decide.
Magnetic MIMO Signal Processing and Optimization for Wireless Power Transfer
Venue: arXiv cs.IT 2017
Year: 2017

In magnetic resonant coupling (MRC) enabled multiple-input multiple-output (MIMO) wireless power transfer (WPT) systems, multiple transmitters (TXs) each with one single coil are used to enhance the efficiency of simultaneous power transfer to multiple single-coil receivers (RXs) by constructively combining their induced magnetic fields at the RXs, a technique termed "magnetic beamforming". In this paper, we study the optimal magnetic beamforming design in a multi-user MIMO MRC-WPT system. We introduce the multi-user power region that constitutes all the achievable power tuples for all RXs, subject to the given total power constraint over all TXs as well as their individual peak voltage and current constraints. We characterize each boundary point of the power region by maximizing the sum-power deliverable to all RXs subject to their minimum harvested power constraints. For the special case without the TX peak voltage and current constraints, we derive the optimal TX current allocation for the single-RX setup in closed-form as well as that for the multi-RX setup. In general, the problem is a non-convex quadratically constrained quadratic programming (QCQP), which is difficult to solve. For the case of one single RX, we show that the semidefinite relaxation (SDR) of the problem is tight. For the general case with multiple RXs, based on SDR we obtain two approximate solutions by applying time-sharing and randomization, respectively. Moreover, for practical implementation of magnetic beamforming, we propose a novel signal processing method to estimate the magnetic MIMO channel due to the mutual inductances between TXs and RXs. Numerical results show that our proposed magnetic channel estimation and adaptive beamforming schemes are practically effective, and can significantly improve the power transfer efficiency and multi-user performance trade-off in MIMO MRC-WPT systems.
Theory and Experiment for Wireless-Powered Sensor Networks: How to Keep Sensors Alive
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we investigate a multi-node multi-antenna wireless-powered sensor networks (WPSN) comprised of one power beacon and multiple sensor nodes. We have implemented a real-life multi-node multi-antenna WPSN testbed that operates in real time. We propose a beam-splitting beamforming technique that enables a power beacon to split microwave energy beams towards multiple nodes for simultaneous charging. We experimentally demonstrate that the beam-splitting beamforming technique achieves the Pareto optimality. For a perpetual operation of the sensor nodes, we adopt an energy neutral control algorithm that keeps a sensor node alive by balancing the harvested and the consumed power. The joint beam-splitting and energy neutral control algorithm is designed by means of the Lyapunov optimization technique. By experiments, we have shown that the proposed algorithm can successfully keep all sensor nodes alive by optimally splitting energy beams towards multiple sensor nodes.
Hierarchy Influenced Differential Evolution: A Motor Operation Inspired Approach
Venue: arXiv cs.NE 2017
Year: 2017

Operational maturity of biological control systems have fuelled the inspiration for a large number of mathematical and logical models for control, automation and optimisation. The human brain represents the most sophisticated control architecture known to us and is a central motivation for several research attempts across various domains. In the present work, we introduce an algorithm for mathematical optimisation that derives its intuition from the hierarchical and distributed operations of the human motor system. The system comprises global leaders, local leaders and an effector population that adapt dynamically to attain global optimisation via a feedback mechanism coupled with the structural hierarchy. The hierarchical system operation is distributed into local control for movement and global controllers that facilitate gross motion and decision making. We present our algorithm as a variant of the classical Differential Evolution algorithm, introducing a hierarchical crossover operation. The discussed approach is tested exhaustively on standard test functions as well as the CEC 2017 benchmark. Our algorithm significantly outperforms various standard algorithms as well as their popular variants as discussed in the results.
Universal Spatiotemporal Sampling Sets for Discrete Spatially Invariant Evolution Systems
Venue: arXiv cs.IT 2017
Year: 2017

Let $(I,+)$ be a finite abelian group and $\mathbf{A}$ be a circular convolution operator on $\ell^2(I)$. The problem under consideration is how to construct minimal $Ω\subset I$ and $l_i$ such that $Y=\{\mathbf{e}_i, \mathbf{A}\mathbf{e}_i, \cdots, \mathbf{A}^{l_i}\mathbf{e}_i: i\in Ω\}$ is a frame for $\ell^2(I)$, where $\{\mathbf{e}_i: i\in I\}$ is the canonical basis of $\ell^2(I)$. This problem is motivated by the spatiotemporal sampling problem in discrete spatially invariant evolution systems. We will show that the cardinality of $Ω$ should be at least equal to the largest geometric multiplicity of eigenvalues of $\mathbf{A}$, and we consider the universal spatiotemporal sampling sets $(Ω, l_i)$ for convolution operators $\mathbf{A}$ with eigenvalues subject to the same largest geometric multiplicity. We will give an algebraic characterization for such sampling sets and show how this problem is linked with sparse signal processing theory and polynomial interpolation theory.
An Overflow Problem in Network Coding for Secure Cloud Storage
Venue: arXiv cs.CR 2017
Year: 2017

In this paper we define the overflow problem of a network coding storage system in which the encoding parameter and the storage parameter are mismatched. Through analyses and experiments, we first show the impacts of the overflow problem in a network coding scheme, which not only waste storage spaces, but also degrade coding efficiency. To avoid the overflow problem, we then develop the network coding based secure storage (NCSS) scheme. Thanks to considering both security and storage requirements in encoding procedures and distributed architectures, the NCSS can improve the performance of a cloud storage system from both the aspects of storage cost and coding processing time. We analyze the maximum allowable stored encoded data under the perfect secrecy criterion, and provide the design guidelines for the secure cloud storage system to enhance coding efficiency and achieve the minimal storage cost.
Theorem Proving Based on Semantics of DNA Strand Graph
Venue: arXiv cs.AI 2017
Year: 2017

Because of several technological limitations of traditional silicon based computing, for past few years a paradigm shift, from silicon to carbon, is occurring in computational world. DNA computing has been considered to be quite promising in solving computational and reasoning problems by using DNA strands. Resolution, an important aspect of automated theorem proving and mathematical logic, is a rule of inference which leads to proof by contradiction technique for sentences in propositional logic and first-order logic. This can also be called refutation theorem-proving. In this paper we have shown how the theorem proving with resolution refutation by DNA computation can be represented by the semantics of process calculus and strand graph.
Degrees of Freedom in Cached MIMO Relay Networks With Multiple Base Stations
Venue: arXiv cs.IT 2017
Year: 2017

The ability of physical layer relay caching to increase the degrees of freedom (DoF) of a single cell was recently illustrated. In this paper, we extend this result to the case of multiple cells in which a caching relay is shared among multiple non-cooperative base stations (BSs). In particular, we show that a large DoF gain can be achieved by exploiting the benefits of having a shared relay that cooperates with the BSs. We first propose a cache-assisted relaying protocol that improves the cooperation opportunity between the BSs and the relay. Next, we consider the cache content placement problem that aims to design the cache content at the relay such that the DoF gain is maximized. We propose an optimal algorithm and a near-optimal low-complexity algorithm for the cache content placement problem. Simulation results show significant improvement in the DoF gain using the proposed relay-caching protocol.
Verifying Digital Systems with MATLAB
Venue: arXiv cs.SY 2017
Year: 2017

A MATLAB toolbox is presented, with the goal of checking occurrences of design errors typically found in fixed-point digital systems, considering finite word-length effects. In particular, the present toolbox works as a front-end to a recently introduced verification tool, known as Digital-System Verifier, and checks overflow, limit cycle, quantization, stability, and minimum phase errors, in digital systems represented by transfer-function and state-space equations. It provides a command-line version, with simplified access to specific functions, and a graphical-user interface, which was developed as a MATLAB application. The resulting toolbox is important for the verification community, since it shows the applicability of verification to real-world systems.
Approximation Algorithms for Independence and Domination on B$_1$-VPG and B$_1$-EPG Graphs
Venue: arXiv cs.CG 2017
Year: 2017

A graph $G$ is called B$_k$-VPG (resp., B$_k$-EPG), for some constant $k\geq 0$, if it has a string representation on a grid such that each vertex is an orthogonal path with at most $k$ bends and two vertices are adjacent in $G$ if and only if the corresponding strings intersect (resp., the corresponding strings share at least one grid edge). If two adjacent strings of a B$_k$-VPG graph intersect exactly once, then the graph is called a one-string B$_k$-VPG graph. In this paper, we study the Maximum Independent Set and Minimum Dominating Set problems on B$_1$-VPG and B$_1$-EPG graphs. We first give a simple $O(\log n)$-approximation algorithm for the Maximum Independent Set problem on B$_1$-VPG graphs, improving the previous $O((\log n)^2)$-approximation algorithm of Lahiri et al. (COCOA 2015). Then, we consider the Minimum Dominating Set problem. We give an $O(1)$-approximation algorithm for this problem on one-string B$_1$-VPG graphs, providing the first constant-factor approximation algorithm for this problem. Moreover, we show that the Minimum Dominating Set problem is APX-hard on B$_1$-EPG graphs, ruling out the possibility of a PTAS unless P=NP. Finally, we give constant-factor approximation algorithms for this problem on two non-trivial subclasses of B$_1$-EPG graphs. To our knowledge, these are the first results for the Minimum Dominating Set problem on B$_1$-EPG graphs, partially answering a question posed by Epstein et al. (WADS 2013).
Online Robust Principal Component Analysis with Change Point Detection
Venue: arXiv cs.LG 2017
Year: 2017

Robust PCA methods are typically batch algorithms which requires loading all observations into memory before processing. This makes them inefficient to process big data. In this paper, we develop an efficient online robust principal component methods, namely online moving window robust principal component analysis (OMWRPCA). Unlike existing algorithms, OMWRPCA can successfully track not only slowly changing subspace but also abruptly changed subspace. By embedding hypothesis testing into the algorithm, OMWRPCA can detect change points of the underlying subspaces. Extensive simulation studies demonstrate the superior performance of OMWRPCA compared with other state-of-art approaches. We also apply the algorithm for real-time background subtraction of surveillance video.
Polynomial Time Efficient Construction Heuristics for Vertex Separation Minimization Problem
Venue: arXiv cs.DS 2017
Year: 2017

Vertex Separation Minimization Problem (VSMP) consists of finding a layout of a graph G = (V,E) which minimizes the maximum vertex cut or separation of a layout. It is an NP-complete problem in general for which metaheuristic techniques can be applied to find near optimal solution. VSMP has applications in VLSI design, graph drawing and computer language compiler design. VSMP is polynomially solvable for grids, trees, permutation graphs and cographs. Construction heuristics play a very important role in the metaheuristic techniques as they are responsible for generating initial solutions which lead to fast convergence. In this paper, we have proposed three construction heuristics H1, H2 and H3 and performed experiments on Grids, Small graphs, Trees and Harwell Boeing graphs, totaling 248 instances of graphs. Experiments reveal that H1, H2 and H3 are able to achieve best results for 88.71%, 43.5% and 37.1% of the total instances respectively while the best construction heuristic in the literature achieves the best solution for 39.9% of the total instances. We have also compared the results with the state-of-the-art metaheuristic GVNS and observed that the proposed construction heuristics improves the results for some of the input instances. It was found that GVNS obtained best results for 82.9% instances of all input instances and the heuristic H1 obtained best results for 82.3% of all input instances.
Axiomatization of if-then-else over monoids of possibly non-halting programs and tests
Venue: arXiv cs.LO 2017
Year: 2017

In order to study the axiomatization of the if-then-else construct over possibly non-halting programs and tests, the notion of $C$-sets was introduced in the literature by considering the tests from an abstract $C$-algebra. This paper extends the notion of $C$-sets to $C$-monoids which include the composition of programs as well as composition of programs with tests. For the class of $C$-monoids where the $C$-algebras are adas a canonical representation in terms of functional $C$-monoids is obtained.
Improving Localization Accuracy in Connected Vehicle Networks Using Rao-Blackwellized Particle Filters: Theory, Simulations, and Experiments
Venue: arXiv cs.SY 2017
Year: 2017

A crucial function for automated vehicle technologies is accurate localization. Lane-level accuracy is not readily available from low-cost Global Navigation Satellite System (GNSS) receivers because of factors such as multipath error and atmospheric bias. Approaches such as Differential GNSS can improve localization accuracy, but usually require investment in expensive base stations. Connected vehicle technologies provide an alternative approach to improving the localization accuracy. It will be shown in this paper that localization accuracy can be enhanced using crude GNSS measurements from a group of connected vehicles, by matching their locations to a digital map. A Rao-Blackwellized particle filter (RBPF) is used to jointly estimate the common biases of the pseudo-ranges and the vehicle positions. Multipath biases, which introduce receiver-specific (non-common) error, are mitigated by a multi-hypothesis detection-rejection approach. The temporal correlation of the estimations is exploited through the prediction-update process. The proposed approach is compared to existing methods using both simulations and experimental results. It was found that the proposed algorithm can eliminate the common biases and reduce the localization error to below 1 meter under open sky conditions.
Collaborative Deep Reinforcement Learning
Venue: arXiv cs.LG 2017
Year: 2017

Besides independent learning, human learning process is highly improved by summarizing what has been learned, communicating it with peers, and subsequently fusing knowledge from different sources to assist the current learning goal. This collaborative learning procedure ensures that the knowledge is shared, continuously refined, and concluded from different perspectives to construct a more profound understanding. The idea of knowledge transfer has led to many advances in machine learning and data mining, but significant challenges remain, especially when it comes to reinforcement learning, heterogeneous model structures, and different learning tasks. Motivated by human collaborative learning, in this paper we propose a collaborative deep reinforcement learning (CDRL) framework that performs adaptive knowledge transfer among heterogeneous learning agents. Specifically, the proposed CDRL conducts a novel deep knowledge distillation method to address the heterogeneity among different learning tasks with a deep alignment network. Furthermore, we present an efficient collaborative Asynchronous Advantage Actor-Critic (cA3C) algorithm to incorporate deep knowledge distillation into the online training of agents, and demonstrate the effectiveness of the CDRL framework using extensive empirical evaluation on OpenAI gym.
Deep learning-based assessment of tumor-associated stroma for diagnosing breast cancer in histopathology images
Venue: arXiv cs.CV 2017
Year: 2017

Diagnosis of breast carcinomas has so far been limited to the morphological interpretation of epithelial cells and the assessment of epithelial tissue architecture. Consequently, most of the automated systems have focused on characterizing the epithelial regions of the breast to detect cancer. In this paper, we propose a system for classification of hematoxylin and eosin (H&E) stained breast specimens based on convolutional neural networks that primarily targets the assessment of tumor-associated stroma to diagnose breast cancer patients. We evaluate the performance of our proposed system using a large cohort containing 646 breast tissue biopsies. Our evaluations show that the proposed system achieves an area under ROC of 0.92, demonstrating the discriminative power of previously neglected tumor-associated stroma as a diagnostic biomarker.
IEEE 802.11ad-based Radar: An Approach to Joint Vehicular Communication-Radar System
Venue: arXiv cs.IT 2017
Year: 2017

Millimeter-wave (mmWave) radar is widely used in vehicles for applications such as adaptive cruise control and collision avoidance. In this paper, we propose an IEEE 802.11ad-based radar for long-range radar (LRR) applications at the 60 GHz unlicensed band. We exploit the preamble of a single-carrier (SC) physical layer (PHY) frame, which consists of Golay complementary sequences with good correlation properties, as a radar waveform. This system enables a joint waveform for automotive radar and a potential mmWave vehicular communication system based on IEEE 802.11ad, allowing hardware reuse. To formulate an integrated framework of vehicle-to-vehicle (V2V) communication and LRR based on a mmWave consumer wireless local area network (WLAN) standard, we make typical assumptions for LRR applications and incorporate the full duplex radar assumption due to the possibility of sufficient isolation and self-interference cancellation. We develop single- and multi-frame radar receiver algorithms for target detection as well as range and velocity estimation within a coherent processing interval. Our proposed radar processing algorithms leverage channel estimation and time-frequency synchronization techniques used in a conventional IEEE 802.11ad receiver with minimal modifications. Analysis and simulations show that in a single target scenario, a Gbps data rate is achieved simultaneously with cm-level range accuracy and cm/s-level velocity accuracy. The target vehicle is detected with a high probability of detection ($>$99.9$\%$) at a low false alarm of 10$^{-6}$ for an equivalent isotropically radiated power (EIRP) of 43 dBm up to a vehicle separation distance of 200 m.
Chaos Engineering
Venue: arXiv cs.SE 2017
Year: 2017

Modern software-based services are implemented as distributed systems with complex behavior and failure modes. Many large tech organizations are using experimentation to verify the reliability of such systems. We use the term "Chaos Engineering" to refer to this approach, and discuss the underlying principles and how to use it to run experiments.
Novel Techniques to Derive Capacity Results for Multi-User Interference Channels
Venue: arXiv cs.IT 2017
Year: 2017

The Interference Channels (ICs) represent fundamental building blocks of wireless communication networks. Despite considerable progress in network information theory, available capacity results for ICs, specifically those with more than two users, are still very limited. One of the main difficulties in the analysis of these networks is how to establish useful capacity outer bounds for them. In this paper, novel techniques requiring subtle sequential application of Csiszar-Korner identity are developed to establish efficient single-letter outer bounds on the sum-rate capacity of interference networks. By using the outer bounds, a full characterization of the sum-rate capacity is then derived for various multi-user ICs under specific conditions. Our capacity results hold for both discrete and Gaussian networks.