OpenRaiser/Intern-Atlas huggingface dataset:
On the Classes of Interval Graphs of Limited Nesting and Count of Lengths
Venue: arXiv cs.DM 2017
Year: 2017

In 1969, Roberts introduced proper and unit interval graphs and proved that these classes are equal. Natural generalizations of unit interval graphs called $k$-length interval graphs were considered in which the number of different lengths of intervals is limited by $k$. Even after decades of research, no insight into their structure is known and the complexity of recognition is open even for $k=2$. We propose generalizations of proper interval graphs called $k$-nested interval graphs in which there are no chains of $k+1$ intervals nested in each other. It is easy to see that $k$-nested interval graphs are a superclass of $k$-length interval graphs. We give a linear-time recognition algorithm for $k$-nested interval graphs. This algorithm adds a missing piece to Gajarský et al. [FOCS 2015] to show that testing FO properties on interval graphs is FPT with respect to the nesting $k$ and the length of the formula, while the problem is W2-hard when parameterized just by the length of the formula. We show that a generalization of recognition called partial representation extension is NP-hard for $k$-length interval graphs, even when $k=2$, while Klavík et al. show that it is polynomial-time solvable for $k$-nested interval graphs.
Predicting popularity of online videos using Support Vector Regression
Venue: arXiv cs.SI 2017
Year: 2017

In this work, we propose a regression method to predict the popularity of an online video based on temporal and visual cues. Our method uses Support Vector Regression with Gaussian Radial Basis Functions. We show that modelling popularity patterns with this approach provides higher and more stable prediction results, mainly thanks to the non-linearity character of the proposed method as well as its resistance against overfitting. We compare our method with the state of the art on datasets containing over 14,000 videos from YouTube and Facebook. Furthermore, we show that results obtained relying only on the early distribution patterns, can be improved by adding social and visual metadata.
Commitment and Oblivious Transfer in the Bounded Storage Model with Errors
Venue: arXiv cs.CR 2017
Year: 2017

The bounded storage model restricts the memory of an adversary in a cryptographic protocol, rather than restricting its computational power, making information theoretically secure protocols feasible. We present the first protocols for commitment and oblivious transfer in the bounded storage model with errors, i.e., the model where the public random sources available to the two parties are not exactly the same, but instead are only required to have a small Hamming distance between themselves. Commitment and oblivious transfer protocols were known previously only for the error-free variant of the bounded storage model, which is harder to realize.
An example of geometric origami design with benefit of graph enumeration algorithms
Venue: arXiv cs.CG 2017
Year: 2017

This article is concerned with an example of complex planar geometry arising from flat origami challenges. The complexity of solution algorithms is illustrated, depending on the depth of the initial analysis of the problem, starting from brute force enumeration, up to the equivalence to a dedicated problem in graph theory. This leads to algorithms starting from an untractable case on modern computers, up to a run of few seconds on a portable personal computer. This emphasizes the need for a prior analysis by humans before considering the assistance of computers for complex design problems. The graph problem is an enumeration of spanning trees from a grid graph, leading to a coarse scale description of the topology of the paper edge on the flat-folded state.
Quirky Quantifiers: Optimal Models and Complexity of Computation Tree Logic
Venue: arXiv cs.LO 2017
Year: 2017

The satisfiability problem of the branching time logic CTL is studied in terms of computational complexity. Tight upper and lower bounds are provided for each temporal operator fragment. In parallel, the minimal model size is studied with a suitable notion of minimality. Thirdly, flat CTL is investigated, i.e., formulas with very low temporal operator nesting depth. A sharp dichotomy is shown in terms of complexity and minimal models: Temporal depth one has low expressive power, while temporal depth two is equivalent to full CTL.
On the Stabilizer of Weight Enumerators of Linear Codes
Venue: arXiv cs.IT 2017
Year: 2017

