COMPUTER SCIENCE TECHNICAL REPORTS 2002
School of Computer Science, Carnegie Mellon University
Pittsburgh PA 15213-3890
(412)268-8525 . (412)268-5576 (fax)


Technical Reports by Author
Theses by Author

CMU-CS-02-100
Model Checking and Theorem Proving: A Unified Framework
Sergery Berezin, Ph.D. Thesis
Abstract, .ps, .pdf

CMU-CS-02-101
A Concurrent Logical Framework I: Judgments and Properties
Kevin Watkins, Iliano Cervesato, Frank Pfenning, David Walker
Abstract, .ps, .pdf

CMU-CS-02-102
A Concurrent Logical Framework II: Examples and Applications
Iliano Cervesato, Frank Pfenning, David Walker, and Kevin Watkins
Abstract, .ps, .pdf

CMU-CS-02-103
Unpublished

CMU-CS-02-104
Existence of Multiagent Equilibria with Limited Agents
Michael Bowling, Manuela Veloso
Abstract, .ps, .pdf

CMU-CS-02-105
A Connectionist Model of Sentence Comprehension and Production
Douglas L.T. Rohde, Ph.D. Thesis
Abstract, .ps, .ps.gz, .pdf

CMU-CS-02-106
Rule-Based Anomaly Pattern Detection for Detecting Disease Outbreaks
Weng-Keen Wong, Andrew Moore, Gregory Cooper, Michael Wagner
Abstract, .ps, .pdf

CMU-CS-02-107
Pegasus: An Efficient Intermediate Representation
Mihai Budiu, Seth Copen Goldstein
Abstract, .ps, .pdf

CMU-CS-02-108
Unavailable to Date

CMU-CS-02-109
Minimization and Reliability Analyses of Attack Graphs
Somesh Jha, Oleg Sheyner, Jeannette M. Wing
Abstract, .ps, .pdf

CMU-CS-02-110
On the Complexity of MAX/MIN/AVRG Circuits
Manuel Blum, Rachel Rue, Ke Yang
Abstract, .ps, .pdf

CMU-CS-02-111
Robotic Mapping: A Survey
Sebastian Thrun
Abstract, .ps, .pdf

CMU-CS-02-112
Simultaneous Mapping and Localization With Sparse Extended Information Filters: Theory and Initial Results
Sebastian Thrun, Daphne Koller, Zoubin Ghahmarani, Hugh Durrant-Whyte, Andrew Y. Ng
Abstract, .ps, .ps.gz, .pdf

CMU-CS-02-113
Affinity Scheduling in Staged Server Architectures
Stavros Harizopoulos, Anastassia Ailamaki
Abstract, .ps, .pdf

CMU-CS-02-114
Verifiable Secret Redistribution for Threshold Sharing Schemes
Theordore M. Wong, Chenxi Wang, Jeannette M. Wing
Abstract, .ps, .pdf

CMU-CS-02-115
Fractal Prefetching B+-Trees: Optimizing Both Cache and Disk Performance
Shimin Chen, Phillip B. Gibbons, Todd C. Mowry, Gary Valentin
Abstract, .ps, .pdf

CMU-CS-02-116
Using Tarjan's Red Rule for Fast Dependency Tree Construction
Dan Pelleg, Andrew Moore
Abstract, .ps, .pdf

CMU-CS-02-117
Telling Humans and Computers Apart (Automatically) or
How Lazy Cryptographers do AI

Luis von Ahn, Manuel Blum, John Langford
Abstract, .ps, .pdf

CMU-CS-02-118
Asymptotic Convergence of Scheduling Policies with Respect to Slowdown
Mor Harchol-Balter, Karl Sigman, Adam Wierman
Abstract, .ps, .pdf

CMU-CS-02-119
Developing a Pedagogical Domain Theory of Early Algebra Problem Solving
Kenneth R. Koedinger, Benjamin A. MacLaren
Abstract, .ps, .pdf

CMU-CS-02-120
The Wizard of TILT: Efficient?, Convenient, and Abstract Type Representations
Tom Murphy, Senior Thesis
Abstract, .ps, .pdf

