OpenRaiser/Intern-Atlas huggingface dataset:
Extending the Trusted Path in Client-Server Interaction
Venue: arXiv cs.CR 2006
Year: 2006

We present a method to secure the complete path between a server and the local human user at a network node. This is useful for scenarios like internet banking, electronic signatures, or online voting. Protection of input authenticity and output integrity and authenticity is accomplished by a combination of traditional and novel technologies, e.g., SSL, ActiveX, and DirectX. Our approach does not require administrative privileges to deploy and is hence suitable for consumer applications. Results are based on the implementation of a proof-of-concept application for the Windows platform.
Barriers and local minima in energy landscapes of stochastic local search
Venue: arXiv cs.CC 2006
Year: 2006

A local search algorithm operating on an instance of a Boolean constraint satisfaction problem (in particular, k-SAT) can be viewed as a stochastic process traversing successive adjacent states in an ``energy landscape'' defined by the problem instance on the n-dimensional Boolean hypercube. We investigate analytically the worst-case topography of such landscapes in the context of satisfiable k-SAT via a random ensemble of satisfiable ``k-regular'' linear equations modulo 2. We show that for each fixed k=3,4,..., the typical k-SAT energy landscape induced by an instance drawn from the ensemble has a set of 2^{Ω(n)} local energy minima, each separated by an unconditional Ω(n) energy barrier from each of the O(1) ground states, that is, solution states with zero energy. The main technical aspect of the analysis is that a random k-regular 0/1 matrix constitutes a strong boundary expander with almost full GF(2)-linear rank, a property which also enables us to prove a 2^{Ω(n)} lower bound for the expected number of steps required by the focused random walk heuristic to solve typical instances drawn from the ensemble. These results paint a grim picture of the worst-case topography of k-SAT for local search, and constitute apparently the first rigorous analysis of the growth of energy barriers in a random ensemble of k-SAT landscapes as the number of variables n is increased.
Rectangular Layouts and Contact Graphs
Venue: arXiv cs.DS 2006
Year: 2006

Contact graphs of isothetic rectangles unify many concepts from applications including VLSI and architectural design, computational geometry, and GIS. Minimizing the area of their corresponding {\em rectangular layouts} is a key problem. We study the area-optimization problem and show that it is NP-hard to find a minimum-area rectangular layout of a given contact graph. We present O(n)-time algorithms that construct $O(n^2)$-area rectangular layouts for general contact graphs and $O(n\log n)$-area rectangular layouts for trees. (For trees, this is an $O(\log n)$-approximation algorithm.) We also present an infinite family of graphs (rsp., trees) that require $Ω(n^2)$ (rsp., $Ω(n\log n)$) area. We derive these results by presenting a new characterization of graphs that admit rectangular layouts using the related concept of {\em rectangular duals}. A corollary to our results relates the class of graphs that admit rectangular layouts to {\em rectangle of influence drawings}.
Very Sparse Stable Random Projections, Estimators and Tail Bounds for Stable Random Projections
Venue: arXiv cs.DS 2006
Year: 2006

This paper will focus on three different aspects in improving the current practice of stable random projections. Firstly, we propose {\em very sparse stable random projections} to significantly reduce the processing and storage cost, by replacing the $α$-stable distribution with a mixture of a symmetric $α$-Pareto distribution (with probability $β$, $0<β\leq1$) and a point mass at the origin (with a probability $1-β$). This leads to a significant $\frac{1}β$-fold speedup for small $β$. Secondly, we provide an improved estimator for recovering the original $l_α$ norms from the projected data. The standard estimator is based on the (absolute) sample median, while we suggest using the geometric mean. The geometric mean estimator we propose is strictly unbiased and is easier to study. Moreover, the geometric mean estimator is more accurate, especially non-asymptotically. Thirdly, we provide an adequate answer to the basic question of how many projections (samples) are needed for achieving some pre-specified level of accuracy. \cite{Proc:Indyk_FOCS00,Article:Indyk_TKDE03} did not provide a criterion that can be used in practice. The geometric mean estimator we propose allows us to derive sharp tail bounds which can be expressed in exponential forms with constants explicitly given.
A higher-order active contour model of a `gas of circles' and its application to tree crown extraction
Venue: arXiv cs.CV 2006
Year: 2006

Many image processing problems involve identifying the region in the image domain occupied by a given entity in the scene. Automatic solution of these problems requires models that incorporate significant prior knowledge about the shape of the region. Many methods for including such knowledge run into difficulties when the topology of the region is unknown a priori, for example when the entity is composed of an unknown number of similar objects. Higher-order active contours (HOACs) represent one method for the modelling of non-trivial prior knowledge about shape without necessarily constraining region topology, via the inclusion of non-local interactions between region boundary points in the energy defining the model. The case of an unknown number of circular objects arises in a number of domains, e.g. medical, biological, nanotechnological, and remote sensing imagery. Regions composed of an a priori unknown number of circles may be referred to as a `gas of circles'. In this report, we present a HOAC model of a `gas of circles'. In order to guarantee stable circles, we conduct a stability analysis via a functional Taylor expansion of the HOAC energy around a circular shape. This analysis fixes one of the model parameters in terms of the others and constrains the rest. In conjunction with a suitable likelihood energy, we apply the model to the extraction of tree crowns from aerial imagery, and show that the new model outperforms other techniques.
Coupling Methodology within the Software Platform Alliances
Venue: arXiv cs.MS 2006
Year: 2006

