OpenRaiser/Intern-Atlas huggingface dataset:
Peer-to-Peer Secure Multi-Party Numerical Computation
Venue: arXiv cs.CR 2008
Year: 2008

We propose an efficient framework for enabling secure multi-party numerical computations in a Peer-to-Peer network. This problem arises in a range of applications such as collaborative filtering, distributed computation of trust and reputation, monitoring and numerous other tasks, where the computing nodes would like to preserve the privacy of their inputs while performing a joint computation of a certain function. Although there is a rich literature in the field of distributed systems security concerning secure multi-party computation, in practice it is hard to deploy those methods in very large scale Peer-to-Peer networks. In this work, we examine several possible approaches and discuss their feasibility. Among the possible approaches, we identify a single approach which is both scalable and theoretically secure. An additional novel contribution is that we show how to compute the neighborhood based collaborative filtering, a state-of-the-art collaborative filtering algorithm, winner of the Netflix progress prize of the year 2007. Our solution computes this algorithm in a Peer-to-Peer network, using a privacy preserving computation, without loss of accuracy. Using extensive large scale simulations on top of real Internet topologies, we demonstrate the applicability of our approach. As far as we know, we are the first to implement such a large scale secure multi-party simulation of networks of millions of nodes and hundreds of millions of edges.
A Gaussian Belief Propagation Solver for Large Scale Support Vector Machines
Venue: arXiv cs.LG 2008
Year: 2008

Support vector machines (SVMs) are an extremely successful type of classification and regression algorithms. Building an SVM entails solving a constrained convex quadratic programming problem, which is quadratic in the number of training samples. We introduce an efficient parallel implementation of an support vector regression solver, based on the Gaussian Belief Propagation algorithm (GaBP). In this paper, we demonstrate that methods from the complex system domain could be utilized for performing efficient distributed computation. We compare the proposed algorithm to previously proposed distributed and single-node SVM solvers. Our comparison shows that the proposed algorithm is just as accurate as these solvers, while being significantly faster, especially for large datasets. We demonstrate scalability of the proposed algorithm to up to 1,024 computing nodes and hundreds of thousands of data points using an IBM Blue Gene supercomputer. As far as we know, our work is the largest parallel implementation of belief propagation ever done, demonstrating the applicability of this algorithm for large scale distributed computing systems.
Demand allocation with latency cost functions
Venue: arXiv cs.DM 2008
Year: 2008

We address the exact resolution of a MINLP model where resources can be activated in order to satisfy a demand (a partitioning constraint) while minimizing total cost. Cost functions are convex latency functions plus a fixed activation cost. A branch and bound algorithm is devised, featuring three important characteristics. First, the lower bound (therefore each subproblem) can be computed in O(nlog n). Second, to break symmetries resulting in improved efficiency, the branching scheme is n-ary (instead of the "classical" binary). Third, a very affective heuristic is used to compute a good upper bound at the root node of the enumeration tree. All three features lead to a successful comparison against CPLEX MIPQ, which is the fastest among several commercial and open-source solvers: computational results showing this fact are provided.
Gaussian Belief Propagation Based Multiuser Detection
Venue: arXiv cs.IT 2008
Year: 2008

In this work, we present a novel construction for solving the linear multiuser detection problem using the Gaussian Belief Propagation algorithm. Our algorithm yields an efficient, iterative and distributed implementation of the MMSE detector. We compare our algorithm's performance to a recent result and show an improved memory consumption, reduced computation steps and a reduction in the number of sent messages. We prove that recent work by Montanari et al. is an instance of our general algorithm, providing new convergence results for both algorithms.
Finite Word Length Effects on Transmission Rate in Zero Forcing Linear Precoding for Multichannel DSL
Venue: arXiv cs.IT 2008
Year: 2008