CMU-CS-02-121
Unavailable to Date

CMU-CS-02-122
A Type System for Higher-Order Modules
Derek Dreyer, Karl Crary, Robert Harper
Abstract, .ps, .pdf

CMU-CS-02-122R
A Type System for Higher-Order Modules (Expanded Version)
Derek Dreyer, Karl Crary, Robert Harper
Abstract, .ps, .pdf

CMU-CS-02-123
Meta-Programming with Names and Necessity
Aleksandar Nanevski
Abstract, .ps, .pdf

CMU-CS-02-123R
Meta-Programming with Names and Necessity
Aleksandar Nanevski
Abstract, .ps, .pdf

CMU-CS-02-124
Effectiveness of Preference Elicitation in Combinatorial Auctions
Benoit Hudson, Tuomas Sandholm
Abstract, .ps, .pdf

CMU-CS-02-125
Unpublished

CMU-CS-02-126
Using Asymmetric Distributions to Improve Classifier Probabilities:
A Comparison of New and Standard Parametric Methods

Paul N. Bennett
Abstract, .ps (B&W), .pdf (B&W), .ps (Color), .ps (Color)

CMU-CS-02-127
John F. Pane, Ph.D. Thesis
A Programming System for Children that is Designed for Usability
Abstract, .ps, .pdf, A.pdf(Appendices)

CMU-CS-02-128
Minimizing Weighted Flow Time
Nikhil Bansal, Kedar Dhamdhere
Abstract, .ps, .pdf

CMU-CS-02-129
On Correlated Failures in Survivable Storage Systems

Mehmet Bakkaloglu, Jay J. Wylie, Chenxi Wang, Gregory R. Ganger
Abstract, .ps, .pdf

CMU-CS-02-130
Temporal Logic for Proof-Carrying Code
Andrew Bernard, Peter Lee
Abstract, .ps, .pdf

CMU-CS-02-131
Face as an index: Knowing Who Is Who Using a PDA
Jie Yang, Xilin Chen, William Kunz, Harsh Kundra
Abstract, .ps, .pdf

CMU-CS-02-132
Reducing Separation Formulas to Propositional Logic
Ofer Strichman, Sanjit A. Seshia, Randal E. Bryant
Abstract, .ps, .pdf

CMU-CS-02-133
Optimizations in Decision Procedures for Propositional Linear Inequalities
Ofer Strichman
Abstract, .ps, .pdf

CMU-CS-02-134
Lightweight Structure in Text
Robert C. Miller, Ph.D. Thesis
Also appears as CMU-HCII-02-103
Abstract, .ps, .pdf

CMU-CS-02-135
Complexity Results about Nash Equilibria
Vincent Conitzer, Tuomas Sandholm
Abstract, .ps, .pdf

CMU-CS-02-136
Game Strategies in Network Security
Kong-wei Lye, Jeannette M. Wing
Abstract, .ps, .pdf

CMU-CS-02-137
Complexity of Determining Nonemptiness of the Core
Vincent Conitzer, Tuomas Sandholm
Abstract, .ps, .pdf

CMU-CS-02-138
Fast Factored Density Estimation and Compression with Bayesian Networks
Scott Davies, Ph.D. Thesis
Abstract, .ps, .pdf

CMU-CS-02-139
Exploring Congestion Control
Aditya Akella, Srinivasan Seshan, Scott Shenker, Ion Stoica
Abstract, .ps, .pdf

CMU-CS-02-140
Intrusion Detection, Dignosis, and Recovery with Self-Securing Storage
John D. Strunk, Garth R. Goodson, Adam G. Pennington, Craig A.N. Soules, Gregory R. Ganger
Abstract, .ps, .pdf

CMU-CS-02-141
An Internet-style Approach to Managing Wireless Link Errors
David A. Eckhardt, Ph.D. Thesis
Abstract, .ps, .pdf

CMU-CS-02-142
Hypertext Classification
Sean Slattery, Ph.D. Thesis
Abstract, .ps, .pdf

