A Dichotomy for Local Small-Bias Generators

We consider pseudorandom generators in which each output bit depends on a constant number of input bits. Such generators have appealingly simple structure: They can be described by a sparse input–output dependency graph \(G\) and a small predicate \(P\) that is applied at each output. Following the works of Cryan and Miltersen (MFCS’01) and by Mossel et al (STOC’03), we ask: which graphs and predicates yield “small-bias” generators (that fool linear distinguishers)? We identify an explicit class of degenerate predicates and prove the following. For most graphs, all non-degenerate predicates yield small-bias generators, \(f:\{0,1\}^n \rightarrow \{0,1\}^m\), with output length \(m = n^{1 + \epsilon }\) for some constant \(\epsilon > 0\). Conversely, we show that for most graphs, degenerate predicates are not secure against linear distinguishers, even when the output length is linear \(m=n+\Omega (n)\). Taken together, these results expose a dichotomy: Every predicate is either very hard or very easy, in the sense that it either yields a small-bias generator for almost all graphs or fails to do so for almost all graphs. As a secondary contribution, we attempt to support the view that small-bias is a good measure of pseudorandomness for local functions with large stretch. We do so by demonstrating that resilience to linear distinguishers implies resilience to a larger class of attacks.     

Practical Thermal Multi–Scale Analysis for Composite Materials–Mechanical-Orientated Approach

This paper describes a thermal multi-scale formulation for composite materials based on a mechanical homogenization approach. The presented formulation evaluates the effective macroscopic thermal conductivity of the composite materials and also the microscopic heat flux field by scaling down to the micro-scale level. The effective thermal conductivity of the composite materials was calculated by applying the homogenization theory over the unit cell. The uniqueness of the presented multi-scale analysis related to the elastic problems solved at the microscopic scale (unit cell). This method has the advantage of applying periodic boundary conditions and uniform macroscopic temperature gradient over the unit cell. The proposed thermal multi-scale analysis was verified and its efficiency was demonstrated on large scale problem.     

Low-energy laser irradiation affects satellite cell proliferation and differentiation in vitro

Low-energy laser (He-Ne) irradiation was found to promote skeletal muscle regeneration in vivo. In this study, its effect on the proliferation and differentiation of satellite cells in vitro was evaluated. Primary rat satellite cells were irradiated for various time periods immediately after preparation, and thymidine incorporation was determined after 2 days in culture. Laser irradiation affected thymidine incorporation in a bell-shaped manner, with a peak at 3 s of irradiation. Three seconds of irradiation caused an induction of cell-cycle regulatory proteins: cyclin D1, cyclin E and cyclin A in an established line of mouse satellite cells, pmi28, and proliferating cell nuclear antigen (PCNA) in primary rat satellite cells. The induction of cyclins by laser irradiation was compatible with their induction by serum refeeding of the cells. Laser irradiation effect on cell proliferation was dependent on the rat's age. At 3 weeks of age, thymidine incorporation in the irradiated cells was more than twofold higher than that in the controls, while at 6 weeks of age this difference had almost disappeared. Myosin heavy chain (MHC) protein levels were twofold lower in the irradiated than in the control cells, whereas the proliferation of the irradiated cells was twofold higher. Fusion percentage was lower in the irradiated compared to non-irradiated cells. In light of these data, the promoting effect of laser irradiation on skeletal muscle regeneration in vivo may be due to its effect on the activation of early cell-cycle regulatory genes in satellite cells, leading to increased proliferation and to a delay in cell differentiation.     

Langevin-schroedinger formulation of electronic tunneling through a molecular bridge with a dissipative acceptor

Modeling electronic tunneling through molecular bridges is desired in order to understand the mechanism of long-range electron transfer reactions in nature, as well as for the design of novel molecular electronics devices. Particularly interesting is the effect of the nuclear motion at the molecular bridge on the electron transfer mechanism and rate. In this work we study the effect of electronic nuclear coupling at the molecular bridge on a unidirectional electronic tunneling process from an electron donor into a dissipative acceptor, as may appear in controlled electron transfer reactions at biological membranes, or in heterogeneous electron transfer reactions. The model includes a collection of harmonic bath modes coupled to the dissipative acceptor site and a single mode at the molecular bridge. The parameters of the dissipative bath are tuned such that the electronic population decays from the donor to the acceptor. This process is simulated using a time-dependent nonlinear Langevin-Schroedinger equation, based on a mean-field approximation for the electronic-nuclear coupling at the acceptor site and a numerically exact treatment of the electronic-nuclear coupling at the molecular bridge. The simulations at zero temperature and weak electronic-nuclear coupling demonstrate that electronic tunneling is promoted by coupling to the nuclear mode at the bridge. This result is consistent with our previous studies of electronic tunneling oscillations in a symmetric donor-bridge-acceptor complex, and it emphasizes the importance of electronic nuclear coupling in analyzing long-range electron transfer processes through molecular bridges or wires.     

