Theory and Algorithms Commons^™

What Is Answer Set Programming To Propositional Satisfiability, Yuliya Lierler

Yuliya Lierler

Constraint Cnf: A Sat And Csp Language Under One Roof, Broes De Cat, Yuliya Lierler

Yuliya Lierler

Detection Of Diabetic Foot Ulcers Using Svm Based Classification, Lei Wang, Peder Pedersen, Diane Strong, Bengisu Tulu, Emmanuel Agu, Qian He, Ronald Ignotz, Raymond Dunn, David Harlan, Sherry Pagoto

Emmanuel O. Agu

Diabetic foot ulcers represent a significant health issue, for both patients’ quality of life and healthcare system costs. Currently, wound care is mainly based on visual assessment of wound size, which suffers from lack of accuracy and consistency. Hence, a more quantitative and computer-based method is needed. Supervised machine learning based object recognition is an attractive option, using training sample images with boundaries labeled by experienced clinicians. We use forty sample images collected from the UMASS Wound Clinic by tracking 8 subjects over 6 months with a smartphone camera. To maintain a consistent imaging environment and facilitate the capture process …

Proceedings Of Naacl Hlt 2009: Short Papers , Pages 157–160, Boulder, Colorado, June 2009. C 2009 Association For Computational Linguistics Answer Credibility: A Language Modeling Approach To Answer Validation, Protima Banerjee, Hyoil Han

Hyoil Han

Answer Validation is a topic of significant interest within the Question Answering community. In this paper, we propose the use of language modeling methodologies for Answer Validation, using corpus-based methods that do not require the use of external sources. Specifically, we propose a model for Answer Credibility which quantifies the reliability of a source document that contains a candidate answer and the Question’s Context Model.

Evaluation Of Particle Swarm Optimization Applied To Grid Scheduling, Wilson Higashino, Miriam Capretz, M. Beatriz Toledo

Wilson A Higashino

The problem of scheduling independent users’ jobs to resources in Grid Computing systems is of paramount importance. This problem is known to be NP-hard, and many techniques have been proposed to solve it, such as heuristics, genetic algorithms (GA), and, more recently, particle swarm optimization (PSO). This article aims to use PSO to solve grid scheduling problems, and compare it with other techniques. It is shown that many often-overlooked implementation details can have a huge impact on the performance of the method. In addition, experiments also show that the PSO has a tendency to stagnate around local minima in high-dimensional …

Theory Identity: A Machine-Learning Approach, Kai Larsen, Dirk Hovorka, Jevin West, James Birt, James Pfaff, Trevor Chambers, Zebula Sampedro, Nick Zager, Bruce Vanstone

Bruce Vanstone

Theory identity is a fundamental problem for researchers seeking to determine theory quality, create theory ontologies and taxonomies, or perform focused theory-specific reviews and meta-analyses. We demonstrate a novel machine-learning approach to theory identification based on citation data and article features. The multi-disciplinary ecosystem of articles which cite a theory's originating paper is created and refined into the network of papers predicted to contribute to, and thus identify, a specific theory. We provide a 'proof-of-concept' for a highly-cited theory. Implications for crossdisciplinary theory integration and the identification of theories for a rapidly expanding scientific literature are discussed.

Identifying Key Variables And Interactions In Statistical Models Of Building Energy Consumption Using Regularization, David Hsu

David Hsu

Statistical models can only be as good as the data put into them. Data about energy consumption continues to grow, particularly its non-technical aspects, but these variables are often interpreted differently among disciplines, datasets, and contexts. Selecting key variables and interactions is therefore an important step in achieving more accurate predictions, better interpretation, and identification of key subgroups for further analysis.

This paper therefore makes two main contributions to the modeling and analysis of energy consumption of buildings. First, it introduces regularization, also known as penalized regression, for principled selection of variables and interactions. Second, this approach is demonstrated by …

Voting Rules As Error Correcting Codes, Nisarg Shah, Ariel Procaccia, Yair Zick

Yair Zick

No abstract provided.

Infectious Texts: Modeling Text Reuse In Nineteenth-Century Newspapers, David Smith, Ryan Cordell, Elizabeth Dillon

Elizabeth Maddock Dillon

