OpenRaiser/Intern-Atlas huggingface dataset:
Simultaneous Integer Relation Detection and Its an Application
Venue: arXiv cs.SC 2010
Year: 2010

Let $\mathbf{x_1}, ..., \mathbf{x_t} \in \mathbb{R}^{n}$. A simultaneous integer relation (SIR) for $\mathbf{x_1}, ..., \mathbf{x_t}$ is a vector $\mathbf{m} \in \mathbb{Z}^{n}\setminus\{\textbf{0}\}$ such that $\mathbf{x_i}^T\mathbf{m} = 0$ for $i = 1, ..., t$. In this paper, we propose an algorithm SIRD to detect an SIR for real vectors, which constructs an SIR within $\mathcal {O}(n^4 + n^3 \log λ(X))$ arithmetic operations, where $λ(X)$ is the least Euclidean norm of SIRs for $\mathbf{x_1}, >..., \mathbf{x_t}$. One can easily generalize SIRD to complex number field. Experimental results show that SIRD is practical and better than another detecting algorithm in the literature. In its application, we present a new algorithm for finding the minimal polynomial of an arbitrary complex algebraic number from its an approximation, which is not based on LLL. We also provide a sufficient condition on the precision of the approximate value, which depends only on the height and the degree of the algebraic number.
A Randomized Sublinear Time Parallel GCD Algorithm for the EREW PRAM
Venue: arXiv cs.DS 2010
Year: 2010

We present a randomized parallel algorithm that computes the greatest common divisor of two integers of n bits in length with probability 1-o(1) that takes O(n loglog n / log n) expected time using n^{6+ε} processors on the EREW PRAM parallel model of computation. We believe this to be the first randomized sublinear time algorithm on the EREW PRAM for this problem.
Algebraic Ordinals
Venue: arXiv cs.FL 2010
Year: 2010

An algebraic tree T is one determined by a finite system of fixed point equations. The frontier \Fr(T) of an algebraic tree t is linearly ordered by the lexicographic order \lex. When (\Fr(T),\lex) is well-ordered, its order type is an \textbf{algebraic ordinal}. We prove that the algebraic ordinals are exactly the ordinals less than $ω^{ω^ω}$.
Protocols and Performance Limits for Half-Duplex Relay Networks
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, protocols for the half-duplex relay channel are introduced and performance limits are analyzed. Relay nodes underly an orthogonality constraint, which prohibits simultaneous receiving and transmitting on the same time-frequency resource. Based upon this practical consideration, different protocols are discussed and evaluated using a Gaussian system model. For the considered scenarios compress-and-forward based protocols dominate for a wide range of parameters decode-and-forward protocols. In this paper, a protocol with one compress-and-forward and one decode-and-forward based relay is introduced. Just as the cut-set bound, which operates in a mode where relays transmit alternately, both relays support each other. Furthermore, it is shown that in practical systems a random channel access provides only marginal performance gains if any.
Primitive Recursive Presentations of Automata and their Products
Venue: arXiv cs.FL 2010
Year: 2010

Methods for specifying Moore type state machines (transducers) abstractly via primitive recursive functions and for defining parallel composition via simultaneous primitive recursion are discussed. The method is mostly of interest as a concise and convenient way of working with the complex state systems found in computer programming and engineering, but a short section indicates connections to algebraic automata theory and the theorem of Krohn and Rhodes.
Maximum-Likelihood Sequence Detector for Dynamic Mode High Density Probe Storage
Venue: arXiv cs.IT 2010
Year: 2010