CMU-CS-02-143
Web Servers Under Overload: How Scheduling Can Help
Bianca Schroeder, Mor Harchol-Balter
Abstract, .ps, .pdf

CMU-CS-02-144
Self-Securing Network Interfaces: What, Why and How
Gregory R. Ganger, Gregg Economou, Stanley M. Bielski
Abstract, .ps, .pdf

CMU-CS-02-145
Metadata Efficiency in a Comprehensive Versioning File System
Craig A.N. Soules, Garth R. Goodson, John D. Strunk, Gregory R. Ganger
Abstract, .ps, .pdf

CMU-CS-02-146
Eliminating Machine Duplicity in Traceroute-based Internet Topology Measurements
Hal Burch
Abstract, .ps, .pdf

CMU-CS-02-147
Quantitatively Tight Sample Complexity Bounds
John Langford, Ph.D. Thesis
Abstract, .pdf

CMU-CS-02-148
Optimal Binary Trees in Online Algorithms
Daniel Sleator, Muralidhar Talupu
Abstract, .ps, .pdf

CMU-CS-02-149
Provably Secure Steganography
Nicholas J. Hopper, John Langford, Luis von Ahn
Abstract, .ps, .pdf

CMU-CS-02-150
Iktara in ConCert: Realizing a Certified Grid Computing Framework from a Programmer's Perspective
Bor-Yuh Evan Chang, Senior Thesis
Abstract, .ps, .pdf

CMU-CS-02-151
Implementing a Framework for Certified Grid Computing
Margaret DeLap, Senior Thesis
Abstract, .ps, .pdf

CMU-CS-02-152
Trustless Grid Computing in ConCert
Bor-Yuh Evan Chang, Karl Crary, Margaret DeLaop, Robert Harper, Jason Liszka, Tom Murphy VII, Frank Pfenning
Abstract, .ps, .pdf

CMU-CS-02-153
Proof Irrelevance and Strict Definitions in a Logical Framework
Jason Reed, Senior Thesis
Abstract, .ps, .pdf

CMU-CS-02-154
Providing Contextual Information to Ubiquitous Computing Applications
Glenn Judd, Peter Steenkiste
Abstract, .ps, .pdf

CMU-CS-02-155
eSourcing Capability Model (eecmsm) for IT-enabled Service Providers v1.1
Elaine B. Hyder, Bennet Kumar, Vivek Mahendra, Jane Siegel, Keith M. Heston, Rajesh Gupta, Habeeb Mahaboob, Palanivelrajan Subramanian
Abstract, .ps, .pdf

CMU-CS-02-156
eSourcing Capability Model (eSCM) Annotated Bibligraphy
Bennet Kumar, Vivek Mahendra, Elaine Hyder, Elise Nawrocki, K. Madhu, Rajesh Gupta
Abstract, .ps, .pdf

CMU-CS-02-157
Shape Reconstruction Using Active Tactile Sensors
Mark Moll, PhD Thesis
Abstract, .ps, .pdf

CMU-CS-02-158
Analysis of Task Assignment with Cycle Stealing
Mor Harchol-Balter, Cuihong Li, Takayuki Osogami, Alan Scheller-Wolf, Mark S. Squillante
Abstract, .ps, .pdf

CMU-CS-02-159
Improving Web Performance in Broadcast-Unicast Networks
Mukesh Agrawal, Amit Manjhi, Nikhil Bansal, Srinivasan Seshan
Abstract, .ps, .pdf

CMU-CS-02-160
Interactive Electronic Technical Manuals (IETMs) Annotated Bibliography
Jane Siegel, Elise Nawrocki
Abstract, .ps, .pdf

CMU-CS-02-161
Discriminative Distance Measures for Object Detection
Shyjan Mahamud, Ph.D. Thesis
Abstract, .ps, .ps.gz, .pdf

CMU-CS-02-162
Unavailable to Date

CMU-CS-02-163
Machanisms for Internet Routing: A Study
Aditya Akella, Shuchi Chawla, Srini Seshan
Abstract, .ps, .pdf

