OpenRaiser/Intern-Atlas huggingface dataset:
Buying Private Data without Verification
Venue: arXiv cs.GT 2014
Year: 2014

We consider the problem of designing a survey to aggregate non-verifiable information from a privacy-sensitive population: an analyst wants to compute some aggregate statistic from the private bits held by each member of a population, but cannot verify the correctness of the bits reported by participants in his survey. Individuals in the population are strategic agents with a cost for privacy, \ie, they not only account for the payments they expect to receive from the mechanism, but also their privacy costs from any information revealed about them by the mechanism's outcome---the computed statistic as well as the payments---to determine their utilities. How can the analyst design payments to obtain an accurate estimate of the population statistic when individuals strategically decide both whether to participate and whether to truthfully report their sensitive information? We design a differentially private peer-prediction mechanism that supports accurate estimation of the population statistic as a Bayes-Nash equilibrium in settings where agents have explicit preferences for privacy. The mechanism requires knowledge of the marginal prior distribution on bits $b_i$, but does not need full knowledge of the marginal distribution on the costs $c_i$, instead requiring only an approximate upper bound. Our mechanism guarantees $ε$-differential privacy to each agent $i$ against any adversary who can observe the statistical estimate output by the mechanism, as well as the payments made to the $n-1$ other agents $j\neq i$. Finally, we show that with slightly more structured assumptions on the privacy cost functions of each agent, the cost of running the survey goes to $0$ as the number of agents diverges.
Gradual Classical Logic for Attributed Objects
Venue: arXiv cs.AI 2014
Year: 2014

There is knowledge. There is belief. And there is tacit agreement.' 'We may talk about objects. We may talk about attributes of the objects. Or we may talk both about objects and their attributes.' This work inspects tacit agreements on assumptions about the relation between objects and their attributes, and studies a way of expressing them, presenting as the result what we term gradual logic in which the sense of truth gradually shifts. It extends classical logic instances with a new logical connective capturing the object-attribute relation. A formal semantics is presented. Decidability is proved. Para- consistent/epistemic/conditional/intensional/description/combined logics are compared.
Enhancing CPU Performance using Subcontrary Mean Dynamic Round Robin (SMDRR) Scheduling Algorithm
Venue: arXiv cs.OS 2014
Year: 2014

Round Robin (RR) Algorithm is considered as optimal in time shared environment because the static time is equally shared among the processes. If the time quantum taken is static then it undergoes degradation of the CPU performance and leads to so many context switches. In this paper, we have proposed a new effective dynamic RR algorithm SMDRR (Subcontrary Mean Dynamic Round Robin) based on dynamic time quantum where we use the subcontrary mean or harmonic mean to find the time quantum. The idea of this approach is to make the time quantum repeatedly adjusted according to the burst time of the currently running processes. Our experimental analysis shows that SMDRR performs better than RR algorithm in terms of reducing the number of context switches, average turnaround time and average waiting time.
Multidimensional Zero-Correlation Linear Cryptanalysis of the Block Cipher KASUMI
Venue: arXiv cs.CR 2014
Year: 2014

The block cipher KASUMI is widely used for security in many synchronous wireless standards. It was proposed by ETSI SAGE for usage in 3GPP (3rd Generation Partnership Project) ciphering algorthms in 2001. There are a great deal of cryptanalytic results on KASUMI, however, its security evaluation against the recent zero-correlation linear attacks is still lacking so far. In this paper, we select some special input masks to refine the general 5-round zero-correlation linear approximations combining with some observations on the $FL$ functions and then propose the 6-round zero-correlation linear attack on KASUMI. Moreover, zero-correlation linear attacks on the last 7-round KASUMI are also introduced under some weak keys conditions. These weak keys take $2^{-14}$ of the whole key space. The new zero-correlation linear attack on the 6-round needs about $2^{85}$ encryptions with $2^{62.8}$ known plaintexts. For the attack under weak keys conditions on the last 7 round, the data complexity is about $2^{62.1}$ known plaintexts and the time complexity $2^{110.5}$ encryptions.
Overlapping Trace Norms in Multi-View Learning
Venue: arXiv cs.LG 2014
Year: 2014

