OpenRaiser/Intern-Atlas huggingface dataset:
String Art: Circle Drawing Using Straight Lines
Venue: arXiv cs.GR 2008
Year: 2008

An algorithm to generate the locus of a circle using the intersection points of straight lines is proposed. The pixels on the circle are plotted independent of one another and the operations involved in finding the locus of the circle from the intersection of straight lines are parallelizable. Integer only arithmetic and algorithmic optimizations are used for speedup. The proposed algorithm makes use of an envelope to form a parabolic arc which is consequent transformed into a circle. The use of parabolic arcs for the transformation results in higher pixel errors as the radius of the circle to be drawn increases. At its current state, the algorithm presented may be suitable only for generating circles for string art.
Cryptanalysis of the SASI Ultralightweight RFID Authentication Protocol with Modular Rotations
Venue: arXiv cs.CR 2008
Year: 2008

In this work we present the first passive attack over the SASI lightweight authentication protocol with modular rotations. This can be used to fully recover the secret $ID$ of the RFID tag, which is the value the protocol is designed to conceal. The attack is described initially for recovering $\lfloor log_2(96) \rfloor=6$ bits of the secret value $ID$, a result that by itself allows to mount traceability attacks on any given tag. However, the proposed scheme can be extended to obtain any amount of bits of the secret $ID$, provided a sufficiently large number of successful consecutive sessions are eavesdropped. We also present results on the attack's efficiency, and some ideas to secure this version of the SASI protocol.
Information-theoretic resolution of perceptual WSS watermarking of non i.i.d. Gaussian signals
Venue: arXiv cs.IT 2008
Year: 2008

The theoretical foundations of data hiding have been revealed by formulating the problem as message communication over a noisy channel. We revisit the problem in light of a more general characterization of the watermark channel and of weighted distortion measures. Considering spread spectrum based information hiding, we release the usual assumption of an i.i.d. cover signal. The game-theoretic resolution of the problem reveals a generalized characterization of optimum attacks. The paper then derives closed-form expressions for the different parameters exhibiting a practical embedding and extraction technique.
Moment matrices, trace matrices and the radical of ideals
Venue: arXiv cs.SC 2008
Year: 2008

Let $f_1,...,f_s \in \mathbb{K}[x_1,...,x_m]$ be a system of polynomials generating a zero-dimensional ideal $\I$, where $\mathbb{K}$ is an arbitrary algebraically closed field. Assume that the factor algebra $\A=\mathbb{K}[x_1,...,x_m]/\I$ is Gorenstein and that we have a bound $δ>0$ such that a basis for $\A$ can be computed from multiples of $f_1,...,f_s$ of degrees at most $δ$. We propose a method using Sylvester or Macaulay type resultant matrices of $f_1,...,f_s$ and $J$, where $J$ is a polynomial of degree $δ$ generalizing the Jacobian, to compute moment matrices, and in particular matrices of traces for $\A$. These matrices of traces in turn allow us to compute a system of multiplication matrices $\{M_{x_i}|i=1,...,m\}$ of the radical $\sqrt{\I}$, following the approach in the previous work by Janovitz-Freireich, Rónyai and Szántó. Additionally, we give bounds for $δ$ for the case when $\I$ has finitely many projective roots in $\mathbb{P}^m_\CC$.
Convergence to Equilibrium in Local Interaction Games and Ising Models
Venue: arXiv cs.GT 2008
Year: 2008

Coordination games describe social or economic interactions in which the adoption of a common strategy has a higher payoff. They are classically used to model the spread of conventions, behaviors, and technologies in societies. Here we consider a two-strategies coordination game played asynchronously between the nodes of a network. Agents behave according to a noisy best-response dynamics. It is known that noise removes the degeneracy among equilibria: In the long run, the ``risk-dominant'' behavior spreads throughout the network. Here we consider the problem of computing the typical time scale for the spread of this behavior. In particular, we study its dependence on the network structure and derive a dichotomy between highly-connected, non-local graphs that show slow convergence, and poorly connected, low dimensional graphs that show fast convergence.
An evaluation of Bradfordizing effects
Venue: arXiv cs.DL 2008
Year: 2008

