OpenRaiser/Intern-Atlas huggingface dataset:
Cell-Probe Bounds for Online Edit Distance and Other Pattern Matching Problems
Venue: arXiv cs.DS 2014
Year: 2014

We give cell-probe bounds for the computation of edit distance, Hamming distance, convolution and longest common subsequence in a stream. In this model, a fixed string of $n$ symbols is given and one $δ$-bit symbol arrives at a time in a stream. After each symbol arrives, the distance between the fixed string and a suffix of most recent symbols of the stream is reported. The cell-probe model is perhaps the strongest model of computation for showing data structure lower bounds, subsuming in particular the popular word-RAM model. * We first give an $Ω((δ\log n)/(w+\log\log n))$ lower bound for the time to give each output for both online Hamming distance and convolution, where $w$ is the word size. This bound relies on a new encoding scheme and for the first time holds even when $w$ is as small as a single bit. * We then consider the online edit distance and longest common subsequence problems in the bit-probe model ($w=1$) with a constant sized input alphabet. We give a lower bound of $Ω(\sqrt{\log n}/(\log\log n)^{3/2})$ which applies for both problems. This second set of results relies both on our new encoding scheme as well as a carefully constructed hard distribution. * Finally, for the online edit distance problem we show that there is an $O((\log n)^2/w)$ upper bound in the cell-probe model. This bound gives a contrast to our new lower bound and also establishes an exponential gap between the known cell-probe and RAM model complexities.
New routing techniques and their applications
Venue: arXiv cs.DS 2014
Year: 2014

Let $G=(V,E)$ be an undirected graph with $n$ vertices and $m$ edges. We obtain the following new routing schemes: - A routing scheme for unweighted graphs that uses $\tilde O(\frac{1}ε n^{2/3})$ space at each vertex and $\tilde O(1/ε)$-bit headers, to route a message between any pair of vertices $u,v\in V$ on a $(2 + ε,1)$-stretch path, i.e., a path of length at most $(2+ε)\cdot d(u,v)+1$. This should be compared to the $(2,1)$-stretch and $\tilde O(n^{5/3})$ space distance oracle of Patrascu and Roditty [FOCS'10 and SIAM J. Comput. 2014] and to the $(2,1)$-stretch routing scheme of Abraham and Gavoille [DISC'11] that uses $\tilde O( n^{3/4})$ space at each vertex. - A routing scheme for weighted graphs with normalized diameter $D$, that uses $\tilde O(\frac{1}ε n^{1/3}\log D)$ space at each vertex and $\tilde O(\frac{1}ε\log D)$-bit headers, to route a message between any pair of vertices on a $(5+ε)$-stretch path. This should be compared to the $5$-stretch and $\tilde O(n^{4/3})$ space distance oracle of Thorup and Zwick [STOC'01 and J. ACM. 2005] and to the $7$-stretch routing scheme of Thorup and Zwick [SPAA'01] that uses $\tilde O( n^{1/3})$ space at each vertex. Since a $5$-stretch routing scheme must use tables of $Ω( n^{1/3})$ space our result is almost tight. - For an integer $\ell>1$, a routing scheme for unweighted graphs that uses $\tilde O(\ell\frac{1}ε n^{\ell/(2\ell \pm 1)})$ space at each vertex and $\tilde O(\frac{1}ε)$-bit headers, to route a message between any pair of vertices on a $(3\pm2/\ell+ε,2)$-stretch path. - A routing scheme for weighted graphs, that uses $\tilde O(\frac{1}εn^{1/k}\log D)$ space at each vertex and $\tilde O(\frac{1}ε\log D)$-bit headers, to route a message between any pair of vertices on a $(4k-7+ε)$-stretch path.
On Partial Wait-Freedom in Transactional Memory
Venue: arXiv cs.DC 2014
Year: 2014