This paper investigates the relation between linear codes and the stabilizer in ${\rm GL}_2(\mathbb{C})$ of their weight enumerators. We prove a result on the finiteness of stabilizers and give a complete classification of linear codes with infinite stabilizer in the non-binary case. We present an efficient algorithm to compute explicitly the stabilizer of weight enumerators and we apply it to the family of Reed-Muller codes to show that some of their weight enumerators have trivial stabilizer.
Local Conflict Coloring
Venue: arXiv cs.DS 2017
Year: 2017

Locally finding a solution to symmetry-breaking tasks such as vertex-coloring, edge-coloring, maximal matching, maximal independent set, etc., is a long-standing challenge in distributed network computing. More recently, it has also become a challenge in the framework of centralized local computation. We introduce conflict coloring as a general symmetry-breaking task that includes all the aforementioned tasks as specific instantiations --- conflict coloring includes all locally checkable labeling tasks from [Naor\&Stockmeyer, STOC 1993]. Conflict coloring is characterized by two parameters $l$ and $d$, where the former measures the amount of freedom given to the nodes for selecting their colors, and the latter measures the number of constraints which colors of adjacent nodes are subject to.We show that, in the standard LOCAL model for distributed network computing, if $l/d \textgreater{} Δ$, then conflict coloring can be solved in $\tilde O(\sqrtΔ)+\log^*n$ rounds in $n$-node graphs with maximum degree $Δ$, where $\tilde O$ ignores the polylog factors in $Δ$. The dependency in~$n$ is optimal, as a consequence of the $Ω(\log^*n)$ lower bound by [Linial, SIAM J. Comp. 1992] for $(Δ+1)$-coloring. An important special case of our result is a significant improvement over the best known algorithm for distributed $(Δ+1)$-coloring due to [Barenboim, PODC 2015], which required $\tilde O(Δ^{3/4})+\log^*n$ rounds. Improvements for other variants of coloring, including $(Δ+1)$-list-coloring, $(2Δ-1)$-edge-coloring, $T$-coloring, etc., also follow from our general result on conflict coloring. Likewise, in the framework of centralized local computation algorithms (LCAs), our general result yields an LCA which requires a smaller number of probes than the previously best known algorithm for vertex-coloring, and works for a wide range of coloring problems.
A Partial Order Reduction Technique for Event-driven Multi-threaded Programs
Venue: arXiv cs.PL 2017
Year: 2017

Event-driven multi-threaded programming is fast becoming a preferred style of developing efficient and responsive applications. In this concurrency model, multiple threads execute concurrently, communicating through shared objects as well as by posting asynchronous events that are executed in their order of arrival. In this work, we consider partial order reduction (POR) for event-driven multi-threaded programs. The existing POR techniques treat event queues associated with threads as shared objects and thereby, reorder every pair of events handled on the same thread even if reordering them does not lead to different states. We do not treat event queues as shared objects and propose a new POR technique based on a novel backtracking set called the dependence-covering set. Events handled by the same thread are reordered by our POR technique only if necessary. We prove that exploring dependence-covering sets suffices to detect all deadlock cycles and assertion violations defined over local variables. To evaluate effectiveness of our POR scheme, we have implemented a dynamic algorithm to compute dependence-covering sets. On execution traces obtained from a few Android applications, we demonstrate that our technique explores many fewer transitions ---often orders of magnitude fewer--- compared to exploration based on persistent sets, wherein, event queues are considered as shared objects.
Combination of binaural and harmonic masking release effects in the detection of a single component in complex tones
Venue: arXiv cs.SD 2017
Year: 2017