The purpose of this paper is to apply and evaluate the bibliometric method Bradfordizing for information retrieval (IR) experiments. Bradfordizing is used for generating core document sets for subject-specific questions and to reorder result sets from distributed searches. The method will be applied and tested in a controlled scenario of scientific literature databases from social and political sciences, economics, psychology and medical science (SOLIS, SoLit, USB Koeln Opac, CSA Sociological Abstracts, World Affairs Online, Psyndex and Medline) and 164 standardized topics. An evaluation of the method and its effects is carried out in two laboratory-based information retrieval experiments (CLEF and KoMoHe) using a controlled document corpus and human relevance assessments. The results show that Bradfordizing is a very robust method for re-ranking the main document types (journal articles and monographs) in today's digital libraries (DL). The IR tests show that relevance distributions after re-ranking improve at a significant level if articles in the core are compared with articles in the succeeding zones. The items in the core are significantly more often assessed as relevant, than items in zone 2 (z2) or zone 3 (z3). The improvements between the zones are statistically significant based on the Wilcoxon signed-rank test and the paired T-Test.
Stackelberg Network Pricing is Hard to Approximate
Venue: arXiv cs.DS 2008
Year: 2008

In the Stackelberg Network Pricing problem, one has to assign tariffs to a certain subset of the arcs of a given transportation network. The aim is to maximize the amount paid by the user of the network, knowing that the user will take a shortest st-path once the tariffs are fixed. Roch, Savard, and Marcotte (Networks, Vol. 46(1), 57-67, 2005) proved that this problem is NP-hard, and gave an O(log m)-approximation algorithm, where m denote the number of arcs to be priced. In this note, we show that the problem is also APX-hard.
A Relaying Incentive Scheme in Multihop Cellular Networks Based on Coalitional Game with Externalities
Venue: arXiv cs.GT 2008
Year: 2008

Cooperative multihop communication can greatly increase network throughput, yet packet forwarding for other nodes involves opportunity and energy cost for relays. Thus one of the pre-requisite problems in the successful implementation of multihop transmission is how to foster cooperation among selfish nodes. Existing researches mainly adopt monetary stimulating. In this manuscript, we propose instead a simple and self-enforcing forwarding incentive scheme free of indirect monetary remunerating for asymmetric (uplink multihop, downlink single-hop) cellar network based on coalitional game theory, which comprises double compensation, namely, Inter- BEA, global stimulating policy allotting resources among relaying coalitions according to group size, and Intra-BEA, local compensating and allocating rule within coalitions. Firstly, given the global allotting policy, we introduce a fair allocation estimating approach which includes remunerating for relaying cost using Myerson value for partition function game, to enlighten the design of local allocating rules. Secondly, given the inter- and intra-BEA relay fostering approach, we check stability of coalition structures in terms of internal and external stability as well as inductive core. Theoretic analysis and numerical simulation show that our measure can provide communication opportunities for outer ring nodes and enlarge system coverage, while at the same time provide enough motivation with respect to resource allocation and energy saving for nodes in inner and middle ring to relay for own profits.
Provenance Traces
Venue: arXiv cs.PL 2008
Year: 2008