Texts propagate through many social networks and provide evidence for their structure. We present efficient algorithms for detecting clusters of reused passages embedded within longer documents in large collections. We apply these techniques to analyzing the culture of reprinting in the United States before the Civil War. Without substantial copyright enforcement, stories, poems, news, and anecdotes circulated freely among newspapers, magazines, and books. From a collection of OCR’d newspapers, we extract a new corpus of reprinted texts, explore the geographic spread and network connections of different publications, and analyze the time dynamics of different genres.

Stratified Polymorphism And Primitive Recursion, Norman Danner, Daniel Leivant

Norman Danner

Natural restrictions on the syntax of the second-order (i.e., polymorphic) lambda calculus are of interest for programming language theory. One of the authors showed in Leivant (1991) that when type abstraction in that calculus is stratified into levels, the definable numeric functions are precisely the super-elementary functions (level [script E]₄ in the Grzegorczyk Hierarchy). We define here a second-order lambda calculus in which type abstraction is stratified to levels up to ω^ω, an ordinal that permits highly uniform (and finite) type inference rules. Referring to this system, we show that the numeric functions definable in …

Adventures In Time And Space, Norman Danner, James Royer

Norman Danner

This paper investigates what is essentially a call-by-value version of PCF under a complexity-theoretically motivated type system. The programming formalism, ATR, has its first-order programs characterize the polynomial-time computable functions, and its second-order programs characterize the type-2 basic feasible functionals of Mehlhorn and of Cook and Urquhart. (The ATR-types are confined to levels 0, 1, and 2.) The type system comes in two parts, one that primarily restricts the sizes of values of expressions and a second that primarily restricts the time required to evaluate expressions. The size-restricted part is motivated by Bellantoni and Cook's and Leivant's implicit characterizations of …

Circuit Principles And Weak Pigeonhole Variants, Chris Pollett, Norman Danner

Norman Danner

This paper considers the relational versions of the surjective, partial surjective, and multifunction weak pigeonhole principles for PV, , , and formulas as well as relativizations of these formulas to higher levels of the bounded arithmetic hierarchy. We show that the partial surjective weak pigeonhole principle for formulas implies that for each k there is a string of length 2^2nk which is hard to block-recognize by circuits of size n^k. These principles in turn imply the partial surjective principle for formulas. We show that the surjective weak pigeonhole principle for formulas in implies …

Two Algorithms In Search Of A Type System, Norman Danner, James Royer

Norman Danner

The authors’ ATR programming formalism is a version of call-by-value PCF under a complexity-theoretically motivated type system. ATR programs run in type-2 polynomial-time and all standard type-2 basic feasible functionals are ATR -definable ( ATR types are confined to levels 0, 1, and 2). A limitation of the original version of ATR is that the only directly expressible recursions are tail-recursions. Here we extend ATR so that a broad range of affine recursions are directly expressible. In particular, the revised ATR can fairly naturally express the classic insertion- and selection-sort algorithms, thus overcoming a sticking point of most prior implicit-complexity-based …

Space-Time Signal Processing For Distributed Pattern Detection In Sensor Networks, Randy Paffenroth, Philip Du Toit, Louis Scharf, Anura Jayasumana, Vidarshana Banadara, Ryan Nong

Randy C. Paffenroth