Both harmonic and binaural signal properties are relevant for auditory processing. To investigate how these cues combine in the auditory system, detection thresholds for an 800-Hz tone masked by a diotic (i.e., identical between the ears) harmonic complex tone were measured in six normal-hearing subjects. The target tone was presented either diotically or with an interaural phase difference (IPD) of 180 degree and in either harmonic or "mistuned" relationship to the diotic masker. Three different maskers were used, a resolved and an unresolved complex tone (fundamental frequency: 160 and 40 Hz) with four components below and above the target frequency and a broadband unresolved complex tone with 12 additional components. The target IPD provided release from masking in most masker conditions, whereas mistuning led to a significant release from masking only in the diotic conditions with the resolved and the narrowband unresolved maskers. A significant effect of mistuning was neither found in the diotic condition with the wideband unresolved masker nor in any of the dichotic conditions. An auditory model with a single analysis frequency band and different binaural processing schemes was employed to predict the data of the unresolved masker conditions. Sensitivity to modulation cues was achieved by including an auditory-motivated modulation filter in the processing pathway. The predictions of the diotic data were in line with the experimental results and literature data in the narrowband condition, but not in the broadband condition, suggesting that across-frequency processing is involved in processing modulation information. The experimental and model results in the dichotic conditions show that the binaural processor cannot exploit modulation information in binaurally unmasked conditions.
Learning to Diagnose with LSTM Recurrent Neural Networks
Venue: arXiv cs.LG 2017
Year: 2017

Clinical medical data, especially in the intensive care unit (ICU), consist of multivariate time series of observations. For each patient visit (or episode), sensor data and lab test results are recorded in the patient's Electronic Health Record (EHR). While potentially containing a wealth of insights, the data is difficult to mine effectively, owing to varying length, irregular sampling and missing data. Recurrent Neural Networks (RNNs), particularly those using Long Short-Term Memory (LSTM) hidden units, are powerful and increasingly popular models for learning from sequence data. They effectively model varying length sequences and capture long range dependencies. We present the first study to empirically evaluate the ability of LSTMs to recognize patterns in multivariate time series of clinical measurements. Specifically, we consider multilabel classification of diagnoses, training a model to classify 128 diagnoses given 13 frequently but irregularly sampled clinical measurements. First, we establish the effectiveness of a simple LSTM network for modeling clinical data. Then we demonstrate a straightforward and effective training strategy in which we replicate targets at each sequence step. Trained only on raw time series, our models outperform several strong baselines, including a multilayer perceptron trained on hand-engineered features.
Diversity Networks: Neural Network Compression Using Determinantal Point Processes
Venue: arXiv cs.LG 2017
Year: 2017

We introduce Divnet, a flexible technique for learning networks with diverse neurons. Divnet models neuronal diversity by placing a Determinantal Point Process (DPP) over neurons in a given layer. It uses this DPP to select a subset of diverse neurons and subsequently fuses the redundant neurons into the selected ones. Compared with previous approaches, Divnet offers a more principled, flexible technique for capturing neuronal diversity and thus implicitly enforcing regularization. This enables effective auto-tuning of network architecture and leads to smaller network sizes without hurting performance. Moreover, through its focus on diversity and neuron fusing, Divnet remains compatible with other procedures that seek to reduce memory footprints of networks. We present experimental results to corroborate our claims: for pruning neural networks, Divnet is seen to be notably superior to competing approaches.
A New Matching Algorithm for Multidimensional Persistence
Venue: arXiv cs.CG 2017
Year: 2017

An algorithm is presented that constructs an acyclic partial matching on the cells of a given simplicial complex from a vector-valued function defined on the vertices and extended to each simplex by taking the least common upper bound of the values on its vertices. The resulting acyclic partial matching may be used to construct a reduced filtered complex with the same multidimensional persistent homology as the original simplicial complex filtered by the sublevel sets of the function. Numerical tests show that in practical cases the rate of reduction in the number of cells achieved by the algorithm is substantial. This promises to be useful for the computation of multidimensional persistent homology of simplicial complexes filtered by sublevel sets of vector-valued functions.
Overcoming Language Variation in Sentiment Analysis with Social Attention
Venue: arXiv cs.CL 2017
Year: 2017

