OpenRaiser/Intern-Atlas huggingface dataset:
Predicting the popularity of online content
Venue: arXiv cs.CY 2008
Year: 2008

We present a method for accurately predicting the long time popularity of online content from early measurements of user access. Using two content sharing portals, Youtube and Digg, we show that by modeling the accrual of views and votes on content offered by these services we can predict the long-term dynamics of individual submissions from initial data. In the case of Digg, measuring access to given stories during the first two hours allows us to forecast their popularity 30 days ahead with remarkable accuracy, while downloads of Youtube videos need to be followed for 10 days to attain the same performance. The differing time scales of the predictions are shown to be due to differences in how content is consumed on the two portals: Digg stories quickly become outdated, while Youtube videos are still found long after they are initially submitted to the portal. We show that predictions are more accurate for submissions for which attention decays quickly, whereas predictions for evergreen content will be prone to larger errors.
Doppler Spread Estimation by Subspace Tracking for OFDM Systems
Venue: arXiv cs.IT 2008
Year: 2008

This paper proposes a novel maximum Doppler spread estimation algorithm for OFDM systems with the comb-type pilot pattern. By tracking the drifting delay subspace of the multipath channel, the time correlation function is measured at a high accuracy, which accordingly improves the estimation accuracy of the maximum Doppler spread considerably.
Secure Arithmetic Computation with No Honest Majority
Venue: arXiv cs.CR 2008
Year: 2008

We study the complexity of securely evaluating arithmetic circuits over finite rings. This question is motivated by natural secure computation tasks. Focusing mainly on the case of two-party protocols with security against malicious parties, our main goals are to: (1) only make black-box calls to the ring operations and standard cryptographic primitives, and (2) minimize the number of such black-box calls as well as the communication overhead. We present several solutions which differ in their efficiency, generality, and underlying intractability assumptions. These include: 1. An unconditionally secure protocol in the OT-hybrid model which makes a black-box use of an arbitrary ring $R$, but where the number of ring operations grows linearly with (an upper bound on) $\log|R|$. 2. Computationally secure protocols in the OT-hybrid model which make a black-box use of an underlying ring, and in which the number of ring operations does not grow with the ring size. These results extend a previous approach of Naor and Pinkas for secure polynomial evaluation (SIAM J. Comput., 35(5), 2006). 3. A protocol for the rings $\mathbb{Z}_m=\mathbb{Z}/m\mathbb{Z}$ which only makes a black-box use of a homomorphic encryption scheme. When $m$ is prime, the (amortized) number of calls to the encryption scheme for each gate of the circuit is constant. All of our protocols are in fact UC-secure in the OT-hybrid model and can be generalized to multiparty computation with an arbitrary number of malicious parties.
Incomplete decode-and-forward protocol using distributed space-time block codes
Venue: arXiv cs.IT 2008
Year: 2008

In this work, we explore the introduction of distributed space-time codes in decode-and-forward (DF) protocols. A first protocol named the Asymmetric DF is presented. It is based on two phases of different lengths, defined so that signals can be fully decoded at relays. This strategy brings full diversity but the symbol rate is not optimal. To solve this problem a second protocol named the Incomplete DF is defined. It is based on an incomplete decoding at the relays reducing the length of the first phase. This last strategy brings both full diversity and full symbol rate. The outage probability and the simulation results show that the Incomplete DF has better performance than any existing DF protocol and than the non-orthogonal amplify-and-forward (NAF) strategy using the same space-time codes. Moreover the diversity-multiplexing gain tradeoff (DMT) of this new DF protocol is proven to be the same as the one of the NAF.
Algorithmic complexity and randomness in elastic solids
Venue: arXiv cs.CC 2008
Year: 2008

