bluuebunny/crossref_metadata_2025 huggingface dataset:
Animation of computer networking concepts
Authors: Holliday Mark A.
Published: July 2004

A number of the key concepts in the design of computer networks lend themselves to illustration through animation. Animation can make the main features of these concepts accessible to the beginning undergraduate student as well as to more advanced students. We have identified six of these networking concepts: packet encapsulation; packet fragmentation; error control; media access in Ethernet local-area networks; domain name resolution; and the hypertext transfer protocol. We developed Java applets and accompanying materials to illustrate four of these concepts. The applets serve two roles: one role as a visual representation of different scenarios with respect to the concept in question; the second role as a vehicle for experimentation. We discuss the applets, the sequence of points each applet is designed to convey, and how the user can conduct experiments to further understand the networking concept. For the other two concepts, we show how the student can use free, easily available software to observe how the concept is implemented in the Internet.
It's not what you say, it's how you say it
Authors: Schindler Esther
Published: July 2004

Increasingly, researchers are finding a correlation between word usage and underlying human behavior. How's that going to affect our lives online?
A study of smoothing methods for language models applied to information retrieval
Authors: Zhai Chengxiang , Lafferty John
Published: July 2004

Language modeling approaches to information retrieval are attractive and promising because they connect the problem of retrieval with that of language model estimation, which has been studied extensively in other application areas such as speech recognition. The basic idea of these approaches is to estimate a language model for each document, and to then rank documents by the likelihood of the query according to the estimated language model. A central issue in language model estimation is
smoothing
, the problem of adjusting the maximum likelihood estimator to compensate for data sparseness. In this article, we study the problem of language model smoothing and its influence on retrieval performance. We examine the sensitivity of retrieval performance to the smoothing parameters and compare several popular smoothing methods on different test collections. Experimental results show that not only is the retrieval performance generally sensitive to the smoothing parameters, but also the sensitivity pattern is affected by the query type, with performance being more sensitive to smoothing for verbose queries than for keyword queries. Verbose queries also generally require more aggressive smoothing to achieve optimal performance. This suggests that smoothing plays two different role---to make the estimated document language model more accurate and to "explain" the noninformative words in the query. In order to decouple these two distinct roles of smoothing, we propose a two-stage smoothing strategy, which yields better sensitivity patterns and facilitates the setting of smoothing parameters automatically. We further propose methods for estimating the smoothing parameters automatically. Evaluation on five different databases and four types of queries indicates that the two-stage smoothing method with the proposed parameter estimation methods consistently gives retrieval performance that is close to---or better than---the best results achieved using a single smoothing method and exhaustive parameter search on the test data.
Multidocument summarization
Authors: Maña-López Manuel J. , De Buenaga Manuel , Gómez-Hidalgo José M.
Published: July 2004

A more and more generalized problem in effective information access is the presence in the same corpus of multiple documents that contain similar information. Generally, users may be interested in locating, for a topic addressed by a group of similar documents, one or several particular aspects. This kind of task, called instance or aspectual retrieval, has been explored in several TREC Interactive Tracks. In this article, we propose in addition to the classification capacity of clustering techniques, the possibility of offering a indicative extract about the contents of several sources by means of multidocument summarization techniques. Two kinds of summaries are provided. The first one covers the similarities of each cluster of documents retrieved. The second one shows the particularities of each document with respect to the common topic in the cluster. The document multitopic structure has been used in order to determine similarities and differences of topics in the cluster of documents. The system is independent of document domain and genre. An evaluation of the proposed system with users proves significant improvements in effectiveness. The results of previous experiments that have compared clustering algorithms are also reported.
Anchor text mining for translation of Web queries
Authors: Lu Wen-Hsiang , Chien Lee-Feng , Lee Hsi-Jian
Published: July 2004

To discover translation knowledge in diverse data resources on the Web, this article proposes an effective approach to finding translation equivalents of query terms and constructing multilingual lexicons through the mining of Web anchor texts and link structures. Although Web anchor texts are wide-scoped hypertext resources, not every particular pair of languages contains sufficient anchor texts for effective extraction of translations for Web queries. For more generalized applications, the approach is designed based on a transitive translation model. The translation equivalents of a query term can be extracted via its translation in an intermediate language. To reduce interference from translation errors, the approach further integrates a competitive linking algorithm into the process of determining the most probable translation. A series of experiments has been conducted, including performance tests on term translation extraction, cross-language information retrieval, and translation suggestions for practical Web search services, respectively. The obtained experimental results have shown that the proposed approach is effective in extracting translations of unknown queries, is easy to combine with the probabilistic retrieval model to improve the cross-language retrieval performance, and is very useful when the considered language pairs lack a sufficient number of anchor texts. Based on the approach, an experimental system called LiveTrans has been developed for English--Chinese cross-language Web search.
XIRQL
Authors: Fuhr Norbert , Groβjohann Kai
Published: July 2004