Variation in language is ubiquitous, particularly in newer forms of writing such as social media. Fortunately, variation is not random, it is often linked to social properties of the author. In this paper, we show how to exploit social networks to make sentiment analysis more robust to social language variation. The key idea is linguistic homophily: the tendency of socially linked individuals to use language in similar ways. We formalize this idea in a novel attention-based neural network architecture, in which attention is divided among several basis models, depending on the author's position in the social network. This has the effect of smoothing the classification function across the social network, and makes it possible to induce personalized classifiers even for authors for whom there is no labeled data or demographic metadata. This model significantly improves the accuracies of sentiment analysis on Twitter and on review data.
Automatic Reasoning on Recursive Data-Structures with Sharing
Venue: arXiv cs.PL 2017
Year: 2017

We consider the problem of automatically verifying programs which manipulate arbitrary data structures. Our specification language is expressive, contains a notion of \emph{separation}, and thus enables a precise specification of \emph{frames}. The main contribution then is a program verification method which combines strongest postcondition reasoning in the form symbolic execution, unfolding recursive definitions of the data structure in question, and a new frame rule to achieve \emph{local reasoning} so that proofs can be compositional. Finally, we present an implementation of our verifier, and demonstrate automation on a number of representative programs. In particular, we present the first automatic proof of a classic graph marking algorithm, paving the way for dealing with a class of programs which traverse a complex data structure.
Feedback Enhances Simultaneous Wireless Information and Energy Transmission in Multiple Access Channels
Venue: arXiv cs.IT 2017
Year: 2017

In this report, the fundamental limits of simultaneous information and energy transmission in the two-user Gaussian multiple access channel (G-MAC) with and without feedback are fully characterized. More specifically, all the achievable information and energy transmission rates (in bits per channel use and energy-units per channel use, respectively) are identified. Furthermore, the fundamental limits on the individual and sum- rates given a minimum energy rate ensured at an energy harvester are also characterized. In the case without feedback, an achievability scheme based on power-splitting and successive interference cancellation is shown to be optimal. Alternatively, in the case with feedback (G-MAC-F), a simple yet optimal achievability scheme based on power-splitting and Ozarow's capacity achieving scheme is presented. Finally, the energy transmission enhancement induced by the use of feedback is quantified. Feedback can at most double the energy transmission rate at high SNRs when the information transmission sum-rate is kept fixed at the sum-capacity of the G-MAC, but it has no effect at very low SNRs.
Passive Communication with Ambient Light
Venue: arXiv cs.NI 2017
Year: 2017

In this work, we propose a new communication system for illuminated areas, indoors and outdoors. Light sources in our environments -such as light bulbs or even the sun- are our signal emitters, but we do not modulate data at the light source. We instead propose that the environment itself modulates the ambient light signals: if mobile elements 'wear' patterns consisting of distinctive reflecting surfaces, single photodiode could decode the disturbed light signals to read passive information. Achieving this vision requires a deep understanding of a new type of communication channel. Many parameters can affect the performance of passive communication based on visible light: the size of reflective surfaces, the surrounding light intensity, the speed of mobile objects, the field-of-view of the receiver, to name a few. In this paper, we present our vision for a passive communication channel with visible light, the design challenges and the evaluation of an outdoor application where our receiver decodes information from a car moving at 18 km/h.
Set-membership improved normalized subband adaptive filter algorithms for acoustic echo cancellation
Venue: arXiv cs.SY 2017
Year: 2017

In order to improve the performances of recently-presented improved normalized subband adaptive filter (INSAF) and proportionate INSAF algorithms for highly noisy system, this paper proposes their set-membership versions by exploiting the theory of set-membership filtering. Apart from obtaining smaller steady-state error, the proposed algorithms significantly reduce the overall computational complexity. In addition, to further improve the steady-state performance for the algorithms, their smooth variants are developed by using the smoothed absolute subband output errors to update the step sizes. Simulation results in the context of acoustic echo cancellation have demonstrated the superiority of the proposed algorithms.
A Survey of Available Corpora for Building Data-Driven Dialogue Systems
Venue: arXiv cs.CL 2017
Year: 2017