A system comprised of an elastic solid and its response to an external random force sequence is shown to behave based on the principles of the theory of algorithmic complexity and randomness. The solid distorts the randomness of an input force sequence in a way proportional to its algorithmic complexity. We demonstrate this by numerical analysis of a one-dimensional vibrating elastic solid (the system) on which we apply a maximally random input force. The level of complexity of the system is controlled via external parameters. The output response is the field of displacements observed at several positions on the body. The algorithmic complexity and stochasticity of the resulting output displacement sequence is measured and compared against the complexity of the system. The results show that the higher the system complexity the more random-deficient the output sequence. This agrees with the theory introduced in [16] which states that physical systems such as this behave as algorithmic selection-rules which act on random actions in their surroundings.
Étude longitudinale d'une procédure de modélisation de connaissances en matière de gestion du territoire agricole
Venue: arXiv cs.AI 2008
Year: 2008

This paper gives an introduction to this issue, and presents the framework and the main steps of the Rosa project. Four teams of researchers, agronomists, computer scientists, psychologists and linguists were involved during five years within this project that aimed at the development of a knowledge based system. The purpose of the Rosa system is the modelling and the comparison of farm spatial organizations. It relies on a formalization of agronomical knowledge and thus induces a joint knowledge building process involving both the agronomists and the computer scientists. The paper describes the steps of the modelling process as well as the filming procedures set up by the psychologists and linguists in order to make explicit and to analyze the underlying knowledge building process.
Raptor Codes and Cryptographic Issues
Venue: arXiv cs.IT 2008
Year: 2008

In this paper two cryptographic methods are introduced. In the first method the presence of a certain size subgroup of persons can be checked for an action to take place. For this we use fragments of Raptor codes delivered to the group members. In the other method a selection of a subset of objects can be made secret. Also, it can be proven afterwards, what the original selection was.
How to turn a scripting language into a domain specific language for computer algebra
Venue: arXiv cs.SC 2008
Year: 2008

We have developed two computer algebra systems, meditor [Jolly:2007] and JAS [Kredel:2006]. These CAS systems are available as Java libraries. For the use-case of interactively entering and manipulating mathematical expressions, there is a need of a scripting front-end for our libraries. Most other CAS invent and implement their own scripting interface for this purpose. We, however, do not want to reinvent the wheel and propose to use a contemporary scripting language with access to Java code. In this paper we discuss the requirements for a scripting language in computer algebra and check whether the languages Python, Ruby, Groovy and Scala meet these requirements. We conclude that, with minor problems, any of these languages is suitable for our purpose.
Efficient Multiplication of Dense Matrices over GF(2)
Venue: arXiv cs.MS 2008
Year: 2008

We describe an efficient implementation of a hierarchy of algorithms for multiplication of dense matrices over the field with two elements (GF(2)). In particular we present our implementation -- in the M4RI library -- of Strassen-Winograd matrix multiplication and the "Method of the Four Russians" multiplication (M4RM) and compare it against other available implementations. Good performance is demonstrated on on AMD's Opteron and particulary good performance on Intel's Core 2 Duo. The open-source M4RI library is available stand-alone as well as part of the Sage mathematics software. In machine terms, addition in GF(2) is logical-XOR, and multiplication is logical-AND, thus a machine word of 64-bits allows one to operate on 64 elements of GF(2) in parallel: at most one CPU cycle for 64 parallel additions or multiplications. As such, element-wise operations over GF(2) are relatively cheap. In fact, in this paper, we conclude that the actual bottlenecks are memory reads and writes and issues of data locality. We present our empirical findings in relation to minimizing these and give an analysis thereof.
A Basic Framework for the Cryptanalysis of Digital Chaos-Based Cryptography
Venue: arXiv cs.CR 2008
Year: 2008

Chaotic cryptography is based on the properties of chaos as source of entropy. Many different schemes have been proposed to take advantage of those properties and to design new strategies to encrypt information. However, the right and efficient use of chaos in the context of cryptography requires a thorough knowledge about the dynamics of the selected chaotic system. Indeed, if the final encryption system reveals enough information about the underlying chaotic system it could be possible for a cryptanalyst to get the key, part of the key or some information somehow equivalent to the key just analyzing those dynamical properties leaked by the cryptosystem. This paper shows what those dynamical properties are and how a cryptanalyst can use them to prove the inadequacy of an encryption system for the secure exchange of information. This study is performed through the introduction of a series of mathematical tools which should be the basic framework of cryptanalysis in the context of digital chaos-based cryptography.
Magic Fairy Tales as Source for Interface Metaphors
Venue: arXiv cs.HC 2008
Year: 2008

