OpenRaiser/Intern-Atlas huggingface dataset:
Anonymity in the Wild: Mixes on unstructured networks
Venue: arXiv cs.CR 2007
Year: 2007

As decentralized computing scenarios get ever more popular, unstructured topologies are natural candidates to consider running mix networks upon. We consider mix network topologies where mixes are placed on the nodes of an unstructured network, such as social networks and scale-free random networks. We explore the efficiency and traffic analysis resistance properties of mix networks based on unstructured topologies as opposed to theoretically optimal structured topologies, under high latency conditions. We consider a mix of directed and undirected network models, as well as one real world case study -- the LiveJournal friendship network topology. Our analysis indicates that mix-networks based on scale-free and small-world topologies have, firstly, mix-route lengths that are roughly comparable to those in expander graphs; second, that compromise of the most central nodes has little effect on anonymization properties, and third, batch sizes required for warding off intersection attacks need to be an order of magnitude higher in unstructured networks in comparison with expander graph topologies.
Virtual Sensor Based Fault Detection and Classification on a Plasma Etch Reactor
Venue: arXiv cs.AI 2007
Year: 2007

The SEMATECH sponsored J-88-E project teaming Texas Instruments with NeuroDyne (et al.) focused on Fault Detection and Classification (FDC) on a Lam 9600 aluminum plasma etch reactor, used in the process of semiconductor fabrication. Fault classification was accomplished by implementing a series of virtual sensor models which used data from real sensors (Lam Station sensors, Optical Emission Spectroscopy, and RF Monitoring) to predict recipe setpoints and wafer state characteristics. Fault detection and classification were performed by comparing predicted recipe and wafer state values with expected values. Models utilized include linear PLS, Polynomial PLS, and Neural Network PLS. Prediction of recipe setpoints based upon sensor data provides a capability for cross-checking that the machine is maintaining the desired setpoints. Wafer state characteristics such as Line Width Reduction and Remaining Oxide were estimated on-line using these same process sensors (Lam, OES, RFM). Wafer-to-wafer measurement of these characteristics in a production setting (where typically this information may be only sparsely available, if at all, after batch processing runs with numerous wafers have been completed) would provide important information to the operator that the process is or is not producing wafers within acceptable bounds of product quality. Production yield is increased, and correspondingly per unit cost is reduced, by providing the operator with the opportunity to adjust the process or machine before etching more wafers.
A collaborative framework to exchange and share product information within a supply chain context
Venue: arXiv cs.HC 2007
Year: 2007

The new requirement for "collaboration" between multidisciplinary collaborators induces to exchange and share adequate information on the product, processes throughout the products' lifecycle. Thus, effective capture of information, and also its extraction, recording, exchange, sharing, and reuse become increasingly critical. These lead companies to adopt new improved methodologies in managing the exchange and sharing of information. The aim of this paper is to describe a collaborative framework system to exchange and share information, which is based on: (i) The Product Process Collaboration Organization model (PPCO) which defines product and process information, and the various collaboration methods for the organizations involved in the supply chain. (ii) Viewpoint model describes relationships between each actor and the comprehensive Product/Process model, defining each actor's "domain of interest" within the evolving product definition. (iii) A layer which defines the comprehensive organization and collaboration relationships between the actors within the supply chain. (iv) Based on the above relationships, the last layer proposes a typology of exchanged messages. A communication method, based on XML, is developed that supports optimal exchange/sharing of information. To illustrate the proposed framework system, an example is presented related to collaborative design of a new piston for an automotive engine. The focus is on user-viewpoint integration to ensure that the adequate information is retrieved from the PPCO.
Universal Quantile Estimation with Feedback in the Communication-Constrained Setting
Venue: arXiv cs.IT 2007
Year: 2007

We consider the following problem of decentralized statistical inference: given i.i.d. samples from an unknown distribution, estimate an arbitrary quantile subject to limits on the number of bits exchanged. We analyze a standard fusion-based architecture, in which each of $m$ sensors transmits a single bit to the fusion center, which in turn is permitted to send some number $k$ bits of feedback. Supposing that each of $\nodenum$ sensors receives $n$ observations, the optimal centralized protocol yields mean-squared error decaying as $\order(1/[n m])$. We develop and analyze the performance of various decentralized protocols in comparison to this centralized gold-standard. First, we describe a decentralized protocol based on $k = \log(\nodenum)$ bits of feedback that is strongly consistent, and achieves the same asymptotic MSE as the centralized optimum. Second, we describe and analyze a decentralized protocol based on only a single bit ($k=1$) of feedback. For step sizes independent of $m$, it achieves an asymptotic MSE of order $\order[1/(n \sqrt{m})]$, whereas for step sizes decaying as $1/\sqrt{m}$, it achieves the same $\order(1/[n m])$ decay in MSE as the centralized optimum. Our theoretical results are complemented by simulations, illustrating the tradeoffs between these different protocols.
On Anomalies in Annotation Systems
Venue: arXiv cs.HC 2007
Year: 2007