Crosstalk interference is the limiting factor in transmission over copper lines. Crosstalk cancelation techniques show great potential for enabling the next leap in DSL transmission rates. An important issue when implementing crosstalk cancelation techniques in hardware is the effect of finite world length on performance. In this paper we provide an analysis of the performance of linear zero-forcing precoders, used for crosstalk compensation, in the presence of finite word length errors. We quantify analytically the trade off between precoder word length and transmission rate degradation. More specifically, we prove a simple formula for the transmission rate loss as a function of the number of bits used for precoding, the signal to noise ratio, and the standard line parameters. We demonstrate, through simulations on real lines, the accuracy of our estimates. Moreover, our results are stable in the presence of channel estimation errors. Finally, we show how to use these estimates as a design tool for DSL linear crosstalk precoders. For example, we show that for standard VDSL2 precoded systems, 14 bits representation of the precoder entries results in capacity loss below 1% for lines over 300m.
SOSEMANUK: a fast software-oriented stream cipher
Venue: arXiv cs.CR 2008
Year: 2008

Sosemanuk is a new synchronous software-oriented stream cipher, corresponding to Profile 1 of the ECRYPT call for stream cipher primitives. Its key length is variable between 128 and 256 bits. It ac- commodates a 128-bit initial value. Any key length is claimed to achieve 128-bit security. The Sosemanuk cipher uses both some basic design principles from the stream cipher SNOW 2.0 and some transformations derived from the block cipher SERPENT. Sosemanuk aims at improv- ing SNOW 2.0 both from the security and from the efficiency points of view. Most notably, it uses a faster IV-setup procedure. It also requires a reduced amount of static data, yielding better performance on several architectures.
Disproving the Neighborhood Conjecture
Venue: arXiv cs.GT 2008
Year: 2008

We study the following Maker/Breaker game. Maker and Breaker take turns in choosing vertices from a given n-uniform hypergraph F, with Maker going first. Maker's goal is to completely occupy a hyperedge and Breaker tries to avoid this. Beck conjectures that if the maximum neighborhood size of F is at most 2^(n-1) then Breaker has a winning strategy. We disprove this conjecture by establishing an n-uniform hypergraph with maximum neighborhood size 3*2^(n-3) where Maker has a winning strategy. Moreover, we show how to construct an n-uniform hypergraph with maximum degree 2^(n-1)/n where Maker has a winning strategy. Finally we show that each n-uniform hypergraph with maximum degree at most 2^(n-2)/(en) has a proper halving 2-coloring, which solves another open problem posed by Beck related to the Neighborhood Conjecture.
Characterizing 1-Dof Henneberg-I graphs with efficient configuration spaces
Venue: arXiv cs.CG 2008
Year: 2008

We define and study exact, efficient representations of realization spaces of a natural class of underconstrained 2D Euclidean Distance Constraint Systems(EDCS) or Frameworks based on 1-dof Henneberg-I graphs. Each representation corresponds to a choice of parameters and yields a different parametrized configuration space. Our notion of efficiency is based on the algebraic complexities of sampling the configuration space and of obtaining a realization from the sample (parametrized) configuration. Significantly, we give purely combinatorial characterizations that capture (i) the class of graphs that have efficient configuration spaces and (ii) the possible choices of representation parameters that yield efficient configuration spaces for a given graph. Our results automatically yield an efficient algorithm for sampling realizations, without missing extreme or boundary realizations. In addition, our results formally show that our definition of efficient configuration space is robust and that our characterizations are tight. We choose the class of 1-dof Henneberg-I graphs in order to take the next step in a systematic and graded program of combinatorial characterizations of efficient configuration spaces. In particular, the results presented here are the first characterizations that go beyond graphs that have connected and convex configuration spaces.
Faster and better: a machine learning approach to corner detection
Venue: arXiv cs.CV 2008
Year: 2008