XIRQL ("circle") is an XML query language that incorporates imprecision and vagueness for both structural and content-oriented query conditions. The corresponding uncertainty is handled by a consistent probabilistic model. The core features of XIRQL are (1) document ranking based on index term weighting, (2) specificity-oriented search for retrieving the most relevant parts of documents, (3) datatypes with vague predicates for dealing with specific types of content and (4) structural vagueness for vague interpretation of structural query conditions. A XIRQL database may contain several classes of documents, where all documents in a class conform to the same DTD; links between documents also are supported. XIRQL queries are translated into a path algebra, which can be processed by our HyREX retrieval engine.
Use of nested certificates for efficient, dynamic, and trust preserving public key infrastructure
Authors: Levi Albert , Caglayan M. Ufuk , Koc Cetin K.
Published: July 2004

Certification is a common mechanism for authentic public key distribution. In order to obtain a public key, verifiers need to extract a certificate path from a network of certificates, which is called public key infrastructure (PKI), and verify the certificates on this path recursively. This is classical methodology. Nested certification is a novel methodology for efficient certificate path verification. Basic idea is to issue special certificates (called nested certificates) for other certificates. Nested certificates can be used together with classical certificates in PKIs. Such a PKI, which is called nested certificate-based PKI (NPKI), is proposed in this paper as an alternative to classical PKI. The concept of "certificates for other certificates" results in nested certificate paths in which the first certificate is verified cryptographically while others are verified by just fast hash computations. Thus, we can employ efficiently verifiable nested certificate paths instead of classical certificate paths. NPKI is a dynamic system and involves several authorities in order to add a new user to the system. This uses the authorities' idle time to the benefit of the verifiers. We formulate the trade-off between the nested certification overhead and the time improvement on certificate path verification. This trade-off is numerically analyzed for a 4-level 20-ary balanced tree-shaped PKI and it has been shown that the extra cost of nested certification is in acceptable limits in order to generate quickly verifiable certificate paths for certain applications. Moreover, PKI-to-NPKI transition preserves the existing hierarchy and trust relationships in the PKI, so that it can be used for PKIs with fixed topology. Although there are many certificates in NPKI, certificate revocation is no more of a problem than with classical PKIs. NPKI even has an advantage on the number of certificate revocation controls: at most two certificate revocation controls are sufficient independent of the path length. Nested certificates can be easily adopted into X.509 standard certificate structure. Both verification efficiency and revocation advantage of NPKI and nested certificates make them suitable for hierarchical PKIs of wireless applications where wireless end users have limited processing power.
Tree-based group key agreement
Authors: Kim Yongdae , Perrig Adrian , Tsudik Gene
Published: July 2004

Secure and reliable group communication is an active area of research. Its popularity is fueled by the growing importance of group-oriented and collaborative applications. The central research challenge is secure and efficient group key management. While centralized methods are often appropriate for key distribution in large multicast-style groups, many collaborative group settings require distributed key agreement techniques. This work investigates a novel group key agreement approach which blends key trees with Diffie--Hellman key exchange. It yields a secure protocol suite called Tree-based Group Diffie--Hellman (TGDH) that is both simple and fault-tolerant. Moreover, the efficiency of TGDH appreciably surpasses that of prior art.
Crypto-based identifiers (CBIDs)
Authors: Montenegro Gabriel , Castelluccia Claude
Published: July 2004

This paper addresses the identifier ownership problem. It does so by using characteristics of Statistical Uniqueness and Cryptographic Verifiability (SUCV) of certain entities which this document calls SUCV Identifiers and Addresses, or, alternatively, Crypto-based Identifiers. Their characteristics allow them to severely limit certain classes of denial-of-service attacks and hijacking attacks. SUCV addresses are particularly applicable to solve the address ownership problem that hinders mechanisms like Binding Updates in Mobile IPv6.
The UCONABCusage control model
Authors: Park Jaehong , Sandhu Ravi
Published: July 2004

In this paper, we introduce the family of UCONABCmodels for usage control (UCON), which integrateAuthorizations (A), oBligations (B), and Conditions (C). We call these core models because they address the essence of UCON, leaving administration, delegation, and other important but second-order issues for later work. The term usage control is a generalization of access control to cover authorizations, obligations, conditions, continuity (ongoing controls), and mutability. Traditionally, access control has dealt only with authorization decisions on users' access to target resources. Obligations are requirements that have to be fulfilled by obligation subjects for allowing access. Conditions are subject and object independent environmental or system requirements that have to be satisfied for access. In today's highly dynamic, distributed environment, obligations and conditions are also crucialdecision factorsfor richer and finer controls on usage of digital resources. Although they have been discussed occasionally in recent literature, most authors have been motivated from specific target problems and thereby limited in their approaches. The UCONABCmodel integrates these diverse concepts in a unified framework. Traditional authorization decisions are generally made at the time of requests but hardly recognizeongoing controlsfor relatively long-lived access or for immediate revocation. Moreover,mutabilityissues that deal with updates on related subject or object attributes as a consequence of access have not been systematically studied.Unlike other studies that have targeted on specific problems or issues, the UCONABCmodel seeks to enrich and refine the access control discipline in its definition and scope. UCONABCcovers traditional access controls such as mandatory, discretionary, and role-based access control. Digital rights management and other modern access controls are also covered. UCONABClays the foundation for next generation access controls that are required for today's real-world information and systems security. This paper articulates the core of this new area of UCON and develops several detailed models.
A federated approach to distributed network simulation
Authors: Riley George F. , Ammar Mostafa H. , Fujimoto Richard M. , Park Alfred , Perumalla Kalyan , Xu Donghua
Published: July 2004