During the past decade, several areas of speech and language understanding have witnessed substantial breakthroughs from the use of data-driven models. In the area of dialogue systems, the trend is less obvious, and most practical systems are still built through significant engineering and expert knowledge. Nevertheless, several recent results suggest that data-driven approaches are feasible and quite promising. To facilitate research in this area, we have carried out a wide survey of publicly available datasets suitable for data-driven learning of dialogue systems. We discuss important characteristics of these datasets, how they can be used to learn diverse dialogue strategies, and their other potential uses. We also examine methods for transfer learning between datasets and the use of external knowledge. Finally, we discuss appropriate choice of evaluation metrics for the learning objective.
On the shelling antimatroids of split graphs
Venue: arXiv cs.DM 2017
Year: 2017

Chordal graph shelling antimatroids have received little attention with regard to their combinatorial properties and related optimization problems, as compared to the case of poset shelling antimatroids. Here we consider a special case of these antimatroids, namely the split graph shelling antimatroids. We show that the feasible sets of such an antimatroid relate to some poset shelling antimatroids constructed from the graph. We discuss a few applications, obtaining in particular a simple polynomial-time algorithm to find a maximum weight feasible set. We also provide a simple description of the circuits and the free sets.
Up in the Air: When Homes Meet the Web of Things
Venue: arXiv cs.CY 2017
Year: 2017

The emerging Internet of Things (IoT) will comprise billions of Web-enabled objects (or "things") where such objects can sense, communicate, compute and potentially actuate. WoT is essentially the embodiment of the evolution from systems linking digital documents to systems relating digital information to real-world physical items. It is widely understood that significant technical challenges exist in developing applications in the WoT environment. In this paper, we report our practical experience in the design and development of a smart home system in a WoT environment. Our system provides a layered framework for managing and sharing the information produced by physical things as well as the residents. We particularly focus on a research prototype named WITS, that helps the elderly live independently and safely in their own homes, with minimal support from the decreasing number of individuals in the working-age population. WITS enables an unobtrusive monitoring of elderly people in a real-world, inhabituated home environment, by leveraging WoT technologies in building context-aware, personalized services.
Popularity Signals in Trial-Offer Markets with Social Influence and Position Bias
Venue: arXiv cs.SI 2017
Year: 2017

This paper considers trial-offer markets where consumer preferences are modeled by a multinomial logit with social influence and position bias. The social signal for a product is given by its current market share raised to power r (or equivalently the number of purchases raised to the power of r). The paper shows that, when r is strictly between 0 and 1, and a static position assignment (e.g., a quality ranking) is used, the market converges to a unique equilibrium where the market shares depend only on product quality, not their initial appeals or the early dynamics. When r is greater than 1, the market becomes unpredictable. In many cases, the market goes to a monopoly for some product: Which product becomes a monopoly depends on the initial conditions of the market. These theoretical results are complemented by an agent-based simulation which indicates that convergence is fast when r is between 0 and 1, and that the quality ranking dominates the well-known popularity ranking in terms of market efficiency. These results shed a new light on the role of social influence which is often blamed for unpredictability, inequalities, and inefficiencies in markets. In contrast, this paper shows that, with a proper social signal and position assignment for the products, the market becomes predictable, and inequalities and inefficiencies can be controlled appropriately.
Computing Chebyshev knot diagrams
Venue: arXiv cs.SC 2017
Year: 2017

A Chebyshev curve $\mathcal{C}(a,b,c,ϕ)$ has a parametrization of the form$ x(t)=T\_a(t)$; \ $y(t)=T\_b(t)$; $z(t)= T\_c(t + ϕ)$, where $a,b,c$are integers, $T\_n(t)$ is the Chebyshev polynomialof degree $n$ and $ϕ\in \mathbb{R}$. When $\mathcal{C}(a,b,c,ϕ)$ is nonsingular,it defines a polynomial knot. We determine all possible knot diagrams when $ϕ$ varies. Let $a,b,c$ be integers, $a$ is odd, $(a,b)=1$, we show that one can list all possible knots $\mathcal{C}(a,b,c,ϕ)$ in$\tilde{\mathcal{O}}(n^2)$ bit operations, with $n=abc$.