Provenance is information about the origin, derivation, ownership, or history of an object. It has recently been studied extensively in scientific databases and other settings due to its importance in helping scientists judge data validity, quality and integrity. However, most models of provenance have been stated as ad hoc definitions motivated by informal concepts such as "comes from", "influences", "produces", or "depends on". These models lack clear formalizations describing in what sense the definitions capture these intuitive concepts. This makes it difficult to compare approaches, evaluate their effectiveness, or argue about their validity. We introduce provenance traces, a general form of provenance for the nested relational calculus (NRC), a core database query language. Provenance traces can be thought of as concrete data structures representing the operational semantics derivation of a computation; they are related to the traces that have been used in self-adjusting computation, but differ in important respects. We define a tracing operational semantics for NRC queries that produces both an ordinary result and a trace of the execution. We show that three pre-existing forms of provenance for the NRC can be extracted from provenance traces. Moreover, traces satisfy two semantic guarantees: consistency, meaning that the traces describe what actually happened during execution, and fidelity, meaning that the traces "explain" how the expression would behave if the input were changed. These guarantees are much stronger than those contemplated for previous approaches to provenance; thus, provenance traces provide a general semantic foundation for comparing and unifying models of provenance in databases.
Preference Games and Personalized Equilibria, with Applications to Fractional BGP
Venue: arXiv cs.GT 2008
Year: 2008

We study the complexity of computing equilibria in two classes of network games based on flows - fractional BGP (Border Gateway Protocol) games and fractional BBC (Bounded Budget Connection) games. BGP is the glue that holds the Internet together and hence its stability, i.e. the equilibria of fractional BGP games (Haxell, Wilfong), is a matter of practical importance. BBC games (Laoutaris et al) follow in the tradition of the large body of work on network formation games and capture a variety of applications ranging from social networks and overlay networks to peer-to-peer networks. The central result of this paper is that there are no fully polynomial-time approximation schemes (unless PPAD is in FP) for computing equilibria in both fractional BGP games and fractional BBC games. We obtain this result by proving the hardness for a new and surprisingly simple game, the fractional preference game, which is reducible to both fractional BGP and BBC games. We define a new flow-based notion of equilibrium for matrix games -- personalized equilibria -- generalizing both fractional BBC and fractional BGP games. We prove not just the existence, but the existence of rational personalized equilibria for all matrix games, which implies the existence of rational equilibria for fractional BGP and BBC games. In particular, this provides an alternative proof and strengthening of the main result in [Haxell, Wilfong]. For k-player matrix games, where k = 2, we provide a combinatorial characterization leading to a polynomial-time algorithm for computing all personalized equilibria. For k >= 5, we prove that personalized equilibria are PPAD-hard to approximate in fully polynomial time. We believe that the concept of personalized equilibria has potential for real-world significance.
Analysis of Group Multiuser Detection Based on Coalitional Game
Venue: arXiv cs.GT 2008
Year: 2008

The issue of group-blind multiuser detection in MAC channel among wireless nodes in the environment of multiple networks coexisting and sharing spectrum is addressed under the Framework of coalitional game. We investigate the performance and stability of multiple access channel (MAC) with linear decorrelating multiuser detection under varying SNR, channel gains and coalitional structures, in which both single BS and multiple BSs cases were considered. The main results and conclusion are as follows: (1) the grand coalition is payoff maximizing under loose SNR; (2) it is in conformity with group and coalitional rationality forming coalition among nodes that have comparative channel gains.
Elagage d'un perceptron multicouches : utilisation de l'analyse de la variance de la sensibilité des paramètres
Venue: arXiv cs.NE 2008
Year: 2008

The stucture determination of a neural network for the modelisation of a system remain the core of the problem. Within this framework, we propose a pruning algorithm of the network based on the use of the analysis of the sensitivity of the variance of all the parameters of the network. This algorithm will be tested on two examples of simulation and its performances will be compared with three other algorithms of pruning of the literature
An Approximation of the Outage Probability for Multi-hop AF Fixed Gain Relay
Venue: arXiv cs.PF 2008
Year: 2008

In this letter, we present a closed-form approximation of the outage probability for the multi-hop amplify-and-forward (AF) relaying systems with fixed gain in Rayleigh fading channel. The approximation is derived from the outage event for each hop. The simulation results show the tightness of the proposed approximation in low and high signal-to-noise ratio (SNR) region.
Decision trees are PAC-learnable from most product distributions: a smoothed analysis
Venue: arXiv cs.LG 2008
Year: 2008

