OpenRaiser/Intern-Atlas huggingface dataset:
Piecewise Linear Patch Reconstruction for Segmentation and Description of Non-smooth Image Structures
Venue: arXiv cs.CV 2012
Year: 2012

In this paper, we propose a unified energy minimization model for the segmentation of non-smooth image structures. The energy of piecewise linear patch reconstruction is considered as an objective measure of the quality of the segmentation of non-smooth structures. The segmentation is achieved by minimizing the single energy without any separate process of feature extraction. We also prove that the error of segmentation is bounded by the proposed energy functional, meaning that minimizing the proposed energy leads to reducing the error of segmentation. As a by-product, our method produces a dictionary of optimized orthonormal descriptors for each segmented region. The unique feature of our method is that it achieves the simultaneous segmentation and description for non-smooth image structures under the same optimization framework. The experiments validate our theoretical claims and show the clear superior performance of our methods over other related methods for segmentation of various image textures. We show that our model can be coupled with the piecewise smooth model to handle both smooth and non-smooth structures, and we demonstrate that the proposed model is capable of coping with multiple different regions through the one-against-all strategy.
Matroid Secretary for Regular and Decomposable Matroids
Venue: arXiv cs.DS 2012
Year: 2012

In the matroid secretary problem we are given a stream of elements and asked to choose a set of elements that maximizes the total value of the set, subject to being an independent set of a matroid given in advance. The difficulty comes from the assumption that decisions are irrevocable: if we choose to accept an element when it is presented by the stream then we can never get rid of it, and if we choose not to accept it then we cannot later add it. Babaioff, Immorlica, and Kleinberg [SODA 2007] introduced this problem, gave O(1)-competitive algorithms for certain classes of matroids, and conjectured that every matroid admits an O(1)-competitive algorithm. However, most matroids that are known to admit an O(1)-competitive algorithm can be easily represented using graphs (e.g. graphic and transversal matroids). In particular, there is very little known about F-representable matroids (the class of matroids that can be represented as elements of a vector space over a field F), which are one of the foundational matroid classes. Moreover, most of the known techniques are as dependent on graph theory as they are on matroid theory. We go beyond graphs by giving an O(1)-competitive algorithm for regular matroids (the class of matroids that are representable over every field), and use techniques that are matroid-theoretic rather than graph-theoretic. We use the regular matroid decomposition theorem of Seymour to decompose any regular matroid into matroids which are either graphic, cographic, or isomorphic to R_{10}, and then show how to combine algorithms for these basic classes into an algorithm for regular matroids. This allows us to generalize beyond regular matroids to any class of matroids that admits such a decomposition into classes for which we already have good algorithms. In particular, we give an O(1)-competitive algorithm for the class of max-flow min-cut matroids.
Hierarchical Performance Modeling for Ranking Dense Linear Algebra Algorithms
Venue: arXiv cs.PF 2012
Year: 2012

A large class of dense linear algebra operations, such as LU decomposition or inversion of a triangular matrix, are usually performed by blocked algorithms. For one such operation, typically, not only one but many algorithmic variants exist; depending on computing architecture, libraries and problem size, each variant attains a different performances. We propose methods and tools to rank the algorithmic variants according to their performance for a given scenario without executing them. For this purpose, we identify the routines upon which the algorithms are built. A first tool - the Sampler - measures the performance of these routines. Using the Sampler, a second tool models their performance. The generated models are then used to predict the performance of the considered algorithms. For a given scenario, these predictions allow us to correctly rank the algorithms according to their performance without executing them. With the help of the same tools, algorithmic parameters such as block-size can be optimally tuned.
Cancellation-free circuits: An approach for proving superlinear lower bounds for linear Boolean operators
Venue: arXiv cs.CC 2012
Year: 2012