Multi-view learning leverages correlations between different sources of data to make predictions in one view based on observations in another view. A popular approach is to assume that, both, the correlations between the views and the view-specific covariances have a low-rank structure, leading to inter-battery factor analysis, a model closely related to canonical correlation analysis. We propose a convex relaxation of this model using structured norm regularization. Further, we extend the convex formulation to a robust version by adding an l1-penalized matrix to our estimator, similarly to convex robust PCA. We develop and compare scalable algorithms for several convex multi-view models. We show experimentally that the view-specific correlations are improving data imputation performances, as well as labeling accuracy in real-world multi-label prediction tasks.
Explicit factorization of $x^n-1\in \mathbb F_q[x]$
Venue: arXiv cs.IT 2014
Year: 2014

Let $\mathbb F_q$ be a finite field and $n$ a positive integer. In this article, we prove that, under some conditions on $q$ and $n$, the polynomial $x^n-1$ can be split into irreducible binomials $x^t-a$ and an explicit factorization into irreducible factors is given. Finally, weakening one of our hypothesis, we also obtain factors of the form $x^{2t}-ax^t+b$ and explicit splitting of $x^n-1$ into irreducible factors is given.
Performance of Python runtimes on a non-numeric scientific code
Venue: arXiv cs.MS 2014
Year: 2014

The Python library FatGHol FatGHoL used in Murri2012 to reckon the rational homology of the moduli space of Riemann surfaces is an example of a non-numeric scientific code: most of the processing it does is generating graphs (represented by complex Python objects) and computing their isomorphisms (a triple of Python lists; again a nested data structure). These operations are repeated many times over: for example, the spaces and are triangulated by 4'583'322 and 747'664 graphs, respectively. This is an opportunity for every Python runtime to prove its strength in optimization. The purpose of this experiment was to assess the maturity of alternative Python runtimes, in terms of: compatibility with the language as implemented in CPython 2.7, and performance speedup. This paper compares the results and experiences from running FatGHol with different Python runtimes: CPython 2.7.5, PyPy 2.1, Cython 0.19, Numba 0.11, Nuitka 0.4.4 and Falcon.
Computing an Optimal Control Policy for an Energy Storage
Venue: arXiv cs.SY 2014
Year: 2014

We introduce StoDynProg, a small library created to solve Optimal Control problems arising in the management of Renewable Power Sources, in particular when coupled with an Energy Storage System. The library implements generic Stochastic Dynamic Programming (SDP) numerical methods which can solve a large class of Dynamic Optimization problems. We demonstrate the library capabilities with a prototype problem: smoothing the power of an Ocean Wave Energy Converter. First we use time series analysis to derive a stochastic Markovian model of this system since it is required by Dynamic Programming. Then, we briefly describe the "policy iteration" algorithm we have implemented and the numerical tools being used. We show how the API design of the library is generic enough to address Dynamic Optimization problems outside the field of Energy Management. Finally, we solve the power smoothing problem and compare the optimal control with a simpler heuristic control.
The Impact Failure Detector
Venue: arXiv cs.DC 2014
Year: 2014

This work proposes a new and flexible unreliable failure detector whose output is related to the trust level of a set of processes. By expressing the relevance of each process of the set by an impact factor value, our approach allows the tuning of the detector output, making possible a softer or stricter monitoring. The idea behind our proposal is that, according to an acceptable margin of failures and the impact factor assigned to processes, in some scenarios, the failure of some low impact processes may not change the user confidence in the set of processes, while the crash of a high impact factor process may seriously affect it. We outline the application scenarios and the proposed unreliable failure detector, giving a detailed account of the concept on which it is based.
Total stretch minimization on single and identical parallel machines
Venue: arXiv cs.DS 2014
Year: 2014