CEA, ANDRA and EDF are jointly developing the software platform ALLIANCES which aim is to produce a tool for the simulation of nuclear waste storage and disposal repository. This type of simulations deals with highly coupled thermo-hydro-mechanical and chemical (T-H-M-C) processes. A key objective of Alliances is to give the capability for coupling algorithms development between existing codes. The aim of this paper is to present coupling methodology use in the context of this software platform.
Quantitative Analysis of the Publishing Landscape in High-Energy Physics
Venue: arXiv cs.DL 2006
Year: 2006

World-wide collaboration in high-energy physics (HEP) is a tradition which dates back several decades, with scientific publications mostly coauthored by scientists from different countries. This coauthorship phenomenon makes it difficult to identify precisely the ``share'' of each country in HEP scientific production. One year's worth of HEP scientific articles published in peer-reviewed journals is analysed and their authors are uniquely assigned to countries. This method allows the first correct estimation on a ``pro rata'' basis of the share of HEP scientific publishing among several countries and institutions. The results provide an interesting insight into the geographical collaborative patterns of the HEP community. The HEP publishing landscape is further analysed to provide information on the journals favoured by the HEP community and on the geographical variation of their author bases. These results provide quantitative input to the ongoing debate on the possible transition of HEP publishing to an Open Access model.
Hard Disk Drive as a Magnetomechanical Logic Device
Venue: arXiv cs.OH 2006
Year: 2006

We consider the conditions how two binary numbers can be superimposed on the same track with the use of different recording magnetic fields. As a result the average magnetization of longitudinal medium along the track can have three states: -M, 0 and +M. Possibility to perform logic operations with these states is considered. We demonstrate OR, AND, XOR and NOT operations and discuss a modification of a recording device.
Rhythms of social interaction: messaging within a massive online network
Venue: arXiv cs.CY 2006
Year: 2006

We have analyzed the fully-anonymized headers of 362 million messages exchanged by 4.2 million users of Facebook, an online social network of college students, during a 26 month interval. The data reveal a number of strong daily and weekly regularities which provide insights into the time use of college students and their social lives, including seasonal variations. We also examined how factors such as school affiliation and informal online friend lists affect the observed behavior and temporal patterns. Finally, we show that Facebook users appear to be clustered by school with respect to their temporal messaging patterns.
On the Benefits of Inoculation, an Example in Train Scheduling
Venue: arXiv cs.AI 2006
Year: 2006

The local reconstruction of a railway schedule following a small perturbation of the traffic, seeking minimization of the total accumulated delay, is a very difficult and tightly constrained combinatorial problem. Notoriously enough, the railway company's public image degrades proportionally to the amount of daily delays, and the same goes for its profit! This paper describes an inoculation procedure which greatly enhances an evolutionary algorithm for train re-scheduling. The procedure consists in building the initial population around a pre-computed solution based on problem-related information available beforehand. The optimization is performed by adapting times of departure and arrival, as well as allocation of tracks, for each train at each station. This is achieved by a permutation-based evolutionary algorithm that relies on a semi-greedy heuristic scheduler to gradually reconstruct the schedule by inserting trains one after another. Experimental results are presented on various instances of a large real-world case involving around 500 trains and more than 1 million constraints. In terms of competition with commercial math ematical programming tool ILOG CPLEX, it appears that within a large class of instances, excluding trivial instances as well as too difficult ones, and with very few exceptions, a clever initialization turns an encouraging failure into a clear-cut success auguring of substantial financial savings.
A Symbolic Intruder Model for Hash-Collision Attacks
Venue: arXiv cs.CR 2006
Year: 2006

In the recent years, several practical methods have been published to compute collisions on some commonly used hash functions. In this paper we present a method to take into account, at the symbolic level, that an intruder actively attacking a protocol execution may use these collision algorithms in reasonable time during the attack. Our decision procedure relies on the reduction of constraint solving for an intruder exploiting the collision properties of hush functions to constraint solving for an intruder operating on words.
A Unified View of TD Algorithms; Introducing Full-Gradient TD and Equi-Gradient Descent TD
Venue: arXiv cs.LG 2006
Year: 2006