We present a theory and algorithm for detecting and classifying weak, distributed patterns in network data that provide actionable information with quantiable measures of uncertainty. Our work demonstrates the eectiveness of space-time inference on graphs, robust matrix completion, and second order analysis for the detection of distributed patterns that are not discernible at the level of individual nodes. Motivated by the importance of the problem, we are specically interested in detecting weak patterns in computer networks related to Cyber Situational Awareness. Our focus is on scenarios where the nodes (terminals, routers, servers, etc.) are sensors that provide measurements (of packet …

Identifying High-Dimension Subspace Subcodes Of Reed-Solomon Codes, Sarah Adams

Sarah Spence Adams

Subspace subcodes of Reed-Solomon (SSRS) codes were introduced by Hattori, McEliece, Solomo, and Lin in the mid-1990s. These authors found a complicated dimension formula and a simple, tight lower bound on thedimension of SSRS codes over F₂^m. We prove a conjecture of Hattori concerning how to identify subspaces that can be used to build SSRS codes whose dimension exceeds this lower bound.

The Minimum Decoding Delay Of Maximum Rate Complex Orthogonal Space–Time Block Codes, Sarah Adams, Nathaniel Karst, Jonathan Pollack

Sarah Spence Adams

The growing demand for efficient wireless transmissions over fading channels motivated the development ofspace-time block codes. Space-time block codes built from generalized complex orthogonal designs are particularly attractive because the orthogonality permits a simple decoupled maximum-likelihood decodingalgorithm while achieving full transmit diversity. The two main research problems for these complex orthogonalspace-time block codes (COSTBCs) have been to determine for any number of antennas the maximum rate andthe minimum decoding delay for a maximum rate code. The maximum rate for COSTBCs was determined by Liang in 2003. This paper addresses the second fundamental problem by providing a tight lower bound on …

On The Issue Of Decoupled Decoding Of Codes Derived From Quaternion Orthogonal Designs, Tadeusz Wysocki, Beata Wysocki, Sarah Spence Adams

Sarah Spence Adams

Quaternion orthogonal designs (QODs) have been previously introduced as a basis for orthogonal space-time polarization block codes (OSTPBCs). This note will serve to correct statements concerning the optimality of a decoupled maximum-likelihood (ML) decoding algorithm. It will be shown that when compared to coupled decoding, the decoupled decoding is only optimal in certain cases. This raises several open problems concerning the decoding of OSTPBCs.

A Parameterized Stereo Vision Core For Fpgas, Mark Chang, Stephen Longfield

Mark L. Chang

We present a parameterized stereo vision core suitable for a wide range of FPGA targets and stereo vision applications. By enabling easy tuning of algorithm parameters, our system allows for rapid exploration of the design space and simpler implementation of high-performance stereo vision systems. This implementation utilizes the census transform algorithm to calculate depth information from a pair of images delivered from a simulated stereo camera pair. This work advances our previous work through implementation improvements, a stereo camera pair simulation framework, and a scalable stereo vision core.

Precis: A Usercentric Word-Length Optimization Tool, Mark Chang, Scott Hauck

Mark L. Chang

Translating an algorithm designed for a general-purpose processor into an algorithm optimized for custom logic requires extensive knowledge of the algorithm and the target hardware. Precis lets designers analyze the precision requirements of algorithms specified in Matlab. The design time tool combines simulation, user input, and program analysis to help designers focus their manual precision optimization efforts.

Computing Highly Accurate Or Exact P-Values Using Importance Sampling, Chris Lloyd

Chris J. Lloyd

Especially for discrete data, standard first order P-values can suffer from poor accuracy, even for quite large sample sizes. Moreover, different test statistics can give practically different results. There are several approaches to computing P-values which do not suffer these defects, such as parametric bootstrap P-values or the partially maximised P-values of Berger and Boos (1994).

Both these methods require computing the exact tail probability of the approximate P-value as a function of the nuisance parameter/s, known as the significance profile. For most practical problems, this is not computationally feasible. I develop an importance sampling approach to this problem. A …

A Hybrid Tabu Search And Constraint Programming Algorithm For The Dynamic Dial-A-Ride Problem, Gerardo Berbeglia

Gerardo Berbeglia

No abstract provided.

Non-Redundant Sequential Rules,Theory And Algorithm, David Lo, Siau-Cheng Khoo, Limsoon Wong

David LO

A sequential rule expresses a relationship between two series of events happening one after another. Sequential rules are potentially useful for analyzing data in sequential format, ranging from purchase histories, network logs and program execution traces. In this work, we investigate and propose a syntactic characterization of a non-redundant set of sequential rules built upon past work on compact set of representative patterns. A rule is redundant if it can be inferred from another rule having the same support and confidence. When using the set of mined rules as a composite filter, replacing a full set of rules with a …

Lm: A Miner For Scenario-Based Specifications, Tuan Anh Doan, David Lo, Shahar Maoz, Siau-Cheng Khoo

David LO

We present LM, a tool for mining scenario-based specifications in the form of Live Sequence Charts, a visual language that extends sequence diagrams with modalities. LM comes with a project management component, a wizard-like interface to the mining algorithm, a set of pre- and postprocessing extensions, and a visualization module.

Checking The Feasibility Of Dial-A-Ride Instances Using Constraint Programming, Gerardo Berbeglia, Gilles Pesant, Louis-Martin Rousseau

Gerardo Berbeglia

No abstract provided.

Dynamic Pickup And Delivery Problems, Gerardo Berbeglia

Gerardo Berbeglia

No abstract provided.