CMU-CS-02-164
Profit Maximizing Mechanisms for the Extended Multicasting Game
Shuchi Chawla, David Kitchin, Uday Rajan, Ramamoorthi Ravi, Amitabh Sinha
Abstract, .ps, .pdf

CMU-CS-02-165
Unavailable to Date

CMU-CS-02-166
Estimating Available Bandwidth Using Packet Pair Probing
Ningning Hu, Peter Steenkiste
Abstract, .ps, .pdf

CMU-CS-02-167
FastCARS: Fast, Correlation-Award Sampling for Network Data Mining
Jia-Yu Pan, Srinivasan Seshan, Christos Faloutsos
Abstract, .ps, .pdf

CMU-CS-02-168
Operating System Support for Mobile Interactive Applications
Dushyanth Narayanan, Ph.D. Thesis
Abstract, .ps, .pdf

CMU-CS-02-169
Tree Based Hierarchical Reinforcement Learning
William T.B. Uther, PhD Thesis
Abstract, .ps, .pdf

CMU-CS-02-170
Multi-Modal Network Protocols: Adapting to Highly Variable Operating Conditions
Aditya Akella, Ashwin Bharambe, Suman Nath, Srinivasan Seshan
Abstract, .ps, .pdf

CMU-CS-02-171
Leaf Petersen, Robert Harper, Karl Crary, Frank Pfenning
A Type Theory for Memory Allocation and Data Layout (Extended Version)
Abstract, .ps, .pdf

CMU-CS-02-172
SetA* Applied to Channel Routing
Rune M. Jensen, Randal E. Bryant, Manuela M. Veloso
Abstract, .ps, .pdf

CMU-CS-02-173
A Comparison Study between the CUDD and BuDDy OBDD Package Applied to AI-Planning Problems
Rune M. Jensen
Abstract, .ps, .pdf

CMU-CS-02-174
State-Set Branching: Leveraging OBDDs for Heuristic Search
Rune M. Jensen, Randal E. Bryant, Manuela M. Veloso
Abstract, .ps, .pdf

CMU-CS-02-175
Unavailable to Date

CMU-CS-02-176
Unavailable to Date

CMU-CS-02-177
A Note on Comparing Response Times in the M/GI/1/FB and M/GI/1/PS Queues
Adam Wierman, Nikhil Bansal, Mor Harchol-Balter
Abstract, .ps, .pdf

CMU-CS-02-178
Necessary and Sufficient Conditions for Representing General Distributions by Coxians
Takayuki Osogami, Mor Harchol-Balter
Abstract, .ps, .pdf

CMU-CS-02-179
Storage-based Intrusion Detection: Watching Sotrage Activity for Suspicious Behavior
Adam G. Pennington, John D. Strunk, John Linwood Griffin,Craig A.N. Soules, Garth R. Goodson, Gregory R. Ganger
Abstract, .ps, .pdf

CMU-CS-02-180
Decentralized Storage Consistency via Versioning Servers
Garth R. Goodson, Jay J. Wylie, Gregory R. Ganger, Michael K. Reiter
Abstract, .ps, .pdf

CMU-CS-02-181
What Makes a Good Molecular-Scale Computer Device?
Seth Copen Goldstein, Dan Rosewater
Abstract, .ps, .pdf

CMU-CS-02-182
Combining Two Forms of Type Refinements
Joshua Dunfield
Abstract, .ps, .pdf

CMU-CS-02-183
Cuckoo: Layered Clustering for NFS
Andrew J. Klosterman, Gregory Ganger
Abstract, .ps, .pdf

CMU-CS-02-184
Unavailable to Date

CMU-CS-02-185
A System for Three-Dimensional Robotic Mapping of Underground Mines
Michael Montemerlo, Dirk Hahnel, David Ferguson, Rudolph Triebel, Wolfram Burgard, Scott Thayer, William Whittaker, Sebastian Thrun
Abstract, .ps, .ps.gz, .pdf

CMU-CS-02-186
My Cache or Yours? Making Storage More Exclusive
Theodore M. Wong, John Wilkes
Abstract, .ps, .pdf