We consider the classical problem of scheduling $n$ jobs with release dates on both single and identical parallel machines. We measure the quality of service provided to each job by its stretch, which is defined as the ratio of its response time to processing time. Our objective is to schedule these jobs non-preemptively so as to minimize sum stretch. So far, there have been very few results for sum stretch minimization especially for the non-preemptive case. For the preemptive version, the Shortest remaining processing time (SRPT) algorithm is known to give $2$-competitive for sum stretch on single machine while its is $13$-competitive on identical parallel machines. Leonardi and Kellerer provided the strong lower bound for the more general problem of \textit{sum (weighted) flow time} in single machine and identical parallel machines, respectively . Therefore, we study this problem with some additional assumptions and present two new competitive ratio for existing algorithms. We show that the Shortest processing time (SPT) algorithm is $Δ- \frac{1}Δ+1$-competitive for non-preemptive sum stretch minimization on single machine and it is $Δ- \frac{1}Δ+ \frac{3}{2} -\frac{1}{2m}$ on $m$ identical parallel machines, where $Δ$ is the upper bound on the ratio between the maximum and the minimum processing time of the jobs.
Distributed Graph Automata
Venue: arXiv cs.FL 2014
Year: 2014

Inspired by distributed algorithms, we introduce a new class of finite graph automata that recognize precisely the graph languages definable in monadic second-order logic. For the cases of words and trees, it has been long known that the regular languages are precisely those definable in monadic second-order logic. In this regard, the automata proposed in the present work can be seen, to some extent, as a generalization of finite automata to graphs. Furthermore, we show that, unlike for finite automata on words and trees, the deterministic, nondeterministic and alternating variants of our automata form a strict hierarchy with respect to their expressive power. For the weaker variants, the emptiness problem is decidable.
ILATO Project: Fusion of Optical Surface Models and Volumetric CT Data
Venue: arXiv cs.CG 2014
Year: 2014

Project ILATO focuses on Improving Limited Angle computed Tomography by Optical data integration in order to enhance image quality and shorten acquisition times in X-ray based industrial quality inspection. Limited angle computed tomography is indicated whenever specimen dimensions exceed cone beam limits or the object is impenetrable from certain angles. Thus, acquiring only a subset of a full circle CT scan poses problems for reconstruction algorithms due to incomplete data which introduces blurred edges and other artifacts. To support volumetric data reconstruction algorithm a surface mesh of the object obtained via structured light optical scan acts as a mask defining boundaries of the reconstructed image. The registration of optically acquired surfaces with data acquired from computed tomography is our current challenge. This article presents our setup, the methods applied and discusses the problems arising from registration of data sets created with considerably different imaging techniques.
Who watches the watchers: Validating the ProB Validation Tool
Venue: arXiv cs.SE 2014
Year: 2014

Over the years, ProB has moved from a tool that complemented proving, to a development environment that is now sometimes used instead of proving for applications, such as exhaustive model checking or data validation. This has led to much more stringent requirements on the integrity of ProB. In this paper we present a summary of our validation efforts for ProB, in particular within the context of the norm EN 50128 and safety critical applications in the railway domain.
Nagoya Termination Tool
Venue: arXiv cs.LO 2014
Year: 2014

This paper describes the implementation and techniques of the Nagoya Termination Tool, a termination prover for term rewrite systems. The main features of the tool are: the first implementation of the weighted path order which subsumes most of the existing reduction pairs, and the efficiency due to the strong cooperation with external SMT solvers. We present some new ideas that contribute to the efficiency and power of the tool.
A Wireless System Using Random Residue Sequences
Venue: arXiv cs.CR 2014
Year: 2014

This paper describes the architecture of wireless communication system using random residue sequences. The basic scheme is that of spread spectrum but instead of using PN sequences for coding, we use random residue sequences. Such a system can provide cryptographic security whose strength would depend on the number of code sequences being used.
Stability and Complexity of Minimising Probabilistic Automata
Venue: arXiv cs.FL 2014
Year: 2014

