OpenRaiser/Intern-Atlas huggingface dataset:
Sampling Algorithms and Coresets for Lp Regression
Venue: arXiv cs.DS 2007
Year: 2007

The Lp regression problem takes as input a matrix $A \in \Real^{n \times d}$, a vector $b \in \Real^n$, and a number $p \in [1,\infty)$, and it returns as output a number ${\cal Z}$ and a vector $x_{opt} \in \Real^d$ such that ${\cal Z} = \min_{x \in \Real^d} ||Ax -b||_p = ||Ax_{opt}-b||_p$. In this paper, we construct coresets and obtain an efficient two-stage sampling-based approximation algorithm for the very overconstrained ($n \gg d$) version of this classical problem, for all $p \in [1, \infty)$. The first stage of our algorithm non-uniformly samples $\hat{r}_1 = O(36^p d^{\max\{p/2+1, p\}+1})$ rows of $A$ and the corresponding elements of $b$, and then it solves the Lp regression problem on the sample; we prove this is an 8-approximation. The second stage of our algorithm uses the output of the first stage to resample $\hat{r}_1/ε^2$ constraints, and then it solves the Lp regression problem on the new sample; we prove this is a $(1+ε)$-approximation. Our algorithm unifies, improves upon, and extends the existing algorithms for special cases of Lp regression, namely $p = 1,2$. In course of proving our result, we develop two concepts--well-conditioned bases and subspace-preserving sampling--that are of independent interest.
Sources of Superlinearity in Davenport-Schinzel Sequences
Venue: arXiv cs.DM 2007
Year: 2007

A generalized Davenport-Schinzel sequence is one over a finite alphabet that contains no subsequences isomorphic to a fixed forbidden subsequence. One of the fundamental problems in this area is bounding (asymptotically) the maximum length of such sequences. Following Klazar, let Ex(σ,n) be the maximum length of a sequence over an alphabet of size n avoiding subsequences isomorphic to σ. It has been proved that for every σ, Ex(σ,n) is either linear or very close to linear; in particular it is O(n 2^{α(n)^{O(1)}}), where αis the inverse-Ackermann function and O(1) depends on σ. However, very little is known about the properties of σthat induce superlinearity of \Ex(σ,n). In this paper we exhibit an infinite family of independent superlinear forbidden subsequences. To be specific, we show that there are 17 prototypical superlinear forbidden subsequences, some of which can be made arbitrarily long through a simple padding operation. Perhaps the most novel part of our constructions is a new succinct code for representing superlinear forbidden subsequences.
Numerical Calculation With Arbitrary Precision
Venue: arXiv cs.NA 2007
Year: 2007

The vast use of computers on scientific numerical computation makes the awareness of the limited precision that these machines are able to provide us an essential matter. A limited and insufficient precision allied to the truncation and rounding errors may induce the user to incorrect interpretation of his/hers answer. In this work, we have developed a computational package to minimize this kind of error by offering arbitrary precision numbers and calculation. This is very important in Physics where we can work with numbers too small and too big simultaneously.
Kinematic Analysis of a Family of 3R Manipulators
Venue: arXiv cs.RO 2007
Year: 2007

The workspace topologies of a family of 3-revolute (3R) positioning manipulators are enumerated. The workspace is characterized in a half-cross section by the singular curves. The workspace topology is defined by the number of cusps that appear on these singular curves. The design parameters space is shown to be divided into five domains where all manipulators have the same number of cusps. Each separating surface is given as an explicit expression in the DH-parameters. As an application of this work, we provide a necessary and sufficient condition for a 3R orthogonal manipulator to be cuspidal, i.e. to change posture without meeting a singularity. This condition is set as an explicit expression in the DH parameters.
A design oriented study for 3R Orthogonal Manipulators With Geometric Simplifications
Venue: arXiv cs.RO 2007
Year: 2007