We describe an approach and our experiences in applying federated simulation techniques to create large-scale parallel simulations of computer networks. Using the federated approach, the topology and the protocol stack of the simulated network is partitioned into a number of submodels, and a simulation process is instantiated for each one. Runtime infrastructure software provides services for interprocess communication and synchronization (time management). We first describe issues that arise in
homogeneous
federations where a sequential simulator is federated with itself to realize a parallel implementation. We then describe additional issues that must be addressed in
heterogeneous
federations composed of different network simulation packages, and describe a
dynamic simulation backplane
mechanism that facilitates interoperability among
different
network simulators. Specifically, the
dynamic simulation backplane
provides a means of addressing key issues that arise in federating different network simulators: differing packet representations, incomplete implementations of network protocol models, and differing levels of detail among the simulation processes. We discuss two different methods for using the backplane for interactions between heterogeneous simulators: the
cross-protocol stack
method and the
split-protocol stack
method. Finally, results from an experimental study are presented for both the homogeneous and heterogeneous cases that provide evidence of the scalability of our federated approach on two moderately sized computing clusters. Two different homogeneous implementations are described:
Parallel/Distributed ns
(
pdns
) and the
Georgia Tech Network Simulator
(
GTNetS
). Results of a heterogeneous implementation federating
ns
with
GloMoSim
are described. This research demonstrates that federated simulations are a viable approach to realizing efficient parallel network simulation tools.
Network simulation enhancing network management in real-time
Authors: Warren Gary , Nolte Ronald , Funk Ken , Merrell Brian
Published: July 2004

This research investigates the application of network simulation to enhance network management in real-time. Its focus is on ad hoc wireless networks as needed for future public safety emergency response, homeland security, and future combat system networks where the network requirements and topology are rapidly changing. The network simulation is used to analyze user satisfaction with the network and to enable real-time what-if studies that show what the user satisfaction will be if the network is reconfigured in various ways. User satisfaction as a metric is defined to correspond to the impact of the network performance on the ability of the network user to complete their public safety, security or military functions. The current network size of interest is up to ad hoc wireless 500 nodes, a typical target load for a single network manager. At the same time, the approach is made scalable to use manager of managers approach to scale to larger networks. The article reports on the approach and performance results.
Can e-learning replace classroom learning?
Authors: Zhang Dongsong , Zhao J. Leon , Zhou Lina , Nunamaker Jay F.
Published: July 2004

In an e-learning environment that emphasizes learner-centered activity and system interactivity, remote learners can outperform traditional classroom students.
Improving software team productivity
Authors: Chiang I. Robert , Mookerjee Vijay S.
Published: July 2004

Choosing the most effective quantitative process design approach will not only improve a firm's project management but, ultimately, the bottom line.
Tracing the roots of markup languages
Authors: Toshniwal Rishi , Agrawal Dharma P.
Published: July 2004

Markup languages provide efficient ways of storing information on the Web and make the retrieval process easier. Indeed, its simplicity and added intelligence to the document makes it useful for messaging between clients and server.
Wanted
Authors: Grove Jeff
Published: July 2004

Don't enact laws and regulations that prevent or inhibit access to the facts and ideas needed for scientific research.
Success and failure in Web-based financial services
Authors: Dandapani Krishnan
Published: July 2004

Examining the financial viability of the underlying business model.
Mobile banking services
Authors: Mallat Niina , Rossi Matti , Tuunainen Virpi Kristiina
Published: July 2004

Adopting new and innovative mobile financial applications and service provisioning methods.
User-experience planning for corporate success
Authors: Marcus Aaron
Published: July 2004

Good news for the CHI community: Behind the scenes, corporations are re-organizing to achieve user-centered products and services.
Are you positive?
Authors: Sklar Aaron , Gilmore David
Published: July 2004