We consider the problem of PAC-learning decision trees, i.e., learning a decision tree over the n-dimensional hypercube from independent random labeled examples. Despite significant effort, no polynomial-time algorithm is known for learning polynomial-sized decision trees (even trees of any super-constant size), even when examples are assumed to be drawn from the uniform distribution on {0,1}^n. We give an algorithm that learns arbitrary polynomial-sized decision trees for {\em most product distributions}. In particular, consider a random product distribution where the bias of each bit is chosen independently and uniformly from, say, [.49,.51]. Then with high probability over the parameters of the product distribution and the random examples drawn from it, the algorithm will learn any tree. More generally, in the spirit of smoothed analysis, we consider an arbitrary product distribution whose parameters are specified only up to a [-c,c] accuracy (perturbation), for an arbitrarily small positive constant c.
Communicating the Difference of Correlated Gaussian Sources Over a MAC
Venue: arXiv cs.IT 2008
Year: 2008

This paper considers the problem of transmitting the difference of two jointly Gaussian sources over a two-user additive Gaussian noise multiple access channel (MAC). The goal is to recover this difference within an average mean squared error distortion criterion. Each transmitter has access to only one of the two Gaussian sources and is limited by an average power constraint. In this work, a lattice coding scheme that achieves a distortion within a constant of a distortion lower bound is presented if the signal to noise ratio (SNR) is greater than a threshold. Further, uncoded transmission is shown to be worse in performance to lattice coding methods. An alternative lattice coding scheme is presented that can potentially improve on the performance of uncoded transmission.
Oscillations with TCP-like Flow Control in Networks of Queues
Venue: arXiv cs.NI 2008
Year: 2008

We consider a set of flows passing through a set of servers. The injection rate into each flow is governed by a flow control that increases the injection rate when all the servers on the flow's path are empty and decreases the injection rate when some server is congested. We show that if each server's congestion is governed by the arriving traffic at the server then the system can *oscillate*. This is in contrast to previous work on flow control where congestion was modeled as a function of the flow injection rates and the system was shown to converge to a steady state that maximizes an overall network utility.
A Novel Clustering Algorithm Based on Quantum Random Walk
Venue: arXiv cs.LG 2008
Year: 2008

The enormous successes have been made by quantum algorithms during the last decade. In this paper, we combine the quantum random walk (QRW) with the problem of data clustering, and develop two clustering algorithms based on the one dimensional QRW. Then, the probability distributions on the positions induced by QRW in these algorithms are investigated, which also indicates the possibility of obtaining better results. Consequently, the experimental results have demonstrated that data points in datasets are clustered reasonably and efficiently, and the clustering algorithms are of fast rates of convergence. Moreover, the comparison with other algorithms also provides an indication of the effectiveness of the proposed approach.
Cognitive Coexistence between Infrastructure and Ad-hoc Systems
Venue: arXiv cs.IT 2008
Year: 2008

The rapid proliferation of wireless systems makes interference management more and more important. This paper presents a novel cognitive coexistence framework, which enables an infrastructure system to reduce interference to ad-hoc or peer-to-peer communication links in close proximity. Motivated by the superior resources of the infrastructure system, we study how its centralized resource allocation can accommodate the ad-hoc links based on sensing and predicting their interference patterns. Based on an ON/OFF continuous-time Markov chain model, the optimal allocation of power and transmission time is formulated as a convex optimization problem and closed-form solutions are derived. The optimal scheduling is extended to the case where the infrastructure channel is random and rate constraints need only be met in the long-term average. Finally, the multi-terminal case is addressed and the problem of optimal sub-channel allocation discussed. Numerical performance analysis illustrates that utilizing the superior flexibility of the infrastructure links can effectively mitigate interference.
Secret Communication with Feedback
Venue: arXiv cs.IT 2008
Year: 2008