There is an increasing need for high density data storage devices driven by the increased demand of consumer electronics. In this work, we consider a data storage system that operates by encoding information as topographic profiles on a polymer medium. A cantilever probe with a sharp tip (few nm radius) is used to create and sense the presence of topographic profiles, resulting in a density of few Tb per in.2. The prevalent mode of using the cantilever probe is the static mode that is harsh on the probe and the media. In this article, the high quality factor dynamic mode operation, that is less harsh on the media and the probe, is analyzed. The read operation is modeled as a communication channel which incorporates system memory due to inter-symbol interference and the cantilever state. We demonstrate an appropriate level of abstraction of this complex nanoscale system that obviates the need for an involved physical model. Next, a solution to the maximum likelihood sequence detection problem based on the Viterbi algorithm is devised. Experimental and simulation results demonstrate that the performance of this detector is several orders of magnitude better than the performance of other existing schemes.
Polynomial Time Algorithms for Minimum Energy Scheduling
Venue: arXiv cs.DS 2010
Year: 2010

The aim of power management policies is to reduce the amount of energy consumed by computer systems while maintaining satisfactory level of performance. One common method for saving energy is to simply suspend the system during the idle times. No energy is consumed in the suspend mode. However, the process of waking up the system itself requires a certain fixed amount of energy, and thus suspending the system is beneficial only if the idle time is long enough to compensate for this additional energy expenditure. In the specific problem studied in the paper, we have a set of jobs with release times and deadlines that need to be executed on a single processor. Preemptions are allowed. The processor requires energy L to be woken up and, when it is on, it uses one unit of energy per one unit of time. It has been an open problem whether a schedule minimizing the overall energy consumption can be computed in polynomial time. We solve this problem in positive, by providing an O(n^5)-time algorithm. In addition we provide an O(n^4)-time algorithm for computing the minimum energy schedule when all jobs have unit length.
Randomized Scheduling Algorithm for Queueing Networks
Venue: arXiv cs.IT 2010
Year: 2010

There has recently been considerable interest in design of low-complexity, myopic, distributed and stable scheduling policies for constrained queueing network models that arise in the context of emerging communication networks. Here, we consider two representative models. One, a model for the collection of wireless nodes communicating through a shared medium, that represents randomly varying number of packets in the queues at the nodes of networks. Two, a buffered circuit switched network model for an optical core of future Internet, to capture the randomness in calls or flows present in the network. The maximum weight scheduling policy proposed by Tassiulas and Ephremide in 1992 leads to a myopic and stable policy for the packet-level wireless network model. But computationally it is very expensive (NP-hard) and centralized. It is not applicable to the buffered circuit switched network due to the requirement of non-premption of the calls in the service. As the main contribution of this paper, we present a stable scheduling algorithm for both of these models. The algorithm is myopic, distributed and performs few logical operations at each node per unit time.
Codes in Permutations and Error Correction for Rank Modulation
Venue: arXiv cs.IT 2010
Year: 2010

Codes for rank modulation have been recently proposed as a means of protecting flash memory devices from errors. We study basic coding theoretic problems for such codes, representing them as subsets of the set of permutations of $n$ elements equipped with the Kendall tau distance. We derive several lower and upper bounds on the size of codes. These bounds enable us to establish the exact scaling of the size of optimal codes for large values of $n$. We also show the existence of codes whose size is within a constant factor of the sphere packing bound for any fixed number of errors.
Canonical extension and canonicity via DCPO presentations
Venue: arXiv cs.LO 2010
Year: 2010

The canonical extension of a lattice is in an essential way a two-sided completion. Domain theory, on the contrary, is primarily concerned with one-sided completeness. In this paper, we show two things. Firstly, that the canonical extension of a lattice can be given an asymmetric description in two stages: a free co-directed meet completion, followed by a completion by \emph{selected} directed joins. Secondly, we show that the general techniques for dcpo presentations of dcpo algebras used in the second stage of the construction immediately give us the well-known canonicity result for bounded lattices with operators.
Effects of Mechanical Coupling on the Dynamics of Balancing Tasks
Venue: arXiv cs.CE 2010
Year: 2010