When someone says "design evaluation," what comes to your mind? I'll bet that, like me, you probably think first of the process of identifying a design's flaws and inadequacies. David Gilmore and Aaron Sklar think otherwise. Calling on us to take inspiration from a recent movement in psychology, David and Aaron urge the usability profession to adopt a positive attitude, to enlarge our focus from problem sniffing to a broader scope that includes appreciating design goodness where it already exists.---
Elizabeth Buie
Managing battery lifetime with energy-aware adaptation
Authors: Flinn Jason , Satyanarayanan M.
Published: July 2004

We demonstrate that a collaborative relationship between the operating system and applications can be used to meet user-specified goals for battery duration. We first describe a novel profiling-based approach for accurately measuring application and system energy consumption. We then show how applications can dynamically modify their behavior to conserve energy. We extend the Linux operating system to yield battery lifetimes of user-specified duration. By monitoring energy supply and demand and by maintaining a history of application energy use, the approach can dynamically balance energy conservation and application quality. Our evaluation shows that this approach can meet goals that extend battery life by as much as 30%.
Coupling compiler-enabled and conventional memory accessing for energy efficiency
Authors: Ashok Raksit , Chheda Saurabh , Moritz Csaba Andras
Published: July 2004

This article presents Cool-Mem, a family of memory system architectures that integrate conventional memory system mechanisms, energy-aware address translation, and compiler-enabled cache disambiguation techniques, to reduce energy consumption in general-purpose architectures. The solutions provided in this article leverage on interlayer tradeoffs between architecture, compiler, and operating system layers. Cool-Mem achieves power reduction by statically matching memory operations with energy-efficient cache and virtual memory access mechanisms. It combines statically speculative cache access modes, a dynamic content addressable memory-based (CAM-based) Tag-Cache used as backup for statically mispredicted accesses, different conventional multilevel associative cache organizations, embedded protection checking along all cache access mechanisms, as well as architectural organizations to reduce the power consumed by address translation in virtual memory. Because it is based on speculative static information, a superset of the predictable program information available at compile-time, our approach removes the burden of provable correctness in compiler analysis passes that extract static information. This makes Cool-Mem highly practical, applicable for large and complex applications, without having any limitations due to complexity issues in our compiler passes or the presence of precompiled static libraries. Based on extensive evaluation, for both SPEC2000 and Mediabench applications, we obtain from 6% to 19% total energy savings in the processor, with performance ranging from 1.5% degradation to 6% improvement, for the applications studied. We have also compared Cool-Mem to several prior arts and have found Cool-Mem to perform better in almost all cases.
A general framework for prefetch scheduling in linked data structures and its application to multi-chain prefetching
Authors: Choi Seungryul , Kohout Nicholas , Pamnani Sumit , Kim Dongkeun , Yeung Donald
Published: July 2004

Pointer-chasing applications tend to traverse composite data structures consisting of multiple independent pointer chains. While the traversal of any single pointer chain leads to the serialization of memory operations, the traversal of independent pointer chains provides a source of memory parallelism. This article investigates exploiting such
interchain memory parallelism
for the purpose of memory latency tolerance, using a technique called
multi--chain prefetching
. Previous works [Roth et al. 1998;Roth and Sohi 1999] have proposed prefetching simple pointer-based structures in a multi--chain fashion. However, our work enables multi--chain prefetching for arbitrary data structures composed of lists, trees, and arrays.This article makes five contributions in the context of multi--chain prefetching. First, we introduce a framework for compactly describing linked data structure (LDS) traversals, providing the data layout and traversal code work information necessary for prefetching. Second, we present an off-line scheduling algorithm for computing a prefetch schedule from the LDS descriptors that overlaps serialized cache misses across separate pointer-chain traversals. Our analysis focuses on static traversals. We also propose using speculation to identify independent pointer chains in dynamic traversals. Third, we propose a hardware prefetch engine that traverses pointer-based data structures and overlaps multiple pointer chains according to the computed prefetch schedule. Fourth, we present a compiler that extracts LDS descriptors via static analysis of the application source code, thus automating multi--chain prefetching. Finally, we conduct an experimental evaluation of compiler-instrumented multi--chain prefetching and compare it against jump pointer prefetching [Luk and Mowry 1996], prefetch arrays [Karlsson et al. 2000], and predictor-directed stream buffers (PSB) [Sherwood et al. 2000].Our results show compiler-instrumented multi--chain prefetching improves execution time by 40% across six pointer-chasing kernels from the Olden benchmark suite [Rogers et al. 1995], and by 3% across four SPECint2000 benchmarks. Compared to jump pointer prefetching and prefetch arrays, multi--chain prefetching achieves 34% and 11% higher performance for the selected Olden and SPECint2000 benchmarks, respectively. Compared to PSB, multi--chain prefetching achieves 27% higher performance for the selected Olden benchmarks, but PSB outperforms multi--chain prefetching by 0.2% for the selected SPECint2000 benchmarks. An ideal PSB with an infinite Markov predictor achieves comparable performance to multi--chain prefetching, coming within 6% across all benchmarks. Finally, speculation can enable multi--chain prefetching for some dynamic traversal codes, but our technique loses its effectiveness when the pointer-chain traversal order is highly dynamic.
Storage requirement estimation for optimized design of data intensive applications
Authors: Kjeldsberg P. G. , Catthoor F. , Aas E. J.
Published: July 2004