We continue to study the notion of cancellation-free linear circuits. We show that every matrix can be computed by a cancellation- free circuit, and almost all of these are at most a constant factor larger than the optimum linear circuit that computes the matrix. It appears to be easier to prove statements about the structure of cancellation-free linear circuits than for linear circuits in general. We prove two nontrivial superlinear lower bounds. We show that a cancellation-free linear circuit computing the $n\times n$ Sierpinski gasket matrix must use at least 1/2 n logn gates, and that this is tight. This supports a conjecture by Aaronson. Furthermore we show that a proof strategy for proving lower bounds on monotone circuits can be almost directly converted to prove lower bounds on cancellation-free linear circuits. We use this together with a result from extremal graph theory due to Andreev to prove a lower bound of Ω(n^(2- ε)) for infinitely many $n \times n$ matrices for every $ε> 0$ for. These lower bounds for concrete matrices are almost optimal since all matrices can be computed with $O(n^2/\log n)$ gates.
A prototype for projecting HPSG syntactic lexica towards LMF
Venue: arXiv cs.CL 2012
Year: 2012

The comparative evaluation of Arabic HPSG grammar lexica requires a deep study of their linguistic coverage. The complexity of this task results mainly from the heterogeneity of the descriptive components within those lexica (underlying linguistic resources and different data categories, for example). It is therefore essential to define more homogeneous representations, which in turn will enable us to compare them and eventually merge them. In this context, we present a method for comparing HPSG lexica based on a rule system. This method is implemented within a prototype for the projection from Arabic HPSG to a normalised pivot language compliant with LMF (ISO 24613 - Lexical Markup Framework) and serialised using a TEI (Text Encoding Initiative) based representation. The design of this system is based on an initial study of the HPSG formalism looking at its adequacy for the representation of Arabic, and from this, we identify the appropriate feature structures corresponding to each Arabic lexical category and their possible LMF counterparts.
A New P2N Approach to Software Development Under the Clustering
Venue: arXiv cs.SE 2012
Year: 2012

In this computer era of rapid development, software development can be seen everywhere, but a lot of softwares are dead in modern development of software. Just as The Mythical Man-Month said, it exists a problem in the software development, and the problem is interflow.A lock of interflow can be said great calamity. Clustering is a environment to breed new life. In this thesis, we elaborate how P2N can be used to thinking, planning, developing, collaborating, releasing. And the approach that make your team and organization more perfect.
Lattice based Least Fixed Point Logic
Venue: arXiv cs.LO 2012
Year: 2012

As software systems become more complex, there is an increasing need for new static analyses. Thanks to the declarative style, logic programming is an attractive formalism for specifying them. However, prior work on using logic programming for static analysis focused on analyses defined over some powerset domain, which is quite limiting. In this paper we present a logic that lifts this restriction, called Lattice based Least Fixed Point Logic (LLFP), that allows interpretations over any complete lattice satisfying Ascending Chain Condition. The main theoretical contribution is a Moore Family result that guarantees that there always is a unique least solution for a given problem. Another contribution is the development of solving algorithm that computes the least model of LLFP formulae guaranteed by the Moore Family result.
FST Based Morphological Analyzer for Hindi Language
Venue: arXiv cs.CL 2012
Year: 2012

Hindi being a highly inflectional language, FST (Finite State Transducer) based approach is most efficient for developing a morphological analyzer for this language. The work presented in this paper uses the SFST (Stuttgart Finite State Transducer) tool for generating the FST. A lexicon of root words is created. Rules are then added for generating inflectional and derivational words from these root words. The Morph Analyzer developed was used in a Part Of Speech (POS) Tagger based on Stanford POS Tagger. The system was first trained using a manually tagged corpus and MAXENT (Maximum Entropy) approach of Stanford POS tagger was then used for tagging input sentences. The morphological analyzer gives approximately 97% correct results. POS tagger gives an accuracy of approximately 87% for the sentences that have the words known to the trained model file, and 80% accuracy for the sentences that have the words unknown to the trained model file.
An Authentication Protocol Based on Combined RFID-Biometric System RFID-Biometric System
Venue: arXiv cs.CR 2012
Year: 2012

