OpenRaiser/Intern-Atlas huggingface dataset:
Application of Deep Convolutional Neural Networks for Detecting Extreme Weather in Climate Datasets
Venue: arXiv cs.CV 2016
Year: 2016

Detecting extreme events in large datasets is a major challenge in climate science research. Current algorithms for extreme event detection are build upon human expertise in defining events based on subjective thresholds of relevant physical variables. Often, multiple competing methods produce vastly different results on the same dataset. Accurate characterization of extreme events in climate simulations and observational data archives is critical for understanding the trends and potential impacts of such events in a climate change content. This study presents the first application of Deep Learning techniques as alternative methodology for climate extreme events detection. Deep neural networks are able to learn high-level representations of a broad class of patterns from labeled data. In this work, we developed deep Convolutional Neural Network (CNN) classification system and demonstrated the usefulness of Deep Learning technique for tackling climate pattern detection problems. Coupled with Bayesian based hyper-parameter optimization scheme, our deep CNN system achieves 89\%-99\% of accuracy in detecting extreme events (Tropical Cyclones, Atmospheric Rivers and Weather Fronts
IISCNLP at SemEval-2016 Task 2: Interpretable STS with ILP based Multiple Chunk Aligner
Venue: arXiv cs.CL 2016
Year: 2016

Interpretable semantic textual similarity (iSTS) task adds a crucial explanatory layer to pairwise sentence similarity. We address various components of this task: chunk level semantic alignment along with assignment of similarity type and score for aligned chunks with a novel system presented in this paper. We propose an algorithm, iMATCH, for the alignment of multiple non-contiguous chunks based on Integer Linear Programming (ILP). Similarity type and score assignment for pairs of chunks is done using a supervised multiclass classification technique based on Random Forrest Classifier. Results show that our algorithm iMATCH has low execution time and outperforms most other participating systems in terms of alignment score. Of the three datasets, we are top ranked for answer- students dataset in terms of overall score and have top alignment score for headlines dataset in the gold chunks track.
Robustness of Bidirectional Interdependent Networks: Analysis and Design
Venue: arXiv cs.SI 2016
Year: 2016

We study the robustness of interdependent networks where two networks are said to be interdependent if the operation of one network depends on the operation of the other one, and vice versa. In this paper, we propose a model for analyzing bidirectional interdependent networks with known topology. We define the metric MR(D) to be the minimum number of nodes that should be removed from one network to cause the failure of D nodes in the other network due to cascading failures. We prove that evaluating this metric is not only NP-complete, but also inapproximable. Next, we propose heuristics for evaluating this metric and compare their performances using simulation results. Finally, we introduce two closely related definitions for robust design of interdependent networks; propose algorithms for explicit design, and demonstrate the relation between robust interdependent networks and expander graphs.
Boltzmann meets Nash: Energy-efficient routing in optical networks under uncertainty
Venue: arXiv cs.NI 2016
Year: 2016

Motivated by the massive deployment of power-hungry data centers for service provisioning, we examine the problem of routing in optical networks with the aim of minimizing traffic-driven power consumption. To tackle this issue, routing must take into account energy efficiency as well as capacity considerations; moreover, in rapidly-varying network environments, this must be accomplished in a real-time, distributed manner that remains robust in the presence of random disturbances and noise. In view of this, we derive a pricing scheme whose Nash equilibria coincide with the network's socially optimum states, and we propose a distributed learning method based on the Boltzmann distribution of statistical mechanics. Using tools from stochastic calculus, we show that the resulting Boltzmann routing scheme exhibits remarkable convergence properties under uncertainty: specifically, the long-term average of the network's power consumption converges within $\varepsilon$ of its minimum value in time which is at most $\tilde O(1/\varepsilon^2)$, irrespective of the fluctuations' magnitude; additionally, if the network admits a strict, non-mixing optimum state, the algorithm converges to it - again, no matter the noise level. Our analysis is supplemented by extensive numerical simulations which show that Boltzmann routing can lead to a significant decrease in power consumption over basic, shortest-path routing schemes in realistic network conditions.
Topological Interference Management with Reconfigurable Antennas
Venue: arXiv cs.IT 2016
Year: 2016

We study the symmetric degrees-of-freedom (DoF) of partially connected interference networks under linear coding strategies at transmitters without channel state information beyond topology. We assume that the receivers are equipped with reconfigurable antennas that can switch among their preset modes. In such a network setting, we characterize the class of network topologies in which half linear symmetric DoF is achievable. Moreover, we derive a general upper bound on the linear symmetric DoF for arbitrary network topologies. We also show that this upper bound is tight if the transmitters have at most two co-interferers.
Usability of AutoProof: a case study of software verification
Venue: arXiv cs.SE 2016
Year: 2016

Many verification tools come out of academic projects, whose natural constraints do not typically lead to a strong focus on usability. For widespread use, however, usability is essential. Using a well-known benchmark, the Tokeneer problem, we evaluate the usability of a recent and promising verification tool: AutoProof. The results show the efficacy of the tool in verifying a real piece of software and automatically discharging nearly two thirds of verification conditions. At the same time, the case study shows the demand for improved documentation and emphasizes the need for improvement in the tool itself and in the Eiffel IDE.
Some reflections on directed lattice paths
Venue: arXiv cs.DM 2016
Year: 2016

This article analyzes directed lattice paths, when a boundary reflecting or absorbing condition is added to the classical models. The lattice paths are characterized by two time-independent sets of rules (also called steps) which have a privileged direction of increase and are therefore essentially one-dimensional objects. Depending on the spatial coordinate, one of the two sets of rules applies, namely one for altitude 0 and one for altitude bigger than 0. The abscissa y=0 thus acts as a border which either absorbs or reflects steps. The absorption model corresponds to the model analyzed by Banderier and Flajolet ("Analytic combinatorics of directed lattice paths"), while the reflecting model leads to a more complicated situation. We show how the generating functions are then modified: the kernel method strikes again but here it unfortunately does not give a nice product formula. This makes the analysis more challenging, and, in the case of Łukasiewicz walks, we give the asymptotics for the number of excursions, arches and meanders. Limit laws for the number of returns to 0 of excursions are given. We also compute the limit laws of the final altitude of meanders. The full analytic situation is more complicated than the Banderier-Flajolet model (partly because new "critical compositions" appear, forcing us to introduce new key quantities, like the drift at 0), and we quantify to what extent the global drift, and the drift at 0 play a role in the "universal" behavior of such walks.
Faster Online Matrix-Vector Multiplication
Venue: arXiv cs.DS 2016
Year: 2016

We consider the Online Boolean Matrix-Vector Multiplication (OMV) problem studied by Henzinger et al. [STOC'15]: given an $n \times n$ Boolean matrix $M$, we receive $n$ Boolean vectors $v_1,\ldots,v_n$ one at a time, and are required to output $M v_i$ (over the Boolean semiring) before seeing the vector $v_{i+1}$, for all $i$. Previous known algorithms for this problem are combinatorial, running in $O(n^3/\log^2 n)$ time. Henzinger et al. conjecture there is no $O(n^{3-\varepsilon})$ time algorithm for OMV, for all $\varepsilon > 0$; their OMV conjecture is shown to imply strong hardness results for many basic dynamic problems. We give a substantially faster method for computing OMV, running in $n^3/2^{Ω(\sqrt{\log n})}$ randomized time. In fact, after seeing $2^{ω(\sqrt{\log n})}$ vectors, we already achieve $n^2/2^{Ω(\sqrt{\log n})}$ amortized time for matrix-vector multiplication. Our approach gives a way to reduce matrix-vector multiplication to solving a version of the Orthogonal Vectors problem, which in turn reduces to "small" algebraic matrix-matrix multiplication. Applications include faster independent set detection, partial match retrieval, and 2-CNF evaluation. We also show how a modification of our method gives a cell probe data structure for OMV with worst case $O(n^{7/4}/\sqrt{w})$ time per query vector, where $w$ is the word size. This result rules out an unconditional proof of the OMV conjecture using purely information-theoretic arguments.
A Survey and Evaluation of Data Center Network Topologies
Venue: arXiv cs.DC 2016
Year: 2016

Data centers are becoming increasingly popular for their flexibility and processing capabilities in the modern computing environment. They are managed by a single entity (administrator) and allow dynamic resource provisioning, performance optimization as well as efficient utilization of available resources. Each data center consists of massive compute, network and storage resources connected with physical wires. The large scale nature of data centers requires careful planning of compute, storage, network nodes, interconnection as well as inter-communication for their effective and efficient operations. In this paper, we present a comprehensive survey and taxonomy of network topologies either used in commercial data centers, or proposed by researchers working in this space. We also compare and evaluate some of those topologies using mininet as well as gem5 simulator for different traffic patterns, based on various metrics including throughput, latency and bisection bandwidth.
Plug-and-Play ADMM for Image Restoration: Fixed Point Convergence and Applications
Venue: arXiv cs.CV 2016
Year: 2016

Alternating direction method of multiplier (ADMM) is a widely used algorithm for solving constrained optimization problems in image restoration. Among many useful features, one critical feature of the ADMM algorithm is its modular structure which allows one to plug in any off-the-shelf image denoising algorithm for a subproblem in the ADMM algorithm. Because of the plug-in nature, this type of ADMM algorithms is coined the name "Plug-and-Play ADMM". Plug-and-Play ADMM has demonstrated promising empirical results in a number of recent papers. However, it is unclear under what conditions and by using what denoising algorithms would it guarantee convergence. Also, since Plug-and-Play ADMM uses a specific way to split the variables, it is unclear if fast implementation can be made for common Gaussian and Poissonian image restoration problems. In this paper, we propose a Plug-and-Play ADMM algorithm with provable fixed point convergence. We show that for any denoising algorithm satisfying an asymptotic criteria, called bounded denoisers, Plug-and-Play ADMM converges to a fixed point under a continuation scheme. We also present fast implementations for two image restoration problems on super-resolution and single-photon imaging. We compare Plug-and-Play ADMM with state-of-the-art algorithms in each problem type, and demonstrate promising experimental results of the algorithm.
Storage-Optimized Data-Atomic Algorithms for Handling Erasures and Errors in Distributed Storage Systems
Venue: arXiv cs.DC 2016
Year: 2016

Erasure codes are increasingly being studied in the context of implementing atomic memory objects in large scale asynchronous distributed storage systems. When compared with the traditional replication based schemes, erasure codes have the potential of significantly lowering storage and communication costs while simultaneously guaranteeing the desired resiliency levels. In this work, we propose the Storage-Optimized Data-Atomic (SODA) algorithm for implementing atomic memory objects in the multi-writer multi-reader setting. SODA uses Maximum Distance Separable (MDS) codes, and is specifically designed to optimize the total storage cost for a given fault-tolerance requirement. For tolerating $f$ server crashes in an $n$-server system, SODA uses an $[n, k]$ MDS code with $k=n-f$, and incurs a total storage cost of $\frac{n}{n-f}$. SODA is designed under the assumption of reliable point-to-point communication channels. The communication cost of a write and a read operation are respectively given by $O(f^2)$ and $\frac{n}{n-f}(δ_w+1)$, where $δ_w$ denotes the number of writes that are concurrent with the particular read. In comparison with the recent CASGC algorithm, which also uses MDS codes, SODA offers lower storage cost while pays more on the communication cost. We also present a modification of SODA, called SODA$_{\text{err}}$, to handle the case where some of the servers can return erroneous coded elements during a read operation. Specifically, in order to tolerate $f$ server failures and $e$ error-prone coded elements, the SODA$_{\text{err}}$ algorithm uses an $[n, k]$ MDS code such that $k=n-2e-f$. SODA$_{\text{err}}$ also guarantees liveness and atomicity, while maintaining an optimized total storage cost of $\frac{n}{n-f-2e}$.
Perceptually Consistent Color-to-Gray Image Conversion
Venue: arXiv cs.CV 2016
Year: 2016

In this paper, we propose a color to grayscale image conversion algorithm (C2G) that aims to preserve the perceptual properties of the color image as much as possible. To this end, we propose measures for two perceptual properties based on contemporary research in vision science: brightness and multi-scale contrast. The brightness measurement is based on the idea that the brightness of a grayscale image will affect the perception of the probability of color information. The color contrast measurement is based on the idea that the contrast of a given pixel to its surroundings can be measured as a linear combination of color contrast at different scales. Based on these measures we propose a graph based optimization framework to balance the brightness and contrast measurements. To solve the optimization, an $\ell_1$-norm based method is provided which converts color discontinuities to brightness discontinuities. To validate our methods, we evaluate against the existing \cadik and Color250 datasets, and against NeoColor, a new dataset that improves over existing C2G datasets. NeoColor contains around 300 images from typical C2G scenarios, including: commercial photograph, printing, books, magazines, masterpiece artworks and computer designed graphics. We show improvements in metrics of performance, and further through a user study, we validate the performance of both the algorithm and the metric.
Design and Analysis of Novel Kernel Measure for Software Fault Localization
Venue: arXiv cs.SE 2016
Year: 2016

The problem of software fault localization may be viewed as an approach for finding hidden faults or bugs in the existing program codes which are syntactically correct and give fault free output for some input instances but fail for all other input instances. Some of the reasons include logical errors, wrong interpretation of specification, coding errors. Finding such faults is not possible sometimes with the help of compilers. This is where the necessity and significance of software fault localization stems out. The main contribution for this work is to first introduce the block hit-miss function which relates block vectors of execution sequences of software code over sample runs performed and the decision vector which denotes fault or error free output. The similarity measure is applied to the block vector and decision vectors as input and the pair with maximum similarity is considered as faulty block.
A Study on Features and Limitations of On-line C Compilers
Venue: arXiv cs.PL 2016
Year: 2016

Compilers are used to run programs that are written in a range of designs from text to executable formats. With the advent of the internet, studies related to the development of cloud based compilers are being carried out. There is a considerable increase of on-line compilers enabling on-line compilation of user programs without any mandate to. This study is specific to on-line C compilers to investigate the correctness, issues and limitations.
Revenue Maximization and Ex-Post Budget Constraints
Venue: arXiv cs.GT 2016
Year: 2016

We consider the problem of a revenue-maximizing seller with m items for sale to n additive bidders with hard budget constraints, assuming that the seller has some prior distribution over bidder values and budgets. The prior may be correlated across items and budgets of the same bidder, but is assumed independent across bidders. We target mechanisms that are Bayesian Incentive Compatible, but that are ex-post Individually Rational and ex-post budget respecting. Virtually no such mechanisms are known that satisfy all these conditions and guarantee any revenue approximation, even with just a single item. We provide a computationally efficient mechanism that is a $3$-approximation with respect to all BIC, ex-post IR, and ex-post budget respecting mechanisms. Note that the problem is NP-hard to approximate better than a factor of 16/15, even in the case where the prior is a point mass \cite{ChakrabartyGoel}. We further characterize the optimal mechanism in this setting, showing that it can be interpreted as a distribution over virtual welfare maximizers. We prove our results by making use of a black-box reduction from mechanism to algorithm design developed by \cite{CaiDW13b}. Our main technical contribution is a computationally efficient $3$-approximation algorithm for the algorithmic problem that results by an application of their framework to this problem. The algorithmic problem has a mixed-sign objective and is NP-hard to optimize exactly, so it is surprising that a computationally efficient approximation is possible at all. In the case of a single item ($m=1$), the algorithmic problem can be solved exactly via exhaustive search, leading to a computationally efficient exact algorithm and a stronger characterization of the optimal mechanism as a distribution over virtual value maximizers.
Attack Resilience and Recovery using Physical Challenge Response Authentication for Active Sensors Under Integrity Attacks
Venue: arXiv cs.CR 2016
Year: 2016

Embedded sensing systems are pervasively used in life- and security-critical systems such as those found in airplanes, automobiles, and healthcare. Traditional security mechanisms for these sensors focus on data encryption and other post-processing techniques, but the sensors themselves often remain vulnerable to attacks in the physical/analog domain. If an adversary manipulates a physical/analog signal prior to digitization, no amount of digital security mechanisms after the fact can help. Fortunately, nature imposes fundamental constraints on how these analog signals can behave. This work presents PyCRA, a physical challenge-response authentication scheme designed to protect active sensing systems against physical attacks occurring in the analog domain. PyCRA provides security for active sensors by continually challenging the surrounding environment via random but deliberate physical probes. By analyzing the responses to these probes, and by using the fact that the adversary cannot change the underlying laws of physics, we provide an authentication mechanism that not only detects malicious attacks but provides resilience against them. We demonstrate the effectiveness of PyCRA through several case studies using two sensing systems: (1) magnetic sensors like those found wheel speed sensors in robotics and automotive, and (2) commercial RFID tags used in many security-critical applications. Finally, we outline methods and theoretical proofs for further enhancing the resilience of PyCRA to active attacks by means of a confusion phase---a period of low signal to noise ratio that makes it more difficult for an attacker to correctly identify and respond to PyCRA's physical challenges. In doing so, we evaluate both the robustness and the limitations of PyCRA, concluding by outlining practical considerations as well as further applications for the proposed authentication mechanism.
Shape from Mixed Polarization
Venue: arXiv cs.CV 2016
Year: 2016

Shape from Polarization (SfP) estimates surface normals using photos captured at different polarizer rotations. Fundamentally, the SfP model assumes that light is reflected either diffusely or specularly. However, this model is not valid for many real-world surfaces exhibiting a mixture of diffuse and specular properties. To address this challenge, previous methods have used a sequential solution: first, use an existing algorithm to separate the scene into diffuse and specular components, then apply the appropriate SfP model. In this paper, we propose a new method that jointly uses viewpoint and polarization data to holistically separate diffuse and specular components, recover refractive index, and ultimately recover 3D shape. By involving the physics of polarization in the separation process, we demonstrate competitive results with a benchmark method, while recovering additional information (e.g. refractive index).
Average Size of a Suffix Tree for Markov Sources
Venue: arXiv cs.DS 2016
Year: 2016

We study a suffix tree built from a sequence generated by a Markovian source. Such sources are more realistic probabilistic models for text generation, data compression, molecular applications, and so forth. We prove that the average size of such a suffix tree is asymptotically equivalent to the average size of a trie built over $n$ independent sequences from the same Markovian source. This equivalence is only known for memoryless sources. We then derive a formula for the size of a trie under Markovian model to complete the analysis for suffix trees. We accomplish our goal by applying some novel techniques of analytic combinatorics on words also known as analytic pattern matching.
All Weather Perception: Joint Data Association, Tracking, and Classification for Autonomous Ground Vehicles
Venue: arXiv cs.SY 2016
Year: 2016

A novel probabilistic perception algorithm is presented as a real-time joint solution to data association, object tracking, and object classification for an autonomous ground vehicle in all-weather conditions. The presented algorithm extends a Rao-Blackwellized Particle Filter originally built with a particle filter for data association and a Kalman filter for multi-object tracking (Miller et al. 2011a) to now also include multiple model tracking for classification. Additionally a state-of-the-art vision detection algorithm that includes heading information for autonomous ground vehicle (AGV) applications was implemented. Cornell's AGV from the DARPA Urban Challenge was upgraded and used to experimentally examine if and how state-of-the-art vision algorithms can complement or replace lidar and radar sensors. Sensor and algorithm performance in adverse weather and lighting conditions is tested. Experimental evaluation demonstrates robust all-weather data association, tracking, and classification where camera, lidar, and radar sensors complement each other inside the joint probabilistic perception algorithm.