A novel storage requirement estimation methodology is presented for use in the early system design phases when the data transfer ordering is only partially fixed. At that stage, none of the existing estimation tools are adequate, as they either assume a fully specified execution order or ignore it completely. A prototype CAD tool has been developed that includes major parts of the storage requirement estimation and optimization methodology. Using representative application demonstrators, we show how our techniques and tool can effectively guide the designer to achieve a transformed specification with low storage requirement.
IDDX-based test methods
Authors: Sabade Sagar S. , Walker Duncan M.
Published: July 2004

Supply current measurement-based test is a valuable defect-based test method for semiconductor chips. Both static leakage current (IDDQ) and transient current (IDDT) based tests have the capability of detecting unique defects that improve the fault detection capacity of a test suite. Collectively these test methods are known as IDDXtests. However, due to advances in the semiconductor manufacturing process, the future of these test methods is uncertain. This paper presents a survey of the research reported in the literature to extend the use of IDDXtests to deep sub-micron (DSM) technologies.
A two-layer library-based approach to synthesis of analog systems from VHDL-AMS specifications
Authors: Doboli Alex , Dhanwada Nagu , Nunez-Aldana Adrian , Vemuri Ranga
Published: July 2004

This paper presents a synthesis methodology for analog systems described using VHDL-AMS language. Synthesis produces net-lists of analog components that are selected from a library, and sized so that specified objectives (like AC response, signal to noise ratio, dynamic range, area) are optimized. The gap between abstract specifications and implementations is bridged using a two-layered methodology. The first layer is architecture generation. The second layer is component synthesis and constraint transformation. Architecture generation employs the branch-and-bound algorithm to create architectural alternatives for a system. Component synthesis and constraint transformation use a directed interval based genetic algorithm that operates on parameter ranges. The performance estimation engine embeds technology process parameters, SPICE models for basic circuits, and symbolic composition equations for basic structural configurations. The paper discusses the VHDL-AMS subset for synthesis. The subset offers the composition semantics. As a result, specifications offer sufficient insight into the system structure to allow automated architecture generation. To justify the flexibility of the methodology, the paper presents results for three case studies, a signal conditioning system, a filter, and an analog to digital converter. Experiments show that constraint-satisfying designs can be synthesized in a short time, at a low cost, and without requesting broad knowledge on analog circuits.
Multi-valued symbolic model-checking
Authors: Chechik Marsha , Devereux Benet , Easterbrook Steve , Gurfinkel Arie
Published: July 2004

This article introduces the concept of multi-valued model-checking and describes a multi-valued symbolic model-checker, ΧChek. Multi-valued model-checking is a generalization of classical model-checking, useful for analyzing models that contain
uncertainty
(lack of essential information) or
inconsistency
(contradictory information, often occurring when information is gathered from multiple sources). Multi-valued logics support the explicit modeling of uncertainty and disagreement by providing additional truth values in the logic.This article provides a theoretical basis for multi-valued model-checking and discusses some of its applications. A companion article [Chechik et al. 2002b] describes implementation issues in detail. The model-checker works for any member of a large class of multi-valued logics. Our modeling language is based on a generalization of Kripke structures, where both atomic propositions and transitions between states may take any of the truth values of a given multi-valued logic. Properties are expressed in ΧCTL, our multi-valued extension of the temporal logic CTL.We define the class of logics, present the theory of multi-valued sets and multi-valued relations used in our model-checking algorithm, and define the multi-valued extensions of CTL and Kripke structures. We explore the relationship between ΧCTL and CTL, and provide a symbolic model-checking algorithm for ΧCTL. We also address the use of fairness in multi-valued model-checking. Finally, we discuss some applications of the multi-valued model-checking approach.
A model-checking verification environment for mobile processes
Authors: Ferrari Gian-Luigi , Gnesi Stefania , Montanari Ugo , Pistore Marco
Published: July 2004

This article presents a semantic-based environment for reasoning about the behavior of mobile systems. The verification environment, called HAL, exploits a novel automata-like model that allows finite-state verification of systems specified in the π-calculus. The HAL system is able to interface with several efficient toolkits (e.g. model-checkers) to determine whether or not certain properties hold for a given specification. We report experimental results on some case studies.
Learning to find answers to questions on the Web
Authors: Agichtein Eugene , Lawrence Steve , Gravano Luis
Published: July 2004