Radio Frequency Identification (RFID) and biometric technologies saw fast evolutions during the last years and which are used in several applications, such as access control. Among important characteristics in the RFID tags, we mention the limitation of resources (memory, energy, ...). Our work focuses on the design of a RFID authentication protocol which uses biometric data and which confirms the secrecy, the authentication and the privacy. Our protocol requires a PRNG (Pseud-Random Number Generator), a robust hash function and Biometric hash function. The Biometric hash function is used to optimize and to protect biometric data. For Security analysis of protocol proposed, we will use AVISPA and SPAN tools to verify the authentication and the secrecy.
Effective Computation of Immersion Obstructions for Unions of Graph Classes
Venue: arXiv cs.DS 2012
Year: 2012

In the final paper of the Graph Minors series N. Robertson and P. Seymour proved that graphs are well-quasi-ordered under the immersion ordering. A direct implication of this theorem is that each class of graphs that is closed under taking immersions can be fully characterized by forbidding a finite set of graphs (immersion obstruction set). However, as the proof of the well-quasi-ordering theorem is non-constructive, there is no generic procedure for computing such a set. Moreover, it remains an open issue to identify for which immersion-closed graph classes the computation of those sets can become effective. By adapting the tools that were introduced by I. Adler, M. Grohe and S. Kreutzer, for the effective computation of minor obstruction sets, we expand the horizon of computability to immersion obstruction sets. In particular, our results propagate the computability of immersion obstruction sets of immersion-closed graph classes to immersion obstruction sets of finite unions of immersion closed graph classes.
Approximating Minimum-Cost Connected T-Joins
Venue: arXiv cs.DS 2012
Year: 2012

We design and analyse approximation algorithms for the minimum-cost connected T-join problem: given an undirected graph G = (V;E) with nonnegative costs on the edges, and a subset of nodes T, find (if it exists) a spanning connected subgraph H of minimum cost such that every node in T has odd degree and every node not in T has even degree; H may have multiple copies of any edge of G. Two well-known special cases are the TSP (|T| = 0) and the s-t path TSP (|T| = 2). Recently, An, Kleinberg, and Shmoys [STOC 2012] improved on the long-standing 5/3-approximation guarantee for the latter problem and presented an algorithm based on LP rounding that achieves an approximation guarantee of (1+sqrt(5))/2 < 1.6181. We show that the methods of An et al. extend to the minimum-cost connected T-join problem. They presented a new proof for a 5/3-approximation guarantee for the s-t path TSP; their proof extends easily to the minimum-cost connected T-join problem. Next, we improve on the approximation guarantee of 5/3 by extending their LP-rounding algorithm to get an approximation guarantee of 13/8 = 1.625 for all |T| >= 4. Finally, we focus on the prize-collecting version of the problem, and present a primal-dual algorithm that is "Lagrangian multiplier preserving" and that achieves an approximation guarantee 3 - 2/(|T|-1) when |T| >= 4. Our primal-dual algorithm is a generalization of the known primal-dual 2-approximation for the prize-collecting s-t path TSP. Furthermore, we show that our analysis is tight by presenting instances with |T| >= 4 such that the cost of the solution found by the algorithm is exactly 3 - 2/(|T|-1) times the cost of the constructed dual solution.
Differentiated QoS with Modified C/I Based Scheduling Algorithm
Venue: arXiv cs.NI 2012
Year: 2012

