OpenRaiser/Intern-Atlas huggingface dataset:
Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits
Venue: arXiv cs.CC 2018
Year: 2018

$ \newcommand{\cclass}[1]{\normalfont\textsf{##1}} $We show average-case lower bounds for explicit Boolean functions against bounded-depth threshold circuits with a superlinear number of wires. We show that for each integer $d > 1$, there is a constant $\varepsilon_d > 0$ such that the Parity function on $n$ bits has correlation at most $n^{-\varepsilon_d}$ with depth-$d$ threshold circuits which have at most $n^{1+\varepsilon_d}$ wires, and the Generalized Andreev function on $n$ bits has correlation at most $\exp(-{n^{\varepsilon_d}})$ with depth-$d$ threshold circuits which have at most $n^{1+\varepsilon_d}$ wires. Previously, only worst-case lower bounds in this setting were known (Impagliazzo, Paturi, and Saks (SICOMP 1997)). We use our ideas to make progress on several related questions. We give satisfiability algorithms beating brute force search for depth-$d$ threshold circuits with a superlinear number of wires. These are the first such algorithms for depth greater than 2. We also show that Parity on $n$ bits cannot be computed by polynomial-size $\textsf{AC}^0$ circuits with $n^{o(1)}$ general threshold gates. Previously no lower bound for Parity in this setting could handle more than $\log(n)$ gates. This result also implies subexponential-time learning algorithms for $\textsf{AC}^0$ with $n^{o(1)}$ threshold gates under the uniform distribution. In addition, we give almost optimal bounds for the number of gates in a depth-$d$ threshold circuit computing Parity on average, and show average-case lower bounds for threshold formulas of any depth. Our techniques include adaptive random restrictions, anti-concentration and the structural theory of linear threshold functions, and bounded-read Chernoff bounds.
Right for the Right Reason: Training Agnostic Networks
Venue: arXiv cs.LG 2018
Year: 2018

We consider the problem of a neural network being requested to classify images (or other inputs) without making implicit use of a "protected concept", that is a concept that should not play any role in the decision of the network. Typically these concepts include information such as gender or race, or other contextual information such as image backgrounds that might be implicitly reflected in unknown correlations with other variables, making it insufficient to simply remove them from the input features. In other words, making accurate predictions is not good enough if those predictions rely on information that should not be used: predictive performance is not the only important metric for learning systems. We apply a method developed in the context of domain adaptation to address this problem of "being right for the right reason", where we request a classifier to make a decision in a way that is entirely 'agnostic' to a given protected concept (e.g. gender, race, background etc.), even if this could be implicitly reflected in other attributes via unknown correlations. After defining the concept of an 'agnostic model', we demonstrate how the Domain-Adversarial Neural Network can remove unwanted information from a model using a gradient reversal layer.
Finding Short Synchronizing Words for Prefix Codes
Venue: arXiv cs.FL 2018
Year: 2018

We study the problems of finding a shortest synchronizing word and its length for a given prefix code. This is done in two different settings: when the code is defined by an arbitrary decoder recognizing its star and when the code is defined by its literal decoder (whose size is polynomially equivalent to the total length of all words in the code). For the first case for every $\varepsilon > 0$ we prove $n^{1 - \varepsilon}$-inapproximability for recognizable binary maximal prefix codes, $Θ(\log n)$-inapproximability for finite binary maximal prefix codes and $n^{\frac{1}{2} - \varepsilon}$-inapproximability for finite binary prefix codes. By $c$-inapproximability here we mean the non-existence of a $c$-approximation polynomial time algorithm under the assumption P $\ne$ NP, and by $n$ the number of states of the decoder in the input. For the second case, we propose approximation and exact algorithms and conjecture that for finite maximal prefix codes the problem can be solved in polynomial time. We also study the related problems of finding a shortest mortal and a shortest avoiding word.
Robust Trajectory and Transmit Power Design for Secure UAV Communications
Venue: arXiv cs.IT 2018
Year: 2018

Unmanned aerial vehicles (UAVs) are anticipated to be widely deployed in future wireless communications, due to their advantages of high mobility and easy deployment. However, the broadcast nature of air-to-ground line-of-sight wireless chan- nels brings a new challenge to the information security of UAV- ground communication. This paper tackles such a challenge in the physical layer by exploiting the mobility of UAV via its trajectory design. We consider a UAV-ground communication system with multiple potential eavesdroppers on the ground, where the information on the locations of the eavesdroppers is imperfect. We formulate an optimization problem which maximizes the average worst-case secrecy rate of the system by jointly designing the robust trajectory and transmit power of the UAV over a given flight duration. The non-convexity of the optimization problem and the imperfect location information of the eavesdroppers make the problem difficult to be solved optimally. We propose an iterative suboptimal algorithm to solve this problem efficiently by applying the block coordinate descent method, S-procedure, and successive convex optimization method. Simulation results show that the proposed algorithm can improve the average worst-case secrecy rate significantly, as compared to two other benchmark algorithms without robust design.
Comparison of DCO-OFDM and M-PAM for LED-Based Communication Systems
Venue: arXiv cs.IT 2018
Year: 2018

Light-emitting diode (LED)-based communications, such as visible light communications (VLC) and infrared (IR) communications, are candidate techniques to provide short-range and high-speed data transmission. In this paper, M-ary pulse amplitude modulation (M-PAM), used as a high bandwidth efficiency scheme, is compared with an optimized DC-biased optical orthogonal frequency division multiplexing (DCO-OFDM) scheme. Considering the bandwidth limit and constrained peak transmitted power characteristics of LEDs, a bit loading algorithm with an optimized modulation index is used for the DCO-OFDM. To reduce the inter-symbol interference caused by LEDs, a waveform design algorithm with a minimum mean squared error (MMSE) equalizer is applied to the M-PAM system. From numerical results, M-PAM with the optimized signal processing can provide a substantially higher data rate than the optimally designed DCO-OFDM for the same performance.
Efficient Beam Alignment for mmWave Single-Carrier Systems with Hybrid MIMO Transceivers
Venue: arXiv cs.IT 2018
Year: 2018

Communication at millimeter wave (mmWave) bands is expected to become a key ingredient of next generation (5G) wireless networks. Effective mmWave communications require fast and reliable methods for beamforming at both the User Equipment (UE) and the Base Station (BS) sides, in order to achieve a sufficiently large Signal-to-Noise Ratio (SNR) after beamforming. We refer to the problem of finding a pair of strongly coupled narrow beams at the transmitter and receiver as the Beam Alignment (BA) problem. In this paper, we propose an efficient BA scheme for single-carrier mmWave communications. In the proposed scheme, the BS periodically probes the channel in the downlink via a pre-specified pseudo-random beamforming codebook and pseudo-random spreading codes, letting each UE estimate the Angle-of-Arrival / Angle-of-Departure (AoA-AoD) pair of the multipath channel for which the energy transfer is maximum. We leverage the sparse nature of mmWave channels in the AoA-AoD domain to formulate the BA problem as the estimation of a sparse non-negative vector. Based on the recently developed Non-Negative Least Squares (NNLS) technique, we efficiently find the strongest AoA-AoD pair connecting each UE to the BS. We evaluate the performance of the proposed scheme under a realistic channel model, where the propagation channel consists of a few multipath scattering components each having different delays, AoAs-AoDs, and Doppler shifts.The channel model parameters are consistent with experimental channel measurements. Simulation results indicate that the proposed method is highly robust to fast channel variations caused by the large Doppler spread between the multipath components. Furthermore, we also show that after achieving BA the beamformed channel is essentially frequency-flat, such that single-carrier communication needs no equalization in the time domain.
On Sketching the $q$ to $p$ norms
Venue: arXiv cs.DS 2018
Year: 2018

We initiate the study of data dimensionality reduction, or sketching, for the $q\to p$ norms. Given an $n \times d$ matrix $A$, the $q\to p$ norm, denoted $\|A\|_{q \to p} = \sup_{x \in \mathbb{R}^d \backslash \vec{0}} \frac{\|Ax\|_p}{\|x\|_q}$, is a natural generalization of several matrix and vector norms studied in the data stream and sketching models, with applications to datamining, hardness of approximation, and oblivious routing. We say a distribution $S$ on random matrices $L \in \mathbb{R}^{nd} \rightarrow \mathbb{R}^k$ is a $(k,α)$-sketching family if from $L(A)$, one can approximate $\|A\|_{q \to p}$ up to a factor $α$ with constant probability. We provide upper and lower bounds on the sketching dimension $k$ for every $p, q \in [1, \infty]$, and in a number of cases our bounds are tight. While we mostly focus on constant $α$, we also consider large approximation factors $α$, as well as other variants of the problem such as when $A$ has low rank.
Combinatorial manifolds are Hamiltonian
Venue: arXiv cs.DM 2018
Year: 2018

Extending a theorem of Whitney of 1931 we prove that all connected d-graphs are Hamiltonian for positive d. A d-graph is a type of combinatorial manifold which is inductively defined as a finite simple graph for which every unit sphere is a (d-1)-sphere. A d-sphere is d-graph such that removing one vertex renders the graph contractible. A graph is contractible if there exists a vertex for which the unit sphere and the graph without that vertex are both contractible. These inductive definitions are primed with the assumptions that the empty graph 0 is the (-1)-sphere and that the one-point graph 1 is the smallest contractible graph. The proof is constructive and shows that unlike for general graphs, the complexity of the construction of Hamiltonian cycles in d-graphs is polynomial in the number of vertices of the graph.
A Hierarchical Approach to Encrypted Data Packet Classification in Smart Home Gateways
Venue: arXiv cs.CR 2018
Year: 2018

With the pervasive network based services in smart homes, traditional network management cannot guarantee end-user quality-of-experience (QoE) for all applications. End-user QoE must be supported by efficient network quality-of-service (QoS) measurement and efficient network resource allocation. With the software-defined network technology, the core network may be controlled more efficiently by a network service provider. However, end-to-end network QoS can hardly be improved the managing the core network only. In this paper, we propose an encrypted packet classification scheme for smart home gateways to improve end-to-end QoS measurement from the network operator side. Furthermore, other services such as statistical data collecting, billing to service providers, etc., can be provided without compromising end-user privacy nor security of a network. The proposed encrypted packet classification scheme has a two-level hierarchical structure. One is the service level, which is based on applications that have the same network QoS requirements. A faster classification scheme based on deep learning is proposed to achieve real-time classification with high accuracy. The other one is the application level, which is based on fine-grained applications. A non-real-time classifier can be applied to provide high accuracy. Evaluation is conducted on both level classifiers to demonstrate the efficiency and accuracy of the two types of classifiers.
Are All Experts Equally Good? A Study of Analyst Earnings Estimates
Venue: arXiv cs.CY 2018
Year: 2018

We investigate whether experts possess differential expertise when making predictions. We note that this would make it possible to aggregate multiple predictions into a result that is more accurate than their consensus average, and that the improvement prospects grow with the amount of differentiation. Turning this argument on its head, we show how differentiation can be measured by how much weighted aggregation improves on simple averaging. Taking stock-market analysts as experts in their domain, we do a retrospective study using historical quarterly earnings forecasts and actual results for large publicly traded companies. We use it to shed new light on the Sinha et al. (1997) result, showing that analysts indeed possess individual expertise, but that their differentiation is modest. On the other hand, they have significant individual bias. Together, these enable a 20%-30% accuracy improvement over consensus average.
Introducing an innovative robot-based mobile platform for programming learning
Venue: arXiv cs.CY 2018
Year: 2018

The present study introduces an Android based application that focuses on promoting students' learning experience when interacting with Lego Mindstorms Robotic Kit NXT. A thorough investigation of the current literature reveals that there are numerous applications attempting to overcome the limitations of Lego platform which, however, appear to only partially succeed in significantly improving children's engagement in fruitful learning. Their main limitations are that they either function on an elemental level or suffer from a general lack of creating effectively room for children to test their abilities and other curiosities. Aiming at confronting these limitations, the proposed android application, which is referred to as MyNXT, was created and presented. MyNXT offers direct access control along with the choice to program using simple linear logic through an easy and a user friendly environment with built in instructions for all ages. Concluding, the proposed application constitutes a stepping to an educating platform, which can facilitate the learning needs of children in contemporary times.
New Approaches for Almost-Sure Termination of Probabilistic Programs
Venue: arXiv cs.LO 2018
Year: 2018

We study the almost-sure termination problem for probabilistic programs. First, we show that supermartingales with lower bounds on conditional absolute difference provide a sound approach for the almost-sure termination problem. Moreover, using this approach we can obtain explicit optimal bounds on tail probabilities of non-termination within a given number of steps. Second, we present a new approach based on Central Limit Theorem for the almost-sure termination problem, and show that this approach can establish almost-sure termination of programs which none of the existing approaches can handle. Finally, we discuss algorithmic approaches for the two above methods that lead to automated analysis techniques for almost-sure termination of probabilistic programs.
End-to-end Sampling Patterns
Venue: arXiv cs.GR 2018
Year: 2018

Sample patterns have many uses in Computer Graphics, ranging from procedural object placement over Monte Carlo image synthesis to non-photorealistic depiction. Their properties such as discrepancy, spectra, anisotropy, or progressiveness have been analyzed extensively. However, designing methods to produce sampling patterns with certain properties can require substantial hand-crafting effort, both in coding, mathematical derivation and compute time. In particular, there is no systematic way to derive the best sampling algorithm for a specific end-task. Tackling this issue, we suggest another level of abstraction: a toolkit to end-to-end optimize over all sampling methods to find the one producing user-prescribed properties such as discrepancy or a spectrum that best fit the end-task. A user simply implements the forward losses and the sampling method is found automatically -- without coding or mathematical derivation -- by making use of back-propagation abilities of modern deep learning frameworks. While this optimization takes long, at deployment time the sampling method is quick to execute as iterated unstructured non-linear filtering using radial basis functions (RBFs) to represent high-dimensional kernels. Several important previous methods are special cases of this approach, which we compare to previous work and demonstrate its usefulness in several typical Computer Graphics applications. Finally, we propose sampling patterns with properties not shown before, such as high-dimensional blue noise with projective properties.
Towards Manipulability of Interactive Lagrangian Systems
Venue: arXiv cs.SY 2018
Year: 2018

This paper investigates manipulability of interactive Lagrangian systems with parametric uncertainty and communication/sensing constraints. Two standard examples are teleoperation with a master-slave system and teaching operation of robots. We here systematically formulate the concept of infinite manipulability for general dynamical systems, and investigate how such a unified motivation yields a design paradigm towards guaranteeing the infinite manipulability of interactive dynamical systems and in particular facilitates the design and analysis of nonlinear adaptive controllers for interactive Lagrangian systems. Specifically, based on a new class of dynamic feedback, we propose adaptive controllers that achieve both the infinite manipulability of the controlled Lagrangian systems and the robustness with respect to the communication/sensing constraints, mainly owing to the resultant dynamic-cascade framework. The proposed paradigm yields the desirable balance between network coupling requirements and controlled dynamics of human-system interaction. We also show that a special case of our main result resolves the longstanding nonlinear bilateral teleoperation problem with arbitrary unknown time-varying delay. Simulation results show the performance of the interactive robotic systems under the proposed adaptive controllers.
Fractal Scaling of Population Counts Over Time Spans
Venue: arXiv cs.CG 2018
Year: 2018

Attributes which are infrequently expressed in a population can require weeks or months of counting to reach statistical significance. But replacement in a stable population increases long-term counts to a degree determined by the probability distribution of lifetimes. If the lifetimes are in a Pareto distribution with shape factor $1-r$ between 0 and 1, then the expected counts for a stable population are proportional to time raised to the $r$ power. Thus $r$ is the fractal dimension of counts versus time for this population. Furthermore, the counts from a series of consecutive measurement intervals can be combined using the $L^p$-norm where $p=1/r$ to approximate the population count over the combined time span. Data from digital advertising support these assertions and find that fractal scaling is useful for early estimates of reach, and that the largest reachable fraction of an audience over a long time span is about $1-r$.
Security Awareness and Affective Feedback: Categorical Behaviour vs. Reported Behaviour
Venue: arXiv cs.HC 2018
Year: 2018

A lack of awareness surrounding secure online behaviour can lead to end-users, and their personal details becoming vulnerable to compromise. This paper describes an ongoing research project in the field of usable security, examining the relationship between end-user-security behaviour, and the use of affective feedback to educate end-users. Part of the aforementioned research project considers the link between categorical information users reveal about themselves online, and the information users believe, or report that they have revealed online. The experimental results confirm a disparity between information revealed, and what users think they have revealed, highlighting a deficit in security awareness. Results gained in relation to the affective feedback delivered are mixed, indicating limited short-term impact. Future work seeks to perform a long-term study, with the view that positive behavioural changes may be reflected in the results as end-users become more knowledgeable about security awareness.
Understanding Patch-Based Learning by Explaining Predictions
Venue: arXiv cs.LG 2018
Year: 2018

Deep networks are able to learn highly predictive models of video data. Due to video length, a common strategy is to train them on small video snippets. We apply the deep Taylor / LRP technique to understand the deep network's classification decisions, and identify a "border effect": a tendency of the classifier to look mainly at the bordering frames of the input. This effect relates to the step size used to build the video snippet, which we can then tune in order to improve the classifier's accuracy without retraining the model. To our knowledge, this is the the first work to apply the deep Taylor / LRP technique on any video analyzing neural network.
Deconvolving convolution neural network for cell detection
Venue: arXiv cs.CV 2018
Year: 2018

Automatic cell detection in histology images is a challenging task due to varying size, shape and features of cells and stain variations across a large cohort. Conventional deep learning methods regress the probability of each pixel belonging to the centre of a cell followed by detection of local maxima. We present deconvolution as an alternate approach to local maxima detection. The ground truth points are convolved with a mapping filter to generate artifical labels. A convolutional neural network (CNN) is modified to convolve it's output with the same mapping filter and is trained for the mapped labels. Output of the trained CNN is then deconvolved to generate points as cell detection. We compare our method with state-of-the-art deep learning approaches where the results show that the proposed approach detects cells with comparatively high precision and F1-score.
Comparative Analysis of Neural QA models on SQuAD
Venue: arXiv cs.CL 2018
Year: 2018

The task of Question Answering has gained prominence in the past few decades for testing the ability of machines to understand natural language. Large datasets for Machine Reading have led to the development of neural models that cater to deeper language understanding compared to information retrieval tasks. Different components in these neural architectures are intended to tackle different challenges. As a first step towards achieving generalization across multiple domains, we attempt to understand and compare the peculiarities of existing end-to-end neural models on the Stanford Question Answering Dataset (SQuAD) by performing quantitative as well as qualitative analysis of the results attained by each of them. We observed that prediction errors reflect certain model-specific biases, which we further discuss in this paper.
Translating MFM into FOL: towards plant operation planning
Venue: arXiv cs.AI 2018
Year: 2018

This paper proposes a method to translate multilevel flow modeling (MFM) into a first-order language (FOL), which enables the utilisation of logical techniques, such as inference engines and abductive reasoners. An example of this is a planning task for a toy plant that can be solved in FOL using abduction. In addition, owing to the expressivity of FOL, the language is capable of describing actions and their preconditions. This allows the derivation of procedures consisting of multiple actions.