We consider the state-minimisation problem for weighted and probabilistic automata. We provide a numerically stable polynomial-time minimisation algorithm for weighted automata, with guaranteed bounds on the numerical error when run with floating-point arithmetic. Our algorithm can also be used for "lossy" minimisation with bounded error. We show an application in image compression. In the second part of the paper we study the complexity of the minimisation problem for probabilistic automata. We prove that the problem is NP-hard and in PSPACE, improving a recent EXPTIME-result.
An Argumentation-Based Framework to Address the Attribution Problem in Cyber-Warfare
Venue: arXiv cs.CR 2014
Year: 2014

Attributing a cyber-operation through the use of multiple pieces of technical evidence (i.e., malware reverse-engineering and source tracking) and conventional intelligence sources (i.e., human or signals intelligence) is a difficult problem not only due to the effort required to obtain evidence, but the ease with which an adversary can plant false evidence. In this paper, we introduce a formal reasoning system called the InCA (Intelligent Cyber Attribution) framework that is designed to aid an analyst in the attribution of a cyber-operation even when the available information is conflicting and/or uncertain. Our approach combines argumentation-based reasoning, logic programming, and probabilistic models to not only attribute an operation but also explain to the analyst why the system reaches its conclusions.
Approximately Minwise Independence with Twisted Tabulation
Venue: arXiv cs.DS 2014
Year: 2014

A random hash function $h$ is $\varepsilon$-minwise if for any set $S$, $|S|=n$, and element $x\in S$, $\Pr[h(x)=\min h(S)]=(1\pm\varepsilon)/n$. Minwise hash functions with low bias $\varepsilon$ have widespread applications within similarity estimation. Hashing from a universe $[u]$, the twisted tabulation hashing of Pǎtraşcu and Thorup [SODA'13] makes $c=O(1)$ lookups in tables of size $u^{1/c}$. Twisted tabulation was invented to get good concentration for hashing based sampling. Here we show that twisted tabulation yields $\tilde O(1/u^{1/c})$-minwise hashing. In the classic independence paradigm of Wegman and Carter [FOCS'79] $\tilde O(1/u^{1/c})$-minwise hashing requires $Ω(\log u)$-independence [Indyk SODA'99]. Pǎtraşcu and Thorup [STOC'11] had shown that simple tabulation, using same space and lookups yields $\tilde O(1/n^{1/c})$-minwise independence, which is good for large sets, but useless for small sets. Our analysis uses some of the same methods, but is much cleaner bypassing a complicated induction argument.
Synchronizing automata with random inputs
Venue: arXiv cs.FL 2014
Year: 2014

We study the problem of synchronization of automata with random inputs. We present a series of automata such that the expected number of steps until synchronization is exponential in the number of states. At the same time, we show that the expected number of letters to synchronize any pair of the famous Cerny automata is at most cubic in the number of states.
Robust and Efficient Subspace Segmentation via Least Squares Regression
Venue: arXiv cs.CV 2014
Year: 2014

This paper studies the subspace segmentation problem which aims to segment data drawn from a union of multiple linear subspaces. Recent works by using sparse representation, low rank representation and their extensions attract much attention. If the subspaces from which the data drawn are independent or orthogonal, they are able to obtain a block diagonal affinity matrix, which usually leads to a correct segmentation. The main differences among them are their objective functions. We theoretically show that if the objective function satisfies some conditions, and the data are sufficiently drawn from independent subspaces, the obtained affinity matrix is always block diagonal. Furthermore, the data sampling can be insufficient if the subspaces are orthogonal. Some existing methods are all special cases. Then we present the Least Squares Regression (LSR) method for subspace segmentation. It takes advantage of data correlation, which is common in real data. LSR encourages a grouping effect which tends to group highly correlated data together. Experimental results on the Hopkins 155 database and Extended Yale Database B show that our method significantly outperforms state-of-the-art methods. Beyond segmentation accuracy, all experiments demonstrate that LSR is much more efficient.
Inventions on Adaptable Menu: A TRIZ based analysis
Venue: arXiv cs.HC 2014
Year: 2014