Coupled human balancing tasks are investigated based on both pseudo-neural controllers characterized by time-delayed feedback with random gain and natural human balancing tasks. It is shown numerically that, compared to single balancing tasks, balancing tasks coupled by mechanical structures exhibit enhanced stability against balancing errors in terms of both amplitude and velocity and also improve the tracking ability of the controllers. We then perform an experiment in which numerical pseudo-neural controllers are replaced with natural human balancing tasks carried out using computer mice. The results reveal that the coupling structure generates asymmetric tracking abilities in subjects whose tracking abilities are nearly symmetric in their single balancing tasks.
Practical Schemes For Privacy & Security Enhanced RFID
Venue: arXiv cs.CR 2010
Year: 2010

Proper privacy protection in RFID systems is important. However, many of the schemes known are impractical, either because they use hash functions instead of the more hardware efficient symmetric encryption schemes as a efficient cryptographic primitive, or because they incur a rather costly key search time penalty at the reader. Moreover, they do not allow for dynamic, fine-grained access control to the tag that cater for more complex usage scenarios. In this paper we investigate such scenarios, and propose a model and corresponding privacy friendly protocols for efficient and fine-grained management of access permissions to tags. In particular we propose an efficient mutual authentication protocol between a tag and a reader that achieves a reasonable level of privacy, using only symmetric key cryptography on the tag, while not requiring a costly key-search algorithm at the reader side. Moreover, our protocol is able to recover from stolen readers.
Qualitative Analysis of Partially-observable Markov Decision Processes
Venue: arXiv cs.LO 2010
Year: 2010

We study observation-based strategies for partially-observable Markov decision processes (POMDPs) with omega-regular objectives. An observation-based strategy relies on partial information about the history of a play, namely, on the past sequence of observations. We consider the qualitative analysis problem: given a POMDP with an omega-regular objective, whether there is an observation-based strategy to achieve the objective with probability~1 (almost-sure winning), or with positive probability (positive winning). Our main results are twofold. First, we present a complete picture of the computational complexity of the qualitative analysis of POMDP s with parity objectives (a canonical form to express omega-regular objectives) and its subclasses. Our contribution consists in establishing several upper and lower bounds that were not known in literature. Second, we present optimal bounds (matching upper and lower bounds) on the memory required by pure and randomized observation-based strategies for the qualitative analysis of POMDP s with parity objectives and its subclasses.
The Universal Recommender
Venue: arXiv cs.IR 2010
Year: 2010

We describe the Universal Recommender, a recommender system for semantic datasets that generalizes domain-specific recommenders such as content-based, collaborative, social, bibliographic, lexicographic, hybrid and other recommenders. In contrast to existing recommender systems, the Universal Recommender applies to any dataset that allows a semantic representation. We describe the scalable three-stage architecture of the Universal Recommender and its application to Internet Protocol Television (IPTV). To achieve good recommendation accuracy, several novel machine learning and optimization problems are identified. We finally give a brief argument supporting the need for machine learning recommenders.
Semidefinite programming, harmonic analysis and coding theory
Venue: arXiv cs.IT 2010
Year: 2010

These lecture notes where presented as a course of the CIMPA summer school in Manila, July 20-30, 2009, Semidefinite programming in algebraic combinatorics. This version is an update June 2010.
Sensitive White Space Detection with Spectral Covariance Sensing
Venue: arXiv cs.NI 2010
Year: 2010

This paper proposes a novel, highly effective spectrum sensing algorithm for cognitive radio and whitespace applications. The proposed spectral covariance sensing (SCS) algorithm exploits the different statistical correlations of the received signal and noise in the frequency domain. Test statistics are computed from the covariance matrix of a partial spectrogram and compared with a decision threshold to determine whether a primary signal or arbitrary type is present or not. This detector is analyzed theoretically and verified through realistic open-source simulations using actual digital television signals captured in the US. Compared to the state of the art in the literature, SCS improves sensitivity by 3 dB for the same dwell time, which is a very significant improvement for this application. Further, it is shown that SCS is highly robust to noise uncertainty, whereas many other spectrum sensors are not.
Recovering low-rank matrices from few coefficients in any basis
Venue: arXiv cs.IT 2010
Year: 2010