This paper addresses the issue of policy evaluation in Markov Decision Processes, using linear function approximation. It provides a unified view of algorithms such as TD(lambda), LSTD(lambda), iLSTD, residual-gradient TD. It is asserted that they all consist in minimizing a gradient function and differ by the form of this function and their means of minimizing it. Two new schemes are introduced in that framework: Full-gradient TD which uses a generalization of the principle introduced in iLSTD, and EGD TD, which reduces the gradient by successive equi-gradient descents. These three algorithms form a new intermediate family with the interesting property of making much better use of the samples than TD while keeping a gradient descent scheme, which is useful for complexity issues and optimistic policy iteration.
Comparison between Networked Control System behaviour based on CAN and Switched Ethernet networks
Venue: arXiv cs.NI 2006
Year: 2006

The distributed control systems are more and more used in many industrial applications. These systems are often referred as "Networked control systems". The goal of this paper is to show the network influence on feedback control systems. Two networks are considered: Switched Ethernet network and CAN fieldbus. The first one represents the non deterministic network and second one represents the deterministic one. Several scenarii are studied to analyse the stability of system according to different network parameters (packets losses, congestion and frame priority). The Truetime simulator is used in this work.
A Novel Bayesian Classifier using Copula Functions
Venue: arXiv cs.LG 2006
Year: 2006

A useful method for representing Bayesian classifiers is through \emph{discriminant functions}. Here, using copula functions, we propose a new model for discriminants. This model provides a rich and generalized class of decision boundaries. These decision boundaries significantly boost the classification accuracy especially for high dimensional feature spaces. We strengthen our analysis through simulation results.
Evocation and elaboration of solutions: Different types of problem-solving actions. An empirical study on the design of an aerospace artifact
Venue: arXiv cs.HC 2006
Year: 2006

An observational study was conducted on a professional designer working on a design project in aerospace industry. The protocol data were analyzed in order to gain insight into the actions the designer used for the development of a solution to the corresponding problem. Different processes are described: from the "simple" evocation of a solution existing in memory, to the elaboration of a "new" solution out of mnesic entities without any clear link to the current problem. Control is addressed in so far as it concerns the priority among the different types of development processes: the progression from evocation of a "standard" solution to elaboration of a "new" solution is supposed to correspond to the resulting order, that is, the one in which the designer's activity proceeds. Short discussions of * the double status of "problem" and "solution," * the problem/solution knowledge units in memory and their access, and * the different abstraction levels on which problem and solution representations are developed, are illustrated by the results.
Users' participation to the design process in an Open Source Software online community
Venue: arXiv cs.HC 2006
Year: 2006

The objective of this research is to analyse the ways members of open-source software communities participate in design. In particular we focus on how users of an Open Source (OS) programming language (Python) participate in adding new functionalities to the language. Indeed, in the OS communities, users are highly skilled in computer sciences; they do not correspond to the common representation of end-users and can potentially participate to the design process. Our study characterizes the Python galaxy and analyses a formal process to introduce new functionalities to the language called Python Enhancement Proposal (PEP) from the idea of language evolution to the PEP implementation. The analysis of a particular pushed-by-users PEP from one application domain community (financial), shows: that the design process is distributed and specialized between online and physical interactions spaces; and there are some cross participants between users and developers communities which may reveal boundary spanners roles.
Geographic Gossip on Geometric Random Graphs via Affine Combinations
Venue: arXiv cs.MA 2006
Year: 2006

In recent times, a considerable amount of work has been devoted to the development and analysis of gossip algorithms in Geometric Random Graphs. In a recently introduced model termed "Geographic Gossip," each node is aware of its position but possesses no further information. Traditionally, gossip protocols have always used convex linear combinations to achieve averaging. We develop a new protocol for Geographic Gossip, in which counter-intuitively, we use {\it non-convex affine combinations} as updates in addition to convex combinations to accelerate the averaging process. The dependence of the number of transmissions used by our algorithm on the number of sensors $n$ is $n \exp(O(\log \log n)^2) = n^{1 + o(1)}$. For the previous algorithm, this dependence was $\tilde{O}(n^{1.5})$. The exponent 1+ o(1) of our algorithm is asymptotically optimal. Our algorithm involves a hierarchical structure of $\log \log n$ depth and is not completely decentralized. However, the extent of control exercised by a sensor on another is restricted to switching the other on or off.
On the Maximum Sum-rate Capacity of Cognitive Multiple Access Channel
Venue: arXiv cs.IT 2006
Year: 2006