The work is devoted to a problem of search of metaphors for interactive systems and systems based on Virtual Reality (VR) environments. The analysis of magic fairy tales as a source of metaphors for interface and virtual reality is offered. Some results of design process based on magic metaphors are considered.
A Transformation--Based Approach for the Design of Parallel/Distributed Scientific Software: the FFT
Venue: arXiv cs.SE 2008
Year: 2008

We describe a methodology for designing efficient parallel and distributed scientific software. This methodology utilizes sequences of mechanizable algebra--based optimizing transformations. In this study, we apply our methodology to the FFT, starting from a high--level algebraic algorithm description. Abstract multiprocessor plans are developed and refined to specify which computations are to be done by each processor. Templates are then created that specify the locations of computations and data on the processors, as well as data flow among processors. Templates are developed in both the MPI and OpenMP programming styles. Preliminary experiments comparing code constructed using our methodology with code from several standard scientific libraries show that our code is often competitive and sometimes performs better. Interestingly, our code handled a larger range of problem sizes on one target architecture.
Exact phase transition of backtrack-free search with implications on the power of greedy algorithms
Venue: arXiv cs.AI 2008
Year: 2008

Backtracking is a basic strategy to solve constraint satisfaction problems (CSPs). A satisfiable CSP instance is backtrack-free if a solution can be found without encountering any dead-end during a backtracking search, implying that the instance is easy to solve. We prove an exact phase transition of backtrack-free search in some random CSPs, namely in Model RB and in Model RD. This is the first time an exact phase transition of backtrack-free search can be identified on some random CSPs. Our technical results also have interesting implications on the power of greedy algorithms, on the width of random hypergraphs and on the exact satisfiability threshold of random CSPs.
An Almost Optimal Rank Bound for Depth-3 Identities
Venue: arXiv cs.CC 2008
Year: 2008

We show that the rank of a depth-3 circuit (over any field) that is simple, minimal and zero is at most k^3\log d. The previous best rank bound known was 2^{O(k^2)}(\log d)^{k-2} by Dvir and Shpilka (STOC 2005). This almost resolves the rank question first posed by Dvir and Shpilka (as we also provide a simple and minimal identity of rank Ω(k\log d)). Our rank bound significantly improves (dependence on k exponentially reduced) the best known deterministic black-box identity tests for depth-3 circuits by Karnin and Shpilka (CCC 2008). Our techniques also shed light on the factorization pattern of nonzero depth-3 circuits, most strikingly: the rank of linear factors of a simple, minimal and nonzero depth-3 circuit (over any field) is at most k^3\log d. The novel feature of this work is a new notion of maps between sets of linear forms, called "ideal matchings", used to study depth-3 circuits. We prove interesting structural results about depth-3 identities using these techniques. We believe that these can lead to the goal of a deterministic polynomial time identity test for these circuits.
A Rational Deconstruction of Landin's SECD Machine with the J Operator
Venue: arXiv cs.PL 2008
Year: 2008