We present novel techniques for analyzing the problem of low-rank matrix recovery. The methods are both considerably simpler and more general than previous approaches. It is shown that an unknown (n x n) matrix of rank r can be efficiently reconstructed from only O(n r nu log^2 n) randomly sampled expansion coefficients with respect to any given matrix basis. The number nu quantifies the "degree of incoherence" between the unknown matrix and the basis. Existing work concentrated mostly on the problem of "matrix completion" where one aims to recover a low-rank matrix from randomly selected matrix elements. Our result covers this situation as a special case. The proof consists of a series of relatively elementary steps, which stands in contrast to the highly involved methods previously employed to obtain comparable results. In cases where bounds had been known before, our estimates are slightly tighter. We discuss operator bases which are incoherent to all low-rank matrices simultaneously. For these bases, we show that O(n r nu log n) randomly sampled expansion coefficients suffice to recover any low-rank matrix with high probability. The latter bound is tight up to multiplicative constants.
Minimum cost mirror sites using network coding: Replication vs. coding at the source nodes
Venue: arXiv cs.IT 2010
Year: 2010

Content distribution over networks is often achieved by using mirror sites that hold copies of files or portions thereof to avoid congestion and delay issues arising from excessive demands to a single location. Accordingly, there are distributed storage solutions that divide the file into pieces and place copies of the pieces (replication) or coded versions of the pieces (coding) at multiple source nodes. We consider a network which uses network coding for multicasting the file. There is a set of source nodes that contains either subsets or coded versions of the pieces of the file. The cost of a given storage solution is defined as the sum of the storage cost and the cost of the flows required to support the multicast. Our interest is in finding the storage capacities and flows at minimum combined cost. We formulate the corresponding optimization problems by using the theory of information measures. In particular, we show that when there are two source nodes, there is no loss in considering subset sources. For three source nodes, we derive a tight upper bound on the cost gap between the coded and uncoded cases. We also present algorithms for determining the content of the source nodes.
Towards Plugging Privacy Leaks in Domain Name System
Venue: arXiv cs.CR 2010
Year: 2010

Privacy leaks are an unfortunate and an integral part of the current Internet domain name resolution. Each DNS query generated by a user reveals -- to one or more DNS servers -- the origin and target of that query. Over time, a user's browsing behavior might be exposed to entities with little or no trust. Current DNS privacy leaks stem from fundamental DNS features and are not easily fixable by simple patches. Moreover, privacy issues have been overlooked by DNS security efforts (i.e. DNSSEC) and are thus likely to propagate into future versions of DNS. In order to mitigate privacy issues in current DNS, this paper proposes a Privacy-Preserving Domain Name System (PPDNS), which maintains privacy during domain name resolution. PPDNS is based on distributed hash tables (DHTs), an alternative naming infrastructure, and computational private information retrieval (cPIR), an advanced cryptographic construct. PPDNS takes advantage of the DHT's index structure to improve name resolution query privacy, while leveraging cPIR to reduce communication overhead for bandwidth-sensitive clients. Our analysis shows that PPDNS is a viable approach for obtaining a higher degree of privacy for name resolution queries. PPDNS also serves as a demonstration of blending advanced systems techniques with their cryptographic counterparts.
Wee LCP
Venue: arXiv cs.DS 2010
Year: 2010

We prove that longest common prefix (LCP) information can be stored in much less space than previously known. More precisely, we show that in the presence of the text and the suffix array, o(n) additional bits are sufficient to answer LCP-queries asymptotically in the same time that is needed to retrieve an entry from the suffix array. This yields the smallest compressed suffix tree with sub-logarithmic navigation time.
Least and Greatest Fixed Points in Linear Logic
Venue: arXiv cs.LO 2010
Year: 2010

The first-order theory of MALL (multiplicative, additive linear logic) over only equalities is an interesting but weak logic since it cannot capture unbounded (infinite) behavior. Instead of accounting for unbounded behavior via the addition of the exponentials (! and ?), we add least and greatest fixed point operators. The resulting logic, which we call muMALL, satisfies two fundamental proof theoretic properties: we establish weak normalization for it, and we design a focused proof system that we prove complete. That second result provides a strong normal form for cut-free proof structures that can be used, for example, to help automate proof search. We show how these foundations can be applied to intuitionistic logic.
Searching a bitstream in linear time for the longest substring of any given density
Venue: arXiv cs.DS 2010
Year: 2010