We consider the communication scenario where multiple cognitive users wish to communicate to the same receiver, in the presence of primary transmission. The cognitive transmitters are assumed to have the side information about the primary transmission. The capacity region of cognitive users is formulated under the constraint that the capacity of primary transmission is not changed as if no cognitive users exist. Moreover, the maximum sum-rate point of the capacity region is characterized, by optimally allocating the power of each cognitive user to transmit its own information.
Estimating Aggregate Properties on Probabilistic Streams
Venue: arXiv cs.DS 2006
Year: 2006

The probabilistic-stream model was introduced by Jayram et al. \cite{JKV07}. It is a generalization of the data stream model that is suited to handling ``probabilistic'' data where each item of the stream represents a probability distribution over a set of possible events. Therefore, a probabilistic stream determines a distribution over potentially a very large number of classical "deterministic" streams where each item is deterministically one of the domain values. The probabilistic model is applicable for not only analyzing streams where the input has uncertainties (such as sensor data streams that measure physical processes) but also where the streams are derived from the input data by post-processing, such as tagging or reconciling inconsistent and poor quality data. We present streaming algorithms for computing commonly used aggregates on a probabilistic stream. We present the first known, one pass streaming algorithm for estimating the \AVG, improving results in \cite{JKV07}. We present the first known streaming algorithms for estimating the number of \DISTINCT items on probabilistic streams. Further, we present extensions to other aggregates such as the repeat rate, quantiles, etc. In all cases, our algorithms work with provable accuracy guarantees and within the space constraints of the data stream model.
Acronym-Meaning Extraction from Corpora Using Multi-Tape Weighted Finite-State Machines
Venue: arXiv cs.CL 2006
Year: 2006

The automatic extraction of acronyms and their meaning from corpora is an important sub-task of text mining. It can be seen as a special case of string alignment, where a text chunk is aligned with an acronym. Alternative alignments have different cost, and ideally the least costly one should give the correct meaning of the acronym. We show how this approach can be implemented by means of a 3-tape weighted finite-state machine (3-WFSM) which reads a text chunk on tape 1 and an acronym on tape 2, and generates all alternative alignments on tape 3. The 3-WFSM can be automatically generated from a simple regular expression. No additional algorithms are required at any stage. Our 3-WFSM has a size of 27 states and 64 transitions, and finds the best analysis of an acronym in a few milliseconds.
Retrieving Reed-Solomon coded data under interpolation-based list decoding
Venue: arXiv cs.IT 2006
Year: 2006

A transform that enables generator-matrix-based Reed-Solomon (RS) coded data to be recovered under interpolation-based list decoding is presented. The transform matrix needs to be computed only once and the transformation of an element from the output list to the desired RS coded data block incurs $k^{2}$ field multiplications, given a code of dimension $k$.
Intermediate Performance of Rateless Codes
Venue: arXiv cs.IT 2006
Year: 2006

Rateless/fountain codes are designed so that all input symbols can be recovered from a slightly larger number of coded symbols, with high probability using an iterative decoder. In this paper we investigate the number of input symbols that can be recovered by the same decoder, but when the number of coded symbols available is less than the total number of input symbols. Of course recovery of all inputs is not possible, and the fraction that can be recovered will depend on the output degree distribution of the code. In this paper we (a) outer bound the fraction of inputs that can be recovered for any output degree distribution of the code, and (b) design degree distributions which meet/perform close to this bound. Our results are of interest for real-time systems using rateless codes, and for Raptor-type two-stage designs.
On the Decrease Rate of the Non-Gaussianness of the Sum of Independent Random Variables
Venue: arXiv cs.IT 2006
Year: 2006

Several proofs of the monotonicity of the non-Gaussianness (divergence with respect to a Gaussian random variable with identical second order statistics) of the sum of n independent and identically distributed (i.i.d.) random variables were published. We give an upper bound on the decrease rate of the non-Gaussianness which is proportional to the inverse of n, for large n. The proof is based on the relationship between non-Gaussianness and minimum mean-square error (MMSE) and causal minimum mean-square error (CMMSE) in the time-continuous Gaussian channel.
Personal Information Ecosystems and Implications for Design
Venue: arXiv cs.HC 2006
Year: 2006

Today, people use multiple devices to fulfill their information needs. However, designers design each device individually, without accounting for the other devices that users may also use. In many cases, the applications on all these devices are designed to be functional replicates of each other. We argue that this results in an over-reliance on data synchronization across devices, version control nightmares, and increased burden of file management. In this paper, we present the idea of a \textit{personal information ecosystem}, an analogy to biological ecosystems, which allows us to discuss the inter-relationships among these devices to fulfill the information needs of the user. There is a need for designers to design devices as part of a complete ecosystem, not as independent devices that simply share data replicated across them. To help us understand this domain and to facilitate the dialogue and study of such systems, we present the terminology, classifications of the interdependencies among different devices, and resulting implications for design.