Secure communication with feedback is studied. An achievability scheme in which the backward channel is used to generate a shared secret key is proposed. The scenario of binary symmetric forward and backward channels is considered, and a combination of the proposed scheme and Maurer's coding scheme is shown to achieve improved secrecy rates. The scenario of a Gaussian channel with perfect output feedback is also analyzed and the Schalkwijk-Kailath coding scheme is shown to achieve the secrecy capacity for this channel.
Efficient Isomorphism Testing for a Class of Group Extensions
Venue: arXiv cs.DS 2008
Year: 2008

The group isomorphism problem asks whether two given groups are isomorphic or not. Whereas the case where both groups are abelian is well understood and can be solved efficiently, very little is known about the complexity of isomorphism testing for nonabelian groups. In this paper we study this problem for a class of groups corresponding to one of the simplest ways of constructing nonabelian groups from abelian groups: the groups that are extensions of an abelian group A by a cyclic group of order m. We present an efficient algorithm solving the group isomorphism problem for all the groups of this class such that the order of A is coprime with m. More precisely, our algorithm runs in time almost linear in the orders of the input groups and works in the general setting where the groups are given as black-boxes.
Urologic robots and future directions
Venue: arXiv cs.RO 2008
Year: 2008

PURPOSE OF REVIEW: Robot-assisted laparoscopic surgery in urology has gained immense popularity with the daVinci system, but a lot of research teams are working on new robots. The purpose of this study is to review current urologic robots and present future development directions. RECENT FINDINGS: Future systems are expected to advance in two directions: improvements of remote manipulation robots and developments of image-guided robots. SUMMARY: The final goal of robots is to allow safer and more homogeneous outcomes with less variability of surgeon performance, as well as new tools to perform tasks on the basis of medical transcutaneous imaging, in a less invasive way, at lower costs. It is expected that improvements for a remote system could be augmented in reality, with haptic feedback, size reduction, and development of new tools for natural orifice translumenal endoscopic surgery. The paradigm of image-guided robots is close to clinical availability and the most advanced robots are presented with end-user technical assessments. It is also notable that the potential of robots lies much further ahead than the accomplishments of the daVinci system. The integration of imaging with robotics holds a substantial promise, because this can accomplish tasks otherwise impossible. Image-guided robots have the potential to offer a paradigm shift.
Sensing Models and Its Impact on Network Coverage in Wireless Sensor Network
Venue: arXiv cs.IT 2008
Year: 2008

Network coverage of wireless sensor network (WSN) means how well an area of interest is being monitored by the deployed network. It depends mainly on sensing model of nodes. In this paper, we present three types of sensing models viz. Boolean sensing model, shadow-fading sensing model and Elfes sensing model. We investigate the impact of sensing models on network coverage. We also investigate network coverage based on Poisson node distribution. A comparative study between regular and random node placement has also been presented in this paper. This study will be useful for coverage analysis of WSN.
Strongly Multiplicative and 3-Multiplicative Linear Secret Sharing Schemes
Venue: arXiv cs.CR 2008
Year: 2008

Strongly multiplicative linear secret sharing schemes (LSSS) have been a powerful tool for constructing secure multiparty computation protocols. However, it remains open whether or not there exist efficient constructions of strongly multiplicative LSSS from general LSSS. In this paper, we propose the new concept of a 3-multiplicative LSSS, and establish its relationship with strongly multiplicative LSSS. More precisely, we show that any 3-multiplicative LSSS is a strongly multiplicative LSSS, but the converse is not true; and that any strongly multiplicative LSSS can be efficiently converted into a 3-multiplicative LSSS. Furthermore, we apply 3-multiplicative LSSS to the computation of unbounded fan-in multiplication, which reduces its round complexity to four (from five of the previous protocol based on strongly multiplicative LSSS). We also give two constructions of 3-multiplicative LSSS from Reed-Muller codes and algebraic geometric codes. We believe that the construction and verification of 3-multiplicative LSSS are easier than those of strongly multiplicative LSSS. This presents a step forward in settling the open problem of efficient constructions of strongly multiplicative LSSS from general LSSS.