Today's computer-based annotation systems implement a wide range of functionalities that often go beyond those available in traditional paper-and-pencil annotations. Conceptually, annotation systems are based on thoroughly investigated psycho-sociological and pedagogical learning theories. They offer a huge diversity of annotation types that can be placed in textual as well as in multimedia format. Additionally, annotations can be published or shared with a group of interested parties via well-organized repositories. Although highly sophisticated annotation systems exist both conceptually as well as technologically, we still observe that their acceptance is somewhat limited. In this paper, we argue that nowadays annotation systems suffer from several fundamental problems that are inherent in the traditional paper-and-pencil annotation paradigm. As a solution, we propose to shift the annotation paradigm for the implementation of annotation system.
Asynchronous games: innocence without alternation
Venue: arXiv cs.LO 2007
Year: 2007

The notion of innocent strategy was introduced by Hyland and Ong in order to capture the interactive behaviour of lambda-terms and PCF programs. An innocent strategy is defined as an alternating strategy with partial memory, in which the strategy plays according to its view. Extending the definition to non-alternating strategies is problematic, because the traditional definition of views is based on the hypothesis that Opponent and Proponent alternate during the interaction. Here, we take advantage of the diagrammatic reformulation of alternating innocence in asynchronous games, in order to provide a tentative definition of innocence in non-alternating games. The task is interesting, and far from easy. It requires the combination of true concurrency and game semantics in a clean and organic way, clarifying the relationship between asynchronous games and concurrent games in the sense of Abramsky and Melliès. It also requires an interactive reformulation of the usual acyclicity criterion of linear logic, as well as a directed variant, as a scheduling criterion.
Constructing a maximum utility slate of on-line advertisements
Venue: arXiv cs.DM 2007
Year: 2007

We present an algorithm for constructing an optimal slate of sponsored search advertisements which respects the ordering that is the outcome of a generalized second price auction, but which must also accommodate complicating factors such as overall budget constraints. The algorithm is easily fast enough to use on the fly for typical problem sizes, or as a subroutine in an overall optimization.
Relative Strength of Strategy Elimination Procedures
Venue: arXiv cs.GT 2007
Year: 2007

We compare here the relative strength of four widely used procedures on finite strategic games: iterated elimination of weakly/strictly dominated strategies by a pure/mixed strategy. A complication is that none of these procedures is based on a monotonic operator. To deal with this problem we use 'global' versions of these operators.
Le travail collaboratif dans le cadre d'un projet architectural
Venue: arXiv cs.HC 2007
Year: 2007

The analysis of the practices and the tendencies of the users at the time of the search for information on Internet makes it possible to highlight several points. The search for information becomes powerful after knowledge of the typology of the various systems of research. This typology supports the adoption of a methodology of research which one can characterize by pull systems, intelligent agents, etc. In addition, the importance of the structure of the electronic document, correctly elaborated in advance, will support a higher relevance ratio to find information. In our article, the problems turn around the study of the behavior of the users in situation of search for information, as well as the constitution of a pole of documentary resources within a framework of an architectural project. It is noted that the evolution of the documentary resources is related to information technologies.
Decisive Markov Chains
Venue: arXiv cs.LO 2007
Year: 2007

We consider qualitative and quantitative verification problems for infinite-state Markov chains. We call a Markov chain decisive w.r.t. a given set of target states F if it almost certainly eventually reaches either F or a state from which F can no longer be reached. While all finite Markov chains are trivially decisive (for every set F), this also holds for many classes of infinite Markov chains. Infinite Markov chains which contain a finite attractor are decisive w.r.t. every set F. In particular, this holds for probabilistic lossy channel systems (PLCS). Furthermore, all globally coarse Markov chains are decisive. This class includes probabilistic vector addition systems (PVASS) and probabilistic noisy Turing machines (PNTM). We consider both safety and liveness problems for decisive Markov chains, i.e., the probabilities that a given set of states F is eventually reached or reached infinitely often, respectively. 1. We express the qualitative problems in abstract terms for decisive Markov chains, and show an almost complete picture of its decidability for PLCS, PVASS and PNTM. 2. We also show that the path enumeration algorithm of Iyer and Narasimha terminates for decisive Markov chains and can thus be used to solve the approximate quantitative safety problem. A modified variant of this algorithm solves the approximate quantitative liveness problem. 3. Finally, we show that the exact probability of (repeatedly) reaching F cannot be effectively expressed (in a uniform way) in Tarski-algebra for either PLCS, PVASS or (P)NTM.
A Design Methodology for Space-Time Adapter
Venue: arXiv cs.AR 2007
Year: 2007