Second-generation (2G) digital cellular systems constitute the majority of cellular communication deployed today. A variety of services of 2G systems has increased significantly and this will continue to grow even further in the emerging third-generation (3G) systems. Universal Mobile Telecommunication System (UMTS) is a third-generation mobile communications system which uses the Wide-Band Code Division Multiple Access (WCDMA) technique to support a wide variety of services, like speech, video telephony, Internet browsing, etc. These services require a wide range of Quality of Service (QoS) requirements. QoS is an important issue as the number of multimedia services increases day by day. Differentiated QoS methods allow the differentiation of users based on their priority levels and channel conditions so that the network can allocate the bandwidth for a particular request based on the QoS requirements. These requirements are controlled by Radio Resource Management (RRM) mechanisms. In this paper we have proposed two RRM algorithms which are modification to the existing scheduling algorithms. One is Prioritized C/I scheduling, which takes the priorities into consideration, and this algorithm serves the user with highest priority. Other algorithm is Modified Inverse C/I scheduling, which takes channel conditions into consideration and serves the users in degraded conditions, thereby improving QoS. The performance evaluation of two algorithms is done with EURANE extensions for NS-2. Simulation results shows the improvement in QoS for the users who are at equidistance from Base Station (BS) but requesting for different services by implementing Prioritized C/I scheduling and also for the users who are in degraded conditions by implementing Modified Inverse C/I scheduling when compared to Max C/I and Inverse C/I scheduling algorithm respectively.
Leveraging information in vehicular parking games
Venue: arXiv cs.GT 2012
Year: 2012

Our paper approaches the parking assistance service in urban environments as an instance of service provision in non-cooperative network environments. We propose normative abstractions for the way drivers pursue parking space and the way they respond to partial or complete information for parking demand and supply as well as specific pricing policies on public and private parking facilities. The drivers are viewed as strategic agents who make rational decisions attempting to minimize the cost of the acquired parking spot. We formulate the resulting games as resource selection games and derive their equilibria under different expressions of uncertainty about the overall parking demand. The efficiency of the equilibrium states is compared against the optimal assignment that could be determined by a centralized entity and conditions are derived for minimizing the related price of anarchy value. Our results provide useful hints for the pricing and practical management of on-street and private parking resources. More importantly, they exemplify counterintuitive less-is-more effects about the way information availability modulates the service cost, which underpin general competitive service provision settings and contribute to the better understanding of effective information mechanisms.
Efficient Snapshot Retrieval over Historical Graph Data
Venue: arXiv cs.DB 2012
Year: 2012

We address the problem of managing historical data for large evolving information networks like social networks or citation networks, with the goal to enable temporal and evolutionary queries and analysis. We present the design and architecture of a distributed graph database system that stores the entire history of a network and provides support for efficient retrieval of multiple graphs from arbitrary time points in the past, in addition to maintaining the current state for ongoing updates. Our system exposes a general programmatic API to process and analyze the retrieved snapshots. We introduce DeltaGraph, a novel, extensible, highly tunable, and distributed hierarchical index structure that enables compactly recording the historical information, and that supports efficient retrieval of historical graph snapshots for single-site or parallel processing. Along with the original graph data, DeltaGraph can also maintain and index auxiliary information; this functionality can be used to extend the structure to efficiently execute queries like subgraph pattern matching over historical data. We develop analytical models for both the storage space needed and the snapshot retrieval times to aid in choosing the right parameters for a specific scenario. In addition, we present strategies for materializing portions of the historical graph state in memory to further speed up the retrieval process. Secondly, we present an in-memory graph data structure called GraphPool that can maintain hundreds of historical graph instances in main memory in a non-redundant manner. We present a comprehensive experimental evaluation that illustrates the effectiveness of our proposed techniques at managing historical graph information.
Algorithm to suppress scanner noise in recorded speech during functional magnetic resonance imaging
Venue: arXiv cs.SD 2012
Year: 2012

The high-intensity, repetitive noise associated with functional magnetic resonance imaging hinders on-line monitoring of subjects' speech and/or recording speech signals suitable for off-line analysis. The proposed algorithm enhances the speech signal by suppressing the scanner noise in the signal recorded by a single-channel microphone. Significant increases in signal-to-noise ratio are achieved using an adaptive filter that combines time and frequency domain elements. In addition to providing a recording suitable for speech analysis, such a real-time system provides an alternative means (to, e.g., the "panic ball") for communication between the patient and the operator during image acquisition.
Selecting Computations: Theory and Applications
Venue: arXiv cs.AI 2012
Year: 2012