We introduce a method for learning to find documents on the Web that contain answers to a given natural language question. In our approach, questions are transformed into new queries aimed at maximizing the probability of retrieving answers from existing information retrieval systems. The method involves automatically learning phrase features for classifying questions into different types, automatically generating candidate query transformations from a training set of question/answer pairs, and automatically evaluating the candidate transformations on target information retrieval systems such as real-world general purpose search engines. At run-time, questions are transformed into a set of queries, and reranking is performed on the documents retrieved. We present a prototype search engine,Tritus, that applies the method to Web search engines. Blind evaluation on a set of real queries from a Web search engine log shows that the method significantly outperforms the underlying search engines, and outperforms a commercial search engine specializing in question answering. Our methodology cleanly supports combining documents retrieved from different search engines, resulting in additional improvement with a system that combines search results from multiple Web search engines.
Smoothed analysis of algorithms
Authors: Spielman Daniel A. , Teng Shang-Hua
Published: July 2004

We introduce the
smoothed analysis of algorithms
, which continuously interpolates between the worst-case and average-case analyses of algorithms. In smoothed analysis, we measure the maximum over inputs of the expected performance of an algorithm under small random perturbations of that input. We measure this performance in terms of both the input size and the magnitude of the perturbations. We show that the simplex algorithm has
smoothed complexity
polynomial in the input size and the standard deviation of Gaussian perturbations.
Lower bounds on the bounded coefficient complexity of bilinear maps
Authors: Bürgisser Peter , Lotz Martin
Published: July 2004

We prove lower bounds of order
n
log
n
for both the problem of multiplying polynomials of degree
n
, and of dividing polynomials with remainder, in the model of bounded coefficient arithmetic circuits over the complex numbers. These lower bounds are optimal up to order of magnitude. The proof uses a recent idea of R. Raz [
Proc. 34th STOC 2002
] proposed for matrix multiplication. It reduces the linear problem of multiplying a random circulant matrix with a vector to the bilinear problem of cyclic convolution. We treat the arising linear problem by extending J. Morgenstern's bound [
J. ACM 20, pp. 305--306, 1973
] in a unitarily invariant way. This establishes a new lower bound on the bounded coefficient complexity of linear forms in terms of the singular values of the corresponding matrix. In addition, we extend these lower bounds for linear and bilinear maps to a model of circuits that allows a restricted number of unbounded scalar multiplications.
Satisfiability of word equations with constants is in PSPACE
Authors: Plandowski Wojciech
Published: July 2004

We prove that satisfiability problem for word equations is in PSPACE.
On clusterings
Authors: Kannan Ravi , Vempala Santosh , Vetta Adrian
Published: July 2004

We motivate and develop a natural bicriteria measure for assessing the quality of a clustering that avoids the drawbacks of existing measures. A simple recursive heuristic is shown to have poly-logarithmic worst-case guarantees under the new measure. The main result of the article is the analysis of a popular
spectral
algorithm. One variant of spectral clustering turns out to have effective worst-case guarantees; another finds a "good" clustering, if one exists.
Should spam be on the menu?
Authors: Sipior Janice C. , Ward Burke T. , Bonner P. Gregory
Published: July 2004

Email marketing is an excellent, low-cost way to reach consumers, but spammers are currently looting much of its potential. The challenge is to develop an email marketing process that is consensual, efficient, and constitutional.
How to retain online customers
Authors: Vatanasombut Banphot , Stylianou Antonis C. , Igbaria Magid
Published: July 2004

When there's a worldwide marketplace available at your customers' fingertips, maintaining a dedicated following is a tremendous challenge. A recent study of a leading bank's online services illustrates what it takes to keep novice and sophisticated users happy and loyal.
Successful e-government in Singapore
Authors: Ke Weiling , Wei Kwok Kee
Published: July 2004

How did Singapore manage to get most of its public services deliverable online?
Real work, necessary friction, optional chaos
Authors: Armour Phillip G.
Published: July 2004

Challenges in estimating software scope by effort.
Growing a participatory programming environment
Authors: Glaser Allan , Fu Snow , Tumelty Mark
Published: July 2004

A leading pharmaceutical company discovers how programming issues are resolved more effectively when a team approach is employed.
Networking support for query processing in sensor networks
Authors: Woo Alec , Madden Sam , Govindan Ramesh
Published: July 2004

Networking and query processing must be co-designed to allow data self-organization for flexible but efficient in-network storage, access, and processing.
MA57---a code for the solution of sparse symmetric definite and indefinite systems
Authors: Duff Iain S.
Published: July 2004

We introduce a new code for the direct solution of sparse symmetric linear equations that solves indefinite systems with 2 × 2 pivoting for stability. This code, called MA57, is in HSL 2002 and supersedes the well used HSL code MA27. We describe some of the implementation details and emphasize the novel features of MA57. These include restart facilities, matrix modification, partial solution for matrix factors, solution of multiple right-hand sides, and iterative refinement and error analysis. The code is written in Fortran 77, but there are additional facilities within a Fortran 90 implementation that include the ability to identify and change pivots. Several of these facilities have been developed particularly to support optimization applications, and we illustrate the performance of the code on problems arising therefrom.
Computing solutions of the modified Bessel differential equation for imaginary orders and positive arguments
Authors: Gil Amparo , Segura Javier , Temme Nico M.
Published: July 2004