Transactional memory (TM) is a convenient synchronization tool that allows concurrent threads to declare sequences of instructions on shared data as speculative \emph{transactions} with "all-or-nothing" semantics. It is known that dynamic transactional memory cannot provide \emph{wait-free} progress in the sense that every transaction commits in a finite number of its own steps. In this paper, we explore the costs of providing wait-freedom to only a \emph{subset} of transactions. Since most transactional workloads are believed to be read-dominated, we require that read-only transactions commit in the wait-free manner, while updating transactions are guaranteed to commit only if they run in the absence of concurrency. We show that this kind of partial wait-freedom, combined with attractive requirements like read invisibility or disjoint-access parallelism, incurs considerable complexity costs.
Detection of Clones in Digital Images
Venue: arXiv cs.MM 2014
Year: 2014

During the recent years, tampering of digital images has become a general habit among people and professionals. As a result, establishment of image authenticity has become a key issue in fields those make use of digital images. Authentication of an image involves separation of original camera outputs from their tampered or Stego counterparts. Digital image cloning being a popular type of image tampering, in this paper we have experimentally analyzed seven different algorithms of cloning detection such as the simple overlapped block matching with lexicographic sorting (SOBMwLS) algorithm, block matching with discrete cosine transformation, principal component analysis, discrete wavelet transformation and singular value decomposition performed on the blocks (DCT, DWT, PCA, SVD), two combination models where, DCT and DWT are combined with singular value decomposition (DCTSVD and DWTSVD. A comparative study of all these techniques with respect to their time complexities and robustness of detection against various post processing operations such as cropping, brightness and contrast adjustments are presented in the paper.
Extending Acyclicity Notions for Existential Rules (\emph{long version})
Venue: arXiv cs.AI 2014
Year: 2014

Existential rules have been proposed for representing ontological knowledge, specifically in the context of Ontology-Based Query Answering. Entailment with existential rules is undecidable. We focus in this paper on conditions that ensure the termination of a breadth-first forward chaining algorithm known as the chase. First, we propose a new tool that allows to extend existing acyclicity conditions ensuring chase termination, while keeping good complexity properties. Second, we consider the extension to existential rules with nonmonotonic negation under stable model semantics and further extend acyclicity results obtained in the positive case.
How,when and how much a card deck is well shuffled?
Venue: arXiv cs.DM 2014
Year: 2014

The thesis consider the mixing of few (3-4) card shuffling as well as of large (52 card) deck. The thesis is showing the limit on the shuffling to homogeneity elaborated in short program; the thesis is in italian.
RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response
Venue: arXiv cs.CR 2014
Year: 2014

Randomized Aggregatable Privacy-Preserving Ordinal Response, or RAPPOR, is a technology for crowdsourcing statistics from end-user client software, anonymously, with strong privacy guarantees. In short, RAPPORs allow the forest of client data to be studied, without permitting the possibility of looking at individual trees. By applying randomized response in a novel manner, RAPPOR provides the mechanisms for such collection as well as for efficient, high-utility analysis of the collected data. In particular, RAPPOR permits statistics to be collected on the population of client-side strings with strong privacy guarantees for each client, and without linkability of their reports. This paper describes and motivates RAPPOR, details its differential-privacy and utility guarantees, discusses its practical deployment and properties in the face of different attack models, and, finally, gives results of its application to both synthetic and real-world data.
High SNR BER Comparison of Coherent and Differentially Coherent Modulation Schemes in Lognormal Fading Channels
Venue: arXiv cs.IT 2014
Year: 2014

Using an auxiliary random variable technique, we prove that binary differential phase-shift keying and binary phase-shift keying have the same asymptotic bit-error rate performance in lognormal fading channels. We also show that differential quaternary phase-shift keying is exactly 2.32 dB worse than quaternary phase-shift keying over the lognormal fading channels in high signal-to-noise ratio regimes.
Quantum Cost Optimization for Reversible Sequential Circuit
Venue: arXiv cs.ET 2014
Year: 2014

Reversible sequential circuits are going to be the significant memory blocks for the forthcoming computing devices for their ultra low power consumption. Therefore design of various types of latches has been considered a major objective for the researchers quite a long time. In this paper we proposed efficient design of reversible sequential circuits that are optimized in terms of quantum cost, delay and garbage outputs. For this we proposed a new 3*3 reversible gate called SAM gate and we then design efficient sequential circuits using SAM gate along with some of the basic reversible logic gates.
Your click decides your fate: Inferring Information Processing and Attrition Behavior from MOOC Video Clickstream Interactions
Venue: arXiv cs.HC 2014
Year: 2014

In this work, we explore video lecture interaction in Massive Open Online Courses (MOOCs), which is central to student learning experience on these educational platforms. As a research contribution, we operationalize video lecture clickstreams of students into cognitively plausible higher level behaviors, and construct a quantitative information processing index, which can aid instructors to better understand MOOC hurdles and reason about unsatisfactory learning outcomes. Our results illustrate how such a metric inspired by cognitive psychology can help answer critical questions regarding students' engagement, their future click interactions and participation trajectories that lead to in-video & course dropouts. Implications for research and practice are discussed
Who negatively influences me? Formalizing diffusion dynamics of negative exposure leading to student attrition in MOOCs
Venue: arXiv cs.SI 2014
Year: 2014

In this work, we explain the underlying interaction mechanisms which govern students' influence on each other in Massive Open Online Courses (MOOCs). Specifically, we outline different ways in which students can be negatively exposed to their peers on MOOC forums and discuss a simple formulation of learning network diffusion, which formalizes the essence of how such an influence spreads and can potentially lead to student attrition over time. We also view the limitations of our student modeling in the light of real world MOOC behavior and consequently suggest ways of extending the diffusion model to handle more complex assumptions. Such an understanding is very beneficial for MOOC designers and instructors to create a conducive learning environment that supports students' growth and increases their engagement in the course.
"Your click decides your fate": Leveraging clickstream patterns from MOOC videos to infer students' information processing & attrition behavior
Venue: arXiv cs.HC 2014
Year: 2014

With an expansive and ubiquitously available gold mine of educational data, Massive Open Online courses (MOOCs) have become the an important foci of learning analytics research. The hope is that this new surge of development will bring the vision of equitable access to lifelong learning opportunities within practical reach. MOOCs offer many valuable learning experiences to students, from video lectures, readings, assignments and exams, to opportunities to connect and collaborate with others through threaded discussion forums and other Web 2.0 technologies. Nevertheless, despite all this potential, MOOCs have so far failed to produce evidence that this potential is being realized in the current instantiation of MOOCs. In this work, we primarily explore video lecture interaction in Massive Open Online Courses (MOOCs), which is central to student learning experience on these educational platforms. As a research contribution, we operationalize video lecture clickstreams of students into behavioral actions, and construct a quantitative information processing index, that can aid instructors to better understand MOOC hurdles and reason about unsatisfactory learning outcomes. Our results illuminate the effectiveness of developing such a metric inspired by cognitive psychology, towards answering critical questions regarding students' engagement, their future click interactions and participation trajectories that lead to in-video dropouts. We leverage recurring click behaviors to differentiate distinct video watching profiles for students in MOOCs. Additionally, we discuss about prediction of complete course dropouts, incorporating diverse perspectives from statistics and machine learning, to offer a more nuanced view into how the second generation of MOOCs be benefited, if course instructors were to better comprehend factors that lead to student attrition.
Distributed Inference in Tree Networks using Coding Theory
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we consider the problem of distributed inference in tree based networks. In the framework considered in this paper, distributed nodes make a 1-bit local decision regarding a phenomenon before sending it to the fusion center (FC) via intermediate nodes. We propose the use of coding theory based techniques to solve this distributed inference problem in such structures. Data is progressively compressed as it moves towards the FC. The FC makes the global inference after receiving data from intermediate nodes. Data fusion at nodes as well as at the FC is implemented via error correcting codes. In this context, we analyze the performance for a given code matrix and also design the optimal code matrices at every level of the tree. We address the problems of distributed classification and distributed estimation separately and develop schemes to perform these tasks in tree networks. The proposed schemes are of practical significance due to their simple structure. We study the asymptotic inference performance of our schemes for two different classes of tree networks: fixed height tree networks, and fixed degree tree networks. We show that the proposed schemes are asymptotically optimal under certain conditions.
Mutual Information and Conditional Mean Prediction Error
Venue: arXiv cs.IT 2014
Year: 2014

Mutual information is fundamentally important for measuring statistical dependence between variables and for quantifying information transfer by signaling and communication mechanisms. It can, however, be challenging to evaluate for physical models of such mechanisms and to estimate reliably from data. Furthermore, its relationship to better known statistical procedures is still poorly understood. Here we explore new connections between mutual information and regression-based dependence measures, $ν^{-1}$, that utilise the determinant of the second-moment matrix of the conditional mean prediction error. We examine convergence properties as $ν\rightarrow0$ and establish sharp lower bounds on mutual information and capacity of the form $\mathrm{log}(ν^{-1/2})$. The bounds are tighter than lower bounds based on the Pearson correlation and ones derived using average mean square-error rate distortion arguments. Furthermore, their estimation is feasible using techniques from nonparametric regression. As an illustration we provide bootstrap confidence intervals for the lower bounds which, through use of a composite estimator, substantially improve upon inference about mutual information based on $k$-nearest neighbour estimators alone.
Principles and Parameters: a coding theory perspective
Venue: arXiv cs.CL 2014
Year: 2014

We propose an approach to Longobardi's parametric comparison method (PCM) via the theory of error-correcting codes. One associates to a collection of languages to be analyzed with the PCM a binary (or ternary) code with one code words for each language in the family and each word consisting of the binary values of the syntactic parameters of the language, with the ternary case allowing for an additional parameter state that takes into account phenomena of entailment of parameters. The code parameters of the resulting code can be compared with some classical bounds in coding theory: the asymptotic bound, the Gilbert-Varshamov bound, etc. The position of the code parameters with respect to some of these bounds provides quantitative information on the variability of syntactic parameters within and across historical-linguistic families. While computations carried out for languages belonging to the same family yield codes below the GV curve, comparisons across different historical families can give examples of isolated codes lying above the asymptotic bound.
MDPs with Unawareness
Venue: arXiv cs.AI 2014
Year: 2014

Markov decision processes (MDPs) are widely used for modeling decision-making problems in robotics, automated control, and economics. Traditional MDPs assume that the decision maker (DM) knows all states and actions. However, this may not be true in many situations of interest. We define a new framework, MDPs with unawareness (MDPUs) to deal with the possibilities that a DM may not be aware of all possible actions. We provide a complete characterization of when a DM can learn to play near-optimally in an MDPU, and give an algorithm that learns to play near-optimally when it is possible to do so, as efficiently as possible. In particular, we characterize when a near-optimal solution can be found in polynomial time.
Mapping R&D support infrastructures: A scientometric and webometric study of UK science parks
Venue: arXiv cs.CY 2014
Year: 2014

This thesis analyses UK SPs with an informetric approach to study (1) the role of public science and HEIs in research and development (R&D) networks associated with SPs, and (2) the web-based patterns that reflect the configuration of R&D support infrastructures associated with SPs.
Recommender Systems using Pennant Diagrams in Digital Libraries
Venue: arXiv cs.DL 2014
Year: 2014

In digital libraries recommendations can be valuable for researchers, e.g. recommending related literature to a given context. Typically, in a scientific context the simple presentation of related content is not sufficient. Often the users demand a more detailed view on the connection of a document and its specific recommendations. The aim of pennants introduced by Howard White (2007) is to provide the user with a graph showing the relatedness / distance between a given document and related documents. Co-citation but also co-occurrence analysis are established methods for finding related documents to a seed. A seed could be for instance an author, a keyword, or a publication. In this paper we introduce a recommender system in the digital library sowiport using pennant diagrams which can be created from co-citation and/or co-occurrence analysis. The presentation at the NKOS workshop will present demos of pennants in sowiport and will elaborate on practical questions in visualizing pennants and evaluating the utility of pennants for search.
Modular Belief Updates and Confusion about Measures of Certainty in Artificial Intelligence Research
Venue: arXiv cs.AI 2014
Year: 2014

Over the last decade, there has been growing interest in the use or measures or change in belief for reasoning with uncertainty in artificial intelligence research. An important characteristic of several methodologies that reason with changes in belief or belief updates, is a property that we term modularity. We call updates that satisfy this property modular updates. Whereas probabilistic measures of belief update - which satisfy the modularity property were first discovered in the nineteenth century, knowledge and discussion of these quantities remains obscure in artificial intelligence research. We define modular updates and discuss their inappropriate use in two influential expert systems.
Online Learning and Profit Maximization from Revealed Preferences
Venue: arXiv cs.DS 2014
Year: 2014

We consider the problem of learning from revealed preferences in an online setting. In our framework, each period a consumer buys an optimal bundle of goods from a merchant according to her (linear) utility function and current prices, subject to a budget constraint. The merchant observes only the purchased goods, and seeks to adapt prices to optimize his profits. We give an efficient algorithm for the merchant's problem that consists of a learning phase in which the consumer's utility function is (perhaps partially) inferred, followed by a price optimization step. We also consider an alternative online learning algorithm for the setting where prices are set exogenously, but the merchant would still like to predict the bundle that will be bought by the consumer for purposes of inventory or supply chain management. In contrast with most prior work on the revealed preferences problem, we demonstrate that by making stronger assumptions on the form of utility functions, efficient algorithms for both learning and profit maximization are possible, even in adaptive, online settings.
Exploiting Large-Scale MIMO Techniques for Physical Layer Security with Imperfect Channel State Information
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we study the problem of physical layer security in large-scale multiple input multiple output (LS-MIMO) systems. The large number of antenna elements in LS-MIMO system is exploited to enhance transmission security and improve system performance, especially when the eavesdropper is closer to the information source and has more antennas than the legitimate user. However, in practical systems, the problem becomes challenging because the eavesdropper channel state information (CSI) is usually unavailable without cooperation and the legitimate CSI may be imperfect due to channel estimation error. In this paper, we first analyze the performance of physical layer security without eavesdropper CSI and with imperfect legitimate CSI, and then propose an energy-efficient power allocation scheme to meet the demand for wireless security and quality of service (QoS) simultaneously. Finally, numerical results validate the effectiveness of the proposed scheme.
A Fast Hierarchical Method for Multi-script and Arbitrary Oriented Scene Text Extraction
Venue: arXiv cs.CV 2014
Year: 2014

Typography and layout lead to the hierarchical organisation of text in words, text lines, paragraphs. This inherent structure is a key property of text in any script and language, which has nonetheless been minimally leveraged by existing text detection methods. This paper addresses the problem of text segmentation in natural scenes from a hierarchical perspective. Contrary to existing methods, we make explicit use of text structure, aiming directly to the detection of region groupings corresponding to text within a hierarchy produced by an agglomerative similarity clustering process over individual regions. We propose an optimal way to construct such an hierarchy introducing a feature space designed to produce text group hypotheses with high recall and a novel stopping rule combining a discriminative classifier and a probabilistic measure of group meaningfulness based in perceptual organization. Results obtained over four standard datasets, covering text in variable orientations and different languages, demonstrate that our algorithm, while being trained in a single mixed dataset, outperforms state of the art methods in unconstrained scenarios.