Open Access. Powered by Scholars. Published by Universities.®

Physical Sciences and Mathematics Commons

Open Access. Powered by Scholars. Published by Universities.®

2006

Computer Sciences

Computer Science Technical Reports

Articles 1 - 20 of 20

Full-Text Articles in Physical Sciences and Mathematics

Cheating To Get Better Roommates In A Random Stable Matching, Chien-Chung Huang Dec 2006

Cheating To Get Better Roommates In A Random Stable Matching, Chien-Chung Huang

Computer Science Technical Reports

This paper addresses strategies for the stable roommates problem, assuming that a stable matching is chosen at random. We investigate how a cheating man should permute his preference list so that he has a higher-ranking roommate probabilistically. In the first part of the paper, we identify a necessary condition for creating a new stable roommate for the cheating man. This condition precludes any possibility of his getting a new roommate ranking higher than all his stable roommates when everyone is truthful. Generalizing to the case that multiple men collude, we derive another impossibility result: given any stable matching in which …


Digital Image Ballistics From Jpeg Quantization, Hany Farid Sep 2006

Digital Image Ballistics From Jpeg Quantization, Hany Farid

Computer Science Technical Reports

Most digital cameras export images in the JPEG file format. This lossy compression scheme employs a quantization table that controls the amount of compression achieved. Different cameras typically employ different tables. A comparison of an image's quantization scheme to a database of known cameras affords a simple technique for confirming or denying an image's source. Similarly, comparison to a database of photo-editing software can be used in a forensic setting to determine if an image was edited after its original recording.


Tools And Algorithms To Advance Interactive Intrusion Analysis Via Machine Learning And Information Retrieval, Javed Aslam, Sergey Bratus, Virgil Pavlu Sep 2006

Tools And Algorithms To Advance Interactive Intrusion Analysis Via Machine Learning And Information Retrieval, Javed Aslam, Sergey Bratus, Virgil Pavlu

Computer Science Technical Reports

We consider typical tasks that arise in the intrusion analysis of log data from the perspectives of Machine Learning and Information Retrieval, and we study a number of data organization and interactive learning techniques to improve the analyst's efficiency. In doing so, we attempt to translate intrusion analysis problems into the language of the abovementioned disciplines and to offer metrics to evaluate the effect of proposed techniques. The Kerf toolkit contains prototype implementations of these techniques, as well as data transformation tools that help bridge the gap between the real world log data formats and the ML and IR data …


Metric Measurements On A Plane From A Single Image, Micah K. Johnson, Hany Farid Aug 2006

Metric Measurements On A Plane From A Single Image, Micah K. Johnson, Hany Farid

Computer Science Technical Reports

The past decade has seen considerable advances in the application of principles from projective geometry to problems in image analysis and computer vision. In this paper, we review a subset of this work, and leverage these results for the purpose of forensic analysis. Specifically, we review three techniques for making metric measurements on planar surfaces from a single image. The resulting techniques should prove useful in forensic settings where real-world measurements are required.


Sampled: Shared Anonymous Music Playback Using Wireless Devices, Constantinos Neophytou Jun 2006

Sampled: Shared Anonymous Music Playback Using Wireless Devices, Constantinos Neophytou

Computer Science Technical Reports

Recent advances in mobile computing enable many new applications, yet at the same time create privacy implications caused by the increasing amount of data that becomes available. This thesis will explore the possibilities of wireless-enabled portable devices and their attending privacy implications. We will describe how such a device containing personal information about the musical preferences of its user can help improve the user's experience in a social setting where music is played for all, and at the same time preserve each user's privacy.


Visualizing Paths In Context, Fabio Pellacini, Lori Lorigo, Geri Gay Apr 2006

Visualizing Paths In Context, Fabio Pellacini, Lori Lorigo, Geri Gay

Computer Science Technical Reports

Data about movement through a space is increasingly becoming available for capture and analysis. In many applications, this data is captured or modeled as transitions between a small number of areas of interests, or a finite set of states, and these transitions constitute paths in the space. Similarities and differences between paths are of great importance to such analyses, but can be difficult to assess. In this work we present a visualization approach for representing paths in context, where individual paths can be compared to other paths or to a group of paths. Our approach summarizes path behavior using a …


A Simple Computational Method For The Identification Of Disease-Associated Loci In Complex, Incomplete Pedigrees, Gregory Leibon, Dan Rockmore, Martin R. Pollak Mar 2006

A Simple Computational Method For The Identification Of Disease-Associated Loci In Complex, Incomplete Pedigrees, Gregory Leibon, Dan Rockmore, Martin R. Pollak

Computer Science Technical Reports

We present an approach, called the Shadow Method, for the identification of disease loci from dense genetic marker maps in complex, potentially incomplete pedigrees. Shadow is a simple method based on an analysis of the patterns of obligate meiotic recombination events in genotypic data. This method can be applied to any high density marker map and was specifically designed to explore the fact that extremely dense marker maps are becoming more readily available. We also describe how to interpret and associated meaningful P-Values to the results. Shadow has significant advantages over traditional parametric linkage analysis methods in that it can …