The repeatability and efficiency of a corner detector determines how likely it is to be useful in a real-world application. The repeatability is importand because the same scene viewed from different positions should yield features which correspond to the same real-world 3D locations [Schmid et al 2000]. The efficiency is important because this determines whether the detector combined with further processing can operate at frame rate. Three advances are described in this paper. First, we present a new heuristic for feature detection, and using machine learning we derive a feature detector from this which can fully process live PAL video using less than 5% of the available processing time. By comparison, most other detectors cannot even operate at frame rate (Harris detector 115%, SIFT 195%). Second, we generalize the detector, allowing it to be optimized for repeatability, with little loss of efficiency. Third, we carry out a rigorous comparison of corner detectors based on the above repeatability criterion applied to 3D scenes. We show that despite being principally constructed for speed, on these stringent tests, our heuristic detector significantly outperforms existing feature detectors. Finally, the comparison demonstrates that using machine learning produces significant improvements in repeatability, yielding a detector that is both very fast and very high quality.
Finite-SNR Diversity-Multiplexing Tradeoff and Optimum Power Allocation in Bidirectional Cooperative Networks
Venue: arXiv cs.IT 2008
Year: 2008

This paper focuses on analog network coding (ANC) and time division broadcasting (TDBC) which are two major protocols used in bidirectional cooperative networks. Lower bounds of the outage probabilities of those two protocols are derived first. Those lower bounds are extremely tight in the whole signal-to-noise ratio (SNR) range irrespective of the values of channel variances. Based on those lower bounds, finite-SNR diversity-multiplexing tradeoffs of the ANC and TDBC protocols are obtained. Secondly, we investigate how to efficiently use channel state information (CSI) in those two protocols. Specifically, an optimum power allocation scheme is proposed for the ANC protocol. It simultaneously minimizes the outage probability and maximizes the total mutual information of this protocol. For the TDBC protocol, an optimum method to combine the received signals at the relay terminal is developed under an equal power allocation assumption. This method minimizes the outage probability and maximizes the total mutual information of the TDBC protocol at the same time.
Linear Time Encoding of LDPC Codes
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, we propose a linear complexity encoding method for arbitrary LDPC codes. We start from a simple graph-based encoding method ``label-and-decide.'' We prove that the ``label-and-decide'' method is applicable to Tanner graphs with a hierarchical structure--pseudo-trees-- and that the resulting encoding complexity is linear with the code block length. Next, we define a second type of Tanner graphs--the encoding stopping set. The encoding stopping set is encoded in linear complexity by a revised label-and-decide algorithm--the ``label-decide-recompute.'' Finally, we prove that any Tanner graph can be partitioned into encoding stopping sets and pseudo-trees. By encoding each encoding stopping set or pseudo-tree sequentially, we develop a linear complexity encoding method for general LDPC codes where the encoding complexity is proved to be less than $4 \cdot M \cdot (\overline{k} - 1)$, where $M$ is the number of independent rows in the parity check matrix and $\overline{k}$ represents the mean row weight of the parity check matrix.
BER and Outage Probability Approximations for LMMSE Detectors on Correlated MIMO Channels
Venue: arXiv cs.IT 2008
Year: 2008

This paper is devoted to the study of the performance of the Linear Minimum Mean-Square Error receiver for (receive) correlated Multiple-Input Multiple-Output systems. By the random matrix theory, it is well-known that the Signal-to-Noise Ratio (SNR) at the output of this receiver behaves asymptotically like a Gaussian random variable as the number of receive and transmit antennas converge to +$\infty$ at the same rate. However, this approximation being inaccurate for the estimation of some performance metrics such as the Bit Error Rate and the outage probability, especially for small system dimensions, Li et al. proposed convincingly to assume that the SNR follows a generalized Gamma distribution which parameters are tuned by computing the first three asymptotic moments of the SNR. In this article, this technique is generalized to (receive) correlated channels, and closed-form expressions for the first three asymptotic moments of the SNR are provided. To obtain these results, a random matrix theory technique adapted to matrices with Gaussian elements is used. This technique is believed to be simple, efficient, and of broad interest in wireless communications. Simulations are provided, and show that the proposed technique yields in general a good accuracy, even for small system dimensions.
Iterated Regret Minimization: A More Realistic Solution Concept
Venue: arXiv cs.GT 2008
Year: 2008