Given an arbitrary bitstream, we consider the problem of finding the longest substring whose ratio of ones to zeroes equals a given value. The central result of this paper is an algorithm that solves this problem in linear time. The method involves (i) reformulating the problem as a constrained walk through a sparse matrix, and then (ii) developing a data structure for this sparse matrix that allows us to perform each step of the walk in amortised constant time. We also give a linear time algorithm to find the longest substring whose ratio of ones to zeroes is bounded below by a given value. Both problems have practical relevance to cryptography and bioinformatics.
ECN verbose mode: a statistical method for network path congestion estimation
Venue: arXiv cs.NI 2010
Year: 2010

This article introduces a simple and effective methodology to determine the level of congestion in a network with an ECN-like marking scheme. The purpose of the ECN bit is to notify TCP sources of an imminent congestion in order to react before losses occur. However, ECN is a binary indicator which does not reflect the congestion level (i.e. the percentage of queued packets) of the bottleneck, thus preventing any adapted reaction. In this study, we use a counter in place of the traditional ECN marking scheme to assess the number of times a packet has crossed a congested router. Thanks to this simple counter, we drive a statistical analysis to accurately estimate the congestion level of each router on a network path. We detail in this paper an analytical method validated by some preliminary simulations which demonstrate the feasibility and the accuracy of the concept proposed. We conclude this paper with possible applications and expected future work.
The Complexity of Iterated Strategy Elimination
Venue: arXiv cs.CC 2010
Year: 2010

We consider the computational complexity of the question whether a certain strategy can be removed from a game by means of iterated elimination of dominated strategies. In particular, we study the influence of different definitions of domination and of the number of different payoff values. In addition, the consequence of restriction to constant-sum games is shown.
A Graph Model for Imperative Computation
Venue: arXiv cs.LO 2010
Year: 2010

Scott's graph model is a lambda-algebra based on the observation that continuous endofunctions on the lattice of sets of natural numbers can be represented via their graphs. A graph is a relation mapping finite sets of input values to output values. We consider a similar model based on relations whose input values are finite sequences rather than sets. This alteration means that we are taking into account the order in which observations are made. This new notion of graph gives rise to a model of affine lambda-calculus that admits an interpretation of imperative constructs including variable assignment, dereferencing and allocation. Extending this untyped model, we construct a category that provides a model of typed higher-order imperative computation with an affine type system. An appropriate language of this kind is Reynolds's Syntactic Control of Interference. Our model turns out to be fully abstract for this language. At a concrete level, it is the same as Reddy's object spaces model, which was the first "state-free" model of a higher-order imperative programming language and an important precursor of games models. The graph model can therefore be seen as a universal domain for Reddy's model.
A Discourse-based Approach in Text-based Machine Translation
Venue: arXiv cs.CL 2010
Year: 2010

This paper presents a theoretical research based approach to ellipsis resolution in machine translation. The formula of discourse is applied in order to resolve ellipses. The validity of the discourse formula is analyzed by applying it to the real world text, i.e., newspaper fragments. The source text is converted into mono-sentential discourses where complex discourses require further dissection either directly into primitive discourses or first into compound discourses and later into primitive ones. The procedure of dissection needs further improvement, i.e., discovering as many primitive discourse forms as possible. An attempt has been made to investigate new primitive discourses or patterns from the given text.
Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems
Venue: arXiv cs.DS 2010
Year: 2010

We design the first polynomial time approximation schemes (PTASs) for the Minimum Betweenness problem in tournaments and some related higher arity ranking problems. This settles the approximation status of the Betweenness problem in tournaments along with other ranking problems which were open for some time now. The results depend on a new technique of dealing with fragile ranking constraints and could be of independent interest.