Landin's SECD machine was the first abstract machine for applicative expressions, i.e., functional programs. Landin's J operator was the first control operator for functional languages, and was specified by an extension of the SECD machine. We present a family of evaluation functions corresponding to this extension of the SECD machine, using a series of elementary transformations (transformation into continu-ation-passing style (CPS) and defunctionalization, chiefly) and their left inverses (transformation into direct style and refunctionalization). To this end, we modernize the SECD machine into a bisimilar one that operates in lockstep with the original one but that (1) does not use a data stack and (2) uses the caller-save rather than the callee-save convention for environments. We also identify that the dump component of the SECD machine is managed in a callee-save way. The caller-save counterpart of the modernized SECD machine precisely corresponds to Thielecke's double-barrelled continuations and to Felleisen's encoding of J in terms of call/cc. We then variously characterize the J operator in terms of CPS and in terms of delimited-control operators in the CPS hierarchy. As a byproduct, we also present several reduction semantics for applicative expressions with the J operator, based on Curien's original calculus of explicit substitutions. These reduction semantics mechanically correspond to the modernized versions of the SECD machine and to the best of our knowledge, they provide the first syntactic theories of applicative expressions with the J operator.
chi2TeX Semi-automatic translation from chiwriter to LaTeX
Venue: arXiv cs.SE 2008
Year: 2008

Semi-automatic translation of math-filled book from obsolete ChiWriter format to LaTeX. Is it possible? Idea of criterion whether to use automatic or hand mode for translation. Illustrations.
Performance Modeling and Evaluation for Information-Driven Networks
Venue: arXiv cs.PF 2008
Year: 2008

Information-driven networks include a large category of networking systems, where network nodes are aware of information delivered and thus can not only forward data packets but may also perform information processing. In many situations, the quality of service (QoS) in information-driven networks is provisioned with the redundancy in information. Traditional performance models generally adopt evaluation measures suitable for packet-oriented service guarantee, such as packet delay, throughput, and packet loss rate. These performance measures, however, do not align well with the actual need of information-driven networks. New performance measures and models for information-driven networks, despite their importance, have been mainly blank, largely because information processing is clearly application dependent and cannot be easily captured within a generic framework. To fill the vacancy, we present a new performance evaluation framework particularly tailored for information-driven networks, based on the recent development of stochastic network calculus. We analyze the QoS with respect to information delivery and study the scheduling problem with the new performance metrics. Our analytical framework can be used to calculate the network capacity in information delivery and in the meantime to help transmission scheduling for a large body of systems where QoS is stochastically guaranteed with the redundancy in information.
Search Result Clustering via Randomized Partitioning of Query-Induced Subgraphs
Venue: arXiv cs.IR 2008
Year: 2008

In this paper, we present an approach to search result clustering, using partitioning of underlying link graph. We define the notion of "query-induced subgraph" and formulate the problem of search result clustering as a problem of efficient partitioning of given subgraph into topic-related clusters. Also, we propose a novel algorithm for approximative partitioning of such graph, which results in cluster quality comparable to the one obtained by deterministic algorithms, while operating in more efficient computation time, suitable for practical implementations. Finally, we present a practical clustering search engine developed as a part of this research and use it to get results about real-world performance of proposed concepts.
Soft-Input Soft-Output Sphere Decoding
Venue: arXiv cs.IT 2008
Year: 2008

Soft-input soft-output (SISO) detection algorithms form the basis for iterative decoding. The associated computational complexity often poses significant challenges for practical receiver implementations, in particular in the context of multiple-input multiple-output wireless systems. In this paper, we present a low-complexity SISO sphere decoder which is based on the single tree search paradigm, proposed originally for soft-output detection in Studer et al., IEEE J-SAC, 2008. The algorithm incorporates clipping of the extrinsic log-likelihood ratios in the tree search, which not only results in significant complexity savings, but also allows to cover a large performance/complexity trade-off region by adjusting a single parameter.
How robust is quicksort average complexity?
Venue: arXiv cs.DS 2008
Year: 2008

The paper questions the robustness of average case time complexity of the fast and popular quicksort algorithm. Among the six standard probability distributions examined in the paper, only continuous uniform, exponential and standard normal are supporting it whereas the others are supporting the worst case complexity measure. To the question -why are we getting the worst case complexity measure each time the average case measure is discredited? -- one logical answer is average case complexity under the universal distribution equals worst case complexity. This answer, which is hard to challenge, however gives no idea as to which of the standard probability distributions come under the umbrella of universality. The morale is that average case complexity measures, in cases where they are different from those in worst case, should be deemed as robust provided only they get the support from at least the standard probability distributions, both discrete and continuous. Regretfully, this is not the case with quicksort.
List Decoding Tensor Products and Interleaved Codes
Venue: arXiv cs.IT 2008
Year: 2008