We describe a variety of methods to compute the functions
K

ia

(
x
),
L

ia

(
x
) and their derivatives for real
a
and positive
x
. These functions are numerically satisfactory independent solutions of the differential equation
x
2
w
" +
xw
' + (
a
2
−
x
2
)
w
= 0. In the accompanying paper [Gil et al. 2004], we describe the implementation of these methods in Fortran 77 codes.
Algorithm 831
Authors: Gil Amparo , Segura Javier , Temme Nico M.
Published: July 2004

Fortran 77 programs for the computation of modified Bessel functions of purely imaginary order are presented. The codes compute the functions
K

ia

(
x
),
L

ia

(
x
) and their derivatives for real
a
and positive
x
; these functions are independent solutions of the differential equation
x
2
w" +
xw
' + (
a
2
−
x
2
)
w
= 0. The code also computes exponentially scaled functions. The range of computation is (
x
,
a
) ∈ (0,1500] × [−1500, 1500] when scaled functions are considered and it is larger than (0,500] × [−400, 400] for standard IEEE double precision arithmetic. The relative accuracy is better than 10
−13
in the range (0,200] × [−200, 200] and close to 10
−12
in (0, 1500] × [−1500, 1500].
A column pre-ordering strategy for the unsymmetric-pattern multifrontal method
Authors: Davis Timothy A.
Published: July 2004

A new method for sparse LU factorization is presented that combines a column pre-ordering strategy with a right-looking unsymmetric-pattern multifrontal numerical factorization. The column ordering is selected to give a good a priori upper bound on fill-in and then refined during numerical factorization (while preserving the bound). Pivot rows are selected to maintain numerical stability and to preserve sparsity. The method analyzes the matrix and automatically selects one of three pre-ordering and pivoting strategies. The number of nonzeros in the LU factors computed by the method is typically less than or equal to those found by a wide range of unsymmetric sparse LU factorization methods, including left-looking methods and prior multifrontal methods.
Consistency analysis of authorization hook placement in the Linux security modules framework
Authors: Jaeger Trent , Edwards Antony , Zhang Xiaolan
Published: July 2004

We present a consistency analysis approach to assist the Linux community in verifying the correctness of authorization hook placement in the Linux Security Modules (LSM) framework. The LSM framework consists of a set of authorization hooks inserted into the Linux kernel to enable additional authorizations to be performed (e.g., for mandatory access control). When compared to system call interposition, authorization within the kernel has both security and performance advantages, but it is more difficult to verify that placement of the LSM hooks ensures that all the kernel's security-sensitive operations are authorized. Static analysis has been used previously to verified mediation (i.e., that some hook mediates access to a security-sensitive operation), but that work did not determine whether the necessary set of authorizations were checked. In this paper, we develop an approach to test the
consistency
of the relationships between security-sensitive operations and LSM hooks. The idea is that whenever a security-sensitive operation is performed as part of specifiable event, a particular set of LSM hooks must have mediated that operation. This work demonstrates that the number of events that impact consistency is manageable and that the notion of consistency is useful for verifying correctness. We describe our consistency approach for performing verification, the implementation of run-time tools that implement this approach, the anomalous situations found in an LSM-patched Linux 2.4.16 kernel, and an implementation of a static analysis version of this approach.
Bound for glory
Authors: Korman Ken
Published: July 2004

How one computer scientist with a good idea started a revolution
Google's GMail
Authors: Weiss Aaron
Published: July 2004

Ani DiFranco is a singer/songwriter from Buffalo, New York who has built a very successful independent music career. DiFranco's personal style and lyrical messages resonated in particular with lesbian audiences, who became a strong component of her fan base. But DiFranco didn't claim the same label for herself and when, in 1996, she released an album about a heterosexual relationship and in 1998 married the man she had sung about, a vocal group of her fans were none too pleased. They felt hurt and betrayed---something that many of Google's current detractors can probably relate to. Google, it turns out, is not a lesbian either.
Dietary K intake regulates the response of apical K channels to adenosine in the thick ascending limb
Authors: Li Dimin , Wei Yuan , Wang Wen-Hui
Published: July 2004