This paper proposes a method to calculate the largest Regular Dextrous Workspace (RDW) of some types of three-revolute orthogonal manipulators that have at least one of their DH parameters equal to zero. Then a new performance index based on the RDW is introduced, the isocontours of this index are plotted in the parameter space of the interesting types of manipulators and finally an inspection of the domains of the parameter spaces is conducted in order to identify the better manipulator architectures. The RDW is a part of the workspace whose shape is regular (cube, cylinder) and the performances (conditioning index) are bounded inside. The groups of 3R orthogonal manipulators studied have interesting kinematic properties such as, a well-connected workspace that is fully reachable with four inverse kinematic solutions and that does not contain any void. This study is of high interest for the design of alternative manipulator geometries.
Two polynomial algorithms for special maximum matching constructing in trees
Venue: arXiv cs.DM 2007
Year: 2007

For an arbitrary tree we investigate the problems of constructing a maximum matching which minimizes or maximizes the cardinality of a maximum matching of the graph obtained from original one by its removal and present corresponding polynomial algorithms.
Mixed Integer Linear Programming For Exact Finite-Horizon Planning In Decentralized Pomdps
Venue: arXiv cs.AI 2007
Year: 2007

We consider the problem of finding an n-agent joint-policy for the optimal finite-horizon control of a decentralized Pomdp (Dec-Pomdp). This is a problem of very high complexity (NEXP-hard in n >= 2). In this paper, we propose a new mathematical programming approach for the problem. Our approach is based on two ideas: First, we represent each agent's policy in the sequence-form and not in the tree-form, thereby obtaining a very compact representation of the set of joint-policies. Second, using this compact representation, we solve this problem as an instance of combinatorial optimization for which we formulate a mixed integer linear program (MILP). The optimal solution of the MILP directly yields an optimal joint-policy for the Dec-Pomdp. Computational experience shows that formulating and solving the MILP requires significantly less time to solve benchmark Dec-Pomdp problems than existing algorithms. For example, the multi-agent tiger problem for horizon 4 is solved in 72 secs with the MILP whereas existing algorithms require several hours to solve it.
A Comparative Study between Two Three-DOF Parallel Kinematic Machines using Kinetostatic Criteria and Interval Analysis
Venue: arXiv cs.RO 2007
Year: 2007

This paper addresses the workspace analysis of two 3-DOF translational parallel mechanisms designed for machining applications. The two machines features three fixed linear joints. The joint axes of the first machine are orthogonal whereas these of the second are parallel. In both cases, the mobile platform moves in the Cartesian $x-y-z$ space with fixed orientation. The workspace analysis is conducted on the basis of prescribed kinetostatic performances. Interval analysis based methods are used to compute the dextrous workspace and the largest cube enclosed in this workspace.
The Virtual Manufacturing concept: Scope, Socio-Economic Aspects and Future Trends
Venue: arXiv cs.RO 2007
Year: 2007

The research area "Virtual Manufacturing (VM)'' is the use of information technology and computer simulation to model real world manufacturing processes for the purpose of analysing and understanding them. As automation technologies such as CAD/CAM have substantially shortened the time required to design products, Virtual Manufacturing will have a similar effect on the manufacturing phase thanks to the modelling, simulation and optimisation of the product and the processes involved in its fabrication. After a description of Virtual Manufacturing (definitions and scope), we present some socio-economic factors of VM and finaly some "hot topics'' for the future are proposed.
OA@MPS - a colourful view
Venue: arXiv cs.DL 2007
Year: 2007

The open access agenda of the Max Planck Society, initiator of the Berlin Declaration, envisions the support of both the green way and the golden way to open access. For the implementation of the green way the Max Planck Society through its newly established unit (Max Planck Digital Library) follows the idea of providing a centralized technical platform for publications and a local support for editorial issues. With regard to the golden way, the Max Planck Society fosters the development of open access publication models and experiments new publishing concepts like the Living Reviews journals.
Covering a line segment with variable radius discs
Venue: arXiv cs.DM 2007
Year: 2007