For some well-known games, such as the Traveler's Dilemma or the Centipede Game, traditional game-theoretic solution concepts--and most notably Nash equilibrium--predict outcomes that are not consistent with empirical observations. In this paper, we introduce a new solution concept, iterated regret minimization, which exhibits the same qualitative behavior as that observed in experiments in many games of interest, including Traveler's Dilemma, the Centipede Game, Nash bargaining, and Bertrand competition. As the name suggests, iterated regret minimization involves the iterated deletion of strategies that do not minimize regret.
The many faces of optimism - Extended version
Venue: arXiv cs.AI 2008
Year: 2008

The exploration-exploitation dilemma has been an intriguing and unsolved problem within the framework of reinforcement learning. "Optimism in the face of uncertainty" and model building play central roles in advanced exploration methods. Here, we integrate several concepts and obtain a fast and simple algorithm. We show that the proposed algorithm finds a near-optimal policy in polynomial time, and give experimental evidence that it is robust and efficient compared to its ascendants.
Grid Computing in the Collider Detector at Fermilab (CDF) scientific experiment
Venue: arXiv cs.DC 2008
Year: 2008

The computing model for the Collider Detector at Fermilab (CDF) scientific experiment has evolved since the beginning of the experiment. Initially CDF computing was comprised of dedicated resources located in computer farms around the world. With the wide spread acceptance of grid computing in High Energy Physics, CDF computing has migrated to using grid computing extensively. CDF uses computing grids around the world. Each computing grid has required different solutions. The use of portals as interfaces to the collaboration computing resources has proven to be an extremely useful technique allowing the CDF physicists transparently migrate from using dedicated computer farm to using computing located in grid farms often away from Fermilab. Grid computing at CDF continues to evolve as the grid standards and practices change.
Social Learning Methods in Board Games
Venue: arXiv cs.AI 2008
Year: 2008

This paper discusses the effects of social learning in training of game playing agents. The training of agents in a social context instead of a self-play environment is investigated. Agents that use the reinforcement learning algorithms are trained in social settings. This mimics the way in which players of board games such as scrabble and chess mentor each other in their clubs. A Round Robin tournament and a modified Swiss tournament setting are used for the training. The agents trained using social settings are compared to self play agents and results indicate that more robust agents emerge from the social training setting. Higher state space games can benefit from such settings as diverse set of agents will have multiple strategies that increase the chances of obtaining more experienced players at the end of training. The Social Learning trained agents exhibit better playing experience than self play agents. The modified Swiss playing style spawns a larger number of better playing agents as the population size increases.
Characterising Testing Preorders for Finite Probabilistic Processes
Venue: arXiv cs.LO 2008
Year: 2008

In 1992 Wang & Larsen extended the may- and must preorders of De Nicola and Hennessy to processes featuring probabilistic as well as nondeterministic choice. They concluded with two problems that have remained open throughout the years, namely to find complete axiomatisations and alternative characterisations for these preorders. This paper solves both problems for finite processes with silent moves. It characterises the may preorder in terms of simulation, and the must preorder in terms of failure simulation. It also gives a characterisation of both preorders using a modal logic. Finally it axiomatises both preorders over a probabilistic version of CSP.
Modeling Spatial and Temporal Dependencies of User Mobility in Wireless Mobile Networks
Venue: arXiv cs.NI 2008
Year: 2008

Realistic mobility models are fundamental to evaluate the performance of protocols in mobile ad hoc networks. Unfortunately, there are no mobility models that capture the non-homogeneous behaviors in both space and time commonly found in reality, while at the same time being easy to use and analyze. Motivated by this, we propose a time-variant community mobility model, referred to as the TVC model, which realistically captures spatial and temporal correlations. We devise the communities that lead to skewed location visiting preferences, and time periods that allow us to model time dependent behaviors and periodic re-appearances of nodes at specific locations. To demonstrate the power and flexibility of the TVC model, we use it to generate synthetic traces that match the characteristics of a number of qualitatively different mobility traces, including wireless LAN traces, vehicular mobility traces, and human encounter traces. More importantly, we show that, despite the high level of realism achieved, our TVC model is still theoretically tractable. To establish this, we derive a number of important quantities related to protocol performance, such as the average node degree, the hitting time, and the meeting time, and provide examples of how to utilize this theory to guide design decisions in routing protocols.
Locally computable approximations for spectral clustering and absorption times of random walks
Venue: arXiv cs.DM 2008
Year: 2008