CMU-CS-02-187
Classifying Scheduling Policies with respect to Unfairness in an M/GI/1
Adam Wierman, Mor Harchol-Balter
Abstract, .ps, .pdf

CMU-CS-02-188
LOCI: Fast Outlier Detection Using the Local Correlation Integral
Spiros Papadimitriou, Hiroyuki Kitagawa, Phillip B. Gibbons, Christos Faloutsos
Abstract, .ps, .ps.gz, .pdf

CMU-CS-02-189
Compromising Privacy in Distributed Population-Based Databases with Trail Matching: A DNA Example
Bradley Malin, Latanya Sweeney
Abstract, .ps, .pdf

CMU-CS-02-190
Integrating Multiple Knowledge Sources for Utterance-Level Confidence Annotation in the CMU Communicator Spoken Dialog System
Dan Bohus, Alexander Rudnicky
Abstract, .ps, .pdf

CMU-CS-02-191
Solving Hard AI Problems Using Computer Games
Luis von Ahn, M. Ian Graham, Laura Dabbish, David Kitchin, Lenore Blum
Abstract, .ps, .pdf
Currently unavailable electronically.
Contact authors directly. See abstract for links.

CMU-CS-02-192
Analysis of Cycle Stealing with Switching Cost
Takayuki Osogami, Mor Harchol-Balter, Alan Scheller-Wolf
Abstract, .ps, .pdf

CMU-CS-02-193
Adventures in Ultra-Small-Space Clustering
Adam Meyerson, Liadan O'Callaghan, Serge Plotkin
Abstract, .ps, .pdf

CMU-CS-02-194
Unpublished

CMU-CS-02-195
Rapid Protein Structure Detection and Assignment using Residual Dipolar Couplings
Michael A. Erdmann, Gordon S. Rule
Abstract, .ps, .ps.gz, .pdf

CMU-CS-02-196
Toward a Foundational Typed Assembly Language
Karl Crary
Abstract, .ps, .pdf

CMU-CS-02-197
Unavailable to Date

CMU-CS-02-198
Architecture, Authorial Idioms and Early Observations of the Interface Drama Fašade
Michael Mateas, Andrew Stern
Abstract, .ps, .pdf

CMU-CS-02-199
The Integrality Gap of Capacitated Facility Location
Zoë Abrams, Adam Meyerson, Kamesh Munagala, Serge Plotkin
Abstract, .ps, .pdf

CMU-CS-02-200
Typed Compilation of Recursive Datatypes
Joseph C. Vanderwaart, Derek Dreyer, Leaf Petersen, Karl Crary, Robert Harper, Perry Cheng
Abstract, .ps, .pdf

CMU-CS-02-201
Competitive Analaysis of M/GI/1/Queueing Policies
Nikhil Bansal, Adam Wierman
Abstract, .ps, .pdf

CMU-CS-02-202
Unpublished

CMU-CS-02-203
Simultaneous Optimization via Approximate Majorization for Concave Profits or Convex Costs
Ashish Goel, Adam Meyerson
Abstract, .ps, .pdf

CMU-CS-02-204
Unavailable to Date

CMU-CS-02-205
Adaptive, Hand-Off Stream Mining
Spiros Papadimitriou, Anthony Brockwell, Christos Faloutsos
Abstract
Currently unavailable electronically.
For copies contact: spapadim@cs.cmu.edu

CMU-CS-02-206
Interactive Drama, Art and Artificial Intelligence
Michael Mateas, Ph.D. Thesis
Abstract, .ps, .pdf

CMU-CS-02-207
Random Key Predistribution Schemes for Sensor Networks
Haowen Chan, Adrian Perrig, Dawn Song
Abstract, .ps, .pdf

CMU-CS-02-208
StackPi: A New Defense Mechanism Against IP Spoofing and DDoS Attacks
Adrian Perrig, Dawn Song, Abraham Yaar
Abstract, .ps, .pdf

CMU-CS-02-209
Reducing Truth-telling Online Mechanisms to Online Optimization
Brauch Awerbuch, Yossi Azar, Adam Meyerson
Abstract, .ps, .pdf


Return to: SCS Technical Report Collection