The paper addresses the problem of locating sensors with a circular field of view so that a given line segment is under full surveillance, which is termed as the Disc Covering Problem on a Line. The cost of each sensor includes a fixed component, and a variable component that is proportional to the field-of-view area. When only one type of sensor or, in general, one type of disc, is available, then a simple polynomial algorithm solves the problem. When there are different types of sensors in terms of fixed and variable costs, the problem becomes NP-hard. A branch-and-bound algorithm as well as an efficient heuristic are developed. The heuristic very often obtains the optimal solution as shown in extensive computational testing.
Instrumented Collective Learning Situations (ICLS): the Gap between Theoretical Research and Observed Practices
Venue: arXiv cs.CY 2007
Year: 2007

According to socio-constructivism approach, collective situations are promoted to favor learning in classroom, at a distance or in a blended educational context. So, many Information and Communication Technologies (ICT) are provided to teachers but there are no clear studies about the way they are used and perceived. Our research is based on the hypothesis that practices of educational actors (instructional designers and tutors) are far away from theoretical results of research in education technologies. In this paper, we consider a precise kind of situation: Instrumented Collective Learning Situations (ICLS). By a survey on 13 fields in higher education in France, Switzerland and Canada, we present how ICLS are designed and how teachers used them. Conclusions give an indication on the gap between the way information technologies are prescribed and the way they are actually used and perceived by teachers.
Neutrality and Many-Valued Logics
Venue: arXiv cs.LO 2007
Year: 2007