We used the patch-clamp technique to study the effect of adenosine on the apical 70-pS K channel in the thick ascending limb (TAL) of the rat kidney. Application of 1 μM cyclohexyladenosine (CHA), an adenosine analog, stimulated apical 70-pS K channel activity and increased the product of channel open probability and channel number ( NPo) from 0.34 to 0.7. Also, addition of CGS-21680, a specific A2a adenosine receptor agonist, mimicked the effect of CHA and increased NPo from 0.33 to 0.77. The stimulatory effect of CHA and CGS-21680 was completely blocked by H89, an inhibitor of protein kinase A (PKA), or by inhibition of adenylate cyclase with SQ-22536. This suggests that the stimulatory effect of adenosine analogs is mediated by a PKA-dependent pathway. The effect of adenosine analog was almost absent in the TAL from rats on a K-deficient (KD) diet for 7 days. Application of DDMS, an agent that inhibits cytochrome P-450 hydrolase, not only significantly increased the activity of the 70-pS K channel but also restored the stimulatory effect of CHA on the 70-pS K channel in the TAL from rats on a KD diet. Also, the effect of CHA was absent in the presence of 20-HETE. Inhibition of PKA blocked the stimulatory effect of CHA on the apical 70-pS K channel in the presence of DDMS in the TAL from rats on a KD diet. We conclude that stimulation of adenosine receptor increases the apical 70-pS K channel activity via a PKA-dependent pathway and that the effect of adenosine on the apical 70-pS K channel is suppressed by low-K intake. Moreover, the diminished response to adenosine is the result of increase in 20-HETE formation, which inhibits the cAMP-dependent pathway in the TAL from rats on a KD diet.
Minimizing energy among homotopic maps
Authors: Miao Pengzi
Published: July 2004

We study an energy minimizing sequence {ui} in a fixed
homotopy class of smooth maps from a 3‐manifold. After deriving
an approximate monotonicity property for {ui} and a
continuous version of the Luckhaus lemma (Simon, 1996) on S2, we
show that, passing to a subsequence, {ui} converges strongly
in W1,2 topology wherever there is small energy
concentration.
The chromatic sum of a graph: history and recent developments
Authors: Kubicka Ewa
Published: July 2004

The chromatic sum of a graph is the
smallest sum of colors among all proper colorings with natural
numbers. The strength of a graph is the minimum number
of colors necessary to obtain its chromatic sum. A natural
generalization of chromatic sum is optimum cost chromatic
partition (OCCP) problem, where the costs of colors can be
arbitrary positive numbers. Existing results about chromatic sum,
strength of a graph, and OCCP problem are presented together with
some recent developments. The focus is on polynomial algorithms
for some families of graphs and NP‐completeness issues.
Projectivity and flatness over the endomorphism ring of a finitely generated module
Authors: Caenepeel S. , Guédénon T.
Published: July 2004

Let A be a ring and Λ a finitely generated A‐module.
We give necessary and sufficient conditions for projectivity and
flatness of a module over the endomorphism ring of Λ.
Acyl-Coenzyme A:Cholesterol Acyltransferase Inhibition Ameliorates Proteinuria, Hyperlipidemia, Lecithin-Cholesterol Acyltransferase, SRB-1, and Low-Denisty Lipoprotein Receptor Deficiencies in Nephrotic Syndrome
Authors: Vaziri N.D. , Liang K.H.
Published: July 2004

Background—

Nephrotic syndrome (NS) is associated with hyperlipidemia, altered lipid regulatory enzymes and receptors, and increased risk of progressive renal and cardiovascular diseases. Acyl-coenzyme A:cholesterol acyltransferase (ACAT) catalyzes intracellular esterification of cholesterol and plays an important role in production of apolipoprotein B-containing lipoproteins, regulation of cholesterol-responsive proteins, and formation of foam cells. Because hepatic ACAT-2 is markedly upregulated in NS, we tested the hypothesis that inhibition of ACAT may improve cholesterol metabolism in NS.

Methods and Results—

Rats with puromycin-induced NS were treated with either the ACAT inhibitor CI-976 or placebo for 2 weeks. Normal rats served as controls. Plasma lipids, renal function, and key lipid regulatory factors were measured. Untreated NS rats showed heavy proteinuria; hypoalbuminemia; elevated plasma cholesterol, triglyceride, LDL, VLDL, and total cholesterol-to-HDL cholesterol ratio; increased hepatic ACAT activity, ACAT-2 mRNA, and ACAT-2 protein; and reduced LDL receptor, HDL receptor, otherwise known as scavenger receptor B-1 (SRB-1) and plasma lecithin-cholesterol acyltransferase (LCAT). ACAT inhibitor reduced plasma cholesterol and triglycerides, normalized total cholesterol-to-HDL cholesterol ratio, and lowered hepatic ACAT activity without changing ACAT-2 mRNA or protein. This was accompanied by near normalizations of plasma LCAT, hepatic SRB-1, and LDL receptor and a significant amelioration of proteinuria and hypoalbuminemia.

Conclusions—

Pharmacological inhibition of ACAT reverses NS-induced LDL receptor, HDL receptor, and LCAT deficiencies; improves plasma lipid profile; and ameliorates proteinuria in nephrotic animals. Further studies are needed to explore the effect of ACAT inhibition in nephrotic humans.