Sequential decision problems are often approximately solvable by simulating possible future action sequences. {\em Metalevel} decision procedures have been developed for selecting {\em which} action sequences to simulate, based on estimating the expected improvement in decision quality that would result from any particular simulation; an example is the recent work on using bandit algorithms to control Monte Carlo tree search in the game of Go. In this paper we develop a theoretical basis for metalevel decisions in the statistical framework of Bayesian {\em selection problems}, arguing (as others have done) that this is more appropriate than the bandit framework. We derive a number of basic results applicable to Monte Carlo selection problems, including the first finite sampling bounds for optimal policies in certain cases; we also provide a simple counterexample to the intuitive conjecture that an optimal policy will necessarily reach a decision in all cases. We then derive heuristic approximations in both Bayesian and distribution-free settings and demonstrate their superiority to bandit-based heuristics in one-shot decision problems and in Go.
Black-box Identity Testing for Low Degree Unmixed $ΣΠΣΠ(k)$ Circuits
Venue: arXiv cs.CC 2012
Year: 2012

A $ΣΠΣΠ(k)$ circuit $C=\sum_{i=1}^kF_i=\sum_{i=1}^k\prod_{j=1}^{d_i}f_{ij}$ is unmixed if for each $i\in[k]$, $F_i=f_{i1}(x_1)... f_{in}(x_n)$, where each $f_{ij}$ is a univariate polynomial given in the sparse representation. In this paper, we give a polynomial time black-box algorithm of identity testing for the low degree unmixed $ΣΠΣΠ(k)$ circuits. In order to obtain the black-box algorithm, we first show that a special class of low degree unmixed $ΣΠΣΠ(k)$ circuits of size $s$ is $s^{O(k^2)}$-sparse. Then we construct a hitting set $\mathcal{H}$ in polynomial time for the low degree unmixed $ΣΠΣΠ(k)$ circuits from the sparsity result above. The constructed hitting set is polynomial size. Thus we can test whether the circuit or the polynomial $C$ is identically zero by checking whether $C(a)=0$ for each $a\in\mathcal{H}$. This is the first polynomial time black-box algorithm for the low degree unmixed $ΣΠΣΠ(k)$ circuits, which also partly answers a question of Saxena \cite{SAX}.
Evolving knowledge through negotiation
Venue: arXiv cs.AI 2012
Year: 2012

Semantic web information is at the extremities of long pipelines held by human beings. They are at the origin of information and they will consume it either explicitly because the information will be delivered to them in a readable way, or implicitly because the computer processes consuming this information will affect them. Computers are particularly capable of dealing with information the way it is provided to them. However, people may assign to the information they provide a narrower meaning than semantic technologies may consider. This is typically what happens when people do not think their assertions as ambiguous. Model theory, used to provide semantics to the information on the semantic web, is particularly apt at preserving ambiguity and delivering it to the other side of the pipeline. Indeed, it preserves as much interpretations as possible. This quality for reasoning efficiency, becomes a deficiency for accurate communication and meaning preservation. Overcoming it may require either interactive feedback or preservation of the source context. Work from social science and humanities may help solving this particular problem.
Sparse extractor families for all the entropy
Venue: arXiv cs.CC 2012
Year: 2012

We consider the problem of extracting entropy by sparse transformations, namely functions with a small number of overall input-output dependencies. In contrast to previous works, we seek extractors for essentially all the entropy without any assumption on the underlying distribution beyond a min-entropy requirement. We give two simple constructions of sparse extractor families, which are collections of sparse functions such that for any distribution X on inputs of sufficiently high min-entropy, the output of most functions from the collection on a random input chosen from X is statistically close to uniform. For strong extractor families (i.e., functions in the family do not take additional randomness) we give upper and lower bounds on the sparsity that are tight up to a constant factor for a wide range of min-entropies. We then prove that for some min-entropies weak extractor families can achieve better sparsity. We show how this construction can be used towards more efficient parallel transformation of (non-uniform) one-way functions into pseudorandom generators. More generally, sparse extractor families can be used instead of pairwise independence in various randomized or nonuniform settings where preserving locality (i.e., parallelism) is of interest.