In this book, we consider various many-valued logics: standard, linear, hyperbolic, parabolic, non-Archimedean, p-adic, interval, neutrosophic, etc. We survey also results which show the tree different proof-theoretic frameworks for many-valued logics, e.g. frameworks of the following deductive calculi: Hilbert's style, sequent, and hypersequent. We present a general way that allows to construct systematically analytic calculi for a large family of non-Archimedean many-valued logics: hyperrational-valued, hyperreal-valued, and p-adic valued logics characterized by a special format of semantics with an appropriate rejection of Archimedes' axiom. These logics are built as different extensions of standard many-valued logics (namely, Lukasiewicz's, Goedel's, Product, and Post's logics). The informal sense of Archimedes' axiom is that anything can be measured by a ruler. Also logical multiple-validity without Archimedes' axiom consists in that the set of truth values is infinite and it is not well-founded and well-ordered. On the base of non-Archimedean valued logics, we construct non-Archimedean valued interval neutrosophic logic INL by which we can describe neutrality phenomena.
A Formal Model of Dictionary Structure and Content
Venue: arXiv cs.CL 2007
Year: 2007

We show that a general model of lexical information conforms to an abstract model that reflects the hierarchy of information found in a typical dictionary entry. We show that this model can be mapped into a well-formed XML document, and how the XSL transformation language can be used to implement a semantics defined over the abstract model to enable extraction and manipulation of the information in any format.
Statistical mechanical analysis of the linear vector channel in digital communication
Venue: arXiv cs.IT 2007
Year: 2007

A statistical mechanical framework to analyze linear vector channel models in digital wireless communication is proposed for a large system. The framework is a generalization of that proposed for code-division multiple-access systems in Europhys. Lett. 76 (2006) 1193 and enables the analysis of the system in which the elements of the channel transfer matrix are statistically correlated with each other. The significance of the proposed scheme is demonstrated by assessing the performance of an existing model of multi-input multi-output communication systems.
Mumford dendrograms
Venue: arXiv cs.DM 2007
Year: 2007

An effective $p$-adic encoding of dendrograms is presented through an explicit embedding into the Bruhat-Tits tree for a $p$-adic number field. This field depends on the number of children of a vertex and is a finite extension of the field of $p$-adic numbers. It is shown that fixing $p$-adic representatives of the residue field allows a natural way of encoding strings by identifying a given alphabet with such representatives. A simple $p$-adic hierarchic classification algorithm is derived for $p$-adic numbers, and is applied to strings over finite alphabets. Examples of DNA coding are presented and discussed. Finally, new geometric and combinatorial invariants of time series of $p$-adic dendrograms are developped.
A Comparative Study of Parallel Kinematic Architectures for Machining Applications
Venue: arXiv cs.RO 2007
Year: 2007

Parallel kinematic mechanisms are interesting alternative designs for machining applications. Three 2-DOF parallel mechanism architectures dedicated to machining applications are studied in this paper. The three mechanisms have two constant length struts gliding along fixed linear actuated joints with different relative orientation. The comparative study is conducted on the basis of a same prescribed Cartesian workspace for the three mechanisms. The common desired workspace properties are a rectangular shape and given kinetostatic performances. The machine size of each resulting design is used as a comparative criterion. The 2-DOF machine mechanisms analyzed in this paper can be extended to 3-axis machines by adding a third joint.
Complexity of Propositional Proofs under a Promise
Venue: arXiv cs.CC 2007
Year: 2007

We study -- within the framework of propositional proof complexity -- the problem of certifying unsatisfiability of CNF formulas under the promise that any satisfiable formula has many satisfying assignments, where ``many'' stands for an explicitly specified function $\Lam$ in the number of variables $n$. To this end, we develop propositional proof systems under different measures of promises (that is, different $\Lam$) as extensions of resolution. This is done by augmenting resolution with axioms that, roughly, can eliminate sets of truth assignments defined by Boolean circuits. We then investigate the complexity of such systems, obtaining an exponential separation in the average-case between resolution under different size promises: 1. Resolution has polynomial-size refutations for all unsatisfiable 3CNF formulas when the promise is $\eps\cd2^n$, for any constant $0<\eps<1$. 2. There are no sub-exponential size resolution refutations for random 3CNF formulas, when the promise is $2^{δn}$ (and the number of clauses is $o(n^{3/2})$), for any constant $0<δ<1$.
Competitive minimax universal decoding for several ensembles of random codes
Venue: arXiv cs.IT 2007
Year: 2007

Universally achievable error exponents pertaining to certain families of channels (most notably, discrete memoryless channels (DMC's)), and various ensembles of random codes, are studied by combining the competitive minimax approach, proposed by Feder and Merhav, with Chernoff bound and Gallager's techniques for the analysis of error exponents. In particular, we derive a single--letter expression for the largest, universally achievable fraction $ξ$ of the optimum error exponent pertaining to the optimum ML decoding. Moreover, a simpler single--letter expression for a lower bound to $ξ$ is presented. To demonstrate the tightness of this lower bound, we use it to show that $ξ=1$, for the binary symmetric channel (BSC), when the random coding distribution is uniform over: (i) all codes (of a given rate), and (ii) all linear codes, in agreement with well--known results. We also show that $ξ=1$ for the uniform ensemble of systematic linear codes, and for that of time--varying convolutional codes in the bit-error--rate sense. For the latter case, we also show how the corresponding universal decoder can be efficiently implemented using a slightly modified version of the Viterbi algorithm which em employs two trellises.
Public Cluster : parallel machine with multi-block approach
Venue: arXiv cs.DC 2007
Year: 2007

We introduce a new approach to enable an open and public parallel machine which is accessible for multi users with multi jobs belong to different blocks running at the same time. The concept is required especially for parallel machines which are dedicated for public use as implemented at the LIPI Public Cluster. We have deployed the simplest technique by running multi daemons of parallel processing engine with different configuration files specified for each user assigned to access the system, and also developed an integrated system to fully control and monitor the whole system over web. A brief performance analysis is also given for Message Parsing Interface (MPI) engine. It is shown that the proposed approach is quite reliable and affect the whole performances only slightly.
ADS as Information Management Service in an M-Learning Environment
Venue: arXiv cs.NI 2007
Year: 2007

Leveraging the potential power of even small handheld devices able to communicate wirelessly requires dedicated support. In particular, collaborative applications need sophisticated assistance in terms of querying and exchanging different kinds of data. Using a concrete example from the domain of mobile learning, the general need for information dissemination is motivated. Subsequently, and driven by infrastructural conditions, realization strategies of an appropriate middleware service are discussed.
Edit and verify
Venue: arXiv cs.LO 2007
Year: 2007

Automated theorem provers are used in extended static checking, where they are the performance bottleneck. Extended static checkers are run typically after incremental changes to the code. We propose to exploit this usage pattern to improve performance. We present two approaches of how to do so and a full solution.
Characterising Web Site Link Structure
Venue: arXiv cs.IR 2007
Year: 2007

The topological structures of the Internet and the Web have received considerable attention. However, there has been little research on the topological properties of individual web sites. In this paper, we consider whether web sites (as opposed to the entire Web) exhibit structural similarities. To do so, we exhaustively crawled 18 web sites as diverse as governmental departments, commercial companies and university departments in different countries. These web sites consisted of as little as a few thousand pages to millions of pages. Statistical analysis of these 18 sites revealed that the internal link structure of the web sites are significantly different when measured with first and second-order topological properties, i.e. properties based on the connectivity of an individual or a pairs of nodes. However, examination of a third-order topological property that consider the connectivity between three nodes that form a triangle, revealed a strong correspondence across web sites, suggestive of an invariant. Comparison with the Web, the AS Internet, and a citation network, showed that this third-order property is not shared across other types of networks. Nor is the property exhibited in generative network models such as that of Barabasi and Albert.
Modeling Visual Information Processing in Brain: A Computer Vision Point of View and Approach
Venue: arXiv cs.AI 2007
Year: 2007

We live in the Information Age, and information has become a critically important component of our life. The success of the Internet made huge amounts of it easily available and accessible to everyone. To keep the flow of this information manageable, means for its faultless circulation and effective handling have become urgently required. Considerable research efforts are dedicated today to address this necessity, but they are seriously hampered by the lack of a common agreement about "What is information?" In particular, what is "visual information" - human's primary input from the surrounding world. The problem is further aggravated by a long-lasting stance borrowed from the biological vision research that assumes human-like information processing as an enigmatic mix of perceptual and cognitive vision faculties. I am trying to find a remedy for this bizarre situation. Relying on a new definition of "information", which can be derived from Kolmogorov's compexity theory and Chaitin's notion of algorithmic information, I propose a unifying framework for visual information processing, which explicitly accounts for the perceptual and cognitive image processing peculiarities. I believe that this framework will be useful to overcome the difficulties that are impeding our attempts to develop the right model of human-like intelligent image processing.
Near Optimal Broadcast with Network Coding in Large Sensor Networks
Venue: arXiv cs.NI 2007
Year: 2007

We study efficient broadcasting for wireless sensor networks, with network coding. We address this issue for homogeneous sensor networks in the plane. Our results are based on a simple principle (IREN/IRON), which sets the same rate on most of the nodes (wireless links) of the network. With this rate selection, we give a value of the maximum achievable broadcast rate of the source: our central result is a proof of the value of the min-cut for such networks, viewed as hypergraphs. Our metric for efficiency is the number of transmissions necessary to transmit one packet from the source to every destination: we show that IREN/IRON achieves near optimality for large networks; that is, asymptotically, nearly every transmission brings new information from the source to the receiver. As a consequence, network coding asymptotically outperforms any scheme that does not use network coding.
An Interval Analysis Based Study for the Design and the Comparison of 3-DOF Parallel Kinematic Machines
Venue: arXiv cs.RO 2007
Year: 2007

This paper addresses an interval analysis based study that is applied to the design and the comparison of 3-DOF parallel kinematic machines. Two design criteria are used, (i) a regular workspace shape and, (ii) a kinetostatic performance index that needs to be as homogeneous as possible throughout the workspace. The interval analysis based method takes these two criteria into account: on the basis of prescribed kinetostatic performances, the workspace is analysed to find out the largest regular dextrous workspace enclosed in the Cartesian workspace. An algorithm describing this method is introduced. Two 3-DOF translational parallel mechanisms designed for machining applications are compared using this method. The first machine features three fixed linear joints which are mounted orthogonally and the second one features three linear joints which are mounted in parallel. In both cases, the mobile platform moves in the Cartesian x-y-z space with fixed orientation.