Tr-2006003: Explicit Proofs In Formal Provability Logic, Evan Goris Jan 2006

Tr-2006003: Explicit Proofs In Formal Provability Logic, Evan Goris

Computer Science Technical Reports

No abstract provided.


Tr-2006007: Root-Finding With Eigen-Solving, Victor Y. Pan, Brian Murphy, Rhys Eric Rosholt Jan 2006

Tr-2006007: Root-Finding With Eigen-Solving, Victor Y. Pan, Brian Murphy, Rhys Eric Rosholt

Computer Science Technical Reports

No abstract provided.


Tr-2006008: Every P-Recursion Category Has An Index Composer, Florian Lengyel Jan 2006

Tr-2006008: Every P-Recursion Category Has An Index Composer, Florian Lengyel

Computer Science Technical Reports

No abstract provided.


Tr-2006005: Logical Omniscience Via Proof Complexity, Sergei Artemov, Roman Kuznets Jan 2006

Tr-2006005: Logical Omniscience Via Proof Complexity, Sergei Artemov, Roman Kuznets

Computer Science Technical Reports

No abstract provided.


Tr-2006006: Additive Preconditioning And Aggregation In Matrix Computations, Victor Y. Pan, Dmitriy Ivolgin, Brian Murphy, Rhys Eric Rosholt, Islam Taj-Eddin, Yuqing Tang, Xiaodong Yan Jan 2006

Tr-2006006: Additive Preconditioning And Aggregation In Matrix Computations, Victor Y. Pan, Dmitriy Ivolgin, Brian Murphy, Rhys Eric Rosholt, Islam Taj-Eddin, Yuqing Tang, Xiaodong Yan

Computer Science Technical Reports

No abstract provided.


Tr-2006012: Every P-Recursion Category Has An Index Composer, Florian Lengyel Jan 2006

Tr-2006012: Every P-Recursion Category Has An Index Composer, Florian Lengyel

Computer Science Technical Reports

No abstract provided.


Tr-2006001: The Em Algorithm As A Lower Bound Optimization Technique, Rave Harpaz, Robert Haralick Jan 2006

Tr-2006001: The Em Algorithm As A Lower Bound Optimization Technique, Rave Harpaz, Robert Haralick

Computer Science Technical Reports

No abstract provided.


Tr-2006002: A Replacement Theorem For Lp, Melvin Fitting Jan 2006

Tr-2006002: A Replacement Theorem For Lp, Melvin Fitting

Computer Science Technical Reports

No abstract provided.


Tr-2006004: Justified Knowledge Is Sufficient, Evangelia Antonakos Jan 2006

Tr-2006004: Justified Knowledge Is Sufficient, Evangelia Antonakos

Computer Science Technical Reports

No abstract provided.


Tr-2006011: Locally Connected Recursion Categories, Florian Lengyel Jan 2006

Tr-2006011: Locally Connected Recursion Categories, Florian Lengyel

Computer Science Technical Reports

No abstract provided.


Tr-2006013: The Dom Event And Its Use In Implementing Constraint Propagators, Neng-Fa Zhou, Mark Wallace, Peter J. Stuckey Jan 2006

Tr-2006013: The Dom Event And Its Use In Implementing Constraint Propagators, Neng-Fa Zhou, Mark Wallace, Peter J. Stuckey

Computer Science Technical Reports

No abstract provided.


Tr-2006014: Geometric Considerations For Distribution Of Sensors In Ad-Hoc Sensor Networks, Ted Brown, Deniz Sarioz, Amotz Bar-Noy, Tom Laporta, Dinesh Verma, Matthew Johnson, Hosam Rowaihy Jan 2006

Tr-2006014: Geometric Considerations For Distribution Of Sensors In Ad-Hoc Sensor Networks, Ted Brown, Deniz Sarioz, Amotz Bar-Noy, Tom Laporta, Dinesh Verma, Matthew Johnson, Hosam Rowaihy

Computer Science Technical Reports

No abstract provided.


A Novel Minimized Dead-End Elimination Criterion And Its Application To Protein Redesign In A Hybrid Scoring And Search Algorithm For Computing Partition Functions Over Molecular Ensembles, Ivelin Georgiev, Ryan H. Lilien, Bruce R. Donald Jan 2006

A Novel Minimized Dead-End Elimination Criterion And Its Application To Protein Redesign In A Hybrid Scoring And Search Algorithm For Computing Partition Functions Over Molecular Ensembles, Ivelin Georgiev, Ryan H. Lilien, Bruce R. Donald

Computer Science Technical Reports

Novel molecular function can be achieved by redesigning an enzyme's active site so that it will perform its chemical reaction on a novel substrate. One of the main challenges for protein redesign is the efficient evaluation of a combinatorial number of candidate structures. The modeling of protein flexibility, typically by using a rotamer library of commonly-observed low-energy side-chain conformations, further increases the complexity of the redesign problem. A dominant algorithm for protein redesign is Dead-End Elimination (DEE), which prunes the majority of candidate conformations by eliminating rigid rotamers that provably are not part of the Global Minimum Energy Conformation (GMEC). …