The menu is one of the most widely used elements of a graphical user interface. The objective of a menu system is to provide various commands and functions to the user in an easy way so that the user can just select the desired operation from a given list instead of typing a complex command in the command prompt. In a conventional menu system the menu items or options are hard-coded in the computer program. The programmer or developer composes menu items at the time of development. The developer tries to include all options that he feels may be required by the user in future. Although the items are decided from "requirement analysis" and other studies, it is difficult to know the exact need of a user at a future period of time. This leads to inclusion of a lot of items in the menu, which leads to user confusion and frustration. Thus there is a need for adaptable menu that can be changed according to user requirement. The items of the adaptable menu should change from user to user and from time to time depending on the program context and likelihood of user selection. This article defines the Ideal Final Result of a dropdown menu system, defines the desirable functions of an adaptable menu, finds and solves the contradictions faced in achieving the desirable functions, and illustrates six selected cases on adaptable menu from US patent database.
10 inventions on Improving Toolbars: A TRIZ based analysis
Venue: arXiv cs.HC 2014
Year: 2014

Toolbar is one among the popular elements of a graphical user interface. The other popular elements of graphical user interface are buttons, menu, scrollbar, dialog box etc., all of which provide easy access to various functions of a GUI System. A toolbar often does a similar function as the menu but with certain differences. A menu has the advantage of holding a large number of items without needing any additional screen space. In contrast, each button on the toolbar permanently occupies some space on the screen. It is not possible to implement large number of functions through a toolbar, as they will occupy more and more valuable screen space. However, the toolbar has an advantage as it gives a single click access to any function unlike a menu system where the user has to navigate through sub-menus to ultimate discover the item he is looking for. This article explores the desired features of a toolbar and the ideal features of an advanced toolbar. The contradictions are described from a TRIZ perspective and solutions are derived using Inventive principles. Besides the article illustrates 10 inventions on improving Toolbars selected from US patent database.
Semi-Streaming Set Cover
Venue: arXiv cs.DS 2014
Year: 2014

This paper studies the set cover problem under the semi-streaming model. The underlying set system is formalized in terms of a hypergraph $G = (V, E)$ whose edges arrive one-by-one and the goal is to construct an edge cover $F \subseteq E$ with the objective of minimizing the cardinality (or cost in the weighted case) of $F$. We consider a parameterized relaxation of this problem, where given some $0 \leq ε< 1$, the goal is to construct an edge $(1 - ε)$-cover, namely, a subset of edges incident to all but an $ε$-fraction of the vertices (or their benefit in the weighted case). The key limitation imposed on the algorithm is that its space is limited to (poly)logarithmically many bits per vertex. Our main result is an asymptotically tight trade-off between $ε$ and the approximation ratio: We design a semi-streaming algorithm that on input graph $G$, constructs a succinct data structure $\mathcal{D}$ such that for every $0 \leq ε< 1$, an edge $(1 - ε)$-cover that approximates the optimal edge \mbox{($1$-)cover} within a factor of $f(ε, n)$ can be extracted from $\mathcal{D}$ (efficiently and with no additional space requirements), where \[ f(ε, n) = \left\{ \begin{array}{ll} O (1 / ε), & \text{if } ε> 1 / \sqrt{n} \\ O (\sqrt{n}), & \text{otherwise} \end{array} \right. \, . \] In particular for the traditional set cover problem we obtain an $O(\sqrt{n})$-approximation. This algorithm is proved to be best possible by establishing a family (parameterized by $ε$) of matching lower bounds.
Inventions on using sound and speech in GUI
Venue: arXiv cs.HC 2014
Year: 2014

Voice Recognition (VR) facilitates a human interaction with the machine. VR may be used to replace the manual task of pushing buttons on a wireless telephone keypad. This is particularly useful when the hands of the user are busy with other activities like driving a car. However, the VRS system has several limitations. The VRS requires lot of training and customization in order to be effectively used by individual users as each individual falls into different voice patterns. Besides the voice interface is complex and is not as reliable as the keyboard or mouse. This article illustrates some interesting inventions on using sound and voice in Graphical User Interfaces.