We address the problem of determining a natural local neighbourhood or "cluster" associated to a given seed vertex in an undirected graph. We formulate the task in terms of absorption times of random walks from other vertices to the vertex of interest, and observe that these times are well approximated by the components of the principal eigenvector of the corresponding fundamental matrix of the graph's adjacency matrix. We further present a locally computable gradient-descent method to estimate this Dirichlet-Fiedler vector, based on minimising the respective Rayleigh quotient. Experimental evaluation shows that the approximations behave well and yield well-defined local clusters.
An Eye Tracking Study into the Effects of Graph Layout
Venue: arXiv cs.HC 2008
Year: 2008

Graphs are typically visualized as node-link diagrams. Although there is a fair amount of research focusing on crossing minimization to improve readability, little attention has been paid on how to handle crossings when they are an essential part of the final visualizations. This requires us to understand how people read graphs and how crossings affect reading performance. As an initial step to this end, a preliminary eye tracking experiment was conducted. The specific purpose of this experiment was to test the effects of crossing angles and geometric-path tendency on eye movements and performance. Sixteen subjects performed both path search and node locating tasks with six drawings. The results showed that small angles can slow down and trigger extra eye movements, causing delays for path search tasks, whereas crossings have little impact on node locating tasks. Geometric-path tendency indicates that a path between two nodes can become harder to follow when many branches of the path go toward the target node. The insights obtained are discussed with a view to further confirmation in future work.
On Granular Knowledge Structures
Venue: arXiv cs.AI 2008
Year: 2008

Knowledge plays a central role in human and artificial intelligence. One of the key characteristics of knowledge is its structured organization. Knowledge can be and should be presented in multiple levels and multiple views to meet people's needs in different levels of granularities and from different perspectives. In this paper, we stand on the view point of granular computing and provide our understanding on multi-level and multi-view of knowledge through granular knowledge structures (GKS). Representation of granular knowledge structures, operations for building granular knowledge structures and how to use them are investigated. As an illustration, we provide some examples through results from an analysis of proceeding papers. Results show that granular knowledge structures could help users get better understanding of the knowledge source from set theoretical, logical and visual point of views. One may consider using them to meet specific needs or solve certain kinds of problems.
Exponential-Time Approximation of Hard Problems
Venue: arXiv cs.DS 2008
Year: 2008

We study optimization problems that are neither approximable in polynomial time (at least with a constant factor) nor fixed parameter tractable, under widely believed complexity assumptions. Specifically, we focus on Maximum Independent Set, Vertex Coloring, Set Cover, and Bandwidth. In recent years, many researchers design exact exponential-time algorithms for these and other hard problems. The goal is getting the time complexity still of order $O(c^n)$, but with the constant $c$ as small as possible. In this work we extend this line of research and we investigate whether the constant $c$ can be made even smaller when one allows constant factor approximation. In fact, we describe a kind of approximation schemes -- trade-offs between approximation factor and the time complexity. We study two natural approaches. The first approach consists of designing a backtracking algorithm with a small search tree. We present one result of that kind: a $(4r-1)$-approximation of Bandwidth in time $O^*(2^{n/r})$, for any positive integer $r$. The second approach uses general transformations from exponential-time exact algorithms to approximations that are faster but still exponential-time. For example, we show that for any reduction rate $r$, one can transform any $O^*(c^n)$-time algorithm for Set Cover into a $(1+\ln r)$-approximation algorithm running in time $O^*(c^{n/r})$. We believe that results of that kind extend the applicability of exact algorithms for NP-hard problems.