A formal perspective on the view selection problem

The view selection problem is to choose a set of views to materialize over a database schema, such that the cost of evaluating a set of workload queries is minimized and such that the views fit into a prespecified storage constraint. The two main applications of the view selection problem are materializing views in a database to speed up query processing, and selecting views to materialize in a data warehouse to answer decision support queries. In addition, view selection is a core problem for intelligent data placement over a wide-area network for data integration applications and data management for ubiquitous computing. We describe several fundamental results concerning the view selection problem. We consider the problem for views and workloads that consist of equality-selection, project and join queries, and show that the complexity of the problem depends crucially on the quality of the estimates that a query optimizer has on the size of the views it is considering to materialize. When a query optimizer has good estimates of the sizes of the views, we show a somewhat surprising result, namely, that an optimal choice of views may involve a number of views that is exponential in the size of the database schema. On the other hand, when an optimizer uses standard estimation heuristics, we show that the number of necessary views and the expression size of each view are polynomially bounded. Received: November 20, 1001 / Accepted: May 30, 2002 / Published online: September 25, 2002     

Language resources for Hebrew

We describe a suite of standards, resources and tools for computational encoding and processing of Modern Hebrew texts. These include an array of XML schemas for representing linguistic resources; a variety of text corpora, raw, automatically processed and manually annotated; lexical databases, including a broad-coverage monolingual lexicon, a bilingual dictionary and a WordNet; and morphological processors which can analyze, generate and disambiguate Hebrew word forms. The resources are developed under centralized supervision, so that they are compatible with each other. They are freely available and many of them have already been used for several applications, both academic and industrial.

Data integration with uncertainty

This paper reports our first set of results on managing uncertainty in data integration. We posit that data-integration systems need to handle uncertainty at three levels and do so in a principled fashion. First, the semantic mappings between the data sources and the mediated schema may be approximate because there may be too many of them to be created and maintained or because in some domains (e.g., bioinformatics) it is not clear what the mappings should be. Second, the data from the sources may be extracted using information extraction techniques and so may yield erroneous data. Third, queries to the system may be posed with keywords rather than in a structured form. As a first step to building such a system, we introduce the concept of probabilistic schema mappings and analyze their formal foundations. We show that there are two possible semantics for such mappings: by-table semantics assumes that there exists a correct mapping but we do not know what it is; by-tuple semantics assumes that the correct mapping may depend on the particular tuple in the source data. We present the query complexity and algorithms for answering queries in the presence of probabilistic schema mappings, and we describe an algorithm for efficiently computing the top-k answers to queries in such a setting. Finally, we consider using probabilistic mappings in the scenario of data exchange.     

Representing uncertain data: models, properties, and algorithms

In general terms, an uncertain relation encodes a set of possible certain relations. There are many ways to represent uncertainty, ranging from alternative values for attributes to rich constraint languages. Among the possible models for uncertain data, there is a tension between simple and intuitive models, which tend to be incomplete, and complete models, which tend to be nonintuitive and more complex than necessary for many applications. We present a space of models for representing uncertain data based on a variety of uncertainty constructs and tuple-existence constraints. We explore a number of properties and results for these models. We study completeness of the models, as well as closure under relational operations, and we give results relating closure and completeness. We then examine whether different models guarantee unique representations of uncertain data, and for those models that do not, we provide complexity results and algorithms for testing equivalence of representations. The next problem we consider is that of minimizing the size of representation of models, showing that minimizing the number of tuples also minimizes the size of constraints. We show that minimization is intractable in general and study the more restricted problem of maintaining minimality incrementally when performing operations. Finally, we present several results on the problem of approximating uncertain data in an insufficiently expressive model.     

MiniCon: A scalable algorithm for answering queries using views

The problem of answering queries using views is to find efficient methods of answering a query using a set of previously materialized views over the database, rather than accessing the database relations. The problem has received significant attention because of its relevance to a wide variety of data management problems, such as data integration, query optimization, and the maintenance of physical data independence. To date, the performance of proposed algorithms has received very little attention, and in particular, their scale up in the presence of a large number of views is unknown. We first analyze two previous algorithms, the bucket algorithm and the inverse-rules, and show their deficiencies. We then describe the MiniCon, a novel algorithm for finding the maximally-contained rewriting of a conjunctive query using a set of conjunctive views. We present the first experimental study of algorithms for answering queries using views. The study shows that the MiniCon scales up well and significantly outperforms the previous algorithms. We describe an extension of the MiniCon to handle comparison predicates, and show its performance experimentally. Finally, we describe how the MiniCon can be extended to the context of query optimization. Received: 15 October 2000 / Accepted: 15 April 2001 Published online: 28 June 2001