This paper presents a solution to efficiently explore the design space of communication adapters. In most digital signal processing (DSP) applications, the overall architecture of the system is significantly affected by communication architecture, so the designers need specifically optimized adapters. By explicitly modeling these communications within an effective graph-theoretic model and analysis framework, we automatically generate an optimized architecture, named Space-Time AdapteR (STAR). Our design flow inputs a C description of Input/Output data scheduling, and user requirements (throughput, latency, parallelism...), and formalizes communication constraints through a Resource Constraints Graph (RCG). The RCG properties enable an efficient architecture space exploration in order to synthesize a STAR component. The proposed approach has been tested to design an industrial data mixing block example: an Ultra-Wideband interleaver.
Variations on Kak's Three Stage Quantum Cryptography Protocol
Venue: arXiv cs.CR 2007
Year: 2007

This paper introduces a variation on Kak's three-stage quanutm key distribution protocol which allows for defence against the man in the middle attack. In addition, we introduce a new protocol, which also offers similar resiliance against such an attack.
Reducing the Error Floor
Venue: arXiv cs.IT 2007
Year: 2007

We discuss how the loop calculus approach of [Chertkov, Chernyak '06], enhanced by the pseudo-codeword search algorithm of [Chertkov, Stepanov '06] and the facet-guessing idea from [Dimakis, Wainwright '06], improves decoding of graph based codes in the error-floor domain. The utility of the new, Linear Programming based, decoding is demonstrated via analysis and simulations of the model $[155,64,20]$ code.
Une sémantique observationnelle du modèle des boîtes pour la résolution de programmes logiques (version étendue)
Venue: arXiv cs.PL 2007
Year: 2007

This report specifies an observational semantics and gives an original presentation of the Byrd's box model. The approach accounts for the semantics of Prolog tracers independently of a particular implementation. Traces are, in general, considered as rather obscure and difficult to use. The proposed formal presentation of a trace constitutes a simple and pedagogical approach for teaching Prolog or for implementing Prolog tracers. It constitutes a form of declarative specification for the tracers. Our approach highlights qualities of the box model which made its success, but also its drawbacks and limits. As a matter of fact, the presented semantics is only one example to illustrate general problems relating to tracers and observing processes. Observing processes know, from observed processes, only their traces. The issue is then to be able to reconstitute by the sole analysis of the trace the main part of the observed process, and if possible, without any loss of information.
A tutorial on conformal prediction
Venue: arXiv cs.LG 2007
Year: 2007

Conformal prediction uses past experience to determine precise levels of confidence in new predictions. Given an error probability $ε$, together with a method that makes a prediction $\hat{y}$ of a label $y$, it produces a set of labels, typically containing $\hat{y}$, that also contains $y$ with probability $1-ε$. Conformal prediction can be applied to any method for producing $\hat{y}$: a nearest-neighbor method, a support-vector machine, ridge regression, etc. Conformal prediction is designed for an on-line setting in which labels are predicted successively, each one being revealed before the next is predicted. The most novel and valuable feature of conformal prediction is that if the successive examples are sampled independently from the same distribution, then the successive predictions will be right $1-ε$ of the time, even though they are based on an accumulating dataset rather than on independent datasets. In addition to the model under which successive examples are sampled independently, other on-line compression models can also use conformal prediction. The widely used Gaussian linear model is one of these. This tutorial presents a self-contained account of the theory of conformal prediction and works through several numerical examples. A more comprehensive treatment of the topic is provided in "Algorithmic Learning in a Random World", by Vladimir Vovk, Alex Gammerman, and Glenn Shafer (Springer, 2005).
On Canonical Forms of Complete Problems via First-order Projections
Venue: arXiv cs.CC 2007
Year: 2007

The class of problems complete for NP via first-order reductions is known to be characterized by existential second-order sentences of a fixed form. All such sentences are built around the so-called generalized IS-form of the sentence that defines Independent-Set. This result can also be understood as that every sentence that defines a NP-complete problem P can be decomposed in two disjuncts such that the first one characterizes a fragment of P as hard as Independent-Set and the second the rest of P. That is, a decomposition that divides every such sentence into a quotient and residue modulo Independent-Set. In this paper, we show that this result can be generalized over a wide collection of complexity classes, including the so-called nice classes. Moreover, we show that such decomposition can be done for any complete problem with respect to the given class, and that two such decompositions are non-equivalent in general. Interestingly, our results are based on simple and well-known properties of first-order reductions.ow that this result can be generalized over a wide collection of complexity classes, including the so-called nice classes. Moreover, we show that such decomposition can be done for any complete problem with respect to the given class, and that two such decompositions are non-equivalent in general. Interestingly, our results are based on simple and well-known properties of first-order reductions.
Experimental Algorithm for the Maximum Independent Set Problem
Venue: arXiv cs.DS 2007
Year: 2007

We develop an experimental algorithm for the exact solving of the maximum independent set problem. The algorithm consecutively finds the maximal independent sets of vertices in an arbitrary undirected graph such that the next such set contains more elements than the preceding one. For this purpose, we use a technique, developed by Ford and Fulkerson for the finite partially ordered sets, in particular, their method for partition of a poset into the minimum number of chains with finding the maximum antichain. In the process of solving, a special digraph is constructed, and a conjecture is formulated concerning properties of such digraph. This allows to offer of the solution algorithm. Its theoretical estimation of running time equals to is $O(n^{8})$, where $n$ is the number of graph vertices. The offered algorithm was tested by a program on random graphs. The testing the confirms correctness of the algorithm.
A Collection of Definitions of Intelligence
Venue: arXiv cs.AI 2007
Year: 2007

This paper is a survey of a large number of informal definitions of ``intelligence'' that the authors have collected over the years. Naturally, compiling a complete list would be impossible as many definitions of intelligence are buried deep inside articles and books. Nevertheless, the 70-odd definitions presented here are, to the authors' knowledge, the largest and most well referenced collection there is.
Bid Optimization for Internet Graphical Ad Auction Systems via Special Ordered Sets
Venue: arXiv cs.DM 2007
Year: 2007

This paper describes an optimization model for setting bid levels for certain types of advertisements on web pages. This model is non-convex, but we are able to obtain optimal or near-optimal solutions rapidly using branch and cut open-source software. The financial benefits obtained using the prototype system have been substantial.
Multi-criteria scheduling of pipeline workflows
Venue: arXiv cs.DC 2007
Year: 2007

Mapping workflow applications onto parallel platforms is a challenging problem, even for simple application patterns such as pipeline graphs. Several antagonist criteria should be optimized, such as throughput and latency (or a combination). In this paper, we study the complexity of the bi-criteria mapping problem for pipeline graphs on communication homogeneous platforms. In particular, we assess the complexity of the well-known chains-to-chains problem for different-speed processors, which turns out to be NP-hard. We provide several efficient polynomial bi-criteria heuristics, and their relative performance is evaluated through extensive simulations.
Getting More From Your Multicore: Exploiting OpenMP From An Open Source Numerical Scripting Language
Venue: arXiv cs.DC 2007
Year: 2007

We introduce SLIRP, a module generator for the S-Lang numerical scripting language, with a focus on its vectorization capabilities. We demonstrate how both SLIRP and S-Lang were easily adapted to exploit the inherent parallelism of high-level mathematical languages with OpenMP, allowing general users to employ tightly-coupled multiprocessors in scriptable research calculations while requiring no special knowledge of parallel programming. Motivated by examples in the ISIS astrophysical modeling & analysis tool, performance figures are presented for several machine and compiler configurations, demonstrating beneficial speedups for real-world operations.
User driven applications - new design paradigm
Venue: arXiv cs.GR 2007
Year: 2007

Programs for complicated engineering and scientific tasks always have to deal with a problem of showing numerous graphical results. The limits of the screen space and often opposite requirements from different users are the cause of the infinite discussions between designers and users, but the source of this ongoing conflict is not in the level of interface design, but in the basic principle of current graphical output: user may change some views and details, but in general the output view is absolutely defined and fixed by the developer. Author was working for several years on the algorithm that will allow eliminating this problem thus allowing stepping from designer-driven applications to user-driven. Such type of applications in which user is deciding what, when and how to show on the screen, is the dream of scientists and engineers working on the analysis of the most complicated tasks. The new paradigm is based on movable and resizable graphics, and such type of graphics can be widely used not only for scientific and engineering applications.
Weighted Popular Matchings
Venue: arXiv cs.DS 2007
Year: 2007

We study the problem of assigning jobs to applicants. Each applicant has a weight and provides a preference list ranking a subset of the jobs. A matching M is popular if there is no other matching M' such that the weight of the applicants who prefer M' over M exceeds the weight of those who prefer M over M'. This paper gives efficient algorithms to find a popular matching if one exists.