[Date Prev][Date Next][Date Index]
CSLI Calendar, Wednesday, 3 March 2004, vol. 19:25
CSLI CALENDAR OF PUBLIC EVENTS
______________________________________________________________________
2 March 2004 Stanford Vol. 19, No. 25
______________________________________________________________________
A weekly publication of the
Center for the Study of Language and Information (CSLI)
Stanford University, Cordura Hall, Stanford, CA 94305-4115
http://www-csli.stanford.edu/
____________
ACTIVITIES FROM 3 MARCH 2004 TO 12 MARCH 2004
WEDNESDAY, 3 MARCH 2004
3:45pm Psychology Department Colloquium
Jordan Hall 420:041
"Neural Components of Inhibitory Processing"
John Jonides
University of Michigan
http://www-psych.stanford.edu/news.html
4:00pm UC Berkeley EECS Colloquium
306 Soda Hall (Berkeley)
"Unsupervised Learning of Natural Language Syntax"
Dan Klein
CS, Stanford
http://coe.berkeley.edu/events/
4:15pm CSLI Seminar on Computational Learning and Adaptation
Cordura Hall, room 100
Title to be announced
Geoff Gordon
Carnegie Mellon University
http://cll.stanford.edu/scla.html
4:15pm EE380: Computer Systems Lab Colloquium
Gates B03 (NEC Auditorium)
"Open for Change"
Matthew Szulik
President and CEO, RedHat
http://ee380.stanford.edu/contents.html
Abstract below
THURSDAY, 4 MARCH 2004
11:00am UC Berkeley CIS Seminar
Soda Hall 310 (UC Berkeley)
"Solving Relational MDPs by Reduction to Classification"
Alan Fern
Purdue
http://min.ecn.purdue.edu/~afern/
http://www.eecs.berkeley.edu/~ywteh/cis-seminar
Abstract below
12 noon Semantics and Pragmatics Workshop
Margaret Jacks Hall 460:126
"Scalar Complexity and the Structure of Events"
John Beavers
Stanford University
http://www-linguistics.stanford.edu/semgroup/
Abstract below
12:15pm Stanford Networking Seminar
Packard 202
"(1) Modeling multimedia file-sharing traffic, and
(2) Quantifying the spread of spyware"
Steven Gribble
University of Washington
http://netseminar.stanford.edu/
Abstract below
3:00pm Reuters Foundation Digital Vision Program Seminar
Reuters lounge, Cordura Hall
Isabel Maxwell
formerly iCognito Technologies
http://cgi.stanford.edu/group/reuters/cgi-bin/calendar/index.cgi
4:00pm Personality Seminar
Jordan Hall 420:100
Title to be announced
Susan Folkman
http://www-psych.stanford.edu/news.html#person_lab
4:00pm SRI AI Seminar Series
EJ228, SRI International
"Applying Plan Recognition to Cyber Attacks"
Peter A Jarvis
Artificial Intelligence Center, SRI
http://www.ai.sri.com/seminars/
Abstract below
4:00pm PARC Forum
George Pake Auditorium at PARC
"Complexity and fragility with applications to Internet technology"
John Doyle
Electrical Engineering, BioEngineering, and Control and
Dynamical Systems, CalTech
http://www.parc.com/forum/
Abstract below
4:00pm Berkeley International Computer Science Institute
ICSI, Rm 607 (UC Berkeley)
"Research at FX Palo Alto Laboratory"
Candace Kamm, FX Palo Alto Laboratory
http://www.icsi.berkeley.edu/talks/
Abstract below
4:10pm UC Berkeley Philosophy Department Colloquium
Howison Philosophy Library, (305 Moses Hall) (Berkeley)
"Virtue Ethics and Social Psychology"
Julia Annas
University of Arizona
http://philosophy.berkeley.edu/html/events/deptevents.html
4:15pm SSP10: Symbolic Systems Forum
Bldg. 380:380C (Math Corner)
"In Search of Bloom's Missing Sigma"
Heather Pon-Barry
Symbolic Systems Program, Stanford University
http://symsys.stanford.edu:8081/ssp-dynamic/servlet/ssp_events
Abstract below
4:15pm Information Systems Seminar
Packard 101
"Cost-Distortion-Optimal Communication Via Measure-Matching:
Key Ideas And Application To Neural Communication"
Bixio Rimoldi
EPFL
http://isl.stanford.edu/groups/seminar/
Abstract below
FRIDAY, 5 MARCH 2004
11:00am Computer Science Talk
Gates 260
"Minimax Regret Methods for Decision Making with Imprecise
Utility Functions"
Craig Boutilier
Computer Science, University of Toronto
http://www.cs.toronto.edu/~cebly/
Abstract below
11:00am UC Berkeley ICBS Colloquium
Tolman 5101 (Berkeley)
"He Doesn't Understand Every Word You Say:
What We Know about Cognition in Dogs"
Stephen Lea
Psychology, University of Exeter
http://socrates.berkeley.edu:4247/seminar.html
12:30pm CS547: Human-Computer Interaction Seminar
Gates B03
"Privacy in the Age of Ubiquitous Computing"
Jason Hong
UC Berkeley
http://www.eecs.berkeley.edu/~jasonh/
http://www-pcd.stanford.edu/cs547/
Abstract below
12 noon Logical Methods in the Humanities
Bldg. 90:92Q (Philosophy)
"Hobbes on Rigorous Demonstration: Theory Meets Practice"
Doug Jesseph
North Carolina
http://www-logic.stanford.edu/seminars.html
Abstract below
1:45pm NLP Reading Group
Ventura 17
"Predicate-argument structure from broad-coverage parse trees:
Improving on the context-free approximation"
Roger Levy
Linguistics, Stanford
http://www-nlp.stanford.edu/nlp/nlpgroup.html
Abstract below
3:15pm Friday Cognitive Seminar
Jordan Hall 420:100
FYP Talks
Nicole Dudukovic and Brice Kuhl
http://www-psych.stanford.edu/news.html#frisem
4:15pm CS545: Database Seminar
Gates B12
"Processing Life Science Data using Scalable Database Technology"
Christoph Freytag
Humboldt University Berlin
http://www-db.stanford.edu/dbseminar/
Abstract below
MONDAY, 8 MARCH 2004
1:00pm Information Systems Seminar
Packard 101
"Connections between Estimation Theory and Information Theory"
Sergio Verdu
Princeton University
http://isl.stanford.edu/groups/seminar/
Abstract below
3:30pm Social Lab
Jordan Hall 420:050
"Stress And Social Support At Work: Social and Psychological
Pathways For Enhancing Health"
Cathy Heaney
Public Health, Ohio State University
http://www-psych.stanford.edu/news.html#social_lab
4:15pm CS528: Broad Area Colloquium in AI,
Geometry, Graphics, Robotics, and Vision
TCSeq 200
Title to be announced
Kenry Kautz
University of Washington
http://www.cs.washington.edu/homes/kautz/
http://graphics.stanford.edu/courses/cs528/
5:45pm Center for Internet and Society Talk
Law School 290
"The Ethics of P2P Filesharing"
Larry Lessig
Deborah Rhode
Law School, Stanford
http://cyberlaw.stanford.edu/
Abstract below
TUESDAY, 9 MARCH 2004
12 noon Linguistics Department Colloquium
Margaret Jacks Hall 460:126
"The Interpretive Loop: Uninterpretable Candidates
and the Phonology-Phonetics Interface"
Paul de Lacy
Cambridge University
http://www-linguistics.stanford.edu/colloq/
Abstract below
2:15pm Semantics and Pragmatics Workshop
Margaret Jacks Hall 460:126
Title to be announced
Klaus von Heusinger
University of Stuttgart
(talking in Linguistics 233A, all welcome)
http://www-linguistics.stanford.edu/semgroup/
3:00pm CS/EE Seminar
Gates 104
"Distributed Hash Tables for Networked Systems"
Sylvia Ratnasamy
Intel Research
Abstract below
3:30pm UC Berkeley Psychology Colloquium
5101 Tolman (Berkeley)
"Coping and Stress Reactivity:
A Dual Process Model of Responses to Stress"
Bruce Compas
Psychology and Human Development, Vanderbilt University
http://psychology.berkeley.edu/admin/colloquia.html
4:15pm EE392: Sensor Networks Seminar
Jordan Hall 041
"Ubiquitous sensor networks. When? Why or Why not?"
Panel discussion
http://www.stanford.edu/class/ee392s/
5:00pm UC Berkeley Cognitive Science Colloquium
2040 Valley Life Sciences Building (Berkeley)
"Interaction in language processing:
Pragmatic constraints on lexical access"
James Magnuson
Psychology, Columbia University
http://psychology.berkeley.edu/admin/colloquia.html
Abstract below
WEDNESDAY, 10 MARCH 2004
3:45pm Psychology Department Colloquium
Jordan Hall 420:041
"Stress, Cognition, and Brain Aging"
David Lyons
Stanford University
http://www-psych.stanford.edu/news.html
4:15pm EE380: Computer Systems Lab Colloquium
Gates B03 (NEC Auditorium)
Title to be announced
Daniel Robbins
Gentto.org
http://www.gentoo.org/
http://ee380.stanford.edu/contents.html
7:00pm SCIL Futures of Learning Lecture Series
Wallenberg Hall Learning theater (Bldg. 160)
Title to be announced
Hans Spade
University of Freiburg, Germany
http://scil.stanford.edu/
THURSDAY, 11 MARCH 2004
12:15pm CSLI CogLunch
Cordura Hall, Room 100
"The Role of Information Scent in Information Foraging on the Web"
Peter Pirolli
PARC
http://www-csli.stanford.edu/events/Coglunch/
Abstract below
3:00pm Reuters Foundation Digital Vision Program Seminar
Reuters lounge, Cordura Hall
Richard Newton
UC Berkeley
http://cgi.stanford.edu/group/reuters/cgi-bin/calendar/index.cgi
4:00pm Personality Seminar
Jordan Hall 420:100
Title to be announced
Jeanne Tsai
http://www-psych.stanford.edu/news.html#person_lab
4:15pm SSP10: Symbolic Systems Forum
Bldg. 380:380C (Math Corner)
"The dative alternation and the meaning of variation: Is
variation at the level of syntax determined by semantic differences?"
Joan Bresnan
Linguistics, Stanford
http://symsys.stanford.edu:8081/ssp-dynamic/servlet/ssp_events
Abstract below
FRIDAY, 12 MARCH 2004
all day Fifth Annual Semantics Fest
Cordura 100
http://www-linguistics.stanford.edu/semgroup/semfest.html
11:00am UC Berkeley ICBS Colloquium
Tolman 5101 (Berkeley)
"Combining Visual Information to Perceive 3-D Layout"
Marty Banks
Optometry and Vision Science, UC Berkeley
http://socrates.berkeley.edu:4247/seminar.html
12:30pm CS547: Human-Computer Interaction Seminar
Gates B03
"Interactive Entertainment:
Sharing Control Between Authors and Participants"
Randy Pausch
Carnegie-Mellon University
http://www-pcd.stanford.edu/cs547/
Abstract below
3:15pm Philosophy Department Colloquium
Bldg. 90:92Q
"Sources of Formalism in Mathematics"
Michael Detlefsen
University of Notre Dame
http://www-philosophy.stanford.edu/ce.html
3:15pm Friday Cognitive Seminar
Jordan Hall 420:100
FYP Talks
Adam November and Angela Kessell
http://www-psych.stanford.edu/news.html#frisem
4:15pm CS545: Database Seminar
Gates B12
"Tracing the Provenance and Flow of Data"
Wang-Chiew Tan
U.C. Santa Cruz
http://www-db.stanford.edu/dbseminar/
Abstract below
____________
Stanford Blood Center status: Shortage of O+, O-, A-, AB+, and AB-.
For an appointment: http://bloodcenter.stanford.edu/ or call
650-723-7831. It only takes an hour of your time.
____________
ANNOUNCEMENT
Child Language Research Forum
16-17 April 2004
http://www-csli.stanford.edu/~clrf/
Constructions in Acquisition
How do children learn constructions---noun phrases, verb phrases, and
other phrase types? Do they begin with specific lexical items in a
construction and use only those? To what extent do they build from
'verb islands' or 'noun islands' in early constructions? Which
constructions emerge first? What criteria should we use in
establishing productivity? What makes constructions easy vs. hard to
acquire? Can children's bases for inferences about the relevant noun
or verb meanings be identified? Are there consistent patterns across
children in the acquisition of constructions? Are there differences
from one verb type to another, or from intransitive to transitive?
Are differences attributable to differences in frequencies in
child-directed speech? What cross-linguistic comparisons are
available? Which constructions have been considered in studies of
children's early syntactic forms?
Registration: Pre-register before March 20, 2004:
1. Preregistration:
$50 for non-students
$20 for students
Send cheque made out to "CLRF-2004" by March 20th, 2004, to:
CLRF-2004,
Department of Linguistics,
Stanford University,
Stanford, CA 94305-2150,
USA
Please include your name, affiliation, and email address.
2. Walk-in registration: $65 for non-students, $30 for students.
____________
EE380: COMPUTER SYSTEMS LAB COLLOQUIUM
on Wednesday, 3 March 2004, 4:15pm to 5:30pm
NEC Auditorium (B03), Gates Computer Science Building
http://ee380.stanford.edu/contents.html
"Open for Change"
Matthew Szulik
President and CEO, RedHat
As a vehicle for economic and social change, the power of open source
is immeasurable. It's changing how people learn, how developers
create, how companies do business. In this talk, Red Hat CEO Matthew
Szulik will share his vision of how the open source model is allowing
greater affordability and access to technology, from the world's
largest organizations to its poorest societies.
About the speaker: Matthew J. Szulik,RedHat Chairman, Chief Executive
Officer and President has been leading early-stage technology
companies, such as Interleaf, MapInfo, and Red Hat, into global,
publicly traded firms for more than 20 years. In 1998, Szulik and Red
Hat founder Bob Young developed a shared vision that the collaborative
approach of open source and a great brand could redistribute the
economics of the technology industry from vendor to customer.
Following successful public offerings in 1999 and 2000, Red Hat has
developed global partnerships with Oracle, IBM, Dell, Intel, and HP to
deliver technology based on open source technology. Today, Red Hat is
the leading provider of Linux and open source technology to the
enterprise and is positioned to be the defining technology company of
the 21st century.
Szulik is passionate about improving the educational opportunities for
students worldwide through open source, and he is a spokesperson to
industry, government, and education leaders on open source computing.
Szulik is the Chairman of the Science and Technology Board for State
of North Carolina's Economic Development Board and is currently a
Director of Tibco Software. He is past Chairman and an Executive
Director of the North Carolina Electronics and Information
Technologies Association.
Szulik was recently recognized by CIO Magazine with its 20/20 Vision
Award.
____________
UC BERKELEY CIS SEMINAR
on Thursday, 4 March 2004, 11:00am-12:30pm
Soda Hall 310 (UC Berkeley)
http://www.eecs.berkeley.edu/~ywteh/cis-seminar
"Solving Relational MDPs by Reduction to Classification"
Alan Fern
Purdue
We present and empirically evaluate heuristic reductions from policy
selection for Markov decision problems (MDPs) to cost-sensitive
classification. Existing reductions that are based on approximate
policy iteration typically represent policies via cost functions and
produce a sequence of cost-function regression problems. Instead, our
approaches represent policies directly as state-action mappings and
produce a sequence of cost-sensitive classification problems. We argue
that reducing to classification rather than regression can have
practical benefits as it is often easier to specify an effective
policy space via a direct policy-language bias rather than a
cost-function bias. Empirically our techniques can select good
stationary policies for very large relational Markov decision
processes (MDPs) where previous techniques fail. In particular, we
induce high-quality domain-specific planners for classical planning
domains (both deterministic and stochastic variants) by solving such
domains as extremely large MDPs.
____________
STANFORD SEMANTICS AND PRAGMATICS WORKSHOP
on Thursday, 4 March 2004, 12 noon
Margaret Jacks Hall 460:126
http://www-linguistics.stanford.edu/semgroup/
"Scalar Complexity and the Structure of Events"
John Beavers
Stanford University
The telicity of change-of-state events often correlates
homomorphically to privileged participants in the event (e.g.
incremental themes, paths, cf. Krifka (1989), Tenny (1992)). In this
paper I adopt a general view of such homomorphisms and apply them to
durativity, arguing that the relevant factor for understanding
durativity is the complexity of the scale of change. This correlation
explains cooccurrence restrictions between certain aspectual classes
of verbs and result/goal XPs in resultative constructions (e.g.
non-gradable AdjPs only cooccurs with punctual Vs ("John shot/*beat
Bill dead") (Wechsler 2002); PP[to] only cooccurs with durative Vs
("John beat/*shot Bill to death") (Beavers 2002)). This correlation
also underlies the interpretation of inherent change-of-state Vs, e.g.
the traditional difference between achievements and accomplishments as
well as change-of-state Vs that allow variable durativity
interpretations (commensurate with variable gradability
interpretations). I provide a mereological account (Krifka 1998) of
this correlation by assuming that all dynamic Vs have both event and
scale arguments and entail a homomorphic mapping between these two
arguments that preserves mereological complexity. Lexical and
contextual factors impose constraints on the mereological complexity
of these two arguments and the homomorphism enforces compatibility
between the lexemes and context. This explains a wide range of
distributional data in a very general way, compatible with previous
work on telicity and expandable to other aspectual types (such as
statives).
____________
STANFORD NETWORKING SEMINAR
on Thursday, 4 March 2004, 12:40pm (lunch 12:15pm)
Packard 202
http://netseminar.stanford.edu/
"(1) Modeling multimedia file-sharing traffic, and
(2) Quantifying the spread of spyware"
Steven Gribble
University of Washington
I will present two measurement and analysis "mini-talks" on separate
(but related) topics: modeling P2P file-sharing workloads, and
quantifying the spread and impact of spyware at the University of
Washington. In both talks, my results are based on passive network
monitoring infrastructure that has allowed us to examine
(post-anonymization) all ingoing and outgoing University of Washington
network traffic. This infrastructure is a "telescope" that allows us
to examine the Internet from the perspective of UW's 60,000 faculty,
staff, and students.
In the first mini-talk, I will probe deeply into modern P2P file
sharing systems and the forces that drive them. Based on a 200-day
long trace of Kazaa traffic, we develop a model of multimedia
workloads that lets us isolate, vary, and explore the impact of key
system parameters and the potential impact of locality-awareness in
Kazaa. Our results reveal dramatic differences between P2P file
sharing and Web traffic. For example, we show how the immutability of
Kazaa's multimedia objects leads clients to fetch objects at most
once. This behavior and object immutability has significant
implications for the performance of multimedia file-sharing systems.
Unlike the Web, whose workload is driven by document change, we
demonstrate that clients' fetch-at-most-once behavior, the creation of
new objects, and the addition of new clients to the system are the
primary forces that drive multimedia workloads such as Kazaa.
In the second mini-talk, I present a recent measurement student of a
new Internet security threat: the spread of spyware. We examine four
spyware programs (Gator, Cydoor, SaveNow and eZula) for which we
derived signatures that can be used to detect their presence on remote
computers through passive network monitoring. Using these signatures,
we quantify the spread of spyware within the University of Washington.
In addition, we demonstrate correlations between certain measurable
behavior and the rate of spyware infections within populations.
Finally, we demonstrate a specific vulnerability within two of these
spyware programs, from which we derive implications about the impact
of spyware on the security of the Internet as a whole.
About the speaker: Steven D. Gribble joined the Computer Science and
Engineering Department of the University of Washington as an Assistant
Professor in November of 2000, after receiving his Ph.D. from UC
Berkeley under Professor Eric Brewer. Steve's research interests
include the design and operation of robust, scalable Internet
infrastructure and services, mobile computing, operating systems,
virtual machine monitors, and networks. He received his B.Sc. in
Computer Science and Physics from the University of British Columbia,
and his M.S. in Computer Science from UC Berkeley. He is an ACM and
USENIX member, and was a co-founder of ProxiNet, Inc. (now a division
of PumaTech). Steve originally hails from Vancouver, Canada. Steve is
a recipient of the Alfred P. Sloan Research Fellowship, as well as the
National Science Foundation CAREER Award. When not in front of a
computer, he loves to play the piano, or to spend his time outdoors
with sports such as triathlon and adventure racing.
____________
SRI AI SEMINAR SERIES
on Thursday, 4 March 2004, 4:00pm - 5:30pm
EJ228, SRI International
http://www.ai.sri.com/seminars/
"Applying Plan Recognition to Cyber Attacks"
Peter A Jarvis
Artificial Intelligence Center, SRI International
http://homepage.mac.com/peterajarvis/
We describe the application of plan recognition techniques to support
computer system administrators in processing cyber security alert sets
by automatically identifying the hostile intent behind them.
Identifying the intent enables us to both prioritize and explain the
clusters for succinct user presentation. Our empirical evaluation
demonstrates that the approach can handle alert sets of as many as 20
elements and can readily distinguish between false and true alert
sets. We discuss important opportunities for the future work that is
needed to increase the cardinality of the alert sets supported by the
system to the level needed by a deployable application. In particular
we outline opportunities to bring the analysts into the process and
the opportunities for heuristic improvements to the plan recognition
algorithm.
About the Speaker: Peter holds a PhD in Artificial Intelligence and a
first class BSc in Computer Science. His research interests center
around tool support for authoring and managing plans. He has worked in
domains as diverse as Air Campaign Planning (USAF) and Product
Innovation in the chemical industry (Unilever, ICI, BG
Technology). Today he is working on the Department of Defense (DARPA)
Active Templates Program to support command and control processes for
Special Operations Forces.
____________
PARC FORUM
on Thursday, 4 March 2004, 4:00pm - 5:00pm
George Pake Auditorium, PARC
http://www.parc.com/forum/
"Complexity and fragility with applications to Internet technology"
John Doyle
Electrical Engineering, BioEngineering, and Control and Dynamical Systems
CalTech
Many complex networks are robust yet fragile (RYF), exhibiting
remarkable robustness of their basic functionality despite large
perturbations in their environments and component parts, yet also
extreme fragility to cascading failure events triggered by relatively
small perturbations. Cancer, infectious diseases of humans, animals,
plants, and computer networks, auto-immunity, power outages, market
crashes, denial-of-service attacks, terrorist hijackings, etc., are
familiar examples of fragilities in complex systems. The entire
scientific enterprise of experimentation, modeling, and simulation of
complex systems has been most successful at studying their typical or
generic behaviors, but our experience of RYF systems in the real world
may be dominated by extremely rare events. While there are areas of
engineering that deal effectively with RYF systems, they are currently
more isolated and fragmented within narrow technical disciplines than
is desirable.
This talk will describe efforts to develop rigorous, systematic, and
general methods to study RYF systems, including a deep understanding
of the intrinsic sources of RYF. Complexity introduced to provide
robustness for some perturbations inevitable creates fragilities
elsewhere, which can lead to a complexity-fragility spiral. Scalable
inference algorithms will be developed to overcome the apparent
intractability of robustness analysis of models exhibiting RYF.
Analysis of RYF systems using standard discrete-event or continuous
simulation methodologies alone is inadequate because the systems can
be enormous, and simulation time for even simple models to get
statistical significance can be prohibitive. Thus both multiscale
models and robustness analysis tools that avoid wasting time in
simulation of benign scenarios are essential. Interaction with data
also has major challenges, typified by two extreme scenarios. In one,
methods of reasoning from sparse data about scenarios as yet untested
is needed, to both suggest targeted testing, but also to predict rare
events that may not be experimentally accessible. At the other
extreme, there can be overwhelming floods of data from which
signatures of anomalous events must be detected.
Automating and computationally augmenting scientific and mathematical
inference from noisy and incomplete data for uncertain models has long
been an elusive goal, but is necessary for the study of RYF.
Essentially all computational problems for detailed models in these
domains are apparently intractable, such as finding worst-case
behavior in a model, verifying the robustness of protocols, or proving
that some proposed model cannot explain observed data. Thus the
asymmetry between NP (where proofs are always short, though search may
be intractable) and coNP (where short proofs may not exist) is as
significant as the more familiar one between P (both search and proof
are easy) and NP. A key enabling insight is that complexity implies
fragility or more precisely dual complexity implies primal fragility.
Through a combination of mathematics from control theory, dynamical
systems, real algebraic geometry, and operator theory, computational
complexity can be directly connected with problem fragility in such a
way as to render robustness analysis and verification tractable.
A broad range of networks from many disciplines exhibit RYF features,
including terrestrial and aquatic ecosystems, the dynamics and impact
of forest fires, earthquakes, and other natural disasters. A main
motivation is from technological networks, but particularly those
involving ubiquitously embedded computer networks, and future
scenarios in which such networks control critical infrastructure. Here
there is tremendous potential for both efficient and robust nominal
operations and catastrophic cascading failure events, both from
malfunction and attack. The Internet itself, though familiar and
well-understood informally, still lacks a coherent theoretical
foundation. The aim in these diverse studies is to identify the common
structures contributing to the RYF behavior, and develop both simple
explanatory and detailed predictive models with associated analysis
tools. The preliminary progress already made is striking and has been
applied to understanding, for example, the robustness of complex
control systems, the performance of internet protocols, the dynamics
of forest fires, and bacterial chemotaxis and stress response. One
signature of RYF systems is power law statistics in event sizes. Power
laws are ubiquitous in natural and human systems, and are heavily
studied, yet remain a source of tremendous confusion and specious
theorizing in the scientific literature. A major aim of this work is
to resolve this confusion and broadly educate scientists, engineers,
and the public about the relevance and rigorous treatment of power law
statistics.
About the Speaker: John Doyle received his PhD in Mathematics from UC
Berkeley in 1984, and has been a Professor at Caltech since 1986,
where he is in the departments of Electrical Engineering,
BioEngineering, and Control and Dynamical Systems. His current
research interests are in theoretical foundations for complex networks
in engineering and biology, as well as multiscale physics and
financial markets, focusing on the interplay between robustness,
feedback, control, dynamical systems, computation, communications, and
statistical physics. The current application domains include Internet
protocols with provably robust theoretical features; theory and
software to support post-genomics research in complex biological
networks; and new theoretical tools for the study of nonequilibrium
statistical physics, turbulence, and quantum measurement and control.
John Doyle's early work was in the mathematics of robust optimal
control. He is the author of several books and of some of the most
widely used control software toolboxes for high performance commercial
and military aerospace systems, including Space Radiometer, F-16,
Shuttle Orbiter, electric power generation, distillation, catalytic
reactors, active suspension, and CD players. He has received almost
every major prize in control theory there is, including the IEEE Baker
(also ranked in the top 10 "most important" papers world-wide in pure
and applied mathematics from 1981-1993), the IEEE AC Transactions
Axelby, and IEEE Control Systems Field Award. Interestingly, he has
also held national and world records and championships in various
sports.
____________
BERKELEY INTERNATIONAL COMPUTER SCIENCE INSTITUTE
on Thursday, 4 March 2004, 4:00pm-5:00pm
Main Lecture Hall, ICSI, 1947 Center Street, Sixth Floor, Berkeley
http://www.icsi.berkeley.edu/talks/
"Research at FX Palo Alto Laboratory"
Candace Kamm
FX Palo Alto Laboratory
FX Palo Alto Laboratory was created in 1995 as a wholly-owned
subsidiary of Fuji-Xerox Corporation, to perform research in
information technology and to be an outpost of Fuji-Xerox (a Japanese
company) in Silicon Valley. This presentation will provide an overview
of the research themes at FXPAL, as well as describing in more detail
our work in multimedia processing and applications and the use of
large-display technology to foster community.
About the Speaker: Candy Kamm is Director of Research at FX Palo Alto
Laboratory. Prior to joining FXPAL in November 2002, she worked at
AT&T Labs Research, where she headed research departments in
Human-Computer Interaction and in Spoken Dialog Systems. Her personal
research at AT&T focused primarily on creating and evaluating user
interfaces for spoken dialog systems.
____________
SSP10: SYMBOLIC SYSTEMS FORUM
on Thursday, 4 March 2004, 4:15pm
Bldg. 380:380C (Math Corner)
http://symsys.stanford.edu:8081/ssp-dynamic/servlet/ssp_events
"In Search of Bloom's Missing Sigma"
Heather Pon-Barry
M.S. Candidate, Symbolic Systems Program, Stanford University
In 1984, Benjamin Bloom reported that students who interacted with
expert human tutors yielded test scores two standard deviations above
those who received ordinary classroom instruction. Since then, this "2
sigma" effect has been commonly used as the gold-standard for
measuring instructional effectiveness. Researchers in various fields
have been building intelligent tutoring systems (ITSs) for over three
decades--with a recent trend towards dialogue-based tutoring
systems--yet currently, the best ITSs report learning gains of only 1
standard deviation above classroom instruction. Naturally this leads
one to wonder, what happened to the second sigma? What is it that
expert human tutors do that makes their interaction so effective? At
CSLI, we have been developing the first Spoken Conversational Tutor
(SCoT) under the hypothesis that spoken dialogue might account for
(part of) Bloom's missing sigma. I have been exploring the idea that
certain features of the student's language can be used to help the
tutor present information at an appropriate level of granularity.
Adapting to their behavior in this way should make it easier for the
student to build a clear mental representation of what is being
discussed, and thus facilitate self-reflection. In this talk, I will
present the work I have been doing to test these hypotheses, and
describe how they have influenced the architecture of the tutorial
component I am designing.
____________
INFORMATION SYSTEMS SEMINAR
on Thursday, 4 March 2004, 4:15pm-5:15pm
Packard 101
http://isl.stanford.edu/groups/seminar/
"Cost-Distortion-Optimal Communication Via Measure-Matching:
Key Ideas And Application To Neural Communication"
Bixio Rimoldi
EPFL
We first review the classical source-channel communication problem
comparing and contrasting separation-based solutions with the
measure-matching approach. The idea of measure-matching (Gastpar,
Rimoldi, Vetterli, IEEE Trans. on Inform. Theory, May 2003) consists
in realizing that, ultimately, achieving a target rate-distortion
operating point is a matter of achieving a desired channel input
distribution and a desired joint distribution between the source and
the destination. The distributions that lead to a cost-distortion
operating point that cannot be improved have to satisfy
simple-to-describe conditions that involve the source and channel
statistic as well as the cost and distortion measures. Hence the name
measure-matching conditions. The separation principle is one way to
approach measure matching. Sometimes the source and the channel are
"almost" matched to begin with. Then, roughly speaking, the channel
code destroys the favorable channel statistic and the source code has
to do more work to ensure the proper measure matching. Latency is one
of the prices of working "against" rather than "with" the inherent
source and channel randomness. Of particular interest is when the
desired match is obtained by means of low-complexity small-latency
transmitter/receiver pairs such as those consisting of memoryless maps
or linear filters. One can make sure that this is the case if once has
some freedom in designing the source and/or the channel. Thinking that
Mother Nature may have this prerogative, we will conclude with some
thoughts on the optimality (or lack of it) of neural communications.
Based on joint work with M. Gastpar and M. Vetterli.
____________
COMPUTER SCIENCE TALK
on Friday, 5 March 2004, 11:00am
Gates 260
"Minimax Regret Methods for Decision Making
with Imprecise Utility Functions"
Craig Boutilier
Computer Science, University of Toronto
http://www.cs.toronto.edu/~cebly/
Preference elicitation is generally required when making or
recommending decisions on behalf of users whose utility function is
not known with certainty. Although one can engage in elicitation until
a utility function is perfectly known, in practice, this is
infeasible. Thus methods for decision making with imprecise utility
functions are needed.
We propose the use of minimax regret as an appropriate decision
criterion in this circumstance, providing the means for determining
robust decisions. We overview recent techniques we have developed for
minimax regret computation in several different settings, including
constraint-based configuration, distributed resource allocation and
(time permitting) mechanism design. We also describe how minimax
regret can be used to drive the process of eliciting preferences
itself.
____________
CS547: HUMAN-COMPUTER INTERACTION SEMINAR
on Friday, 5 March 2004, 12:30-2:00pm
Gates B03
http://www-pcd.stanford.edu/cs547/
"Privacy in the Age of Ubiquitous Computing"
Jason I. Hong
UC Berkeley Group for User Interface Research
In 1991, Mark Weiser described his vision of "Ubiquitous Computing", a
world in which computation and communication would be invisibly
enmeshed in all aspects of our everyday lives. Advances in sensors and
wireless networking are taking us closer towards this vision, enabling
us to gather and share information at unprecedented levels in
real-time. A simple example of this is E911, where 911 emergency calls
are augmented by the caller's current location. A more radical version
of ubiquitous computing was portrayed in the recent movie Minority
Report.
However, while there is great promise in terms of safety and
efficiency, there are numerous concerns about privacy in such a
world. In this talk, I outline some ongoing work in privacy and
ubiquitous computing that our research group has been
investigating. This includes surveys and interviews we have done to
understand the nature of people's concerns, some pitfalls we have
encountered in designing for privacy, and some applications we have
been developing that make it easier for people to manage their
personal privacy.
About the Speaker: Jason I. Hong is a Computer Science PhD student in
the Group for User Interface Research (GUIR) at the University of
California at Berkeley. His research interests are in Human-Computer
Interaction, specifically in sensor-based context-aware systems,
multimodal interaction enabling richer kinds of input and output,
information technology and privacy, and applications for streamlining
emergency response. He is also an author of the book The Design of
Sites, a pattern-based approach to designing customer-centered web
sites.
____________
LOGICAL METHODS IN THE HUMANITIES
on Friday, 5 March 2004, 3:15pm-5:15pm
Bldg. 90:92Q (Philosophy)
http://www-logic.stanford.edu/seminars.html
"Hobbes on Rigorous Demonstration: Theory Meets Practice"
Doug Jesseph
North Carolina
This paper investigates Hobbes's stated criteria for rigorous
demonstration and contrasts them with his mathematical practice, as
exemplified in various efforts at circle quadrature and failed
attempts to solve other notable problems. I argue that Hobbes was
misled into thinking that not only must every geometric problem must
be solvable, but also that he had hit upon a method that would deliver
quick and easy solutions to any geometric problem. The sources of this
mistake are to be found in Hobbes's methodological doctrine that all
proper geometric demonstrations must proceed from causes, together
with his belief that his own program for geometry was based upon
definitions that adequately expressed geometric causes and thus
offered the prospect of solving every problem. I also argue that
Hobbes's repeated and emphatic rejection of analytic geometry is a
consequence of his belief that analytic techniques are essentially
arithmetical rather than geometrical, and are consequently irrelevant
to the solution of purely geometric problems.
____________
NLP READING GROUP
on Friday, 5 March 2004, 2:0pm - 3:20pm
Ventura 17
http://www-nlp.stanford.edu/nlp/nlpgroup.html
"Predicate-argument structure from broad-coverage parse trees:
Improving on the context-free approximation"
Roger Levy
Linguistics, Stanford
We present a linguistically-motivated algorithm for reconstructing
nonlocal dependency in broad-coverage context-free parse trees derived
from treebanks. Contemporary broad-coverage treebanks contain a rich
set of non-local dependency annotations that are generally ignored in
probabilistic parsing work. We use an algorithm based on loglinear
classifiers trained on this data to augment and reshape context-free
trees so as to reintroduce underlying nonlocal dependencies lost in
the context-free approximation. We find that our algorithm performs
comparably with prior work on English using an existing evaluation
metric, and also introduce and argue for a new dependency-based
evaluation metric. We compare performance on gold-standard and
machine-parsed sentences in both English and German with this new
metric, also finding good performance for our algorithm, and are able
to quantitatively corroborate the intuition that in a language with
freer word order, the surface dependencies in context-free parse trees
are a poorer approximation to underlying dependency structure, and
that the problem of correcting this approximation post-hoc seems to be
harder.
____________
CS545: DATABASE SEMINAR
on Friday, 5 March 2004, 4:15pm - 5:30pm
Gates B12
http://www-db.stanford.edu/dbseminar/
"Processing Life Science Data using Scalable Database Technology"
Christoph Freytag
Humboldt University Berlin
This talk provides an overview of our (DBIS) research work in the area
of Genomics (Life Science), one of the most challenging areas for
computer science and database systems. Based on the current technology
we describe some of the challenges that we try to tackle using
scalable database technology.
First, we discuss some of fundamental problems that arise when
integrating, storing, and accessing genomic data in an ORDBMS. The
genomics view differs in several aspects compared to the database
view. Based on our observations and our experience with real users we
describe our approach to data integration by suggesting a processing
framework that encompasses flexibility and extensibility.
Second, we show that existing approaches to data cleansing have very
little success in the area of life science. I show how to identify
inconsistencies and errors in life science data before trying to
correct them, if possible.
Third, we focus on one of the major algorithms for similarity search
and discuss its alternatives for integration it into a database
oriented processing environment.
Finally, based on cooperation with life scientists I use a challenging
problem from the area of genetics (alternative splicing), to show how
to support complex data processing using data base technology both on
the data and metadata level.
About the Speaker: Johann-Christoph Freytag is currently full
professor for databases and information systems at the Computer
Science Department of the Humboldt-Universitaet zu Berlin,
Germany. Before joining the department in 1994 he was a research staff
member at the IBM Almaden Research Center (1985-1987), a researcher at
the European Computer-Industry-Research Centre (ECRC, in Munich,
Germany, 1987-1989), and the head of Digital's Database Technology
Center (also in Munich, 1990-1993). He holds a Ph.D. from Harvard
University.
Dr. Freytag's research interests include all aspects of query
processing and query optimization in object-relational database
systems, new developments in the database area (such as semistructured
data, data quality, databases and security), and applying database
technology to applications such as GIS, genomics, and
bioinformatics/life science. In the last years he received the IBM
Faculty Award 4 times for collaborative work in the areas of
databases, middleware, and bioinformatics/life science.
____________
INFORMATION SYSTEMS SEMINAR
on Monday, 8 March 2004, 1:00pm-2:00pm
Packard 101
http://isl.stanford.edu/groups/seminar/
"Connections between Estimation Theory and Information Theory"
Sergio Verdu
Princeton University
For signals observed in Gaussian noise, we show a relationship between
the input-output mutual information and the minimum mean-square error
(MMSE) achievable by the optimal estimator of the input. This
relationship holds for arbitrarily distributed scalar and vector
signals, as well as for discrete-time and continuous-time noncausal
MMSE estimation (smoothing). Using these information theoretic
results we show a new result in continuous-time nonlinear filtering
which couples the signal-to-noise ratios achievable by smoothing and
filtering.
I will also show several instances of problems where MMSE structures
play a key role in capacity-achieving receivers.
Joint work with D. Guo and S. Shamai.
____________
CENTER FOR INTERNET AND SOCIETY TALK
on Monday, 8 March 2004, 5:45pm-7:00pm
Law School 290
http://cyberlaw.stanford.edu/
jointly with The Center for Ethics (CE)
"The Ethics of P2P Filesharing"
Larry Lessig and Deborah Rhode
Stanford Law School
When a technology's integration into society outpaces the laws that
govern it, the boundary between lawful and unlawful behavior can blur.
Nowhere is this observation more prevalent than in the maelstrom of
debate surrounding the peer-to-peer technologies that allow users to
download and trade music with an ease and immediacy never before
available. This panel will discuss whether downloading music without
paying for it is civil disobedience, fair use, or just plain wrong.
The Speakers will use excerpts from an episode of the new docu-drama
"K Street" as a springboard for addressing questions like:
*Are all downloaders pirates?
*Does the legality matter? Or, Even if it's legal, is it ethical?
*Do downloaders have an ethical obligation to investigate the
legality of what they're doing?
*Does it matter that everyone is doing it?
*Does it matter if the shared content is not lawfully available elsewhere?
*Should advocates for changes in the law advocate breaking the law?
____________
LINGUISTICS DEPARTMENT COLLOQUIUM
on Tuesday, 9 March 2004, 12 noon
Margaret Jacks Hall, Room 460:126
http://www-linguistics.stanford.edu/colloq/
"The Interpretive Loop: Uninterpretable Candidates
and the Phonology-Phonetics Interface"
Paul de Lacy
Cambridge University
This talk focuses on the status of phonetically uninterpretable output
forms in phonological theory. Examples of uninterpretable forms are
structures with a [+high,+low] vowel, crossed autosegmental
association lines, and so on.
This talk aims to show that uninterpretable forms present a conundrum
for phonological theory. On the one hand, there are conceptual
arguments that support the claim that they are produced by the
Phonological component. On the other hand, I will argue that if
uninterpretable forms are produced by the Phonological component they
would prevent many attested phonological processes from happening. In
short, there are reasons for both accepting and rejecting the claim
that the Phonology generates uninterpretable forms.
To resolve this conflict, I present a mechanism whereby the
Interpretive component (i.e. 'Phonetics') is persistent in its search
for an interpretable form. In other words, an uninterpretable output
emitted by the Phonology does not spell doom -- the derivation
proceeds until an interpretable form is found. The applicability of
this proposal to both Optimality Theory and serialist
(i.e. derivational rule-based) theories will be discussed.
____________
CS/EE SEMINAR
on Tuesday, 9 March 2004, 3:00pm
Gates 104
"Distributed Hash Tables for Networked Systems"
Sylvia Ratnasamy
Intel Research
A DHT is a distributed system that provides hash table functionality
-- mapping "keys" to "values" -- on Internet-like scales. DHTs had an
ignoble origin, being first proposed as scalable replacements for
Napster and Gnutella, but are now seen as a much more general tool for
building large, robust, networked systems. For example, in the three
years since they were first introduced, DHTs have been applied to
areas such as: storage services (e.g., OceanStore), distributed query
processing (e.g., PIER), communication services (e.g., scalable
multicast, anycast) and Internet architecture (e.g., realizing the
long sought split between routing and addressing). More recently, DHTs
have been applied to sensor networks. By enabling their intelligent
in-network storage, DHTs allow sensed events to be efficiently located
and extracted from a sensor network.
There is one basic operation in a DHT system, "lookup (key)", which
returns the identity (e.g., the IP address) of the node storing the
object with that key. The challenge in building a DHT is to
efficiently support this operation in systems with millions of nodes
that join and leave the system at will. In this talk, I will describe
how we build DHTs (on both the Internet and on sensor networks) to
meet these challenges.
About the Speaker: Sylvia Ratnasamy received her Ph.D. in computer
science from U.C.Berkeley in 2002. As a Ph.D. student, Sylvia also
worked at the ICSI Center for Internet Research (formerly ACIRI). She
is currently on the research staff at the Intel Research Laboratory in
Berkeley. Her research interests lie in the area of networked systems.
____________
BERKELEY COGNITIVE SCIENCE TALK
on Tuesday, 9 March 2004, 5:00pm
2050 VLSB, UC Berkeley campus
(The Chan Shun Auditorium in the Valley Life Sciences Building)
http://psychology.berkeley.edu/admin/colloquia.html
Jointly sponsored by the Program in Cognitive Science and the
Department of Linguistics. Professor Magnuson is a candidate for the
faculty position in Cognition and Language.
"Interaction in language processing:
Pragmatic constraints on lexical access"
James Magnuson
Psychology, Columbia University
Everyday language use is rich and textured. Conventional
psycholinguistic laboratory tasks abstract away from natural
complexity in order to isolate information relevant at different
levels of linguistic description. Such simplifications reduce language
use to smaller, tractable problems, and allow fine-grained
chronometric processing measures. I argue that this approach
paradoxically overestimates the complexity and modularity of language
processing, as natural contexts provide layers of constraints that
reduce the burden on bottom-up and within-level processing. I will
address two primary issues. The first is how we can study language in
naturalistic contexts without sacrificing fine-grained measures and
precise stimulus control. I will describe an eye tracking measure that
is closely time-locked to spoken instructions in naturalistic tasks
and that can be transparently linked to computational models, and an
artificial lexicon paradigm that provides precise control over lexical
characteristics. I will discuss how we have used both techniques to
address debates in adult and developmental word recognition. The
second issue is whether lexical access - a process typically assumed
to be encapsulated from higher levels of linguistic representation -
is constrained by pragmatic context. Subjects learned to recognize an
artificial lexicon of names of novel objects ("nouns") and textures
that could be applied to them ("adjectives"). Each word had
phonological competitors in both form classes. We compared competition
effects given visual displays that required adjective use or made
adjectives infelicitous. Consistent with the hypothesis that language
processing makes use of reliable contextual constraints, we found an
immediate impact of pragmatic visual cues: similar-sounding words
competed when they were from the same class, but not when they were
from different classes. This result adds to growing evidence that
language processing is highly interactive, and the approach provides a
foundation for the development of integrated theories of language use
in natural contexts.
____________
CSLI COGLUNCH
on Thursday, 11 March 2004, 12:15pm-1:30pm
Cordura Hall, Room 100
http://www-csli.stanford.edu/events/Coglunch/
"The Role of Information Scent in Information Foraging on the Web"
Peter Pirolli
PARC
The Web can be viewed as a probabilistically textured environment in
which users have to use local cues (graphical icons; link summaries)
to make navigation choices in order to get to desired information. A
rational analysis of this problem has lead to the development of
computational cognitive model of users seeking information on the Web
that simulates user data from a variety of experimental studies.
About the Speaker: Peter Pirolli is Principal Scientist in the User
Interface Research Area at the Palo Alto Research Center (PARC).
____________
SSP10: SYMBOLIC SYSTEMS FORUM
on Thursday, 11 March 2004, 4:15pm
Bldg. 380:380C (Math Corner)
http://symsys.stanford.edu:8081/ssp-dynamic/servlet/ssp_events
"The dative alternation and the meaning of variation:
Is variation at the level of syntax determined by semantic differences?"
Joan Bresnan
Linguistics Department
In the linguistics literature it is now almost universally agreed that
semantics determines syntactic choices, and in a particularly visible
way with the two dative constructions of English. Yet recent corpus
work shows that the widely reported evidence for subtle semantic
differences in these constructions is flawed. An alternative view is
that the choice of constructions is influenced by the need to
differentiate the receiver and entity arguments along dimensions such
as nominal expression type, animacy, person, definiteness,
accessability, and length. These properties are only indirectly
influenced by verbal semantics; they primarily reflect actual
usage. An informational approach to the dative alternation
incorporating this idea can be extended to explain quantitative
lexical variation (cf. Gries and Stefanowitsch to appear), as shown by
ongoing research with Anna Cueni and Tatiana Nikitina.
____________
CS547: HUMAN-COMPUTER INTERACTION SEMINAR
on Friday, 12 March 2004, 12:30-2:00pm
Gates B03
http://www-pcd.stanford.edu/cs547/
"Interactive Entertainment:
Sharing Control Between Authors and Participants"
Randy Pausch
Carnegie Mellon Univ., Entertainment Technology Center
(Currently on Sabbatical at Electronic Arts in the Bay Area)
New forms of entertainment, training, and education are now possible
due to advances in digital technology. Carnegie Mellon has created the
Entertainment Technology Center (ETC) [ http://etc.cmu.edu/ ], a joint
initiative between the School of Computer Science and the College of
Fine Arts. The ETC grants a two-year "Masters of Entertainment
Technology" degree. We have seventy students in our Masters program;
half are artists and half are technologists. Students from the ETC
have been hired by companies such as Electronic Arts, Rockstar
Studios, Industrial Light & Magic (ILM), Microsoft, MERL, PIXAR, Walt
Disney Imagineering, etc. In addition to video games and other
traditional entertainment forms, our students go on to create museum
installations, WWW sites, and other novel interactive experiences.
A fundamental intellectual challenge of the ETC is finding ways to
share control between content authors and the
audiences/users/players/guests of that content. A fundamental social
challenge of the ETC is finding ways to get artists and technologists
to work together. ETC students are continuously involved in project
courses, where teams of four or five students from different
backgrounds work closely under faculty guidance to create a
technology-enhanced entertainment experience. A typical project might
be to create an interactive theatrical piece, a robot who can sustain
conversation, or a small scale educational video game.
This talk will describe what we believe is important in educating
students for the entertainment industry, and how we do it. We will
describe typical ETC student projects, including work in the "Building
Virtual Worlds" course, where student teams build interactive,
helmet-based virtual reality worlds on a two-week production
schedule. We will also describe the lessons we have learned in how to
most effectively put artists and technologists together into small
teams that succeed.
Professor Pausch is currently on Sabbatical at Electronic Arts (EA)
and may have a few words to say about that culture, as well.
About the Speaker: Randy Pausch is a Professor of Computer Science,
Human-Computer Interaction, and Design at Carnegie Mellon, where he is
the co-director of CMU's Entertainment Technology Center (ETC). He was
a National Science Foundation Presidential Young Investigator and a
Lilly Foundation Teaching Fellow. He has consulted with Walt Disney
Imagineering on the user interface design and testing of interactive
theme park attractions, and with Google on user interface design. He
is currently on Sabbatical at Electronic Arts (EA). Dr. Pausch is the
author or co-author of five books and over 50 reviewed journal and
conference proceedings articles, and he is the director of the Alice
project which lowers the barriers to learning how to program
( http://www.alice.org/ ).
____________
CS545: DATABASE SEMINAR
on Friday, 12 March 2004, 4:15pm - 5:30pm
Gates B12
http://www-db.stanford.edu/dbseminar/
"Tracing the Provenance and Flow of Data"
Wang-Chiew Tan
U.C. Santa Cruz
http://www.soe.ucsc.edu/~wctan/
In this talk, I shall describe an annotation management system that
can be used to "eagerly" trace the provenance (i.e. origins) or flow
of a piece of data. In this system, every piece of data is assumed to
have one or more annotations attached to it. As data is being
transformed, e.g., through a query, the relevant annotations are
automatically propagated along. This system also has potential
applications in other areas such as markup of data and quality
control.
We show that optimizing a query in such an annotation management
system can be rather different from traditional query optimizations:
Two queries that are considered to be equivalent by a traditional
query optimizer may not be annotation-equivalent (i.e. generate the
same annotated outcome) in general. Despite this, we show that the
same annotated result is obtained whether intermediate constructs of a
query are evaluated with set or bag semantics. We also give a
necessary and sufficient condition, via homomorphisms, that checks
whether a query is annotation-contained in another. Even though our
characterization suggests that annotation-containment is more complex
than query containment, we show that the annotation-containment
problem is NP-complete, thus putting it in the same complexity class
as query containment. In addition, we show that the annotation
placement problem, which was first shown to be NP-hard, is in fact
DP-hard and the exact complexity of this problem still remains open.
About the Speaker: Wang-Chiew Tan is an assistant professor in the
Computer Science Department at UC Santa Cruz. She received her PhD
from the University of Pennsylvania in 2002. Her research interests
include data provenance, information integration, and database query
languages.
____________
END MATERIAL
The CSLI Calendar appears weekly on Wednesdays throughout the academic
year. Announcements, abstracts, and other information to appear in
the Calendar should be submitted to the editor, who reserves the right
to decide what does or does not go in the calendar
mailto:incalendar@csli.stanford.edu
Requests to be added to the mailing list should be sent to
majordomo@csli.stanford.edu. With the lines in the body of the text
of either
subscribe csli-calendar
for the long form or
subscribe csli-short-calendar
for the short form (i.e., no abstracts). Problems with subscribing or
unsubscribing should be sent to
owner-csli-calendar@csli.stanford.edu.
The full current issue is at
http://www-csli.stanford.edu/Archive/calendar/current.shtml
and the archives at
http://www-csli.stanford.edu/Archive/calendar/
People on most of the CSLI computers can type 'help csli-calendar' to
see the current issue.
The CSLI Calendar is also posted each week to
news://nntp-csli.stanford.edu/csli.bboard.
and
news://news.stanford.edu/su.events
Information about CSLI's research program is available at
http://www-csli.stanford.edu/
For maps to the Stanford University campus see
http://www.stanford.edu/home/visitors/maps.html
____________