On the complexity of approximating k-set packing

Given a k-uniform hypergraph, the Maximum k -Set Packing problem is to find the maximum disjoint set of edges. We prove that this problem cannot be efficiently approximated to within a factor of unless P = NP. This improves the previous hardness of approximation factor of by Trevisan. This result extends to the problem of k-Dimensional-Matching.     

A parallel implementation of Flat Concurrent Prolog

Flat Concurrent Prolog is a simple, practical, concurrent programming language which has an efficient uniprocessor implementation. This paper describes an initial parallel implementation of the language; it consists of an interpreter implemented on an Intel iPSC Hypercube. The parallel execution of concurrent logic programming languages involves many nontrivial implementation problems. Some of these problems are well known and have been treated extensively in the literature. The most difficult task is to integrate problem solutions in a coherent and efficient manner. The algorithm presented has been useful in providing insights into the major problems and includes a number of novel ideas to simplify implementation. It does not attempt to solve all the problems involved but rather provides a workable basis for current and future research. The algorithm is under ongoing refinement, simplification and improvement.     

Multiway merge with constant delay in Concurrent Prolog

Multiway dynamic mergers with constant delay are an essential component of a parallel logic programming language. Previous attempts to defined efficient mergers have required complex optimising compilers and run-time support. This paper proposes a simple technique to implement mergers efficiently. The technique requires an additional data type and the definition of an operation on it. The operation allows multiple processes to access a stream without incurring the cost of searching for the end of stream. It is specified in Concurrent Prolog and is used to define multiple assignment variables using a monitor. The technique forms the basis for stream merging in Logix, a practical programming environment written in Flat Concurrent Prolog.     

Objective determination of the consensual accommodation (author''s transl)

The direct and consensual accommodation of both eyes were determined by a modified coincidence refractometer. Young individuals with normal monocular and binocular vision revealed a close quantitative correspondence between the direct and the ipsi- and contralateral consensual accommodation. Experimental impairment of the function of the ciliary muscle by medical means caused disturbed consensual accommodation of both eyes. The weakening of the function of the ciliary muscle of one eye by instillation of, for example Homatropin leads to an important increase of the contralateral and diminution of the ipsilateral consensual accommodation. By the results of the investigations it was concluded: 1. that the regulation of the direct accommodation reflex is influenced also by the function of the ciliary muscle in the fixating eye and has stimulating and depressing components, 2. that the innervation of the nonfixating eye passes through an efferent neuron, from where the accommodation impulse emerges to both eyes. - The anatomically based relation between the direct and the ipsilateral and contralateral consensual accommodation allows one to use its quantitative determination in both eyes as a diagnostic test in afferent and efferent disturbances of the accommodation reflex.     

On the hardness of approximating label-cover

The Label-Cover problem, defined by S. Arora, L. Babai, J. Stern, Z. Sweedyk [Proceedings of 34th IEEE Symposium on Foundations of Computer Science, 1993, pp. 724-733], serves as a starting point for numerous hardness of approximation reductions. It is one of six ‘canonical’ approximation problems in the survey of Arora and Lund [Hardness of Approximations, in: Approximation Algorithms for NP-Hard Problems, PWS Publishing Company, 1996, Chapter 10]. In this paper we present a direct combinatorial reduction from low error-probability PCP [Proceedings of 31st ACM Symposium on Theory of Computing, 1999, pp. 29-40] to Label-Cover showing it NP-hard to approximate to within 2^{(logn)1−o(1)}. This improves upon the best previous hardness of approximation results known for this problem.We also consider the Minimum-Monotone-Satisfying-Assignment (MMSA) problem of finding a satisfying assignment to a monotone formula with the least number of 1's, introduced by M. Alekhnovich, S. Buss, S. Moran, T. Pitassi [Minimum propositional proof length is NP-hard to linearly approximate, 1998]. We define a hierarchy of approximation problems obtained by restricting the number of alternations of the monotone formula. This hierarchy turns out to be equivalent to an AND/OR scheduling hierarchy suggested by M.H. Goldwasser, R. Motwani [Lecture Notes in Comput. Sci., Vol. 1272, Springer-Verlag, 1997, pp. 307-320]. We show some hardness results for certain levels in this hierarchy, and place Label-Cover between levels 3 and 4. This partially answers an open problem from M.H. Goldwasser, R. Motwani regarding the precise complexity of each level in the hierarchy, and the place of Label-Cover in it.     

Hyaluronic Acid and a Short Peptide Improve the Performance of a PCL Electrospun Fibrous Scaffold Designed for Bone Tissue Engineering Applications

Bone tissue engineering is a rapidly developing, minimally invasive technique for regenerating lost bone with the aid of biomaterial scaffolds that mimic the structure and function of the extracellular matrix (ECM). Recently, scaffolds made of electrospun fibers have aroused interest due to their similarity to the ECM, and high porosity. Hyaluronic acid (HA) is an abundant component of the ECM and an attractive material for use in regenerative medicine; however, its processability by electrospinning is poor, and it must be used in combination with another polymer. Here, we used electrospinning to fabricate a composite scaffold with a core/shell morphology composed of polycaprolactone (PCL) polymer and HA and incorporating a short self-assembling peptide. The peptide includes the arginine-glycine-aspartic acid (RGD) motif and supports cellular attachment based on molecular recognition. Electron microscopy imaging demonstrated that the fibrous network of the scaffold resembles the ECM structure. In vitro biocompatibility assays revealed that MC3T3-E1 preosteoblasts adhered well to the scaffold and proliferated, with significant osteogenic differentiation and calcium mineralization. Our work emphasizes the potential of this multi-component approach by which electrospinning, molecular self-assembly, and molecular recognition motifs are combined, to generate a leading candidate to serve as a scaffold for bone tissue engineering.     

Testing juntas

We show that a boolean valued function over n variables, where each variable ranges in an arbitrary probability space, can be tested for the property of depending on only J of them using a number of queries that depends only polynomially on J and the approximation parameter ε. We present several tests that require a number of queries that is polynomial in J and linear in ε⁻¹. We show a non-adaptive test that has one-sided error, an adaptive version of it that requires fewer queries, and a non-adaptive two-sided version of the test that requires the least number of queries. We also show a two-sided non-adaptive test that applies to functions over n boolean variables, and has a more compact analysis.We then provide a lower bound of on the number of queries required for the non-adaptive testing of the above property; a lower bound of for adaptive algorithms naturally follows from this. In establishing this lower bound we also prove a result about random walks on the group Z^q₂ that may be interesting in its own right. We show that for some , the distributions of the random walk at times t and t+2 are close to each other, independently of the step distribution of the walk.We also discuss related questions. In particular, when given in advance a known J-junta function , we show how to test a function for the property of being identical to up to a permutation of the variables, in a number of queries that is polynomial in J and ε⁻¹.     

PCP Characterizations of NP: Toward a Polynomially-Small Error-Probability

This paper strengthens the low-error PCP characterization of NP, coming closer to the upper limit of the BGLR conjecture. Consider the task of verifying a written proof for the membership of a given input in an NP language. In this paper, this is achieved by making a constant number of accesses to the proof, obtaining error probability that is exponentially small in the total number of bits that are read.