We design the first efficient algorithms and prove new combinatorial bounds for list decoding tensor products of codes and interleaved codes. We show that for {\em every} code, the ratio of its list decoding radius to its minimum distance stays unchanged under the tensor product operation (rather than squaring, as one might expect). This gives the first efficient list decoders and new combinatorial bounds for some natural codes including multivariate polynomials where the degree in each variable is bounded. We show that for {\em every} code, its list decoding radius remains unchanged under $m$-wise interleaving for an integer $m$. This generalizes a recent result of Dinur et al \cite{DGKS}, who proved such a result for interleaved Hadamard codes (equivalently, linear transformations). Using the notion of generalized Hamming weights, we give better list size bounds for {\em both} tensoring and interleaving of binary linear codes. By analyzing the weight distribution of these codes, we reduce the task of bounding the list size to bounding the number of close-by low-rank codewords. For decoding linear transformations, using rank-reduction together with other ideas, we obtain list size bounds that are tight over small fields.
Joint Adaptive Modulation-Coding and Cooperative ARQ for Wireless Relay Networks
Venue: arXiv cs.IT 2008
Year: 2008

This paper presents a cross-layer approach to jointly design adaptive modulation and coding (AMC) at the physical layer and cooperative truncated automatic repeat request (ARQ) protocol at the data link layer. We first derive an exact closed form expression for the spectral efficiency of the proposed joint AMC-cooperative ARQ scheme. Aiming at maximizing this system performance measure, we then optimize an AMC scheme which directly satisfies a prescribed packet loss rate constraint at the data-link layer. The results indicate that utilizing cooperative ARQ as a retransmission strategy, noticeably enhances the spectral efficiency compared with the system that employs AMC alone at the physical layer. Moreover, the proposed adaptive rate cooperative ARQ scheme outperforms the fixed rate counterpart when the transmission modes at the source and relay are chosen based on the channel statistics. This in turn quantifies the possible gain achieved by joint design of AMC and ARQ in wireless relay networks.
Channel State Prediction, Feedback and Scheduling for a Multiuser MIMO-OFDM Downlink
Venue: arXiv cs.IT 2008
Year: 2008

We consider the downlink of a MIMO-OFDM wireless systems where the base-station (BS) has M antennas and serves K single-antenna user terminals (UT) with K larger than or equal to M. Users estimate their channel vectors from common downlink pilot symbols and feed back a prediction, which is used by the BS to compute the linear beamforming matrix for the next time slot and to select the users to be served according to the proportional fair scheduling (PFS) algorithm. We consider a realistic physical channel model used as a benchmark in standardization and some alternatives for the channel estimation and prediction scheme. We show that a parametric method based on ESPRIT is able to accurately predict the channel even for relatively high user mobility. However, there exists a class of channels characterized by large Doppler spread (high mobility) and clustered angular spread for which prediction is intrinsically difficult and all considered methods fail. We propose a modified PFS that take into account the "predictability" state of the UTs, and significantly outperform the classical PFS in the presence of prediction errors. The main conclusion of this work is that multiuser MIMO downlink yields very good performance even in the presence of high mobility users, provided that the nonpredictable users are handled appropriately
The Good, the Bad, and the Ugly: three different approaches to break their watermarking system
Venue: arXiv cs.GR 2008
Year: 2008

The Good is Blondie, a wandering gunman with a strong personal sense of honor. The Bad is Angel Eyes, a sadistic hitman who always hits his mark. The Ugly is Tuco, a Mexican bandit who's always only looking out for himself. Against the backdrop of the BOWS contest, they search for a watermark in gold buried in three images. Each knows only a portion of the gold's exact location, so for the moment they're dependent on each other. However, none are particularly inclined to share...